A faster algorithm for commutator length in free groups
Abstract
We compute the commutator length $\cl(w)$ of a reduced word $w\in[F,F]$ of length $M$ in a free group. Given a target $g\ge1$, a deterministic algorithm decides $\cl(w)\le g$ and, when it holds, returns a decomposition into at most $g$ commutators, in $O(M^{3g})$ steps; trying $g=1,2,\dots$ gives $\cl(w)$ in $O(M^{3\cl(w)})$ steps. For $g=1$ the same test takes $O(M)$ expected steps on a uniformly random reduced input in $[F,F]$. All bounds are in the unit-cost model.