Translation-like actions by $\mathbb{Z}$, the subgroup membership problem, and Medvedev degrees of effective subshifts
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913792862978048 |
|---|---|
| author | Carrasco-Vargas, Nicanor |
| author_facet | Carrasco-Vargas, Nicanor |
| contents | We show that every infinite, locally finite, and connected graph admitsa translation-like action by $\mathbb{Z}$, and that this action can be takento be transitive exactly when the graph has either one or two ends.The actions constructed satisfy $d(v,v\ast 1)\leq3$ for every vertex$v$. This strengthens a theorem by Brandon Seward. We also study the effective computability of translation-like actionson groups and graphs. We prove that every finitely generated infinitegroup with decidable word problem admits a translation-like actionby $\mathbb{Z}$ which is computable, and satisfies an extra condition whichwe call decidable orbit membership problem. As a nontrivial application of our results, we prove that for everyfinitely generated infinite group with decidable word problem, effectivesubshifts attain all $Π_{1}^{0}$ Medvedev degrees. This extends a classification proved by Joseph Miller for $\mathbb{Z}^{d},$ $d\geq1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_14820 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Translation-like actions by $\mathbb{Z}$, the subgroup membership problem, and Medvedev degrees of effective subshifts Carrasco-Vargas, Nicanor Dynamical Systems Combinatorics Group Theory Logic 37B10, 05C63, 20F65, 03D99 We show that every infinite, locally finite, and connected graph admitsa translation-like action by $\mathbb{Z}$, and that this action can be takento be transitive exactly when the graph has either one or two ends.The actions constructed satisfy $d(v,v\ast 1)\leq3$ for every vertex$v$. This strengthens a theorem by Brandon Seward. We also study the effective computability of translation-like actionson groups and graphs. We prove that every finitely generated infinitegroup with decidable word problem admits a translation-like actionby $\mathbb{Z}$ which is computable, and satisfies an extra condition whichwe call decidable orbit membership problem. As a nontrivial application of our results, we prove that for everyfinitely generated infinite group with decidable word problem, effectivesubshifts attain all $Π_{1}^{0}$ Medvedev degrees. This extends a classification proved by Joseph Miller for $\mathbb{Z}^{d},$ $d\geq1$. |
| title | Translation-like actions by $\mathbb{Z}$, the subgroup membership problem, and Medvedev degrees of effective subshifts |
| topic | Dynamical Systems Combinatorics Group Theory Logic 37B10, 05C63, 20F65, 03D99 |
| url | https://arxiv.org/abs/2303.14820 |