Effective equation solving, constraints and growth in virtually abelian groups
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916181049344000 |
|---|---|
| author | Ciobanu, Laura Evetts, Alex Levine, Alex |
| author_facet | Ciobanu, Laura Evetts, Alex Levine, Alex |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_00475 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Effective equation solving, constraints and growth in virtually abelian groups Ciobanu, Laura Evetts, Alex Levine, Alex Group Theory Discrete Mathematics Formal Languages and Automata Theory 03D05, 20F10, 20F65, 68Q45 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. |
| title | Effective equation solving, constraints and growth in virtually abelian groups |
| topic | Group Theory Discrete Mathematics Formal Languages and Automata Theory 03D05, 20F10, 20F65, 68Q45 |
| url | https://arxiv.org/abs/2309.00475 |