Effective Equation Solving, Constraints, and Growth in Virtually Abelian Groups

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, abelianization, 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 the work of Benson [Invent. Math., 73 (1983), pp. 251–269], but his approach is not constructive.