Twisted Equations and Palindrome Length
Abstract
Twisted equations in free groups are equations in which a finite group of symmetries acts on the free group by automorphisms and anti-automorphisms, such as inversion and reversal; moreover, the variables may be subject to rational constraints. Algorithms from the theory of equations in virtually free groups solve such equations in PSPACE, but they are intricate. Our main result is an elementary algorithm for quadratic twisted equations, which extends the algorithm of Comerford and Edmunds (1981) for quadratic equations in free groups to the twisted setting and to rational constraints. Besides deciding solvability in PSPACE and yielding EDT0L descriptions of solution sets, our algorithm computes, for every quadratic expression, finitely many parametric forms describing its values as freely reduced words. As an application, we study the palindrome length of elements of free groups, that is, the least number of palindromes whose product they are. Guided by the parametric forms that our algorithm computes for products of palindromes, we found, and then proved directly, a characterization of the freely reduced words of palindrome length at most n in terms of patterns describing how palindromes are nested by twisted conjugations, thereby confirming a Catalan structure conjectured by the second author. Consequently, these words form a context-free language, and palindrome length is computable in cubic time as well as in LOGCFL, answering a question of Bardakov, Shpilrain, and Tolstykh (2005).
Related
- Length-generating functions for twisted involutions of Coxeter groups
- A Twisted Affine Interpolation of the ℤ22-graded Integrable Super-Liouville and super-Sinh-Gordon Equations
- The twisted twin of the Grigorchuk group
- Quivers with Involutions and Shifted Twisted Yangians via Coulomb Branches
- Hard Lefschetz theorem for logarithmic sheaves twisted by pseudo-effective line bundles
BibTeX
@misc{diekert2026twisted,
title = {{Twisted Equations and Palindrome Length}},
author = {Volker Diekert and Anna E. Frid and Silas Natterer and Alexander Thumm},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14536},
eprint = {2610.14536},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14536},
}
RIS
TY - UNPB
TI - Twisted Equations and Palindrome Length
AU - Volker Diekert
AU - Anna E. Frid
AU - Silas Natterer
AU - Alexander Thumm
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2610.14536
UR - https://arxiv.org/abs/2610.14536
AB - Twisted equations in free groups are equations in which a finite group of symmetries acts on the free group by automorphisms and anti-automorphisms, such as inversion and reversal; moreover, the variables may be subject to rational constraints. Algorithms from the theory of equations in virtually free groups solve such equations in PSPACE, but they are intricate. Our main result is an elementary algorithm for quadratic twisted equations, which extends the algorithm of Comerford and Edmunds (1981) for quadratic equations in free groups to the twisted setting and to rational constraints. Besides deciding solvability in PSPACE and yielding EDT0L descriptions of solution sets, our algorithm computes, for every quadratic expression, finitely many parametric forms describing its values as freely reduced words. As an application, we study the palindrome length of elements of free groups, that is, the least number of palindromes whose product they are. Guided by the parametric forms that our algorithm computes for products of palindromes, we found, and then proved directly, a characterization of the freely reduced words of palindrome length at most n in terms of patterns describing how palindromes are nested by twisted conjugations, thereby confirming a Catalan structure conjectured by the second author. Consequently, these words form a context-free language, and palindrome length is computable in cubic time as well as in LOGCFL, answering a question of Bardakov, Shpilrain, and Tolstykh (2005).
ER -