Effective equation solving, constraints and growth in virtually abelian groups

Laura Ciobanu, Alex Evetts, Alex Levine

Research output: Working paperPreprint

67 Downloads (Pure)

Abstract

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.
Original languageEnglish
PublisherarXiv
Publication statusPublished - 1 Sept 2023

Keywords

  • math.GR
  • cs.DM
  • cs.FL
  • 03D05, 20F10, 20F65, 68Q45

Fingerprint

Dive into the research topics of 'Effective equation solving, constraints and growth in virtually abelian groups'. Together they form a unique fingerprint.

Cite this