5
$\begingroup$

Geometrically, it's easy to "draw" the permutation braids, but I was wondering if there was an algorithm to write down all the permutation braids in terms of the Artin generators. I had a few ideas, but none of them seem quite feasible or efficient.

First, I considered the fundamental braid $\Delta_n \in B_n$ and I thought permutation braids must be formed from the fundamental braid by removing some Artin generators. So by going through all choices and checking whether they are permutation braids, we can get the set of permutation braids.

Second, because $B_{n-1}$ embeds into $B_n$, the permutation braids of $B_n$ are the permutation braids of $B_{n-1}$ and the permutation braids containing the last generator $\sigma_{n-1}.$ So if we have the set of permutation braids of $B_{n-1},$ we can try to insert one or more $\sigma_{n-1}$ to get the other permutation braids of $B_n$.

Thirdly, I know there is a bijection between the permutation braids of $B_n$ and the symmetric group $S_n$. But it's difficult to explicitly write the permutation braid in terms of the generators. One method I thought of is: if we number the braids $1$ through $n$ and we have a permutation $\rho$, then first send the $n$th braid to position $\rho(n)$ which can be done by $\sigma_{n-1}\sigma_{n-2}\cdots \sigma_{\rho(n)}$ and etc. However, this method doesn't work always because if we have $\sigma_1\sigma_2 \in B_3$ corresponding to the permutation $(1 2 3),$ we can't write that as a permutation braid starting with $\sigma_2.$

These are the ideas that I had, but the first two seem much too inefficient while the third one doesn't seem to even work. Since permutation braids seem crucial to the theory of braid cryptography, I was thinking there must be some efficient method to write them out, but I couldn't find them in literature. Help would be much appreciated.

$\endgroup$
  • $\begingroup$ What do you mean by "the" permutation braids? Every permutation of $\{1,...,n\}$ is induced by many different braids... do you intend to choose out one special braid inducing each permutation? If so, how do you make this choice? $\endgroup$ – Lee Mosher Jul 5 '17 at 23:45
  • $\begingroup$ @LeeMosher Ah, that is indeed true, completely slipped my mind. Is there absolutely no way to make a choice, e.g. put some sort of order on the braids (perhaps lexicographically on the indices)? But I suppose making such a restriction would make it harder to solve my original problem... $\endgroup$ – dhk628 Jul 6 '17 at 0:00
  • $\begingroup$ @LeeMosher Would there be a method to get "a" permutation braid from an element of $S_n$? $\endgroup$ – dhk628 Jul 6 '17 at 0:01
  • $\begingroup$ I should mention that the reason I'm asking this question is: in the survey arxiv.org/abs/0711.3941 on braid group cryptography. it says for Diffie-Hellman-type key-exchange protocol, it's suggested to use a braids specified by 12 permutations, but I was wondering how one can construct such a braid randomly $\endgroup$ – dhk628 Jul 6 '17 at 0:11
  • 1
    $\begingroup$ You can certainly get "a" permutation braid from an element of $S_n$: write the permutation as a word $w$ in the standard transpositions $(1,2)$, $(2,3)$, ...; take the standard braid generators $\sigma_1$, $\sigma_2$,... which are constructed so that they induce those transpositions respectively; then replace each transposition in the word $w$ by the corresponding braid generator and multiply. $\endgroup$ – Lee Mosher Jul 6 '17 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.