TY - UNPB
T1 - Effective equation solving, constraints and growth in virtually abelian groups
AU - Ciobanu, Laura
AU - Evetts, Alex
AU - Levine, Alex
N1 - 28 pages
PY - 2023/9/1
Y1 - 2023/9/1
N2 - In this paper we study the satisfiability and solutions of group equations when combinatorial, algebraic and language-theoretic constraints are imposed on the solutions. We show that the solutions to equations with length, lexicographic order, abelianisation or context-free constraints added, can be effectively produced in finitely generated virtually abelian groups. Crucially, we translate each of the constraints above into a rational set in an effective way, and so reduce each problem to solving equations with rational constraints, which is decidable and well understood in virtually abelian groups. A byproduct of our results is that the growth series of a virtually abelian group, with respect to any generating set and any weight, is effectively computable. This series is known to be rational by a result of Benson, but his proof is non-constructive.
AB - In this paper we study the satisfiability and solutions of group equations when combinatorial, algebraic and language-theoretic constraints are imposed on the solutions. We show that the solutions to equations with length, lexicographic order, abelianisation or context-free constraints added, can be effectively produced in finitely generated virtually abelian groups. Crucially, we translate each of the constraints above into a rational set in an effective way, and so reduce each problem to solving equations with rational constraints, which is decidable and well understood in virtually abelian groups. A byproduct of our results is that the growth series of a virtually abelian group, with respect to any generating set and any weight, is effectively computable. This series is known to be rational by a result of Benson, but his proof is non-constructive.
KW - math.GR
KW - cs.DM
KW - cs.FL
KW - 03D05, 20F10, 20F65, 68Q45
M3 - Preprint
BT - Effective equation solving, constraints and growth in virtually abelian groups
PB - arXiv
ER -