A function $f:X^{2}\rightarrow X^{2}$ is said to satisfy the Yang-Baxter equation if $$(f\times\textrm{Id}_{X})\circ(\textrm{Id}_{X}\times f)\circ(f\times\textrm{Id}_{X})=(\textrm{Id}_{X}\times f)\circ(f\times\textrm{Id}_{X})\circ(\textrm{Id}_{X}\times f).$$ If $f:X^{2}\rightarrow X^{2}$ satisfies the Yang-Baxter equation and $B_{n}$ denotes the braid group, then define a group action $\pi_{f,n}:X^{n}\times B_{n}\rightarrow X^{n}$ by $$\pi_{f,n}(x_{1},...,x_{n})\cdot\sigma_{i}=(x_{1},...,x_{i-1},f(x_{i},x_{i+1}),x_{i+2},...,x_{n}).$$

Define $x^{+}=\max(x,0)$. Define a mapping $f:\mathbb{R}^{4}\rightarrow\mathbb{R}^{4}$ by letting $f(a,b,c,d)=(a',b',c',d')$ where

$$a'=\max(a,a+b,b+c),$$ $$b'=d-(a-b-c+b^{+}+d^{+})^{+},$$ $$c'=a+c+d-\max(a,c,a+d),$$ $$d'=\max(b,a-c+b^{+}+d^{+}).$$

Then the function $f$ satisfies the Yang-Baxter equations. Therefore the braid group $B_{n}$ acts on $\mathbb{R}^{2n}$ and this action restricts to an action on $\mathbb{Z}^{2n}$. See 1 for more information about this group action.

We say that a positive braid $b\in B_{n}$ is simple if $b$ cannot be factored as $b_{1}\sigma_{i}^{2}b_{2}$ for positive braids $b_{1},b_{2}$ and some $i$. The simple braids are in a one-to-one correspondence with the permutations in $S_{n}$, so these simple braids are sometimes called permutation braids.

Given a simple braid $b\in B_{n}$, the mapping $\mathbb{Z}^{2n}\rightarrow\mathbb{Z}^{2n},\mathbf{x}\mapsto\mathbf{x}\cdot b$ may be computed using $O(n^{2})$ $+,-,\min,\max$ operations. Can the mapping $\mathbf{x}\mapsto\mathbf{x}\cdot b$ be computed using only $O(n\cdot\log(n))$ of these $+,-,\min,\max$ operations?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.