1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Joseph Van Name Dec 28 '17 at 23:06
0
$\begingroup$

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.

$\endgroup$

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.