← 研踪 PaperTrailarXiv:2611.22303 · v1
A faster algorithm for commutator length in free groups
首次提交 2026-11-17 15:01
版本更新 2026-11-17 15:01
雷达观测 2026-11-18 19:43
摘要
We compute the commutator length $\cl(w)$ of a reduced word of length in a free group. Given a target , a deterministic algorithm decides $\cl(w)\le g$ and, when it holds, returns a decomposition into at most commutators, in steps; trying gives $\cl(w)$ in $O(M^{3\cl(w)})$ steps. For the same test takes expected steps on a uniformly random reduced input in . All bounds are in the unit-cost model.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-17 15:01 · 最新观测版本
A faster algorithm for commutator length in free groups
We compute the commutator length $\cl(w)$ of a reduced word of length in a free group. Given a target , a deterministic algorithm decides $\cl(w)\le g$ and, when it holds, returns a decomposition into at most commutators, in steps; trying gives $\cl(w)$ in $O(M^{3\cl(w)})$ steps. For the same test takes expected steps on a uniformly random reduced input in . All bounds are in the unit-cost model.
查看此版本解读 →查看此版本原文 ↗