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

Question

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.

Answer 1

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);
N:=LogInt(n,2);
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.