<p>A function <span class="math-container">$f:X^{2}\rightarrow X^{2}$</span> is said to satisfy the Yang-Baxter equation if 
<span class="math-container">$$(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).$$</span>
If <span class="math-container">$f:X^{2}\rightarrow X^{2}$</span> satisfies the Yang-Baxter equation and <span class="math-container">$B_{n}$</span> denotes the <a href="https://en.wikipedia.org/wiki/Braid_group" rel="nofollow noreferrer">braid group</a>, then define a group action
<span class="math-container">$\pi_{f,n}:X^{n}\times B_{n}\rightarrow X^{n}$</span> by
<span class="math-container">$$\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}).$$</span></p>

<p>Define <span class="math-container">$x^{+}=\max(x,0)$</span>. Define a mapping <span class="math-container">$f:\mathbb{R}^{4}\rightarrow\mathbb{R}^{4}$</span> by letting
<span class="math-container">$f(a,b,c,d)=(a',b',c',d')$</span> where</p>

<p><span class="math-container">$$a'=\max(a,a+b,b+c),$$</span>
<span class="math-container">$$b'=d-(a-b-c+b^{+}+d^{+})^{+},$$</span>
<span class="math-container">$$c'=a+c+d-\max(a,c,a+d),$$</span>
<span class="math-container">$$d'=\max(b,a-c+b^{+}+d^{+}).$$</span></p>

<p>Then the function <span class="math-container">$f$</span> satisfies the Yang-Baxter equations. Therefore the braid group <span class="math-container">$B_{n}$</span> acts on <span class="math-container">$\mathbb{R}^{2n}$</span> and this action restricts to an action on <span class="math-container">$\mathbb{Z}^{2n}$</span>. See <a href="https://en.wikipedia.org/wiki/Braid_group" rel="nofollow noreferrer">1</a> for more information about this group action.</p>

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

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

<p><a href="http://iopscience.iop.org/article/10.1070/RM2002v057n03ABEH000519/pdf" rel="nofollow noreferrer">http://iopscience.iop.org/article/10.1070/RM2002v057n03ABEH000519/pdf</a></p>

CC BY-SA 4.0
2018-09-22T05:09:14.863Z
Great another downvote.... for a reasonable looking query. Ban the users who frequently downvote without comment.
Turbo
CC BY-SA 4.0
2018-09-22T20:20:08.287Z
@user124864 Downvoting has been discussed on meta: https://cstheory.meta.stackexchange.com/questions/2722/drive-by-downvoting-on-new-users-questions
Bjørn Kjos-Hanssen
<circuit-complexity><gr.group-theory><arithmetic-circuits>
How many arithmetic and max operations does it take to compute Dynnikov's action of the braid groups on $\mathbb{Z}^{2n}$?
Joseph Van Name
# How many arithmetic and max operations does it take to compute Dynnikov's action of the braid groups on $\mathbb{Z}^{2n}$?

(Asked by: username_0 on 2018-09-21)

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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Braid_group) 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>

**Tags:** circuit-complexity, gr.group-theory, arithmetic-circuits
> **Comments:**
> **username_1**: Great another downvote.... for a reasonable looking query. Ban the users who frequently downvote without comment.  
> **username_2**: @user124864 Downvoting has been discussed on meta: https://cstheory.meta.stackexchange.com/questions/2722/drive-by-downvoting-on-new-users-questions  

---

## 0 answers

