{"id":"arxiv/2609.26307","url":"https://arxiv.org/abs/2609.26307","tags":["math.GR","cs.CC"],"score":0,"title":"Word Length and Diameter in Permutation Groups","domain":"math.GR","source":"arxiv","authors":["Markus Lohrey","Alexander Thumm"],"reviews":0,"subject":"math.GR","summary":"The input for the binary diameter problem consists of explicitly represented permutations generating a finite group $G$ and a binary-encoded nonnegative integer $k$. The question is whether every element of $G$ is a product of at most $k$ input generators. For the binary length problem, the input contains in addition a permutation $g \\in G$ and it is asked whether $g$ is a product of at most $k$ input generators. We prove that the binary diameter problem is PSPACE-complete. When restricted to $2$-step nilpotent groups, the binary diameter problem is shown to be complete for $\\mathsf{Π_2^P}$,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-22","reactions":{}}