pith. sign in

arxiv: 2507.21342 · v2 · submitted 2025-07-28 · 🧮 math.DS · cs.CC· cs.DM

Undecidability of the block gluing classes of homshifts

Nishant Chandgotia , Silv\`ere Gangloff , Benjamin Hellouin de Menibus , Piotr Oprocha This is my paper

Pith reviewed 2026-05-19 03:19 UTC · model grok-4.3

classification 🧮 math.DS cs.CCcs.DM
keywords homshiftsblock gluingundecidabilityfinitely presented groupsshifts of finite typesymbolic dynamicsmixing properties
0
0 comments X

The pith

Deciding whether a homshift is Θ(n)-block gluing is undecidable.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Homshifts are shifts of finite type consisting of all graph homomorphisms from the integer grid to a fixed finite connected undirected graph. Prior work raised the possibility that their mixing and gluing properties might be decidable, in contrast to the general undecidability results for multidimensional shifts of finite type. This paper establishes that the question of whether a homshift belongs to the Θ(n)-block gluing class is undecidable. The argument proceeds by giving a topological reading to the square cover and showing that this property holds precisely when certain finitely presented groups obtained from the cover are finite.

Core claim

By interpreting the square cover topologically, the authors reduce the problem of recognizing Θ(n)-block gluing homshifts to the problem of deciding finiteness for finitely presented groups, thereby proving the former decision problem undecidable.

What carries the argument

The square cover, read topologically, which equates the Θ(n)-block gluing condition for a homshift with the finiteness of associated finitely presented groups.

If this is right

  • Finer mixing properties of homshifts lie outside the decidable regime.
  • Undecidability for homshifts arises from algebraic rather than combinatorial sources used for general shifts of finite type.
  • The square-cover construction yields a systematic way to embed group-theoretic undecidability into questions about symbolic dynamics on graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same reduction technique may apply to other quantitative gluing or mixing classes beyond Θ(n).
  • One could test the result on small explicit graphs G whose associated groups are known to be finite or infinite.
  • The topological view of the square cover may connect block-gluing questions to homology or fundamental-group computations in the space of homomorphisms.

Load-bearing premise

The topological interpretation of the square cover correctly encodes the Θ(n)-block gluing property as equivalent to finiteness of associated finitely presented groups.

What would settle it

Exhibit a concrete homshift together with its square cover such that the block-gluing class can be computed directly while the finiteness status of the associated group is known, and the two disagree.

Figures

Figures reproduced from arXiv: 2507.21342 by Benjamin Hellouin de Menibus, Nishant Chandgotia, Piotr Oprocha, Silv\`ere Gangloff.

Figure 2
Figure 2. Figure 2: Illustration for the definition of fundamental group on three examples. [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of the function v 7→ p a T (v). The spanning tree T has been indicated in the middle column. 3.2 Graph covers and deck transformations Definition 3.8. A covering map from a graph G˜ to G is a graph homomor￾phism θ : G˜ → G which is a ‘local isomorphism’, meaning that for all a ∈ G, θ −1 (NG(a)) = G a˜∈θ−1(a) NG˜(˜a), and the map θ|NG˜ (˜a) is bijection onto NG(θ(˜a)) for all a˜ ∈ VG˜. A cover … view at source ↗
Figure 4
Figure 4. Figure 4: Illustration for the definition of cover. For each graph [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Illustration for the definition of universal cover. Left column: the [PITH_FULL_IMAGE:figures/full_fig_p014_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: An example of cover G˜ of a graph G. Notation 3.20. For any spanning tree T of G and a ∈ G, set: ψ a T : π1(G) × G → UG g, b 7→ ηg ◦ p a T (b). Lemma 3.21. For any spanning tree T of G and a ∈ G, the map ψ a T is a bijection. Furthermore, for all g, ψ a T (g, .) is a graph homomorphism as a map from T to UG. Proof. Indeed, its inverse is the map defined by: (ψ a T ) −1 : w 7→ (w ⋆ (p a T (α(w)))−1 , α(w)).… view at source ↗
Figure 7
Figure 7. Figure 7: Illustration for the definition of square group. Left: the graph [PITH_FULL_IMAGE:figures/full_fig_p020_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: illustrates the types of situations where two walks differ by a square. p q (i) p q (ii) p q (iii) [PITH_FULL_IMAGE:figures/full_fig_p023_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: A configuration that cannot be lifted to [PITH_FULL_IMAGE:figures/full_fig_p025_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: A bipartite graph whose square group is Z/3Z. All vertices with the same label are identified. In [PITH_FULL_IMAGE:figures/full_fig_p027_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Example of flat quadrangulation. Definition 5.13. A connected planar graph G is called a flat quadrangula￾tion if it has a planar embedding for which borders of all internal faces are squares and every square is the border of some internal face [PITH_FULL_IMAGE:figures/full_fig_p030_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Illustration for the proof of Proposition [PITH_FULL_IMAGE:figures/full_fig_p031_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Illustration of Notation 5.16. The graph on the right is G\(v, w), where G is the graph on its left. Lemma 5.17. Consider a flat quadrangulation G with fixed planar embedding, and (v, w) an edge which belongs to the border of an external face and the border of an internal face. Then G \ (v, w) is a flat quadrangulation, has one less internal face than G and π □ 1 (G \ (v, w)) ∼= π □ 1 (G). 31 [PITH_FULL_… view at source ↗
Figure 14
Figure 14. Figure 14: Illustration for the definition of the graph [PITH_FULL_IMAGE:figures/full_fig_p034_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Illustration of the effect of ν. The graph on the left corresponds to the choice νr = (0, 1, 0, 1 . . .) and the one on the right corresponds to the choice νr = (0, 0, 0, 0 . . .). Proof. We pick N = 6, νr = (0)k≤6|r| for all r, and Fr as a flat quadrangulation whose border is Cr and such that no vertex outside of the border has two neighbours in the border (for instance the one provided by Proposition 5.… view at source ↗
Figure 16
Figure 16. Figure 16: Illustration of the definition of the tree [PITH_FULL_IMAGE:figures/full_fig_p035_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: Illustration of the step 2.5 in the proof of Theorem [PITH_FULL_IMAGE:figures/full_fig_p037_17.png] view at source ↗
read the original abstract

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 $\Theta(n)$-block gluing or not, by relating this problem to the one of finiteness for finitely presented groups.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proves undecidability of whether a homshift X_G (the space of graph homomorphisms from Z^d to a finite connected undirected graph G) belongs to the Θ(n)-block gluing class. Building on the square cover construction of Gangloff-Hellouin de Menibus-Oprocha, the authors give a topological reinterpretation via elementary algebraic topology and homotopy theory, then reduce the decision problem to the known undecidable question of finiteness for finitely presented groups Γ_G associated to G.

Significance. If the central reduction is correct, the result shows that even within the restricted class of homshifts, finer quantitative mixing properties remain undecidable, using a method distinct from the usual Turing-machine embeddings employed for general multidimensional SFTs. The work is notable for its explicit connection between symbolic dynamics and group presentations via the square cover, and for crediting the prior topological and dynamical foundations while extending them to obtain a computable reduction.

major comments (2)
  1. [§3] §3 (Topological interpretation of the square cover): The argument that the square cover is homotopy-equivalent to the classifying space of the finitely presented group Γ_G, and that this equivalence exactly captures Θ(n)-block gluing, must be verified uniformly for every finite connected G. The current sketch leaves open whether the correspondence holds when G contains odd cycles or is not vertex-transitive; an explicit check or counter-example family would be required to confirm the reduction is total.
  2. [§4] §4 (Reduction to finiteness): The proof that X_G is Θ(n)-block gluing if and only if Γ_G is finite must include an explicit, effective procedure that, given any finite connected G, produces a finite presentation of Γ_G and shows that the topological invariants are computable from G. Without this, the transfer of undecidability from the group-finiteness problem is not fully established.
minor comments (2)
  1. [Introduction] The definition of Θ(n)-block gluing should be recalled verbatim in the introduction with a precise citation to the Gangloff et al. paper, rather than assuming the reader recalls the exact quantitative formulation.
  2. [§3] Notation for the square cover and the associated group presentation should be introduced once and used consistently; several local re-definitions appear in the topological section.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the constructive comments. We address each major comment below. The central reduction is correct as stated, and we will revise the manuscript to include the requested explicit verifications and algorithmic details.

read point-by-point responses

  1. Referee: [§3] §3 (Topological interpretation of the square cover): The argument that the square cover is homotopy-equivalent to the classifying space of the finitely presented group Γ_G, and that this equivalence exactly captures Θ(n)-block gluing, must be verified uniformly for every finite connected G. The current sketch leaves open whether the correspondence holds when G contains odd cycles or is not vertex-transitive; an explicit check or counter-example family would be required to confirm the reduction is total.

    Authors: The construction and homotopy equivalence in §3 are uniform and apply to every finite connected undirected graph G. The square cover is defined combinatorially from the vertex and edge sets of G; its 2-skeleton is the standard presentation complex for the group Γ_G whose generators are the length-2 paths in G and whose relations are the commuting squares. This presentation complex is homotopy-equivalent to the classifying space K(Γ_G,1) by the standard algebraic-topology fact that the universal cover is contractible precisely when the group is the fundamental group of the complex. Neither vertex-transitivity nor the absence of odd cycles is used: odd cycles simply contribute additional generators or relations in the presentation, while non-transitive graphs are handled by labeling vertices distinctly. We will add a short subsection in the revision that explicitly verifies the equivalence on two families: (i) any triangle (odd cycle) and (ii) a non-vertex-transitive graph such as the path of length 3 with an extra pendant edge. These checks confirm that the reduction to finiteness of Γ_G remains total. revision: yes

  2. Referee: [§4] §4 (Reduction to finiteness): The proof that X_G is Θ(n)-block gluing if and only if Γ_G is finite must include an explicit, effective procedure that, given any finite connected G, produces a finite presentation of Γ_G and shows that the topological invariants are computable from G. Without this, the transfer of undecidability from the group-finiteness problem is not fully established.

    Authors: We agree that spelling out the effective procedure makes the reduction fully rigorous. Given a finite connected graph G with vertex set V and edge set E, the finite presentation of Γ_G is obtained as follows: generators are the ordered pairs (v,e) where e is an edge incident to v (or equivalently the length-2 paths); relations are the words corresponding to each 2×2 square in the grid that map to a commuting square in G. Both the generator list and the relation list are finite and can be enumerated in time linear in |V|+|E|. The topological invariants (fundamental group, homotopy type of the square cover) are then read directly from this presentation. Because the equivalence between Θ(n)-block gluing of X_G and finiteness of Γ_G is proved via the homotopy equivalence already established in §3, the undecidability of group finiteness transfers immediately. We will insert this algorithmic description as a new paragraph in §4 together with a short proof that the procedure is computable from the adjacency matrix of G. revision: yes

Circularity Check

0 steps flagged

No circularity; self-contained reduction to external undecidability

full rationale

The paper proves undecidability of Θ(n)-block gluing for homshifts by introducing a topological interpretation (inspired by Gao-Jackson-Krohne-Seward and algebraic topology) of the square cover from prior work, then establishing an equivalence to finiteness of associated finitely presented groups Γ_G for finite connected graphs G. This equivalence is derived within the manuscript and transfers undecidability from the independently known undecidability of the finiteness problem for finitely presented groups in group theory. The self-citation to arXiv:2211.04075 supplies only the definition of the square cover; the load-bearing steps (topological reinterpretation and the if-and-only-if relation to group finiteness) are proven here and are externally falsifiable via standard group-theoretic results, rendering the derivation self-contained with no reduction by construction to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Relies on standard results from algebraic topology and combinatorial group theory plus definitions of homshifts and square covers from cited prior papers; no new free parameters or invented entities are introduced in the abstract.

axioms (2)
  • standard math Finiteness of finitely presented groups is undecidable
    Known result invoked to transfer undecidability to the block-gluing question.
  • domain assumption Topological interpretation of the square cover captures block-gluing behavior
    Central modeling step stated in the abstract as the bridge to the group-theoretic problem.

pith-pipeline@v0.9.0 · 5753 in / 1315 out tokens · 71674 ms · 2026-05-19T03:19:32.937076+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Finitely Dependent Processes on Subshifts

    math.PR 2026-05 unverdicted novelty 7.0

    Finitely dependent processes exist densely on mixing subshifts but are obstructed by cohomology on some tiling spaces, with a characterization for Z^2 box tilings that resolves a prior open question.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages · cited by 1 Pith paper

  1. [1]

    Noga Alon, Raimundo Brice \ n o, Nishant Chandgotia, Alexander Magazinov, and Yinon Spinka, Mixing properties of colourings of the \( Z ^d\) lattice , Comb. Probab. Comput. 30 (2021), no. 3, 360--373

    work page 2021

  2. [2]

    Adian, On algorithmic problems in effectively complete classes of groups, Dokl

    Sergei I. Adian, On algorithmic problems in effectively complete classes of groups, Dokl. Akad. Nauk SSSR 123 (1958), 13--16

    work page 1958

  3. [3]

    298 (2005), no

    H \'e l \`e ne Barcelo and Reinhard Laubenbacher, Perspectives on \(A\) -homotopy theory and its applications , Discrete Math. 298 (2005), no. 1-3, 39--61

    work page 2005

  4. [4]

    3, 2110--2137

    Raimundo Brice\ n o and Ronnie Pavlov, Strong spatial mixing in homomorphism spaces, SIAM Journal on Discrete Mathematics 31 (2017), no. 3, 2110--2137

    work page 2017

  5. [5]

    Mike Boyle, Ronnie Pavlov, and Michael Schraudner, Multidimensional sofic shifts without separation and their factors, Transactions of the American Mathematical Society 362 (2010), 4617--4653

    work page 2010

  6. [6]

    Nishant Chandgotia and Brian Marcus, Mixing properties for hom-shifts and the distance between walks on associated graphs, Pacific J. Math. 294 (2018), no. 1, 41--69

    work page 2018

  7. [7]

    Nishant Chandgotia and Tom Meyerovitch, Borel subsystems and ergodic universality for compact \( Z ^d\) -systems via specification and beyond , Proc. Lond. Math. Soc. (3) 123 (2021), no. 3, 231--312

    work page 2021

  8. [8]

    David Bruce Cohen, The large scale geometry of strongly aperiodic subshifts of finite type, Adv. Math. 308 (2017), 599--626

    work page 2017

  9. [9]

    Nicanor Carrasco-Vargas, On a R ice theorem for dynamical properties of SFT s on groups , 2024

    work page 2024

  10. [10]

    Blondel, Quasi-periodic configurations and undecidable dynamics for tilings, infinite words and T uring machines , Theoretical Computer Science 319 (2004), no

    Jean-Charles Delvenne and Vincent D. Blondel, Quasi-periodic configurations and undecidable dynamics for tilings, infinite words and T uring machines , Theoretical Computer Science 319 (2004), no. 1-3, 127--143

    work page 2004

  11. [11]

    4, 292--301

    Roland L’vovich Dobrushin, Gibbsian random fields for lattice systems with pairwise interactions, Functional Analysis and its applications 2 (1968), no. 4, 292--301

    work page 1968

  12. [12]

    1-3, 199--220

    Shmuel Friedland, On the entropy of Z ^d subshifts of finite type , Linear algebra and its applications 252 (1997), no. 1-3, 199--220

    work page 1997

  13. [13]

    Silv \`e re Gangloff, Benjamin Hellouin de Menibus, and Piotr Oprocha, Short-range and long-range order: a transition in block-gluing behavior in H om shifts , Journal d'Analyse Math\'ematique (2024), in press

    work page 2024

  14. [14]

    Su Gao, Steve Jackson, Edward Krohne, and Brandon Seward, Continuous combinatorics of abelian group actions, Memoirs of the American Mathematical Society (2018), to appear; arXiv preprint arXiv:1803.03872

    work page arXiv 2018

  15. [15]

    6, 1091–1118

    William Geller and James Propp, The projective fundamental group of a Z ^2 -shift , Ergodic Theory and Dynamical Systems 15 (1995), no. 6, 1091–1118

    work page 1995

  16. [16]

    1, 21--118

    Silv \`e re Gangloff and Mathieu Sablik, Quantified block gluing for multidimensional subshifts of finite type: aperiodicity and entropy , Journal d'Analyse Math \'e matique 144 (2021), no. 1, 21--118

    work page 2021

  17. [17]

    Allen Hatcher, Algebraic topology, Cambridge University Press, 2002

    work page 2002

  18. [18]

    Krzysztof Kapulkin and Udit Mavinkurve, The fundamental group in discrete homotopy theory, Adv. Appl. Math. 164 (2025), 56, Id/No 102838

    work page 2025

  19. [19]

    Florian Lehner, Chromatic numbers of infinite abelian C ayley graphs , https://mathoverflow.net/questions/304715/chromatic-numbers-of-infinite-abelian-cayley-graphs, Accessed: 2025-05-24

    work page 2025

  20. [20]

    Lyndon and Paul E

    Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, vol. 89, Springer, 2001

    work page 2001

  21. [21]

    2-3, 235--239

    Richard Nowakowski and Peter Winkler, Vertex-to-vertex pursuit in a graph, Discrete Mathematics 43 (1983), no. 2-3, 235--239

    work page 1983

  22. [22]

    Ronnie Pavlov and Michael Schraudner, Entropies realizable by block gluing Z ^d shifts of finite type , Journal d'Analyse Mathématique 126 (2015), 113--174

    work page 2015

  23. [23]

    Leibniz Int

    L\' e o Paviet Salomon and Pascal Vanier, Realizing finitely presented groups as projective fundamental groups of SFT s , 48th I nternational S ymposium on M athematical F oundations of C omputer S cience, LIPIcs. Leibniz Int. Proc. Inform., vol. 272, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2023, pp. Art. No. 75, 15

    work page 2023

  24. [24]

    Quas and Paul B

    Anthony N. Quas and Paul B. Trow, Subshifts of multi-dimensional shifts of finite type, Ergodic Theory and Dynamical Systems 20 (2000), no. 3, 859--874

    work page 2000

  25. [25]

    Rabin, Recursive unsolvability of group theoretic problems, Ann

    Michael O. Rabin, Recursive unsolvability of group theoretic problems, Ann. of Math. (2) 67 (1958), 172--194

    work page 1958

  26. [26]

    4, 641--674

    Joseph Rotman, Covering complexes with applications to algebra, The Rocky Mountain Journal of Mathematics 3 (1973), no. 4, 641--674

    work page 1973

  27. [27]

    119, Springer Science & Business Media, 2013

    , An introduction to algebraic topology, vol. 119, Springer Science & Business Media, 2013

    work page 2013

  28. [28]

    Stallings, Topology of finite graphs, Invent

    John R. Stallings, Topology of finite graphs, Invent. Math. 71 (1983), no. 3, 551--565

    work page 1983

  29. [29]

    Marcin Wrochna, Square-free graphs are multiplicative, J. Comb. Theory, Ser. B 122 (2017), 479--507

    work page 2017