Recovering information about braids from their decomposition into positive and negative braids

Question

Suppose that $b$ is a braid. Then $b$ can be uniquely written as $D_{RL}(b)^{-1}N_{RL}(b)$ where $D_{RL}(b),N_{RL}(b)$ are the unique positive braids such that $b=D_{RL}(b)^{-1}N_{RL}(b)$ and where $D_{RL}(b)^{-1}\wedge_{L}N_{RL}(b)=e$ where $r\wedge_{L}s$ denotes the left gcd of the positive braids $r$ and $s$. See Chapter 2 of Dehornoy's book Braids and Self-Distributivity for more information about this decomposition.

I wonder what information about the braid $b$ can be recovered from the positive braids $D_{RL}(b),N_{RL}(b)$.

Suppose that $b$ is a braid. Then if Karen has access to both $D_{RL}(b),N_{RL}(b)$, then Karen is able to recover the entire braid $b$. What information about the braid $b$ can Karen recover if she has access to only $D_{RL}(b)$ or only $N_{RL}(b)$? I am mainly interested in orderly braids $b$ where if $w=\sigma_{\alpha_{1}}^{e_{1}}...\sigma_{\alpha_{k}}^{e_{k}}$ is a braid word for $b$ with a minimized length, then there will likely be many $i$'s where $\alpha_{i}$ is very close to $\alpha_{i+1}$. I am also interested in what properties of the braid $b$ make it likely or unlikely for one to recover information about $b$ when one knows $D_{RL}(b)$ or $N_{RL}(b)$.

Answer 1

I claim that $D_{RL}(b)$ in practice contains most of the information about the left half of the braid $b$ and $N_{RL}(b)$ contains most information about the right half of the braid $b$. Furthermore, I claim that whenever $b=uv$ where $u$ is positive and $v$ is negative, then one can recover much information about the braid $b$ from either $u$ or $v$.

If $b$ is a highly structured braid, then it is usually very difficult to hide any information about $b$. After all, all the current braid based cryptographic algorithms have been broken since braids do not do a very good job at concealing information. In particular, if $b$ is a braid, then Dehornoy's handle reduction could be used to find a braid word that represents $b$ and which reveals much of the information about the braid $b$. It seems like handle reduction is the best technique for revealing information about a braid. In fact, one can do slightly better by using Algorithm 1 in this paper to minimize the length of a braid and also reveal information about the braid. One could also improve Algorithm 1 by sorting and other techniques.

Since positive braids are already handle reduced, handle reduction cannot be used to transform a positive braid word or a negative braid word because positive braids word and negative braid words are already reduced. We however can use the following technique that allows us to use handle reduction to reveal information even about positive braids. If $b$ is a positive braid, then one could find a canonical positive braid $c$ where $b$ and $c$ have about the same length and then use handle reduction to find a reduced word that represents $bc^{-1}$ and then the reduced word representing $bc^{-1}$ would reveal all the information that one was attempting to conceal using the braid $b$. If you know anything about braids, you would know that the canonical choice of the braid $c$ is either a power of $\Delta_{n}$ or a power of $\delta_{n}$ where we define $\delta_{n}=\sigma_{n-1}\dots\sigma_{1}$ and we define $\Delta_{n}=\delta_{1}\dots\delta_{n}$. It is not too difficult to show that $\delta_{n}^{n}=\Delta_{n}^{2}$ (so there is not much difference in choosing $\delta_{n}$ or $\Delta_{n}$) and that $\Delta_{n}^{-1}\sigma_{i}\Delta_{n}^{-1}=\sigma_{n-i}$ for $1\leq i<n$. The braids $\delta_{n},\Delta_{n}$ are essential in the Garside normal form and the Birman-Ko-Lee normal forms of the braid groups. Furthermore, for each positive braid $b$, there is some $k$ and positive braid $c$ where $bc=\Delta_{n}^{k}$.

Suppose that $b=uv$ where $u$ is positive and $v$ is negative. Let $L:B_{n}\rightarrow\mathbb{Z}$ be the homomorphism where $L(\sigma_{i})=1$ for all $i$. Let $r=\lfloor\frac{2\cdot L(u)}{n(n-1)}\rfloor$ and $s=-\lfloor\frac{2\cdot L(v)}{n(n-1)}\rfloor$.

Now, $$b=uv=u\Delta_{n}^{-r}\Delta_{n}^{r-s}\Delta_{n}^{s}v.$$

An entity with access to $u$ can extract information about the braid $b$ by applying handle reduction and other techniques on the braid $u\Delta_{n}^{-r}$ and an entity with access to $v$ can extract information about $b$ from $\Delta_{n}^{s}v$.

In practice, handle reduction a very fast algorithm and handle reduction is conjectured to always terminate within quadratically many steps.

Example

Suppose that $b$ is the following braid.

[ 1, 1, -2, -2, -3, -3, -4, -4, 5, 5, -6, -6, 7, 7, 8, 8, -9, -9, -10, -10, 1, 1, 2, 2, 3, 3, -4, -4, -5, -5, -6, -6, 7, 7, 8, 8, -9, -9, 10, 10, -1, -1, 2, 2, -3, -3, 4, 4, 5, 5, -6, -6, -7, -7, -8, -8, 9, 9, -10, -10, 1, 1, -2, -2, 3, 3, 4, 4, 5, 5, -6, -6, 7, 7, 8, 8, -9, -9, 10, 10, 1, 1, 2, 2, 3, 3, 4, 4, -5, -5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 1, 1, -2, -2, -3, -3, 4, 4, 5, 5, 6, 6, -7, -7, -8, -8, -9, -9, 10, 10, 1, 1, -2, -2, 3, 3, 4, 4, -5, -5, -6, -6, -7, -7, -8, -8, 9, 9, -10, -10, 1, 1, -2, -2, -3, -3, 4, 4, -5, -5, -6, -6, -7, -7, 8, 8, -9, -9, 10, 10, -1, -1, 2, 2, 3, 3, 4, 4, 5, 5, -6, -6, 7, 7, 8, 8, 9, 9, -10, -10, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, -7, -7, -8, -8, -9, -9, -10, -10, 1, 1, -2, -2, -3, -3, -4, -4, -5, -5, 6, 6, 7, 7, 8, 8, -9, -9, -10, -10, -1, -1, -2, -2, -3, -3, 4, 4, 5, 5, -6, -6, -7, -7, -8, -8, -9, -9, -10, -10, 1, 1, -2, -2, 3, 3, -4, -4, 5, 5, -6, -6, 7, 7, 8, 8, 9, 9, -10, -10, 1, 1, 2, 2, -3, -3, 4, 4, -5, -5, -6, -6, -7, -7, 8, 8, 9, 9, -10, -10, 1, 1, -2, -2, -3, -3, 4, 4, -5, -5, 6, 6, -7, -7, 8, 8, 9, 9, -10, -10, -1, -1, 2, 2, -3, -3, -4, -4, 5, 5, -6, -6, -7, -7, 8, 8, 9, 9, 10, 10, 1, 1, 2, 2, -3, -3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, -9, -9, -10, -10, 1, 1, -2, -2, 3, 3, -4, -4, -5, -5, -6, -6, -7, -7, 8, 8, 9, 9, 10, 10, -1, -1, 2, 2, 3, 3, 4, 4, -5, -5, -6, -6, 7, 7, 8, 8, 9, 9, 10, 10, 1, 1, 2, 2, -3, -3, 4, 4, -5, -5, -6, -6, 7, 7, -8, -8, 9, 9, -10, -10 ]

Write $b=D_{RL}(b)^{-1}N_{RL}(b)$. Then the following braid word obtained through techniques listed in this answer represents a braid of the form $\Delta_{n}^{r}N_{RL}(b)$. On the other hand, the following braid gives most of the information about the right half of the braid $b$.

[ 9, 8, -9, -10, 7, 8, 9, -10, 9, 10, 10, 9, 10, 8, 9, 6, 7, 8, 9, 10, 5, 6, 7, -8, 9, 10, 10, -8, -9, -9, 10, 10, -4, -5, -3, -4, -5, -5, -1, 2, -3, 4, 4, 5, 2, -3, 4, 5, 2, 3, 4, 5, -6, -6, 7, 7, 8, 8, 9, 9, 10, 10, 5, 5, 6, 6, -7, -7, -8, -8, -9, -9, -10, -10, -1, 2, -3, 2, -3, -3, -1, 2, 3, 4, 4, -5, -5, 6, -7, 6, 6, 7, -8, -8, 9, 9, 10, 10, -1, 2, 3, 3, -4, -4, -5, -6, -6, -6, -5, 6, 7, 7, -8, -8, 9, 9, 10, 10, -1, -2, -2, -3, -3, -4, 5, -4, 5, -6, -6, -7, -7, -8, -8, -9, -9, -10, -10, -1, -1, -2, -2, -3, 4, -5, -6, -7, -8, -9, -10, -3, 4, -5, -6, -7, -8, -9, 4, -5, -6, -7, -8, 9, 10, 4, -5, -6, -7, 8, 9, 10, 4, -5, -6, 4, -5, 6, 7, 8, 9, 10, 4, 5, 6, 7, 8, 9, 10, -3, -4, -5, 6, -2, -3, -1, -2, -3, -3, -4, 5, -6, -7, -8, -9, -10, 5, -6, -7, -8, -9, 10, -4, -5, -5, 6, -7, -8, 9, 10, -5, -6, -7, 8, -4, -5, -6, 7, -8, 9, -3, -4, -5, -6, -6, -7, 8, -9, -10, 8, -9, 10, -7, 8, 9, 10, -7, 8, 9, -6, -7, -7, 8, -9, -10, 8, -9, 10, 8, 9, 10, -7, -8, -8, 9, -10, 9, -8, -9, 10, -9, -9, -10, -10, -2, 3, -4, 5, 3, -2, -3, -4, 5, -4, -5, -6, -6, -7, -7, 8, 8, 9, 9, 10, 10, -5, -5, -6, -6, 7, 7, 8, 8, 9, 9, 10, 10, -3, -3, 4, 4, -5, -5, -6, -6, 7, 7, -8, -8, 9, 9, -10, -10 ]