Every braid admits a short sigma-definite expression. (Q645351): Difference between revisions

The author provides an algorithm to decide whether a braid on \(n\) strands, represented by a word of length \(\ell\) in the standard Artin generators, is positive. Its running time is quadratic in \(\ell\). The algorithm consists in obtaining a new expression for the braid from which its positivity or negativity can be read off, i.e. a `sigma-definite expression'. The length of the new expression is at most \(6(n-1)^2\) times the length of a shortest representative for the braid. This is the most interesting feature of the result, for all previously known algorithms provide sigma-definite expressions whose lengths are exponential in \(\ell\). The sigma-definite expression is obtained by considering a new normal form for the braid, called the `rotating normal form', with respect to the Birman-Ko-Lee generators. Its main characteristic is that it is adapted to the Garside element of the Birman-Ko-Lee (or dual) braid monoid, which acts by conjugacy as a rotation of order \(n\) when the strands of the braid are arranged in a circular pattern (rather than in the usual linear one), hence its name.