Algorithm for identifying reducible braids

Question

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.

Answer 1

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.

Answer 2

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.