On subshifts with low maximal pattern complexity

Anh N. Le; Casey Schlortt; Ronnie Pavlov

REVIEW 2 major objections 5 minor 1 cited by

On subshifts with low maximal pattern complexity

T0 review · 2 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every recurrent pattern Sturmian sequence is one of two known types, closing a 2002 classification question.

desk verdict Strong paper that likely answers the Kamae-Zamboni question, but the odometer half of Theorem A rests on an unjustified reduction in Proposition 5.4. read the letter →

arxiv 2508.13420 v1 pith:NXN3SF4P submitted 2025-08-19 math.DS

Anh N. Le , Ronnie Pavlov , Casey Schlortt This is my paper · ORCID

classification math.DS MSC 37B1037B05

keywords maximalpatterncomplexitySturmiansequencessymbolicdynamicsToeplitzsubshiftscirclerotationsequicontinuousfactornullsystemsodometers

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper closes a classification problem left open in 2002: it proves that every recurrent sequence of minimal maximal pattern complexity—those for which $p^*_x(n)=2n$ for every $n$, called pattern Sturmian—is either a coding of an irrational circle rotation by two intervals or a member of a nearly simple Toeplitz subshift. These were the two known families of examples, so the answer says there are no others. For nonrecurrent pattern Sturmian sequences the paper gives a near characterization: they are either nonrecurrent circle-rotation codings or almost constant sequences, with no other possibilities. The proof introduces a structural method, analyzing the boundary set of a partition of the maximal equicontinuous factor of the orbit closure, and yields a broader theorem about all recurrent sequences whose maximal pattern complexity grows at most linearly.

What carries the argument

The load-bearing object is the maximal equicontinuous factor (MEF) of the orbit closure $X$ of $x$: since pattern Sturmian subshifts are null, $X$ is an almost 1-1 extension of a group rotation, and Theorem 3.4 represents $x$ as the coding of the orbit of a point by a partition $G=U_0\cup U_1\cup B$ whose common boundary $B$ is finite when complexity is non-superlinear. The proof shows the size of $B$ controls $p^*_X$: if $|B|\ge k$ then $p^*_X(n)-kn$ is bounded below, so minimal growth $p^*=2n$ forces $|B|\le 2$. A structural argument limits the possible MEFs to a circle times a finite cyclic group or an odometer; in the circle case $B$ must have exactly two points, yielding circle-rotation codings, while in the odometer case a 3-window combinatorial lemma forces an MEF partition with $|B|=1$, which by the known characterization of pattern Sturmian 1-hole Toeplitz sequences yields the nearly simple Toeplitz conclusion.

What would settle it

Take a recurrent 2-hole Toeplitz sequence with period structure $(n_k)$ whose two nonconstant residue classes satisfy $j_k-i_k\neq n_k/2$ for some $k$, and compute its maximal pattern complexity at a suitable window: Proposition 5.4 predicts $p^*_x(3)\ge 7$, so exhibiting such a sequence with exactly six 3-letter patterns would refute the odometer half of the classification.

Watch

Extended reading notes

Core claim

The central claim is Theorem A: for $x\in\{0,1\}^{\mathbb{N}_0}$, if $x$ is recurrent then $x$ is pattern Sturmian if and only if $x$ is a recurrent simple circle rotation coding sequence or belongs to a nearly simple Toeplitz subshift. The converse directions were already known; the new content is that these exhaust the recurrent case. Theorem B says a nonrecurrent pattern Sturmian $x$ is either a nonrecurrent simple circle rotation coding sequence or almost constant, and Theorem C describes the larger class of recurrent non-superlinear complexity sequences as finite interleavings of circle-rotation codings sharing one irrational rotation, or as elements of $m$-hole Toeplitz subshifts. Theorem D adds that a recurrent sequence that is not uniformly recurrent must have $\liminf p^*_x(n)/(n\ln n)>0$, so within recurrent pattern Sturmian sequences uniform recurrence is automatic.

Load-bearing premise

In the odometer case, the proof assumes that when a 2-hole Toeplitz pattern Sturmian sequence's two one-hole subsequences have matching letter sequences, one can pass to a subsequence of periods that keeps the subsequences simple Toeplitz and makes the letters alternate; if that reduction fails, the argument that the boundary has size one rather than two breaks.

Editorial extensions

If this is right

Every recurrent pattern Sturmian sequence is uniformly recurrent; non-uniformly recurrent recurrent sequences have complexity at least of order $n\ln n$, so they cannot be pattern Sturmian.
The previously known families are exhaustive for recurrent sequences, so any future example must be a circle coding or a nearly simple Toeplitz sequence.
Nonrecurrent pattern Sturmian sequences are almost constant or circle codings; the only remaining open subproblem is which almost constant sequences qualify.
Combined with known spectral results, the classification leaves exactly one case to be settled for Schrödinger operators with pattern Sturmian potentials: the simple circle rotation coding sequences.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The boundary-counting mechanism suggests a template for larger alphabets: if minimal nonperiodic complexity for $r$-letter sequences is $rn$, the same MEF partition argument might classify those sequences, provided an analogue of the 3-window lemma exists.
Theorem D's $n\ln n$ lower bound gives a concrete target for the open question of recurrent null subshifts that are not uniformly recurrent: such a subshift, if it exists, must sit exactly in the window between linear and $n\ln n$ complexity.
The proof's dependence on dropping periods in the odometer case points to a possible simplification: a direct proof that period-dropping preserves the simple Toeplitz property would remove the need for the subsequence argument in Proposition 5.4.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

This paper is a serious piece of work. It answers Kamae and Zamboni's 2002 question on recurrent pattern Sturmian sequences, and it does so with a technique that is genuinely new: using the cardinality of the boundary of the MEF partition to control maximal pattern complexity. Theorem 4.1 is elegant, Theorem D (recurrent but not uniformly recurrent sequences have complexity growing at least like n log n) is a nice standalone result, and the nonrecurrent case (Theorem B) is handled well. The paper is clearly written and the overall architecture is coherent.

The soft spot is Proposition 5.4, which is the odometer half of Theorem A. In the |B|=2 case, the proof reduces to a contradiction by truncating the period structure and passing to a subsequence so that the two 1-hole Toeplitz sequences x' and x'' are simple and have the same alternating letter sequence. Neither reduction is proved. The first cites the proof of Theorem 2.13 in [14]; that may be true, but it is not a consequence of the theorem as stated, and the paper gives the reader no way to check it. The second, 'by passing to a subsequence ... that a_k = b_k for all k and alternates', does not follow. An arbitrary binary sequence has an alternating subsequence only if it is not eventually constant; nothing in the preceding argument rules out a_k eventually constant. Since the contradiction that forces j_k - i_k = n_k/2 and the final reduction to |B|=1 both rely on Lemma 5.3 and the alternating assumption, this gap is load-bearing. The Toeplitz half of Theorem A is not fully established as written.

I don't endorse every detail of the stress-test note: a cofinal subsequence of a period structure is still a period structure in the sense of Definition 2.12. But the main concern is real and needs to be addressed.

This gap is significant but looks fixable. The statements are probably true. It needs to be written out. Minor issues: a couple of typos (e.g., 'x,x' in the text of Prop 5.4) and the paper defers the technical condition in Theorem 2.13 to [14], which is acceptable but slows verification.

Who this is for: specialists in symbolic dynamics and low-complexity subshifts, and people working on Schrödinger operators with aperiodic potentials, since the classification enables the head-on approach the introduction describes. I'd send it to a serious referee, with instructions to focus on Proposition 5.4. It should be a reading-group candidate if you want to see the MEF boundary method in action.

Referee Report

2 major / 5 minor

Summary. This paper classifies recurrent binary sequences whose maximal pattern complexity attains the minimum possible growth p*_x(n)=2n. Theorem A states that a recurrent sequence is pattern Sturmian exactly when it is either a recurrent simple circle rotation coding sequence or a sequence in a nearly simple Toeplitz subshift, thereby answering Kamae and Zamboni's Problem 1. Theorem B gives a near characterization of nonrecurrent pattern Sturmian sequences as either nonrecurrent simple circle rotation codings or almost constant sequences. The technical engine is a structural result, Theorem C, showing that recurrent sequences with non-superlinear maximal pattern complexity generate minimal subshifts whose maximal equicontinuous factor is either a circle times a finite cyclic group or an odometer, together with Theorem D, which proves a lower bound for recurrent but not uniformly recurrent sequences. The circle case is handled in Proposition 5.2, and the odometer case is handled in Proposition 5.4 via Lemma 5.3.

Significance. If the proof can be completed, Theorems A and B would close a natural question from 2002 and would show that all previously known pattern Sturmian examples are exhaustive. The MEF-based approach is a genuine methodological innovation, and Theorem D is a new and independently useful complexity lower bound. The paper is careful to rely on external results only as stated, and several folklore facts are proved in-line, which is a strength. However, the odometer case in Proposition 5.4 contains an unproved and load-bearing reduction, and the definition of simple Toeplitz in Definition 2.12 is in tension with the way Lemma 5.3 uses alternating fill letters. These issues affect the Toeplitz half of Theorem A, so the current version is not yet publishable.

major comments (2)

[Proposition 5.4 (§5)] The reduction to simple Toeplitz subsequences is not proved. After forming x' and x'', the paper invokes 'the proof of Theorem 2.13 in [14]' to assert that the decomposition can be taken modulo the first period, and then says that 'by truncating the first term from (n_k)' one may assume x' and x'' are simple. This is precisely the step where a cofinal subsequence of a Toeplitz period structure can fail to be a 1-hole simple period structure: positions whose first covering level is skipped may become holes, or may split into several constant progressions, and Lemma 5.3 requires the same period structure for x' and x''. The later step 'by passing to a subsequence of (n_k) if necessary, that a_k=b_k for all k and alternates' has the same problem. Since the contradiction forcing j_k-i_k=n_k/2 and the final reduction to a 1-hole Toeplitz both rely on Lemma 5.3, this gap is load-bearing for the Toeplitz half of Theorem A. Please supply a complete proof, or restructure the argument so that no culling of periods is used.
[Definition 2.12 / Lemma 5.3 (§2.2.2, §5)] Definition 2.12 and Lemma 5.3 appear inconsistent under the literal wording of 'simple Toeplitz.' If a residue class r modulo n_k is constant with value a_k, then every subresidue r+t n_k modulo n_{k+1} is also constant with the same value; induction then forces a_k=a_{k+1}, so the choices in Lemma 5.3 with a_c=0 and a_d=1 for c<d are impossible. If the authors intend the fill letters a_k to be allowed to alternate, the definition must be reworded, for example by restricting 'constant progressions' to the progressions selected in the defining partition, and Lemma 5.3's indexing convention must be reconciled with that wording. As written, the proof of Lemma 5.3 relies on an interpretation of simple Toeplitz that is not stated in Definition 2.12.

minor comments (5)

[Definition 2.1-2.2] In Definition 2.2, the orbit closure is written identically to the orbit; please use an overline or another notation to distinguish Orb(x) from its closure.
[Theorem 3.1] The notation p_X^*(n) is used for subshifts, but p^* was defined only for sequences; please define p_X^*(n) explicitly.
[Definition 2.12] The formula for the number of holes at step k is hard to parse because the notation |{a_{j,i}}_i| is not defined clearly; please state it in terms of the number of distinct selected progressions at each level.
[Example 3.8] The phrase 'nonsimple 1-hole Toeplitz' may confuse readers because two constant progressions are listed at each level; please explain why the hole count is still one despite the multiple fill letters.
[Abstract and §2.1] The abstract writes x in A^N while the body consistently uses N0; please make the indexing conventions uniform.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the classification theorems are derived from external results, with only background self-citations.

full rationale

The derivation chain is self-contained relative to external theorems. Theorem A reduces recurrent pattern Sturmian sequences to the two known families via Theorem 2.13 ([14], Gjini et al., no author overlap) and structural MEF results (Theorem 3.3, Proposition 4.6, Proposition 5.2, Proposition 5.4). Theorem B uses Theorem A on the recurrent limit point and then proved lemmas (Propositions 6.3, 6.4, 6.6, 6.7). No parameter is fitted and then renamed as a prediction: pattern Sturmian is defined by the unconditional equality p*_x(n)=2n, and the properties 'simple circle rotation coding', 'nearly simple Toeplitz', and 'almost constant' are independent definitions. The only self-citations are [4,5] (Creutz–Pavlov) in the introduction as background about word-complexity thresholds; they are not used to justify any theorem in this paper. The reliance on [14] in Proposition 5.4 includes an unproved assertion about truncating period structures, but that is a potential correctness gap, not circularity: the cited result is external and the assertion does not define its target in terms of the paper's own outputs.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

Pure mathematics paper; no free parameters fitted to data and no invented physical entities. The axioms are standard external theorems from the symbolic dynamics and topological dynamics literature, plus the binary-alphabet convention stated in Section 2.1.

assumptions (5)

standard math Theorem 2.7 (Kamae-Zamboni): a non-eventually-periodic sequence x satisfies p*_x(n) >= 2n for all n.
Defines pattern Sturmian as the minimum-growth case; used in Lemma 2.10 and throughout.
standard math A {0,1}-subshift is null iff ln p*_X(n)/n -> 0 (Theorem 3.1, from Huang-Ye and Glasner-Megrelishvili).
Connects pattern Sturmian subshifts to nullness, enabling MEF theory.
standard math Every minimal null system is an almost 1-1 extension of its maximal equicontinuous factor (Theorem 3.3, from Huang-Li-Shao-Ye and Kerr-Li).
Basis for MEF partitions and Theorem 3.4/3.6 coding representations.
standard math Pattern Sturmian 1-hole Toeplitz sequences are exactly simple Toeplitz sequences or shifts of images under a constant-length morphism satisfying D((w?)^infinity,L)<=0 (Theorem 2.13, from Gjini-Kamae-Bo-Yu-Mei).
Used to conclude a 1-hole Toeplitz pattern Sturmian subshift is nearly simple Toeplitz.
standard math A torus of dimension >=2 or a solenoidal space cannot be partitioned into two nonempty open sets and a countable set (Lemma 4.4, using path-connectedness and path components of solenoids from McCord).
Crucial for Proposition 4.6, which restricts possible MEFs to circle times finite cyclic group or odometer.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On subshifts with low maximal pattern complexity." pith.science (2026). https://pith.science/paper/NXN3SF4P

@misc{pith2026250813420,
  author       = {Pith},
  title        = {Pith review of: On subshifts with low maximal pattern complexity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NXN3SF4P}},
  note         = {Machine review of arXiv:2508.13420}
}

abstract

For a finite alphabet $\mathcal{A}$ and a sequence $x \in \mathcal{A}^{\mathbb{N}}$, Kamae and Zamboni defined the maximal pattern complexity function $p^*_x(n)$ as a natural generalization of usual word complexity. They defined a nonperiodic sequence $x$ to be pattern Sturmian if it achieves the minimal growth rate $p^*_x(n) = 2n$, and asked the question of whether one could classify recurrent pattern Sturmian sequences. We answer their question by characterizing recurrent pattern Sturmian sequences as one of two known types: either a coding of an irrational circle rotation by two intervals, or an element of what we call a nearly simple Toeplitz subshift. We also show that nonrecurrent pattern Sturmian sequences are either very close to constant (such examples were given by Kamae and Zamboni) or a (nonrecurrent) coding of an irrational circle rotation by two intervals. Our main new technique is to use topological properties of the maximal equicontinuous factor (MEF) of the subshift generated by $x$. In this way, we prove a general structural result about sequences with non-superlinear maximal pattern complexity: they are either nonrecurrent or minimal with MEF either an odometer or the product of a circle with a finite cyclic group.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

Maximal pattern complexity and structure of null systems
math.DS 2026-08 accept novelty 8.0 of 10

Nullness is equivalent to polynomial maximal pattern complexity, equicontinuity to bounded pattern complexity, and transitive nonminimal null systems exist with prescribed rigidity and scattering properties.

Reference graph

Works this paper leans on

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

[14]

Gjini, T

N. Gjini, T. Kamae, T. Bo, and X. Yu-Mei. Maximal pattern complexity for Toeplitz words. Ergodic Theory Dynam. Systems , 26(4):1073–1086, 2006

work page 2006
[1]

Auslander

J. Auslander. Minimal flows and their extensions , volume 153 of North-Holland Mathematics Studies . North-Holland Publishing Co., Amsterdam, 1988. Notas de Matem´ atica [Mathematical Notes], 122

work page 1988
[2]

Barge and J

M. Barge and J. Kellendonk. Proximality and pure point spectrum for tiling dynamical systems. Michigan Math. J., 62(4):793–822, 2013

work page 2013
[3]

Bellissard, B

J. Bellissard, B. Iochum, E. Scoppola, and D. Testard. Spectral properties of one-dimensional quasi- crystals. Comm. Math. Phys. , 125(3):527–543, 1989

work page 1989
[4]

On minimal subshifts of linear word complexity with slope less than 3/2

D. Creutz and R. Pavlov. On minimal subshifts of linear word complexity with slope less than 3/2. arXiv:2308.14901

work page Pith review arXiv
[5]

Creutz and R

D. Creutz and R. Pavlov. Low complexity subshifts have discrete spectrum. Forum Math. Sigma, 11:Paper No. e96, 22, 2023

work page 2023
[6]

Cyr and B

V. Cyr and B. Kra. The automorphism group of a shift of linear growth: beyond transitivity. Forum Math. Sigma, 3:Paper No. e5, 27, 2015

work page 2015
[7]

Cyr and B

V. Cyr and B. Kra. Counting generic measures for a subshift of linear growth. J. Eur. Math. Soc. (JEMS) , 21(2):355–380, 2019

work page 2019

Show all 26 references

[8]

Damanik, R

D. Damanik, R. Killip, and D. Lenz. Uniform spectral properties of one-dimensional quasicrystals. III. α-continuity. Comm. Math. Phys. , 212(1):191–204, 2000

2000
[9]

Damanik, Q.-H

D. Damanik, Q.-H. Liu, and Y.-H. Qu. Spectral properties of Schr¨ odinger operators with pattern Sturmian potentials. arXiv:1511.03834

arXiv
[10]

Donoso, F

S. Donoso, F. Durand, A. Maass, and S. Petite. On automorphism groups of low complexity subshifts. Ergodic Theory Dynam. Systems , 36(1):64–95, 2016

2016
[11]

Donoso, F

S. Donoso, F. Durand, A. Maass, and S. Petite. Interplay between finite topological rank minimal Cantor systems,S-adic subshifts and their complexity. Trans. Amer. Math. Soc., 374(5):3453–3489, 2021

2021
[12]

Downarowicz

T. Downarowicz. Survey of odometers and Toeplitz flows. In Algebraic and topological dynamics, volume 385 of Contemp. Math., pages 7–37. Amer. Math. Soc., Providence, RI, 2005

2005
[13]

N. P. Fogg. Substitutions in dynamics, arithmetics and combinatorics , volume 1794 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 2002

2002
[15]

Glasner and M

E. Glasner and M. Megrelishvili. More on tame dynamical systems. In Ergodic theory and dynamical systems in their interactions with arithmetics and combinatorics , volume 2213 of Lecture Notes in Math. , pages 351–392. Springer, Cham, 2018

2018
[16]

T. N. T. Goodman. Topological sequence entropy. Proc. London Math. Soc. (3) , 29:331–350, 1974

1974
[17]

Huang, S

W. Huang, S. M. Li, S. Shao, and X. D. Ye. Null systems and sequence entropy pairs. Ergodic Theory Dynam. Systems, 23(5):1505–1523, 2003

2003
[18]

Huang and X

W. Huang and X. Ye. Combinatorial lemmas and applications to dynamics. Adv. Math., 220(6):1689–1716, 2009

2009
[19]

Kamae and L

T. Kamae and L. Zamboni. Maximal pattern complexity for discrete systems. Ergodic Theory Dynam. Systems, 22(4):1201–1214, 2002

2002
[20]

Kamae and L

T. Kamae and L. Zamboni. Sequence entropy and the maximal pattern complexity of infinite words. Ergodic Theory Dynam. Systems , 22(4):1191–1199, 2002

2002
[21]

Kerr and H

D. Kerr and H. Li. Independence in topological and C∗-dynamics. Math. Ann., 338(4):869–926, 2007

2007
[22]

A. G. Kuˇ snirenko. Metric invariants of entropy type.Uspehi Mat. Nauk , 22(5(137)):57–65, 1967

1967
[23]

Liu and Y.-H

Q.-H. Liu and Y.-H. Qu. Uniform convergence of Schr¨ odinger cocycles over simple Toeplitz subshift.Ann. Henri Poincar´ e, 12(1):153–172, 2011

2011
[24]

M. C. McCord. Inverse limit sequences with covering maps. Trans. Amer. Math. Soc., 114:197–209, 1965

1965
[25]

Morse and G

M. Morse and G. A. Hedlund. Symbolic Dynamics. Amer. J. Math. , 60(4):815–866, 1938

1938
[26]

Peter and H

F. Peter and H. Weyl. Die Vollst¨ andigkeit der primitiven Darstellungen einer geschlossenen kontinuier- lichen Gruppe. Math. Ann., 97(1):737–755, 1927. 28 ANH N. LE, RONNIE PA VLOV, AND CASEY SCHLORTT Anh N. Le, Department of Mathematics, University of Denver, 2390 S. York St...

1927

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [14]

Gjini, T

N. Gjini, T. Kamae, T. Bo, and X. Yu-Mei. Maximal pattern complexity for Toeplitz words. Ergodic Theory Dynam. Systems , 26(4):1073–1086, 2006

work page 2006

[2] [1]

Auslander

J. Auslander. Minimal flows and their extensions , volume 153 of North-Holland Mathematics Studies . North-Holland Publishing Co., Amsterdam, 1988. Notas de Matem´ atica [Mathematical Notes], 122

work page 1988

[3] [2]

Barge and J

M. Barge and J. Kellendonk. Proximality and pure point spectrum for tiling dynamical systems. Michigan Math. J., 62(4):793–822, 2013

work page 2013

[4] [3]

Bellissard, B

J. Bellissard, B. Iochum, E. Scoppola, and D. Testard. Spectral properties of one-dimensional quasi- crystals. Comm. Math. Phys. , 125(3):527–543, 1989

work page 1989

[5] [4]

On minimal subshifts of linear word complexity with slope less than 3/2

D. Creutz and R. Pavlov. On minimal subshifts of linear word complexity with slope less than 3/2. arXiv:2308.14901

work page Pith review arXiv

[6] [5]

Creutz and R

D. Creutz and R. Pavlov. Low complexity subshifts have discrete spectrum. Forum Math. Sigma, 11:Paper No. e96, 22, 2023

work page 2023

[7] [6]

Cyr and B

V. Cyr and B. Kra. The automorphism group of a shift of linear growth: beyond transitivity. Forum Math. Sigma, 3:Paper No. e5, 27, 2015

work page 2015

[8] [7]

Cyr and B

V. Cyr and B. Kra. Counting generic measures for a subshift of linear growth. J. Eur. Math. Soc. (JEMS) , 21(2):355–380, 2019

work page 2019