pith. sign in

arxiv: 2606.25005 · v1 · pith:RK7BEAHXnew · submitted 2026-06-23 · 🧮 math.DS

Matching Rules for Substitution and Hierarchical Tilings for any Substitution with Finite Local Complexity

Nikolay Vereshchagin This is my paper

Pith reviewed 2026-06-25 21:49 UTC · model grok-4.3

classification 🧮 math.DS
keywords substitution tilingsfinite local complexitymatching rulessofic tilingshierarchical tilingsGoodman-Strauss theoremtiling dynamics
0
0 comments X

The pith

For any substitution with finite local complexity, its tilings and hierarchical tilings can be defined by local matching rules on decorated tiles.

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

This paper establishes a simplified version of the Goodman-Strauss theorem for substitution tilings. It shows that whenever a substitution has finite local complexity—meaning only finitely many distinct local patterns appear in its supertiles—the family of all substitution tilings becomes sofic. Sofic means the tilings can be characterized exactly by a finite set of local matching rules after decorating the tiles with additional information. The result also extends to the larger family of hierarchical tilings, which are those that admit infinite descent under the substitution. A reader cares because this covers all known substitution examples with a single, easy-to-check condition instead of the original theorem's more involved requirements.

Core claim

The paper proves that if a substitution has finite local complexity, then there exist decorations of the tiles and local matching rules such that the tilings satisfying those rules are exactly the substitution tilings. The same holds for the hierarchical tilings associated to the substitution, which include but are not limited to the substitution tilings themselves.

What carries the argument

Finite local complexity of the substitution, which bounds the number of distinct crowns in supertiles to a finite set and enables explicit construction of the matching rules and decorations.

If this is right

  • All substitution tilings can be enforced by checking only local conditions on decorated tiles.
  • Hierarchical tilings, defined by repeated infinite composability under the substitution, also admit exact local definitions.
  • The matching rules apply uniformly to every known substitution tiling.
  • The rules can be constructed directly from the finite list of crowns that appear in supertiles.

Where Pith is reading between the lines

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

  • The result may allow algorithmic enumeration of all valid tilings for any FLC substitution by running a local-rule checker.
  • It suggests examining the boundary case of substitutions whose crown sets grow without bound but still slowly, to test where the local-rule property breaks.
  • Connections to symbolic dynamics could transfer the construction to produce shifts of finite type whose factors recover the tiling spaces.

Load-bearing premise

That finite local complexity of the substitution is sufficient to guarantee the existence of the required tile decorations and matching rules via the paper's construction method.

What would settle it

A concrete substitution with only finitely many distinct crowns in its supertiles for which no finite set of local matching rules on any decoration can exactly capture the substitution tilings.

Figures

Figures reproduced from arXiv: 2606.25005 by Nikolay Vereshchagin.

Figure 1
Figure 1. Figure 1: First substitution [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Second substitution. The first prototile can be rotated by 90, 180, and 270 degrees. [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The figure shows a substitution and supertiles of order 1, 2 and 3. [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The central part of a macrotile consisting of triangular tiles. The large quasi-square [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Ports and paths in a macrotile. The ports are colored green. Paths connecting the [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The central type 1 is acyclic, and the central type 2 is cyclic. [PITH_FULL_IMAGE:figures/full_fig_p018_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: On the left is a proper tiling M ∈ σ ′′D with π(M) = σ ′α and with the central tile A. On the right is the legal parent C of B and a decomposition of C. The type of C and the parent indices in its decomposition and in the tiling M are denoted by t. Let us show that this tile D is normal. Let indD(i, d) be a local index of D. By construc￾tion, indD(i, d) = indB(3, b) where b is the ith port on the macroside… view at source ↗
Figure 8
Figure 8. Figure 8: Tiles C, D, A have types r, t, s, respectively, where r is a non-central type and t is a central acyclic type. The macrotile M′ is a decomposition of C, and the macrotile M is a decomposition of D. The figure illustrates the proof that D is legal. Thus tile A has a legal parent A1 of type t and a normal parent D also of type t. We claim that A1 = D and hence D is legal. By construction, on every marked sid… view at source ↗
Figure 9
Figure 9. Figure 9: Red indices on the north side of a τ 2 -macrotile, where τ is the substitution of our first example (a square is substituted with a 3 by 3 grid). 3.8 Proof of Theorem 1(b) Let τ denote the given substitution. Construct the tile set P ′ and the substitution σ ′ = ∆−1 τ m∆ as before. Then we define P ′′ and σ ′′ along the same lines as before. But this time we make a small modification: • First we remove the… view at source ↗
Figure 10
Figure 10. Figure 10: The set S is in grey. 5 Acknowledgments The author is sincerely grateful to Thomas Fernique for explaining the Fernique — Ollinger technique in detail, to Nikita Andrusov, Andrei Romashchenko and Alexander Shen for listening to several previous versions of the results, and to all participants of the Kolmogorov seminar at Moscow State University for attention and patience. A Appendix Proof of Lemma 3. (a) … view at source ↗
Figure 11
Figure 11. Figure 11: An incomplete crown K at V . The angle ang(K) is the union of the angles of the tiles of K at V , and sec(K, r) = disc(V, r) ∩ ang(K) is the shaded sector. Let A be any tile intersecting S, say in point C, and let D be any point from S \ A. Consider the segment [C, D]. At some point E that segment leaves the tile A. W.l.o.g. assume that S is convex and hence E ∈ S. Since E ∈ S and the diameter of S is les… view at source ↗
Figure 12
Figure 12. Figure 12: Solving the first problem (the supertile [PITH_FULL_IMAGE:figures/full_fig_p032_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Solving the second problem: E and F lie on the two supersides θ j [Ai−1Ai ] and θ j [AiAi+1] meeting at the reflex vertex V0 = θ jAi , both at distance > d/2 from V0. The chord EF crosses the exterior wedge of angle µ, so |EF| > 2(d/2) sin(µ/2). Therefore, to solve the first problem it suffices to make d ≤ min(ν, λ, γ sin µ). Then R ∩ disc(V, d) ⊂ ang(K). Recall that in the second case we had S ⊂ disc(V, … view at source ↗
read the original abstract

The Goodman-Strauss theorem states that for ``almost every'' substitution $\tau$, the family of substitution tilings is sofic, that is, it can be defined by local matching rules for some decoration of tiles. The conditions on the substitution that guarantee the soficity are quite complicated in the statement of the theorem. In this paper we propose a version of the Goodman-Strauss theorem with very simple conditions on the substitution: the family of substitution tilings must have finite local complexity (FLC), that is, the number of crowns that appear in $\tau$-supertiles is finite. Like the original theorem, our theorem provides matching rules for all known substitution tilings. We also prove a similar theorem for the family of \emph{hierarchical} tilings associated with the given substitution. A tiling is called $\tau$-hierarchical if it has a composition under $\tau$, such that this composition also has a composition, and so on, infinitely many times. Every substitution tiling is hierarchical, but the converse is not always true.

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 / 0 minor

Summary. The paper presents a simplified version of the Goodman-Strauss theorem: for any substitution with finite local complexity (FLC, i.e., finitely many distinct crowns in supertiles), the family of substitution tilings is sofic and can be realized by local matching rules after a suitable finite decoration of the tiles. A parallel result is claimed for the associated family of hierarchical tilings (those admitting infinite iterated compositions under the substitution).

Significance. If the central implication holds, the result replaces the complicated hypotheses of the original Goodman-Strauss theorem with the single, readily checkable condition of FLC, while still covering all known substitution examples. The extension to hierarchical tilings is a natural strengthening that clarifies the relationship between substitution and hierarchical families.

major comments (1)
  1. [Abstract] Abstract: the theorem is asserted under the FLC hypothesis, yet the abstract (and the provided statement) supplies no proof outline, key construction steps, or verification that the finite-crown assumption produces a finite decoration whose local rules exactly recover the substitution and hierarchical families. Without these details the central claim cannot be assessed for correctness.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review and recommendation. We respond to the major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the theorem is asserted under the FLC hypothesis, yet the abstract (and the provided statement) supplies no proof outline, key construction steps, or verification that the finite-crown assumption produces a finite decoration whose local rules exactly recover the substitution and hierarchical families. Without these details the central claim cannot be assessed for correctness.

    Authors: Abstracts are conventionally concise and omit detailed proof outlines; the full construction and verification appear in the body of the manuscript (Sections 3–5), where finite crowns under FLC are used to produce a finite decoration, local rules are defined to enforce supertile compatibility, and it is proved that the resulting sofic shift exactly recovers both the substitution tilings and the hierarchical tilings. To address the concern that the abstract itself does not convey these steps, we will revise the abstract to include a brief outline of the key construction. revision: yes

Circularity Check

0 steps flagged

No circularity; theorem is a direct implication from explicit FLC hypothesis

full rationale

The paper states a theorem that any substitution with finite local complexity (FLC, i.e., finitely many distinct crowns in supertiles) yields a sofic family of substitution tilings and hierarchical tilings via local matching rules on a finite decoration. This is presented as a simplification of the Goodman-Strauss theorem (cited as prior independent work) under the single FLC assumption, with no parameter fitting, self-definitional loops, or load-bearing self-citations. The derivation chain constructs the rules from the FLC property without reducing the conclusion to the inputs by construction or renaming known results. The result is self-contained against the stated hypothesis.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

No free parameters, invented entities, or ad-hoc axioms are introduced; the result is a theorem about existing notions of substitution and hierarchical tilings under the finite-local-complexity condition.

axioms (1)
  • standard math Standard axioms and definitions of substitution tilings, finite local complexity, and soficity in topological dynamics
    The paper operates entirely within established mathematical framework for tilings.

pith-pipeline@v0.9.1-grok · 5712 in / 1154 out tokens · 38337 ms · 2026-06-25T21:49:35.361000+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

7 extracted references · 1 linked inside Pith

  1. [1]

    Chaim Goodman-Strauss, Matching rules and substitution tilings, Ann. of Math. 147 (1998) 181–223

    1998

  2. [2]

    F.; Rivier, N

    Chaim Goodman-Strauss, Aperiodic Hierarchical Tilings, in Sadoc, J. F.; Rivier, N. (eds.), Foams and Emulsions, Dordrecht: Springer, pp. 481–496 (1999)

    1999

  3. [3]

    Branko Gr¨ unbaum, Geoffrey Colin Shephard, Tilings and Patterns, New York: W. H. Freeman (1987)

    1987

  4. [4]

    Analyze Math

    Shahar Mozes, Tilings, substitution systems and dynamical systems generated by them, J. Analyze Math. 53 (1989) 139–186

    1989

  5. [5]

    Combinatorial substitutions and sofic tilings

    Thomas Fernique, Nicolas Ollinger. Combinatorial substitutions and sofic tilings. arXiv:1009.5167 (2010)

    Pith/arXiv arXiv 2010

  6. [6]

    Nikolay Vereshchagin, Aperiodic Tilings by Right Triangles. Proc. of DCFS 2014, Lecture Notes in Computer Science (LNCS, volume 8614), pp. 29–41 (2014)

    2014

  7. [7]

    arXiv:2510.02842 (2025) 34

    Nikolay Vereshchagin, Goodman-Strauss theorem revisited. arXiv:2510.02842 (2025) 34

    arXiv 2025