# How many arithmetic and max operations does it take to compute Dynnikov's action of the braid groups on $\mathbb{Z}^{2n}$?

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?

http://iopscience.iop.org/article/10.1070/RM2002v057n03ABEH000519/pdf

• Great another downvote.... for a reasonable looking query. Ban the users who frequently downvote without comment. Sep 22 '18 at 5:09
• @user124864 Downvoting has been discussed on meta: cstheory.meta.stackexchange.com/questions/2722/… Sep 22 '18 at 20:20