Membership problems in nilpotent groups
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912351479922688 |
|---|---|
| author | Bodart, Corentin |
| author_facet | Bodart, Corentin |
| contents | We study both the Submonoid Membership problem and the Rational Subset Membership problem in finitely generated nilpotent groups. We give two reductions with important applications. First, Submonoid Membership in any nilpotent group can be reduced to Rational Subset Membership in smaller groups. As a corollary, we prove the existence of a group with decidable Submonoid Membership and undecidable Rational Subset Membership, confirming a conjecture of Lohrey and Steinberg. Second, the Rational Subset Membership problem in $H_3(\mathbb Z)$ can be reduced to the Knapsack problem in the same group, and is therefore decidable. Combining both results, we deduce that the filiform $3$-step nilpotent group has decidable Submonoid Membership. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_15504 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Membership problems in nilpotent groups Bodart, Corentin Group Theory Discrete Mathematics Formal Languages and Automata Theory We study both the Submonoid Membership problem and the Rational Subset Membership problem in finitely generated nilpotent groups. We give two reductions with important applications. First, Submonoid Membership in any nilpotent group can be reduced to Rational Subset Membership in smaller groups. As a corollary, we prove the existence of a group with decidable Submonoid Membership and undecidable Rational Subset Membership, confirming a conjecture of Lohrey and Steinberg. Second, the Rational Subset Membership problem in $H_3(\mathbb Z)$ can be reduced to the Knapsack problem in the same group, and is therefore decidable. Combining both results, we deduce that the filiform $3$-step nilpotent group has decidable Submonoid Membership. |
| title | Membership problems in nilpotent groups |
| topic | Group Theory Discrete Mathematics Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2401.15504 |