pith. sign in

arxiv: 2512.10499 · v2 · pith:NKEAI7JFnew · submitted 2025-12-11 · 🧮 math.DS · cs.DM

A Three-Dimensional SFT with Sparse Columns

Ville Salo , Ilkka T\"orm\"a This is my paper

Pith reviewed 2026-05-21 17:25 UTC · model grok-4.3

classification 🧮 math.DS cs.DM
keywords subshift of finite typethree-dimensionalsparse columnsZ-tracedeterminismpartial cellular automatonWang cubes
0
0 comments X

The pith

A nontrivial three-dimensional subshift of finite type can have a two-sparse Z-trace.

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

The paper constructs a three-dimensional subshift of finite type that remains nontrivial even though its projection onto any vertical line contains at most two nonzero symbols. This Z-trace is deterministic, so the entire system is topologically conjugate to the spacetime diagrams of a partial cellular automaton. The authors also give versions of the construction that use Wang cubes and that restrict the alphabet to two symbols. The result shows that a strong sparsity constraint along one axis can coexist with nontrivial global behavior in three-dimensional symbolic dynamics.

Core claim

We construct a nontrivial three-dimensional subshift of finite type whose projective Z-subdynamics, or Z-trace, is 2-sparse, meaning that there are at most two nonzero symbols in any vertical column. The subshift is deterministic in the direction of the subdynamics, so it is topologically conjugate to the set of spacetime diagrams of a partial cellular automaton. We also present a variant of the subshift that is defined by Wang cubes, and one whose alphabet is binary.

What carries the argument

Local forbidden patterns that simultaneously enforce at most two nonzero symbols per vertical column and unique determination of each symbol from those below it.

If this is right

  • The system is conjugate to the spacetime diagrams of a partial cellular automaton acting on two-symbol columns.
  • Wang-cube and binary-alphabet versions show the same sparsity and determinism properties hold under stricter presentations.
  • The Z-projection being 2-sparse separates the vertical dynamics from the horizontal ones without collapsing the subshift to a single point.
  • Such constructions separate the property of having a sparse trace from the property of being trivial in higher-dimensional SFTs.

Where Pith is reading between the lines

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

  • Similar local-rule techniques might produce examples with other fixed sparsity levels or with aperiodicity in the horizontal plane.
  • The deterministic sparse trace could serve as a model for studying limited-activity symbolic systems in three dimensions.
  • The existence result raises the question of which other projection or trace properties remain compatible with nontrivial three-dimensional SFTs.

Load-bearing premise

Local rules can force both column sparsity and vertical determinism while still allowing infinitely many distinct global configurations.

What would settle it

An explicit list of the forbidden patterns together with a concrete configuration that satisfies all rules, contains exactly two nonzero symbols in some columns, and is not periodic in the horizontal directions.

Figures

Figures reproduced from arXiv: 2512.10499 by Ilkka T\"orm\"a, Ville Salo.

Figure 1
Figure 1. Figure 1: A rendering of a fluctuating surface. Definition 1. A mat is a triple (A,(Cs)s∈[a,b] ,(Ss,i)s∈[a,b],i∈Is ) where the fol￾lowing conditions hold for some a, b, c, d, x, y ∈ R. • A ⊂ R 3 is a compact set with πH(A) = [a, b] × [c, d] and A = S s∈[a,b] Cs. • Each Cs is a compact subset of {s} × [c, d] × R with Cs = S i∈Is Ss,i. • For each S = Ss,i there exists a continuous function f = fS : R → R with f(c) = x… view at source ↗
Figure 2
Figure 2. Figure 2: Typical positions of Bi , Bj , and Bk, viewed from (0, 0,∞) and (0, −∞, 0). The black dot marks the same possible origin in both figures, and the hatched area marks the intersection in the rightmost figure, which gives the final contradiction. Not drawn to scale, and the ϵ-perturbation of the mats is not shown. 10 [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Mat structures for which Lemma 3 does not hold. [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Representation of sloped tiles by cubes. The south-north axis is [PITH_FULL_IMAGE:figures/full_fig_p016_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The three clusters and the surface inside a spine (shown for difference [PITH_FULL_IMAGE:figures/full_fig_p024_5.png] view at source ↗
read the original abstract

We construct a nontrivial three-dimensional subshift of finite type whose projective $\Z$-subdynamics, or $\Z$-trace, is 2-sparse, meaning that there are at most two nonzero symbols in any vertical column. The subshift is deterministic in the direction of the subdynamics, so it is topologically conjugate to the set of spacetime diagrams of a partial cellular automaton. We also present a variant of the subshift that is defined by Wang cubes, and one whose alphabet is binary.

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 manuscript constructs a nontrivial three-dimensional subshift of finite type (SFT) on a finite alphabet such that its projective Z-subdynamics (Z-trace) is 2-sparse: every vertical column contains at most two nonzero symbols. The SFT is deterministic along the Z-direction and is topologically conjugate to the spacetime diagrams of a partial cellular automaton. The paper also gives a Wang-cube presentation of the same SFT and a variant whose alphabet is binary.

Significance. If the local rules are correctly verified, the construction supplies an explicit, finite-alphabet example of a 3-D SFT in which a global cardinality constraint is enforced by local matching rules while preserving determinism in one coordinate. This is useful for studying the boundary between local and global constraints in multidimensional shifts and for reducing questions about 3-D SFTs to questions about 2-D partial cellular automata. The binary-alphabet and Wang-cube variants further strengthen the result by showing that the phenomenon does not require a large alphabet.

major comments (2)
  1. [§3.1] §3.1, transition table for the sparsity counter: the forward update rules (0-seen → 1-seen on first nonzero, 1-seen → 2-seen on second nonzero) are stated, but the manuscript must explicitly confirm that the same finite set of symbols and forbidden patterns also forbids any configuration containing a third nonzero arbitrarily far in the negative-Z direction. Without a backward-deterministic closure argument or an exhaustive check of all admissible 2×2×2 windows that straddle the “2-seen” state, the global 2-sparsity claim remains unverified.
  2. [§4.2] §4.2, proof that the SFT is nonempty: the existence argument relies on an inductive construction of finite-height cylinders that respect the counter states. The induction step must be checked against the specific forbidden patterns listed in Table 1; if any cylinder of height greater than 3 can be extended downward only by introducing a third nonzero, the claimed nonempty 2-sparse SFT would be empty.
minor comments (2)
  1. [§2] Notation for the alphabet symbols is introduced in §2 but reused without redefinition in the Wang-cube section; a single consolidated table would improve readability.
  2. [Figure 3] Figure 3 (spacetime diagram) has overlapping labels on the vertical axis; the two allowed nonzero positions should be marked with distinct colors or symbols for clarity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments on the manuscript. We address each major comment below and will revise the paper to incorporate the requested verifications.

read point-by-point responses

  1. Referee: [§3.1] §3.1, transition table for the sparsity counter: the forward update rules (0-seen → 1-seen on first nonzero, 1-seen → 2-seen on second nonzero) are stated, but the manuscript must explicitly confirm that the same finite set of symbols and forbidden patterns also forbids any configuration containing a third nonzero arbitrarily far in the negative-Z direction. Without a backward-deterministic closure argument or an exhaustive check of all admissible 2×2×2 windows that straddle the “2-seen” state, the global 2-sparsity claim remains unverified.

    Authors: We agree that an explicit verification of the backward direction is needed to rigorously establish global 2-sparsity. In the revised manuscript we will add an exhaustive enumeration of all admissible 2×2×2 windows containing the '2-seen' state. This enumeration will show that none of these windows permits a third nonzero symbol in the negative-Z direction. We will also include a short argument establishing that the set of allowed local patterns is closed under the backward-deterministic extension required by the counter rules. revision: yes

  2. Referee: [§4.2] §4.2, proof that the SFT is nonempty: the existence argument relies on an inductive construction of finite-height cylinders that respect the counter states. The induction step must be checked against the specific forbidden patterns listed in Table 1; if any cylinder of height greater than 3 can be extended downward only by introducing a third nonzero, the claimed nonempty 2-sparse SFT would be empty.

    Authors: We acknowledge that the induction in §4.2 requires an explicit check against the forbidden patterns of Table 1. The construction ensures that every valid finite-height cylinder admits a downward extension that respects the counter state without introducing a third nonzero. In the revision we will augment the proof with a case-by-case verification for cylinders of height greater than 3, confirming that each forbidden pattern in Table 1 is avoided by at least one admissible downward extension. This will complete the nonemptiness argument. revision: yes

Circularity Check

0 steps flagged

Explicit construction of 3D SFT with enforced 2-sparsity

full rationale

The paper presents a direct construction of a three-dimensional SFT by defining a finite alphabet and a set of local forbidden patterns (or Wang cubes) that simultaneously enforce determinism along the Z-direction and the global 2-sparsity constraint on vertical columns. This is achieved through explicit state tracking within the symbols themselves, without any fitted parameters, self-referential equations, or load-bearing self-citations that reduce the central claim to its own inputs. The nonempty property and conjugacy to partial CA diagrams follow from verifying that the chosen rules close all finite windows consistently, which is a standard constructive argument in symbolic dynamics and remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on the standard definition of subshifts of finite type together with the existence of suitable local rules that simultaneously enforce sparsity, nontriviality, and determinism.

axioms (2)
  • standard math Standard axioms of symbolic dynamics on Z^3: configurations are functions from Z^3 to a finite alphabet that avoid a finite set of forbidden patterns.
    Invoked implicitly when the paper states that the object is a subshift of finite type.
  • domain assumption There exist finite local rules whose global solutions project to exactly 2-sparse columns and are deterministic in the Z-direction.
    This is the load-bearing premise of the construction; its verification requires the explicit rules.

pith-pipeline@v0.9.0 · 5599 in / 1215 out tokens · 103267 ms · 2026-05-21T17:25:48.529230+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

18 extracted references · 18 canonical work pages

  1. [1]

    The domino problem for self-similar structures

    Sebasti´ an Barbieri and Mathieu Sablik. The domino problem for self-similar structures. InConference on Computability in Europe, pages 205–214. Springer, 2016

    work page 2016

  2. [2]

    Sofic trace subshift of a cellular automaton

    Julien Cervelle, Enrico Formenti, and Pierre Guillon. Sofic trace subshift of a cellular automaton. InComputation and logic in the real world, volume 4497 ofLecture Notes in Comput. Sci., pages 152–161. Springer, Berlin, 2007

    work page 2007

  3. [3]

    NonexpansiveZ 2-subdynamics and Nivat’s con- jecture.Trans

    Van Cyr and Bryna Kra. NonexpansiveZ 2-subdynamics and Nivat’s con- jecture.Trans. Amer. Math. Soc., 367(9):6487–6537, 2015

    work page 2015

  4. [4]

    Decidable properties for regular cellular automata

    Pietro Di Lena. Decidable properties for regular cellular automata. In Gonzalo Navarro, Leopoldo Bertossi, and Yoshiharu Kohayakawa, editors, Fourth IFIP International Conference on Theoretical Computer Science- TCS 2006, pages 185–196, Boston, MA, 2006. Springer US

    work page 2006

  5. [5]

    Fixed-point tile sets and their applications.J

    Bruno Durand, Andrei Romashchenko, and Alexander Shen. Fixed-point tile sets and their applications.J. Comput. System Sci., 78(3):731–764, 2012

    work page 2012

  6. [6]

    Reliable cellular automata with self-organization.J

    Peter G´ acs. Reliable cellular automata with self-organization.J. Statist. Phys., 103(1-2):45–267, 2001

    work page 2001

  7. [7]

    Nilpotency and limit sets of cellular automata

    Pierre Guillon and Ga´ etan Richard. Nilpotency and limit sets of cellular automata. InMathematical foundations of computer science 2008, volume 5162 ofLecture Notes in Comput. Sci., pages 375–386. Springer, Berlin, 2008

    work page 2008

  8. [8]

    Non-expansive directions forZ 2 actions.Ergodic Theory Dynam

    Michael Hochman. Non-expansive directions forZ 2 actions.Ergodic Theory Dynam. Systems, 31(1):91–112, 2011

    work page 2011

  9. [9]

    Projectional entropy in higher dimensional shifts of finite type.Complex Systems, 17(3):243–257, 2007

    Aimee Johnson, Steve Kass, and Kathleen Madden. Projectional entropy in higher dimensional shifts of finite type.Complex Systems, 17(3):243–257, 2007

    work page 2007

  10. [10]

    Languages, equicontinuity and attractors in cellular automata

    Petr K˚ urka. Languages, equicontinuity and attractors in cellular automata. Ergodic Theory Dynam. Systems, 17(2):417–433, 1997. 28

    work page 1997

  11. [11]

    Tilings, substitution systems and dynamical systems gen- erated by them.J

    Shahar Mozes. Tilings, substitution systems and dynamical systems gen- erated by them.J. Analyse Math., 53:139–186, 1989

    work page 1989

  12. [12]

    A class of nonsofic multidimensional shift spaces.Proc

    Ronnie Pavlov. A class of nonsofic multidimensional shift spaces.Proc. Amer. Math. Soc., 141(3):987–996, 2013

    work page 2013

  13. [13]

    Classification of sofic projective subdynamics of multidimensional shifts of finite type.Transactions of the American Mathematical Society, 367(5):3371–3421, 2015

    Ronnie Pavlov and Michael Schraudner. Classification of sofic projective subdynamics of multidimensional shifts of finite type.Transactions of the American Mathematical Society, 367(5):3371–3421, 2015

    work page 2015

  14. [14]

    On nilpotency and asymptotic nilpotency of cellular automata

    Ville Salo. On nilpotency and asymptotic nilpotency of cellular automata. In Enrico Formenti, editor,Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journ´ ees Automates Cellulaires, pages 86–96. Open Publishing Association, 2012

    work page 2012

  15. [15]

    Strict asymptotic nilpotency in cellular automata

    Ville Salo. Strict asymptotic nilpotency in cellular automata. InCellular automata and discrete complex systems, volume 10248 ofLecture Notes in Comput. Sci., pages 3–15. Springer, Cham, 2017

    work page 2017

  16. [16]

    Subshifts with sparse traces.Studia Mathematica, 255:159–207, 2020

    Ville Salo. Subshifts with sparse traces.Studia Mathematica, 255:159–207, 2020

    work page 2020

  17. [17]

    Nilpotent endomorphisms of expansive group actions.International Journal of Algebra and Computation, 31(03):393– 452, 2021

    Ville Salo and Ilkka T¨ orm¨ a. Nilpotent endomorphisms of expansive group actions.International Journal of Algebra and Computation, 31(03):393– 452, 2021

    work page 2021

  18. [18]

    Schraudner

    Michael H. Schraudner. One-dimensional projective subdynamics of uni- formly mixingZ d shifts of finite type.Ergodic Theory Dynam. Systems, 35(6):1962–1999, 2015. 29

    work page 1962