# Algorithm for identifying reducible braids

If $$\vec{n} = (n_1,...,n_k)$$ is a vector of integers, there seems to be a well-defined homomorphism

$$B_k \ltimes \left(B_{n_1} \times \cdots \times B_{n_k}\right) \to B_N$$

where $$N = \sum n_i$$ and $$B_N$$ denotes the braid group with $$N$$ strands. To see this, use the $$k$$ braids supplied by the right factors as strands for the "large" braid specified by the left factor $$B_k$$. Let us call a braid $$b \in B_N$$ nested if it lies in the image of such a homomorphism for some $$\vec n \neq (1,...,1), (N)$$.

Are there algorithms for determining whether a braid is nested?

Thanks!

EDIT: Here nested braids are called "reducible" following the Nielsen-Thurston classification. Not sure whether the classification is effective.

As has been pointed out in the comments, the question can also be reformulated in terms of the composition map of the little squares operad.

• Your homomorphism of braid groups, you would either need to make those pure braid groups, or make the $n_i's$ all equal and turn it into a wreath product construction. Regardless, this is the $\pi_1$ map for the $2$-cubes operad's multiplication map. It's discussed in many books and papers that talk about operads, as the cubes operad is perhaps the most heavily studied object in the subject. Oct 4 '19 at 17:37
• @RyanBudney Thanks for the correction. Do you have a reference giving some kind of algorithm for determining whether an element lies in the image of this map? Oct 4 '19 at 18:33
• I can imagine a relatively "expensive" way to do it in Regina, looking for incompressible tori in the mapping torus. Have you tried the Bell-Webb algorithm? I have not, but here is an implementation: curver.readthedocs.io/en/master It sounds like it might be exactly what you want, although the authors seem to imply this implementation can be slow, or perhaps memory-intensive. Oct 5 '19 at 16:12
• Mark Bell's "Flipper" appears to be an all-in-one implementation of my initial suggestion, finding the JSJ decomposition of the mapping torus -- although I doubt he uses Regina. flipper.readthedocs.io His software appears well-written. I had looked at some of his software many years ago. These packages appear complete now. Oct 5 '19 at 16:18
• Thanks @RyanBudney, I'll take a look. You seem to make a few mental leaps which I'll have to climb... if you'd like to turn your comments into an answer, I'd gladly accept it. Oct 5 '19 at 17:57

Yes, this is something that the Python package flipper can do. Flipper comes with the spherical braid group $$SB_N$$ already available within it - which is the braid $$B_{N-1}$$ modulo its center. This comes with the braid generators s_i = $$\sigma_i$$ and S_i = $$\sigma_i^{-1}$$. So after installing flipper via:

\$ pip install flipper


Then within Python you can do:

>>> import flipper
>>> S = flipper.load('SB_5')  # B_4 / Z(B_4)
>>> h = S('s_1.S_2')  # A mapping class made from the provided generators.
>>> h.is_reducible()
True
>>> g = h**2 * S('S_3^5')  # Composition and powers are supported.
>>> g.is_reducible()
False


Flipper uses measured laminations and Agol's theory of maximal train track splitting sequences to determine the Nielsen--Thurston type of mapping classes. Since this involves manipulating algebraic numbers, if you need to do complicated examples then you should look at running flipper within SageMath or installing the cypari / cypari2 package.

The Python package curver can also do this (in fact the exact same code will work if you replace flipper with curver) using theory of curve complexes. However although the current release of this package runs in polynomial time, as the documentation describes there is a large constant which makes this impractical. However there is a strategy to work around this and this will be dealt with in a future release.

Yes, there are algorithms to answer your questions. I don't have an encyclopedic knowledge of the algorithms out there, but I know Mark Bell has a few solutions coded-up, in his software packages Flipper and Curver. Flipper works via 3-manifold theory. The Nielsen-Thurston classification of a surface diffeomorphism is closely related to the geometric decomposition of the mapping torus. Curver appears to be an algorithm that works in the curve complex of the surface.

In principle you should be able to answer your question in Regina, as well. The code to find the JSJ decomposition is in Regina, but likely the code to construct the mapping torus, if it is fully implemented in Regina, would likely have been taken from Bell -- I had been meaning to import Bell's code into Regina for some time. Perhaps someone else has done it. If not, it is here.

• I'm afraid it's still not clear to me how to use these packages to solve the question of whether a braid is reducible. Could you clarify? I mean - which algorithm to run, how to construct the input, how to interpret the output...? Oct 5 '19 at 18:22
• In curver there's the nielsen_thurston_type() call on a mapping class. Presumably you would use that. curver.readthedocs.io/en/master/user/… Oct 5 '19 at 18:30