pith. sign in

arxiv: 2605.02226 · v1 · submitted 2026-05-04 · 🧮 math.PR · math.DS

Finitely Dependent Processes on Subshifts

Nishant Chandgotia , Aditya Thorat This is my paper

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

classification 🧮 math.PR math.DS
keywords finitely dependent processessubshiftsheight functionscohomologytilingsZ^2symbolic dynamicsmixing properties
0
0 comments X

The pith

Conway-Lagarias-Thurston height functions characterize exactly when finitely dependent processes exist on the subshift of box tilings of Z^2.

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

The paper shows that stationary finitely dependent processes are dense among those supported on subshifts that satisfy strong mixing conditions such as the finite extension property. At the same time, the cohomology of a subshift can block the existence of any such process. For the concrete case of tilings of the plane by rectangles, the authors use Conway-Lagarias-Thurston height functions to compute the relevant cohomology and thereby decide precisely which tiling subshifts admit a finitely dependent process. This supplies a complete answer to the dimension-two case of a tiling problem raised by Gao, Jackson, Krohne and Seward. The same height-function technique and a related rigidity result for cocycles apply to several other combinatorial models, including graph homomorphisms and ribbon tilings.

Core claim

On the space of tilings by boxes of Z^2, a stationary finitely dependent process exists if and only if the cohomology of the subshift, computed via Conway-Lagarias-Thurston height functions, satisfies the appropriate vanishing condition; when the cohomology is nontrivial the process is obstructed, answering the two-dimensional tiling problem posed by Gao, Jackson, Krohne and Seward.

What carries the argument

Conway-Lagarias-Thurston height functions, which assign integer heights to tilings so that the resulting cohomology class detects whether finite dependence is possible.

If this is right

  • A dense set of stationary finitely dependent processes exists on any subshift with the finite extension property.
  • Continuous cocycles on strongly irreducible subshifts taking values in torsion-free Gromov hyperbolic groups or free products of cyclic groups must be perturbations of group homomorphisms.
  • The same obstruction technique applies directly to graph homomorphisms and ribbon tilings.
  • Finite dependence fails exactly when the height-function cohomology is nontrivial for box tilings of the plane.

Where Pith is reading between the lines

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

  • The density result suggests that, for most mixing combinatorial models, one can sample finitely dependent configurations by perturbing a deterministic tiling or coloring in a local way.
  • Similar height or cohomology obstructions may classify possible short-range random processes on higher-dimensional or non-rectangular tiling spaces.
  • The cocycle rigidity statement links the probabilistic question to algebraic rigidity phenomena already studied in geometric group theory.

Load-bearing premise

The subshifts possess strong mixing properties such as the finite extension property or strong irreducibility, and the cohomology of the tiling space is correctly captured by the standard height functions.

What would settle it

Constructing a stationary finitely dependent process on a rectangular-tiling subshift whose height-function cohomology is known to be nontrivial, or proving that none exists on a subshift whose cohomology vanishes, would falsify the claimed characterization.

Figures

Figures reproduced from arXiv: 2605.02226 by Aditya Thorat, Nishant Chandgotia.

Figure 1
Figure 1. Figure 1: A pattern of domino tilings and corresponding perfect matching and P := { view at source ↗
Figure 2
Figure 2. Figure 2: Some ribbon tiles of order 4 A map Ψ from X ⊂ AG to Y ⊂ BG is equivariant if Ψ(g · x) = g ·Φ(x) for all g ∈ G and x ∈ X. Definition 2.13. A map Ψ from a subshift X ⊂ AG to a subshift Y ⊂ BG is called a sliding block code, if there exists a finite set F and a map ψ : L(X, F) → B such that Ψ(x)g = ψ(x|g.F ) for all x ∈ X and g ∈ G. The sliding block code is called a factor if it is surjective. We will refer … view at source ↗
Figure 3
Figure 3. Figure 3: Domino tilings are not strongly irreducible Consider the pattern on the left-hand side of the view at source ↗
Figure 4
Figure 4. Figure 4: The cocycle for the 2 × 1 and 1 × 3 boxes takes values in the group ⟨h, v|h 2 , v3 ⟩ henceforth. Here is a quick application of the cocycle introduced above. Lemma 2.26. If a box R in R 2 can be tiled by {R1, R2} where R1 is a m ×1 box and R2 is a 1×n box, then either R can be tiled by R1 or R can be tiled by R2. Proof. Let l and b be horizontal and vertical sidelengths of R. Since R can be tiled by {R1, R… view at source ↗
Figure 5
Figure 5. Figure 5: A pattern of ribbon tiling We first define a function crib : X(ribbon, n) × Z 2 → Z n (whose values will be referred to as ‘heights’ ) by specifying height changes across edges. To this end, let ei,i+1, i = 0, 1, · · · , n − 1 denote the standard basis elements of Z n (the choice of notation will become clear soon ). We say that an edge in Z 2 has the type (i, i + 1), if it lies at the intersection of squa… view at source ↗
Figure 6
Figure 6. Figure 6: A schematic representation (not up to scale) of coloring Zv for r = 1. The dotted boxes are Voronoi cells. All points in a same colored polygons have same color label. Proof of 1): We first show that the r-components of the sets Wi = Z −1 (i) are finite a.s. Suppose on the contrary that v1, v2, · · · is an infinite sequence of elements such that Zvj = i and ||vj − vj+1||∞ ≤ r. Then B(v1, ri) intersects i V… view at source ↗
Figure 9
Figure 9. Figure 9: a2 view at source ↗
read the original abstract

The existence of stationary finitely dependent processes on combinatorial models like $\mathbb Z^d$ subshifts can be quite mysterious. For instance, Holroyd and Liggett constructed such processes on proper $4$-colorings of $\mathbb Z^d$ for all $d$ while Holroyd, Schramm and Wilson showed that there are no such processes on proper $3$-colorings of $\mathbb Z^d$ for $d>1$. In this paper, we take inspiration from these results and investigate them further. On the positive side, we show that there exists a dense set of stationary finitely dependent processes supported on subshifts with strong mixing properties like the finite extension property. On the negative side, we see that the cohomology of the subshifts can form an obstruction to the existence of such processes. In particular we use Conway-Lagarias-Thurston height functions to characterise when there exists a finitely dependent process on the space of tilings by boxes of $\mathbb Z^2$ answering the tiling problem posed by Gao, Jackson, Krohne and Seward in dimension $2$. The ideas also apply to many other models, such as graph homomorphisms and ribbon tilings. On the way, we also show that continuous cocycles on strongly irreducible subshifts valued in a special class of groups (including torsion free Gromov hyperbolic groups and free product of cyclic groups) are perturbations of group homomorphisms.

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 manuscript investigates existence of stationary finitely dependent processes on subshifts. It proves that such processes form a dense set among stationary processes on subshifts with the finite extension property (or strong irreducibility). It further shows that continuous cocycles on strongly irreducible subshifts with values in torsion-free Gromov hyperbolic groups or free products of cyclic groups are perturbations of homomorphisms. Using Conway-Lagarias-Thurston height functions, the paper characterizes precisely when finitely dependent processes exist on the subshift of box tilings of Z^2, thereby answering the tiling problem of Gao, Jackson, Krohne and Seward in dimension 2. The ideas extend to graph homomorphisms and ribbon tilings.

Significance. If the results hold, the work provides a cohomological obstruction to finite dependence that explains phenomena such as the contrast between 3- and 4-colorings of Z^d, extending Holroyd-Liggett and Holroyd-Schramm-Wilson. The density theorem gives a general positive existence result under mixing hypotheses. The cocycle perturbation theorem is a technical contribution of independent value in symbolic dynamics. The resolution of the two-dimensional box-tiling question is a concrete advance.

major comments (1)
  1. [characterization for box tilings] The section characterizing existence for box tilings of Z^2: the positive direction (trivial height function implies existence of a finitely dependent process) is asserted to follow from the cocycle perturbation result, but the perturbation controls only the cocycle; it is not shown how this produces a process that remains supported on the tiling subshift while satisfying finite dependence. The negative direction (non-trivial cohomology obstructs) is clearer, but the positive direction requires an explicit construction or additional argument.
minor comments (2)
  1. The topology with respect to which the set of finitely dependent processes is dense should be stated explicitly (e.g., weak topology on measures or a metric on the space of processes).
  2. Notation for the height functions, cocycles, and the precise class of groups could be introduced in a preliminary section to improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thorough review, positive assessment of the significance of the results, and for identifying the need for greater clarity in one aspect of the box-tiling characterization. We address the major comment below.

read point-by-point responses

  1. Referee: The section characterizing existence for box tilings of Z^2: the positive direction (trivial height function implies existence of a finitely dependent process) is asserted to follow from the cocycle perturbation result, but the perturbation controls only the cocycle; it is not shown how this produces a process that remains supported on the tiling subshift while satisfying finite dependence. The negative direction (non-trivial cohomology obstructs) is clearer, but the positive direction requires an explicit construction or additional argument.

    Authors: We agree that the positive direction in the characterization would benefit from a more explicit argument. The manuscript currently asserts that the result follows from the cocycle perturbation theorem but does not spell out the steps connecting the perturbed cocycle to a finitely dependent process that remains supported on the subshift. In the revised manuscript we will add a dedicated paragraph (or short subsection) providing this explicit construction, showing how a homomorphism close to the cocycle yields a stationary process with the required support and finite-dependence properties. revision: yes

Circularity Check

0 steps flagged

No significant circularity; results rely on external Conway-Lagarias-Thurston height functions and a new independent cocycle perturbation theorem

full rationale

The paper's derivation chain is self-contained against external benchmarks. It invokes Conway-Lagarias-Thurston height functions (prior literature) to characterize existence of finitely dependent processes on Z^2 box tilings, and proves a new result that continuous cocycles on strongly irreducible subshifts into torsion-free Gromov hyperbolic groups (and free products of cyclics) are perturbations of homomorphisms. This supports both the negative obstruction (non-trivial cohomology blocks processes) and positive existence claims without reducing any central claim to a self-definition, fitted input renamed as prediction, or load-bearing self-citation chain. No equations or steps equate outputs to inputs by construction; the work answers an external open problem (Gao-Jackson-Krohne-Seward) using independent tools.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Abstract only; the paper relies on standard background from symbolic dynamics and tiling theory rather than introducing new free parameters or entities.

axioms (2)
  • domain assumption Subshifts possess the finite extension property or strong irreducibility
    Invoked to guarantee the dense existence of finitely dependent processes.
  • standard math Conway-Lagarias-Thurston height functions correctly capture the cohomology of box tilings
    Standard tool from tiling theory used for the characterization in dimension 2.

pith-pipeline@v0.9.0 · 5544 in / 1328 out tokens · 72965 ms · 2026-05-08T19:04:57.385876+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

15 extracted references · 4 canonical work pages · 2 internal anchors

  1. [1]

    [ABnC+21] Noga Alon, Raimundo Brice˜ no, Nishant Chandgotia, Alexander Magazinov, and Yinon Spinka, Mixing properties of colourings of the Zd lattice, Combin. Probab. Comput. 30 (2021), no. 3, 360–373. [ACRd+24] Amirreza Akbari, Xavier Coiteux-Roy, Francesco d’Amore, Fran¸ cois Le Gall, Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai, Marc-Ol...

    2021

  2. [2]

    [AGK92] Jon Aaronson, David Gilat, and Michael Keane, On the structure of 1-dependent Markov chains , J. Theoret. Probab. 5 (1992), no. 3, 545–561. [AGKdV89] Jon Aaronson, David Gilat, Michael Keane, and Vincent de Valk, An algebraic construction of a class of one-dependent processes, Ann. Probab. 17 (1989), no. 1, 128–143. [Ber66] Robert Berger, The unde...

    1992

  3. [3]

    Sci., vol

    [Ber88] Anne Bertrand, Specification, synchronisation, average length , Coding theory and applications (Cachan, 1986), Lecture Notes in Comput. Sci., vol. 311, Springer, Berlin, 1988, pp. 86–95. [Ber23] Anton Bernshteyn, Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms, Adv. Math. 415 (2023), Paper No. 108895,

    1986

  4. [4]

    Burton, Marc Goulet, and Ronald Meester, On 1-dependent processes and k-block factors, Ann

    [BGM93] Robert M. Burton, Marc Goulet, and Ronald Meester, On 1-dependent processes and k-block factors, Ann. Probab. 21 (1993), no. 4, 2157–2168. [BH99] Martin R. Bridson and Andr´ e Haefliger, Metric spaces of non-positive curvature , Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 319, Springer- Ver...

    1993

  5. [5]

    [Bn18] Raimundo Brice˜ no, The topological strong spatial mixing property and new conditions for pressure approximation, Ergodic Theory Dynam

    [BM25] Robert Bland and Kevin Mcgoff, Homomorphisms from aperiodic subshifts to subshifts with the finite extension property, Ergodic Theory and Dynamical Systems (2025), 1–17. [Bn18] Raimundo Brice˜ no, The topological strong spatial mixing property and new conditions for pressure approximation, Ergodic Theory Dynam. Systems 38 (2018), no. 5, 1658–1696. ...

    work page arXiv 2025

  6. [6]

    66 NISHANT CHANDGOTIA AND ADITYA THORAT [CGdMO25b] , Undecidability of the block gluing classes of homshifts , Preprint, arXiv:2507.21342 [math.DS] (2025),

    work page internal anchor Pith review arXiv 2025

  7. [7]

    Systems 37 (2017), no

    [Cha17] Nishant Chandgotia, Four-cycle free graphs, height functions, the pivot property and entropy minimal- ity, Ergodic Theory Dynam. Systems 37 (2017), no. 4, 1102–1132. [CHM+14] Nishant Chandgotia, Guangyue Han, Brian Marcus, Tom Meyerovitch, and Ronnie Pavlov, One- dimensional Markov random fields, Markov chains and topological Markov fields , Proc....

    2017

  8. [8]

    [GR23] Jan Greb´ ık and V´ aclav Rozhoˇ n, Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics , Adv. Math. 431 (2023), Paper No. 109241,

    2023

  9. [9]

    Holroyd, Tom Hutchcroft, and Avi Levy, Mallows permutations and finite dependence , Ann

    [HHL20] Alexander E. Holroyd, Tom Hutchcroft, and Avi Levy, Mallows permutations and finite dependence , Ann. Probab. 48 (2020), no. 1, 343–379. [HL16] Alexander E. Holroyd and Thomas M. Liggett, Finitely dependent coloring, Forum Math. Pi 4 (2016), e9,

    2020

  10. [10]

    [Hoc24] Michael Hochman, Irreducibility and periodicity in Z2 symbolic systems, Preprint, arXiv:2401.02273,

    work page arXiv

  11. [11]

    Holroyd, Symmetrization for finitely dependent colouring , Electron

    [Hol24] Alexander E. Holroyd, Symmetrization for finitely dependent colouring , Electron. Commun. Probab. 29 (2024), Paper No. 44,

    2024

  12. [12]

    Holroyd, Oded Schramm, and David B

    MR 4806804 [HSW17] Alexander E. Holroyd, Oded Schramm, and David B. Wilson, Finitary coloring , Ann. Probab. 45 (2017), no. 5, 2867–2898. [Jun10] Uijin Jung, On the existence of open and bi-continuing codes , Transactions of the American Mathe- matical Society 363 (2010), no. 3, 1399–1417. FINITELY DEPENDENT PROCESSES ON SUBSHIFTS 67 [KK92] Claire Kenyon ...

    2017

  13. [13]

    Ram´ ırez Alfons´ ın, A tiling problem and the Frobenius number , Additive number theory, Springer, New York, 2010, pp

    [LRA10] Denis Labrousse and Jorge L. Ram´ ırez Alfons´ ın, A tiling problem and the Frobenius number , Additive number theory, Springer, New York, 2010, pp. 203–220. [Mar80] Brian Marcus, A note on periodic points for ergodic toral automorphisms , Monatsh. Math. 89 (1980), 121–129. [MKS04] Wilhelm Magnus, Abraham Karrass, and Donald Solitar, Combinatorial...

    2010

  14. [14]

    Contractible subshifts

    [OW87] Donald S. Ornstein and Benjamin Weiss, Entropy and isomorphism theorems for actions of amenable groups, J. Analyse Math. 48 (1987), 1–141. [Pav16] Ronnie Pavlov, On intrinsic ergodicity and weakenings of the specification property , Adv. Math. 295 (2016), 250–270. [PS24] Leo Poirier and Ville Salo, Contractible subshifts, Preprint, arXiv:2401.16774,

    work page internal anchor Pith review Pith/arXiv arXiv 1987

  15. [15]

    Discrete Math

    [R´02] Eric R´ emila, On the structure of some spaces of tilings , SIAM J. Discrete Math. 16 (2002), no. 1, 1–19. [Sch95] Klaus Schmidt, The cohomology of higher-dimensional shifts of finite type, Pacific J. Math. 170 (1995), no. 1, 237–269. [She02] Scott Sheffield, Ribbon tilings and multidimensional height functions , Trans. Amer. Math. Soc. 354 (2002),...

    2002