Word Length and Diameter in Permutation Groups

Abstract

In the binary diameter problem, the input consists of explicitly given permutations generating a finite group G and a binary-encoded number k, and the question is whether every element of G is a product of at most k of the given generators. In the binary length problem, the input additionally contains a permutation g ∈ G, and the question is whether g is such a product. We show that the binary diameter problem is PSPACE-complete, thereby confirming a conjecture of Lohrey and Rosowski (2023). Moreover, we show that PSPACE-hardness already holds for solvable groups of derived length at most 3, whereas the problem is Π₂^P-complete for 2-step nilpotent groups. For the binary length problem, we establish a sharp complexity threshold: the problem is NP-complete for 2-step nilpotent groups, which extends a result of Lohrey and Rosowski for abelian groups, and PSPACE-complete for groups that are simultaneously 3-step nilpotent and metabelian, which strengthens the main result of Jerrum (1985). Finally, we show that the unary diameter problem, where k is encoded in unary, is Π₂^P-complete for generating sets of the full symmetric group, confirming another conjecture of Lohrey and Rosowski.

Exact curve counting of given word length on the once-punctured torus
Filippo Baroni, David Fisac, Mingkun Liu
arXiv1 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematics Geometry & topologyarXiv
Short permutation pattern waves: The complete length-five classification
Lihong Qiu, Minglei Mao, Yaping Mao
arXiv3 Nov 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Hankel Submatrices with Bounded Word Length: Dimension Tradeoffs in Probabilistic and Quantum Automata
Yixin Zhao
arXiv19 Oct 2026PreprintarXiv licenceFull textGeneral mathematics Quantum physics & quantum informationarXiv
On the word and period growth of some groups of tree automorphisms
Laurent Bartholdi, Zoran Sunik
Communications in Algebra3 Nov 2026Peer-reviewedLicence not statedFull text44 citedAlgebra & number theoryHAL
Word Trace Formulas over Compact Groups and Connected Cumulants
Liviu Paunescu, Florin Radulescu
arXiv25 Oct 2026PreprintCC BY 4.0Full textAlgebra & number theory Analysis & PDEsarXiv

Cite

BibTeX RIS

BibTeX

@misc{lohrey2026word,
  title = {{Word Length and Diameter in Permutation Groups}},
  author = {Markus Lohrey and Alexander Thumm},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.26307},
  eprint = {2609.26307},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.26307},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Word Length and Diameter in Permutation Groups
AU  - Markus Lohrey
AU  - Alexander Thumm
PY  - 2026
DA  - 2026/09/22
PB  - arXiv
DO  - 10.48550/arxiv.2609.26307
UR  - https://arxiv.org/abs/2609.26307
AB  - In the binary diameter problem, the input consists of explicitly given permutations generating a finite group G and a binary-encoded number k, and the question is whether every element of G is a product of at most k of the given generators. In the binary length problem, the input additionally contains a permutation g ∈ G, and the question is whether g is such a product. We show that the binary diameter problem is PSPACE-complete, thereby confirming a conjecture of Lohrey and Rosowski (2023). Moreover, we show that PSPACE-hardness already holds for solvable groups of derived length at most 3, whereas the problem is Π_2^P-complete for 2-step nilpotent groups. For the binary length problem, we establish a sharp complexity threshold: the problem is NP-complete for 2-step nilpotent groups, which extends a result of Lohrey and Rosowski for abelian groups, and PSPACE-complete for groups that are simultaneously 3-step nilpotent and metabelian, which strengthens the main result of Jerrum (1985). Finally, we show that the unary diameter problem, where k is encoded in unary, is Π_2^P-complete for generating sets of the full symmetric group, confirming another conjecture of Lohrey and Rosowski.
ER  -

Abstract

Related

Cite