The Identity Problem in virtually solvable matrix groups over algebraic numbers
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917893273288704 |
|---|---|
| author | Bodart, Corentin Dong, Ruiwen |
| author_facet | Bodart, Corentin Dong, Ruiwen |
| contents | The Tits alternative states that a finitely generated matrix group either contains a nonabelian free subgroup $F_2$, or it is virtually solvable. This paper considers two decision problems in virtually solvable matrix groups: the Identity Problem (does a given finitely generated subsemigroup contain the identity matrix?), and the Group Problem (is a given finitely generated subsemigroup a group?). We show that both problems are decidable in virtually solvable matrix groups over the field of algebraic numbers $\overline{\mathbb{Q}}$. Our proof also extends the decidability result for nilpotent groups by Bodart, Ciobanu, Metcalfe and Shaffrir, and the decidability result for metabelian groups by Dong (STOC'24). Since the Identity Problem and the Group Problem are known to be undecidable in matrix groups containing $F_2 \times F_2$, our result significantly reduces the decidability gap for both decision problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_02264 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Identity Problem in virtually solvable matrix groups over algebraic numbers Bodart, Corentin Dong, Ruiwen Group Theory Discrete Mathematics Formal Languages and Automata Theory Algebraic Geometry The Tits alternative states that a finitely generated matrix group either contains a nonabelian free subgroup $F_2$, or it is virtually solvable. This paper considers two decision problems in virtually solvable matrix groups: the Identity Problem (does a given finitely generated subsemigroup contain the identity matrix?), and the Group Problem (is a given finitely generated subsemigroup a group?). We show that both problems are decidable in virtually solvable matrix groups over the field of algebraic numbers $\overline{\mathbb{Q}}$. Our proof also extends the decidability result for nilpotent groups by Bodart, Ciobanu, Metcalfe and Shaffrir, and the decidability result for metabelian groups by Dong (STOC'24). Since the Identity Problem and the Group Problem are known to be undecidable in matrix groups containing $F_2 \times F_2$, our result significantly reduces the decidability gap for both decision problems. |
| title | The Identity Problem in virtually solvable matrix groups over algebraic numbers |
| topic | Group Theory Discrete Mathematics Formal Languages and Automata Theory Algebraic Geometry |
| url | https://arxiv.org/abs/2404.02264 |