A faster algorithm for commutator length in free groups
Source: arxiv.org/abs/2611.22303
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.22303
curl -X POST /api/v1/records/arxiv/2611.22303/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.22303/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'