Fast Nielsen-Thurston classification of braids. (Q2453736)

The paper provides an algorithm to decide when a braid is either reducible, periodic or pseudo-Anosov. The result relies on many previous works which also involve algorithms; notoriously the work by \textit{J. González-Meneses} and \textit{B. Wiest} [Algebr. Geom. Topol. 11, No. 5, 2971-3010 (2011; Zbl 1252.20035)]. The main result is the algorithm given as follows: Theorem 1. Let \(n\) be a positive integer. There exists an algorithm which decides the Nielsen-Thurston type of any braid \(x\) with \(n\) strands and runs in time \(O(|x|^2)\). The explicit description of the algorithm, which is provided in 4 steps, is too technical to be described here. Nevertheless a main step of the algorithm relies in the following relevant result which is Theorem 12. There exists a constant \(C(n)\) (depending only on \(n\)) such that for any pseudo-Anosov \(n\)-strand braid \(x\in SSS(x)\), the following holds: \(x\) has a rigid conjugate if and only if \(s^{C(n).|x|}(x)\) is rigid. As pointed out by the author, the algorithm rests on a linear bound, which is not explicitly known. Therefore the main result is an existence result.