Equations in groups, formal languages and complexity

Abstract

We study the use of EDT0L languages to describe solutions to systems of equations in various classes of groups. We show that solutions to systems of equations with rational constraints in virtually abelian groups can be expressed as EDT0L languages. We also study the growth series of these solutions. In addition, we show that the class of groups where solutions can be described using EDT0L languages is closed under direct products, wreath products with finite groups and passing to finite-index subgroups, using standard normal forms in each of the constructions. Using these operations together, we show that the solutions to systems of equations, when expressed as suitable quasi-geodesic normal forms, in virtually direct products of hyperbolic groups, including dihedral Artin groups, can be described using EDT0L languages. We conclude by showing that single equations in one variable in the Heisenberg group can also be expressed using EDT0L languages, with words expressed in Mal’cev normal form. Proving this requires us to first show that solutions to quadratic equations in the ring of integers are EDT0L.