Undecidability of the block gluing classes of homshifts
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916005109825536 |
|---|---|
| author | Chandgotia, Nishant Gangloff, Silvère de Menibus, Benjamin Hellouin Oprocha, Piotr |
| author_facet | Chandgotia, Nishant Gangloff, Silvère de Menibus, Benjamin Hellouin Oprocha, Piotr |
| contents | A homshift is a $d$-dimensional shift of finite type which arises as the space of graph homomorphisms from the grid graph $\mathbb Z^d$ to a finite connected undirected graph $G$. While shifts of finite type are known to be mired by the swamp of undecidability, homshifts seem to be better behaved and there was hope that all the properties of homshifts are decidable. In this paper we build on the work by Gangloff, Hellouin de Menibus and Oprocha (arxiv:2211.04075) to show that finer mixing properties are undecidable for reasons completely different than the ones used to prove undecidability for general multidimensional shifts of finite type. Inspired by the work of Gao, Jackson, Krohne and Seward (arxiv:1803.03872) and elementary algebraic topology, we interpret the square cover introduced by Gangloff, Hellouin de Menibus and Oprocha topologically. Using this interpretation, we prove that it is undecidable whether a homshift is $Θ(n)$-block gluing or not, by relating this problem to the one of finiteness for finitely presented groups. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_21342 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Undecidability of the block gluing classes of homshifts Chandgotia, Nishant Gangloff, Silvère de Menibus, Benjamin Hellouin Oprocha, Piotr Dynamical Systems Computational Complexity Discrete Mathematics 37B51 05C60 68Q17 A homshift is a $d$-dimensional shift of finite type which arises as the space of graph homomorphisms from the grid graph $\mathbb Z^d$ to a finite connected undirected graph $G$. While shifts of finite type are known to be mired by the swamp of undecidability, homshifts seem to be better behaved and there was hope that all the properties of homshifts are decidable. In this paper we build on the work by Gangloff, Hellouin de Menibus and Oprocha (arxiv:2211.04075) to show that finer mixing properties are undecidable for reasons completely different than the ones used to prove undecidability for general multidimensional shifts of finite type. Inspired by the work of Gao, Jackson, Krohne and Seward (arxiv:1803.03872) and elementary algebraic topology, we interpret the square cover introduced by Gangloff, Hellouin de Menibus and Oprocha topologically. Using this interpretation, we prove that it is undecidable whether a homshift is $Θ(n)$-block gluing or not, by relating this problem to the one of finiteness for finitely presented groups. |
| title | Undecidability of the block gluing classes of homshifts |
| topic | Dynamical Systems Computational Complexity Discrete Mathematics 37B51 05C60 68Q17 |
| url | https://arxiv.org/abs/2507.21342 |