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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.