Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.12112 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914261210497024 |
|---|---|
| author | Ushakov, Alexander Wang, Yankun |
| author_facet | Ushakov, Alexander Wang, Yankun |
| contents | We study one-variable equations over the lamplighter group $\MZ_2 \wr \MZ$. While the decidability of arbitrary equations over $L_2$ remains open, we prove that the Diophantine problem for single equations in one variable is decidable. Our approach reduces the problem to a divisibility question for families of parametric Laurent polynomials over $\MZ_2$, whose coefficients depend linearly on an integer parameter. We develop an automaton-theoretic framework to analyze divisibility of such polynomials, exploiting eventual periodicity phenomena arising from polynomial division over finite fields. This yields an explicit decision procedure, which is super-exponential in the worst case. On the other hand, we show that for a generic class of equations, solvability can be decided in nearly quadratic time. These results establish a sharp contrast between worst-case and typical computational behavior and provide new tools for the study of equations over wreath products. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_12112 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | One-variable equations over the lamplighter group Ushakov, Alexander Wang, Yankun Group Theory 20F16, 20F10, 68W30 We study one-variable equations over the lamplighter group $\MZ_2 \wr \MZ$. While the decidability of arbitrary equations over $L_2$ remains open, we prove that the Diophantine problem for single equations in one variable is decidable. Our approach reduces the problem to a divisibility question for families of parametric Laurent polynomials over $\MZ_2$, whose coefficients depend linearly on an integer parameter. We develop an automaton-theoretic framework to analyze divisibility of such polynomials, exploiting eventual periodicity phenomena arising from polynomial division over finite fields. This yields an explicit decision procedure, which is super-exponential in the worst case. On the other hand, we show that for a generic class of equations, solvability can be decided in nearly quadratic time. These results establish a sharp contrast between worst-case and typical computational behavior and provide new tools for the study of equations over wreath products. |
| title | One-variable equations over the lamplighter group |
| topic | Group Theory 20F16, 20F10, 68W30 |
| url | https://arxiv.org/abs/2601.12112 |