# How quickly can one compute the Hurwitz action of braid groups on finite groups?

Let $G$ be a finite group. Define the Hurwitz action of $B_{n}$ on $G^{n}$ by letting $(x_{1},...,x_{n})\sigma_{i}=(x_{1},...,x_{i}x_{i+1}x_{i}^{-1},x_{i},x_{i+2},...,x_{n})$. I wonder what algorithms exist that produce a small circuit $C$ such that $C(x_{1},...,x_{n})=(x_{1},...,x_{n})b$ for all $x_{1},...,x_{n}\in G$.

$\textbf{Algorithm 1:}$ Let $b$ be a braid. Then a braid word $w$ representing $b$ is said to be a geodesic braid word if $w$ has minimal length among all braids that represent $b$. The set of all braids in $B_{\infty}$ is a $co-NP$-complete problem. However, while the geodesic braid word of a braid $w$ is $co-NP$-complete, in practice, there is an approximate algorithms for finding nearly geodesic braid words for a braid.

In particular, in this paper, the authors have observed that Dehornoy's handle reduction usually replaces a braid word $w$ with an equivalent but shorter braid word $w'$. The authors therefore proposed alternating between left handle reductions and right handle reductions as an algorithm for finding very short braid words $w^{\sharp}$ for a given braid $b$. Therefore, when we consider the nearly geodesic braid word $w^{\sharp}$ as a circuit, then the word $w^{\sharp}$ is a quite short circuit that computes $(x_{1},...,x_{n})\mapsto(x_{1},...,x_{n})b$.

$\textbf{Possible algorithm 2: The fast Hurwitz action}$

Let $\Delta_{n}=(\sigma_{1}...\sigma_{n-1})(\sigma_{1}...\sigma_{n-2})... (\sigma_{1}\sigma_{2})\sigma_{1}$. Then $\Delta_{n}$ is known as the fundamental braid.

Then while the braid $\Delta_{n}$ has $\frac{n(n-1)}{2}$, elements, the action $(x_{1},...,x_{n})\mapsto(x_{1},...,x_{n})\Delta_{n}$ can be computed by performing $O(n)$ many group operations on $G$ (instead of the $O(n^{2})$ operations which one has to do if one applies the braid $\Delta_{n}$ directly).

Suppose that $(x_{1},...,x_{n})\in G$. Then compute $(y_{1},...,y_{n})$ recursively by letting $y_{1}=e$ and $y_{n+1}=y_{n}\cdot x_{n}$. Then $$(x_{1},...,x_{n})\Delta_{n}=(y_{n}x_{n}y_{n}^{-1},y_{n-1}x_{n-1}y_{n-1}^{-1},...,y_{2}x_{2}y_{2}^{-1},y_{1}x_{1}y_{1}^{-1}).$$ Therefore, one obtains a fast algorithm for computing $(x_{1},...,x_{n})\Delta_{n}$ using $O(n)$ group operations rather than $O(n^{2})$ group operations. The fast Hurwitz action also allows us to compute $(x_{1},...,x_{n})(\sigma_{1}...\sigma_{i_{1}})...(\sigma_{1}...\sigma_{i_{k}})$ where $i_{1}>...>i_{k}$ in $O(n)$ steps as well.

Is there any way to generalize this fast Hurwitz action to other braids? Does there exist a braid form in which one is able to easily apply the fast Hurwitz action or a generalized fast Hurwitz action? Is there a good way to in general decompose a braid $b$ as the composition of braids in which one can apply the fast Hurwitz action? If algorithm 2 can be applied to all braids in a reasonable manner, does algorithm 2 in general use more or less gates than algorithm 1?

The braids $(\sigma_{1}...\sigma_{i_{1}})...(\sigma_{1}...\sigma_{i_{k}})$ look very similar to the simple braids which one obtains from the Garside normal form of a braid, but I have not yet been able to apply the fast Hurwitz action to simple braids in general.

$\textbf{A possible application to cryptography}$ If one defines the length $\ell(b)$ of the braid $b$ to be the number of gates in a suitably optimized circuit $C$ with $C(x_{1},...,x_{n})=(x_{1},...,x_{n})b$, then the length function $\ell$ may be useful in constructing length based attacks against various braid group cryptosystems. However, one needs to optimize the circuit size $\ell(b)$ in order for this length based attack to be effective.

• I am now interested in this problem not only when the braids have both positive and negative twists but now when the braids are positive. – Joseph Van Name Dec 28 '17 at 23:06

I have good news. The Hurwitz action of a simple braid or the inverse of a simple braid from a tuple on a group takes $$O(n\cdot\log(n))$$ many group operations which is much better than the $$O(n^{2})$$ many operations it would take using the bubblesort-like Hurwitz action algorithm.

In particular, the Hurwitz action of a braid $$b$$ which can be written as the composition of $$k$$ simple braids in $$B_{n}$$ takes $$O(k\cdot n\cdot\log(n))$$ many group operations.

Let $$G$$ be a finite group and let $$(x_{1},\dots,x_{n})\in G^{n}$$. Let $$b$$ be a simple braid. For easier-to-read code, we shall assume that $$n=2^{N}$$ for some $$N$$.

The following code in the programming language GAP returns the output of the action $$(x_{1},...,x_{n})\cdot b$$ where list denotes $$(x_{1},...,x_{n})$$ and where if perm denotes the array $$(f(1),...,f(n))$$ where $$f=\pi(b)$$ where $$\pi:B_{n}\rightarrow S_{n}$$ is the projection to the semigroup. The following algorithm shall be called the fast Hurwitz action.

fastactionsimple:=function(perm,list)
n:=Length(perm);
output:=[];
tree:=[list];
for i in [1..N-1] do
tree[i+1]:=[];
for j in [1..Length(tree[i])/2] do
tree[i+1][j]:=tree[i][2*j-1]*tree[i][2*j];
od;
od;
for i in [1..n] do
a:=perm[i];
b:=tree[1][a];
aa:=a;
tree[1][a]:=();
for j in [2..N] do
aa:=(aa+RemInt(aa,2))/2;
if 2*aa<=Length(tree[j-1]) then
tree[j][aa]:=tree[j-1][2*aa-1]*tree[j-1][2*aa];
else
tree[j][aa]:=tree[j-1][2*aa-1];
fi;
od;
v:=();
bin:=0;
for j in Reversed([1..N]) do
if (bin+1)*2^(j-1)<=a then v:=v*tree[j][bin+1]; bin:=(bin+1)*2;
else bin:=bin*2;
fi;
od;
output[i]:=v*b*v^(-1);
od;
return output;
end;


Remark: The following example illustrates how to make further improvements to compute the Hurwitz action even quicker. Let $$T_{r}$$ denotes the collection of all transpositions in $$S_{r}$$. Then computing the group operation in $$S_{r}$$ takes $$O(r)$$ time which makes the fast Hurwitz action on $$S_{r}$$ take take $$O(nr\cdot\log(n))$$ time which may be worse than the $$O(n^{2})$$ time that the standard Hurwitz action would take. Luckily, one can modify the above algorithm so that the Hurwitz action $$(x_{1},...,x_{n})\cdot b$$ where $$b$$ is simple and $$x_{1},...,x_{n}\in T_{r}$$ can be computed in $$O(n\cdot\log(n))$$ time by a straightforward modification to the algorithm for the fast Hurwitz action.