pith. sign in

arxiv: 2302.07249 · v3 · submitted 2023-02-14 · 💻 cs.DM · cs.FL· math.GR

Graph subshifts

Pablo Arrighi , Am\'elia Durbec , Pierre Guillon This is my paper

Pith reviewed 2026-05-24 10:06 UTC · model grok-4.3

classification 💻 cs.DM cs.FLmath.GR
keywords graph subshiftssubshifts of finite typeaperiodicresidual finitenessperiod groupsymbolic dynamicscombinatorial group theoryundecidability
0
0 comments X

The pith

Graph subshifts consisting only of infinite graphs are either aperiodic or their period group lacks residual finiteness.

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

The paper defines graph subshifts of finite type as sets of graphs obtained by forbidding a finite collection of local patterns. It proves that any such subshift containing exclusively infinite graphs must either contain no periodic elements or have a period group that is not residually finite. This construction extends the classical notion of subshifts of finite type from grids or shifts to arbitrary graphs while also connecting to finitely presented groups. A sympathetic reader cares because the result supplies concrete examples that cannot be reduced to periodic cases and produces two undecidability theorems as direct consequences.

Core claim

The central claim is that the subshifts that contain only infinite graphs are either aperiodic, or feature no residual finiteness of their period group. The argument proceeds by showing that local forbidden patterns can enforce a fixed support graph and that any periodicity in the resulting object must be accompanied by residual finiteness failure in the associated group of periods.

What carries the argument

Graph subshifts of finite type, sets of graphs defined by forbidding finitely many local patterns, which serve both to enforce support graphs and to define a period group.

If this is right

  • The result supplies non-trivial examples of graph subshifts that cannot be reduced to periodic ones.
  • Two natural undecidability theorems follow directly for properties of these subshifts.
  • The construction yields objects that simultaneously generalize classical subshifts of finite type and finitely presented groups.
  • Local conditions on graphs can be used to force global structural properties such as infinity of the support.

Where Pith is reading between the lines

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

  • The same local-rule mechanism might be used to construct new families of aperiodic graphs whose symmetries are controlled by non-residually finite groups.
  • Decidability questions for the existence of finite graphs satisfying given local rules could be reduced to questions about residual finiteness.
  • The framework may allow embedding classical tiling problems into graph subshifts while preserving the aperiodicity or group-theoretic features.

Load-bearing premise

The definition of graph subshifts of finite type via finitely many forbidden local patterns is a valid extension that can enforce specific support graphs.

What would settle it

A concrete example of a graph subshift of finite type whose graphs are all infinite, that admits a periodic element, and whose period group is residually finite would refute the claim.

Figures

Figures reproduced from arXiv: 2302.07249 by Am\'elia Durbec, Pablo Arrighi, Pierre Guillon.

Figure 1
Figure 1. Figure 1: The different types of graphs. (a) A graph G. (b) A pointed graph (G, 1). (c) A pointed graph modulo X. We single out a vertex as the origin: Pointed graph non-modulo. A pointed graph is a pair (G, p) with p ∈ V (G). The set of pointed graphs with states in Σ and ports π is written PΣ,π, or simply P. Here is when graph differ only modulo names of vertices: Graph Isomorphism. An isomorphism R is a function … view at source ↗
Figure 2
Figure 2. Figure 2: Locally grid-like SFT corresponding to the Cayley graph of ha, b|aba−1 b −1 i. The SFT is defined by forbidding all but these patterns, on their corresponding languages. Example 2 (Locally grid-like SFT). We can define a graph SFT with ports π = {a, a0 , b, b0 } corresponding to the monochromatic fullshift on ha, b|aba−1 b −1 = εi, by imposing three families of constraints: 1. enforcing that edges be of th… view at source ↗
Figure 3
Figure 3. Figure 3: Configuration of the hard-square model that is present in Z 2 . The colours represent the 0/1 internal states of the vertices. 1. each edge involves two inverse ports; 2. every vertex must have all possible ports; 3. for every word u ∈ R and L its language of prefixes, one forbids the pair (Y, L) for every graph Y supported by L in which path u is not a cycle back to the origin. This SFT obviously contains… view at source ↗
Figure 4
Figure 4. Figure 4: Configuration of the hard-square model whose support graph is not Z 2 . In order to preserve clarity, only half of the ports are written and some edges have been dashed. Let Γ be a finitely presented group. A SFT is defined by Γ-NN constraints if they include precisely the forbidden patterns defining Z Γ and some additional nearest-neighbor forbidden patterns. Note that if Γ = Fk, then Fk-NN constraints ar… view at source ↗
read the original abstract

We propose a definition of graph subshifts of finite type that can be seen as extending both the notions of subshifts of finite type from classical symbolic dynamics and finitely presented groups from combinatorial group theory. These are sets of graphs that are defined by forbidding finitely many local patterns. In this paper, we focus on the question whether such local conditions can enforce a specific support graph, and thus relate the model to classical symbolic dynamics. We prove that the subshifts that contain only infinite graphs are either aperiodic, or feature no residual finiteness of their period group, yielding non-trivial examples as well as two natural undecidability theorems.

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

1 major / 2 minor

Summary. The paper proposes a definition of graph subshifts of finite type (GSFTs) as sets of graphs obtained by forbidding finitely many local patterns. This is presented as extending both classical subshifts of finite type in symbolic dynamics and finitely presented groups in combinatorial group theory. The authors focus on whether such local forbids can enforce a specific support graph. They prove a dichotomy: any GSFT consisting only of infinite graphs is either aperiodic or its period group is not residually finite. This is used to construct non-trivial examples and to derive two undecidability theorems.

Significance. If the definition is robust and the dichotomy holds, the work supplies a concrete bridge between symbolic dynamics on graphs and combinatorial group theory. The structural result on infinite-graph GSFTs yields explicit examples of aperiodic or non-residually-finite objects and supplies natural undecidability corollaries, which are strengths of the manuscript.

major comments (1)
  1. [Main theorem / proof of dichotomy] The central dichotomy (abstract) rests on the new definition of GSFTs and on the handling of infinite versus finite graphs. The manuscript must supply a fully detailed proof of the dichotomy, including explicit verification that the local-pattern forbids correctly distinguish infinite graphs and that the period-group construction is free of circularity with the residual-finiteness property.
minor comments (2)
  1. [Abstract] The abstract states that two undecidability theorems follow but does not name the decision problems; a one-sentence indication of the problems (e.g., emptiness or periodicity) would improve readability.
  2. [Preliminaries] Notation for the period group and residual finiteness should be introduced with a short reminder of the classical definitions to aid readers coming from symbolic dynamics.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their detailed reading and for identifying the need to strengthen the presentation of the central result. We address the major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Main theorem / proof of dichotomy] The central dichotomy (abstract) rests on the new definition of GSFTs and on the handling of infinite versus finite graphs. The manuscript must supply a fully detailed proof of the dichotomy, including explicit verification that the local-pattern forbids correctly distinguish infinite graphs and that the period-group construction is free of circularity with the residual-finiteness property.

    Authors: We agree that the proof of the dichotomy requires fuller detail and explicit checks. In the revised manuscript we will expand the proof (currently in Section 4) to include: (i) a self-contained verification that each forbidden local pattern is satisfied by all infinite graphs in the GSFT but violated by any finite graph that could otherwise appear; (ii) a reorganized construction of the period group that first defines the group operation and generators independently of residual finiteness, then separately proves the non-residual-finiteness claim. These additions will eliminate any appearance of circularity and make the distinction between finite and infinite supports fully explicit. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper defines graph subshifts of finite type via a new local-forbidding construction that extends symbolic dynamics and combinatorial group theory. The central claim (subshifts containing only infinite graphs are aperiodic or lack residual finiteness of the period group) and the undecidability corollaries are stated as direct consequences of this definition and standard arguments in the extended model. No equations, fitted parameters, self-citations, or ansatzes are invoked in a load-bearing way that reduces the result to its own inputs by construction. The derivation chain is therefore self-contained and non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper's contribution rests on introducing a new definition; no numerical free parameters are described. The definition itself functions as the central invented entity.

axioms (1)
  • standard math Standard definitions of graphs, local patterns, subshifts of finite type, and finitely presented groups from prior literature in symbolic dynamics and combinatorial group theory.
    The work explicitly positions itself as extending these existing notions.
invented entities (1)
  • graph subshift of finite type no independent evidence
    purpose: To define sets of graphs by forbidding finitely many local patterns, bridging symbolic dynamics and group presentations.
    This is the core new object introduced in the paper; no independent evidence outside the definition is supplied in the abstract.

pith-pipeline@v0.9.0 · 5627 in / 1262 out tokens · 22043 ms · 2026-05-24T10:06:54.252466+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.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages · 2 internal anchors

  1. [1]

    Reversibility vs local creation/destruction

    Pablo Arrighi, Am´ elia Durbec, and Aur´ elien Emmanuel. Reversibility vs local creation/destruction. In Michael Kirkedal Thomsen and Mathias Soeken, editors, Reversible Computation - 11th Interna- tional Conference, RC 2019, Lausanne, Switzerland, June 24-25, 2019, Proceedings , volume 11497 of Lecture Notes in Computer Science, pages 51–66. Springer, 20...

    work page doi:10.1007/978-3-030-21500-2 2019

  2. [2]

    Cellular automata over generalized cay- ley graphs

    Pablo Arrighi, Simon Martiel, and Vincent Nesme. Cellular automata over generalized cay- ley graphs. Mathematical Structures in Computer Science , 28(3):340–383, 2018. doi:10.1017/ S0960129517000044

    work page 2018

  3. [3]

    Propri´ et´ es structurelles, combinatoires et logiques des pavages

    Alexis Ballier. Propri´ et´ es structurelles, combinatoires et logiques des pavages. Ph.d. thesis, Universit´ e de Provence, Nov 2009

    work page 2009

  4. [4]

    Some two-generator one-relator non-hopfian groups

    Gilbert Baumslag and Donald Solitar. Some two-generator one-relator non-hopfian groups. Bulletin of the American Mathematical Society , 68(3):199–201, 1962. 00471. URL: https://www.ams.org/ bull/1962-68-03/S0002-9904-1962-10745-9/ , doi:10.1090/S0002-9904-1962-10745-9

    work page doi:10.1090/s0002-9904-1962-10745-9 1962

  5. [5]

    The undecidability of the domino problem

    Robert Berger. The undecidability of the domino problem . Phd, Harvard University, jul 1964

    work page 1964

  6. [6]

    When periodicities enforce aperiodicity

    Nicolas B´ edaride and Thomas Fernique. When periodicities enforce aperiodicity. Communications in Mathematical Physics, 335(3):1099–1120, May 2015. arXiv: 1309.3686. URL: http://arxiv.org/ abs/1309.3686, doi:10.1007/s00220-015-2334-8

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/s00220-015-2334-8 2015

  7. [7]

    Cellular Automata and Groups

    Tullio Ceccherini-Silberstein and Michel Coornaert. Cellular Automata and Groups . Springer, 2009

    work page 2009

  8. [8]

    Tilings of the plane and Thurston semi-norm

    J.-R. Chazottes, J.-M. Gambaudo, and F. Gautero. Tilings of the plane and Thurston semi-norm. arXiv.org, May 2012. URL: https://arxiv.org/abs/1205.5118v2

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  9. [9]

    Tiling an arbitrary amenable group is decidable

    Benjamin Hellouin de Menibus. Tiling an arbitrary amenable group is decidable. private communi- cation, 2021

    work page 2021

  10. [10]

    Weak colored local rules for planar tilings

    Thomas Fernique and Mathieu Sablik. Weak colored local rules for planar tilings. arXiv:1603.09485 [cs, math], March 2016. URL: http://arxiv.org/abs/1603.09485

    work page arXiv 2016

  11. [11]

    Koryakov

    Yuri Gurevich and I. Koryakov. A remark on berger’s paper on the domino problem. Siberian Journal of Mathematics , 13:459–463, 1972

    work page 1972

  12. [12]

    G. A. Hedlund. Endomorphisms and automorphisms of the shift dynamical system. Math. Systems Theory, 3:320–375, 1969

    work page 1969

  13. [13]

    The Undecidability of the Domino Problem

    Emmanuel Jeandel and Pascal Vanier. The Undecidability of the Domino Problem. In Shigeki Akiyama and Pierre Arnoux, editors, Substitution and Tiling Dynamics: Introduction to Self-inducing Structures, Lecture Notes in Mathematics, page 66. Springer, 2017

    work page 2017

  14. [14]

    The nilpotency problem of one-dimensional cellular automata

    Jarkko Kari. The nilpotency problem of one-dimensional cellular automata. siam Journal on Computing, 21(3):571–586, 1992

    work page 1992

  15. [15]

    Logical aspects of Cayley-graphs: the group case

    Dietrich Kuske and Markus Lohrey. Logical aspects of Cayley-graphs: the group case. Annals of Pure and Applied Logic, 131(1-3):263–286, 2005. URL: http://linkinghub.elsevier.com/retrieve/ pii/S0168007204000831, doi:10.1016/j.apal.2004.06.002

    work page doi:10.1016/j.apal.2004.06.002 2005

  16. [16]

    C. G. Langton. Self-reproduction in cellular automata. Physica D, 10:135–144, 1984

    work page 1984

  17. [17]

    Lind and Brian Marcus

    Douglas A. Lind and Brian Marcus. An introduction to symbolic dynamics and coding . Cambridge University Press, Cambridge ; New York, 1995. 03085

    work page 1995

  18. [18]

    Lyndon and Paul E

    Roger C. Lyndon and Paul E. Schupp. Combinatorial Group Theory . Classics in Mathematics. Springer-Verlag, Berlin Heidelberg, 2001. 04184. URL: https://www.springer.com/gp/book/ 9783540411581

    work page 2001

  19. [19]

    Down with hierarchy !, 2013

    Thierry Monteil. Down with hierarchy !, 2013

    work page 2013

  20. [20]

    Geometry of defining relations in groups , volume 70

    A Yu Ol’shanskiI. Geometry of defining relations in groups , volume 70. Springer Science & Business Media, 2012

    work page 2012

  21. [21]

    Symbolic dynamics on free groups.Discrete & Continuous Dynamical Systems - A, 20(3):725–738, 2008

    Steven Piantadosi. Symbolic dynamics on free groups.Discrete & Continuous Dynamical Systems - A, 20(3):725–738, 2008. URL: http://aimsciences.org//article/doi/10.3934/dcds.2008.20.725, doi:10.3934/dcds.2008.20.725. 13

    work page doi:10.3934/dcds.2008.20.725 2008