On the complexity function for sequences which are not uniformly recurrent

Nic Ormes; Ronnie Pavlov

arxiv: 1907.06626 · v1 · pith:WLBJJHIOnew · submitted 2019-07-15 · 🧮 math.DS

On the complexity function for sequences which are not uniformly recurrent

Nic Ormes , Ronnie Pavlov This is my paper

Pith reviewed 2026-05-24 21:11 UTC · model grok-4.3

classification 🧮 math.DS

keywords subshiftcomplexity functiontransitiveminimalunique ergodicityaperiodicitysymbolic dynamics

0 comments

The pith

Every non-minimal transitive subshift with mild aperiodicity satisfies limsup c_n(X) - 1.5n = infinity.

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

The paper proves that non-minimal transitive subshifts satisfying a mild aperiodicity condition have their complexity function c_n growing such that the limsup of c_n minus 1.5 times n equals infinity. This establishes that the excess number of distinct blocks of length n over the 1.5n line becomes arbitrarily large at infinitely many scales. A family of examples demonstrates that no larger constant than 1.5 works in general. The result yields a corollary that any transitive system whose complexity exceeds n infinitely often yet stays within a bounded gap of 1.5n must in fact be minimal. Additional structural constraints on non-minimal transitive systems with liminf c_n minus 2n equal to negative infinity imply unique ergodicity with respect to a periodic invariant measure.

Core claim

Every non-minimal transitive subshift X satisfying a mild aperiodicity condition satisfies limsup c_n(X) - 1.5n = ∞. A class of examples shows that the threshold of 1.5n cannot be increased. As a corollary, any transitive X satisfying limsup c_n(X) - n = ∞ and limsup c_n(X) - 1.5n < ∞ must be minimal. Transitive non-minimal X satisfying liminf c_n(X) - 2n = -∞ have structural restrictions that imply unique ergodicity for a periodic measure.

What carries the argument

The complexity function c_n(X), counting distinct words of length n appearing in the subshift X, together with the growth condition limsup c_n(X) - 1.5n = ∞.

If this is right

The constant 1.5 is optimal, as shown by explicit constructions of non-minimal transitive subshifts.
Transitive subshifts whose complexity exceeds n infinitely often but remains bounded relative to 1.5n are necessarily minimal.
Non-minimal transitive systems with liminf c_n - 2n = -∞ obey structural restrictions that force unique ergodicity with a periodic measure.
The unique ergodicity conclusion extends the corresponding statement known for minimal systems.

Where Pith is reading between the lines

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

Complexity growth rates may serve as a practical test for minimality in symbolic systems constructed from concrete rules.
The boundary cases between linear and superlinear complexity could classify additional dynamical properties beyond ergodicity.
Similar limsup thresholds might be derived for other combinatorial invariants such as the number of periodic points.

Load-bearing premise

The subshift must satisfy the mild aperiodicity condition for the limsup growth statement to hold.

What would settle it

A single non-minimal transitive subshift obeying the aperiodicity condition for which limsup c_n(X) - 1.5n stays finite would disprove the main claim.

read the original abstract

We prove that every non-minimal transitive subshift $X$ satisfying a mild aperiodicity condition satisfies $\limsup c_n(X) - 1.5n = \infty$, and give a class of examples which shows that the threshold of $1.5n$ cannot be increased. As a corollary, we show that any transitive $X$ satisfying $\limsup c_n(X) - n = \infty$ and $\limsup c_n(X) - 1.5n < \infty$ must be minimal. We also prove some restrictions on the structure of transitive non-minimal $X$ satisfying $\liminf c_n(X) - 2n = -\infty$, which imply unique ergodicity (for a periodic measure) as a corollary, which extends a result of Boshernitzan from the minimal case to the more general transitive case.

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.

Desk Editor's Note private letter to a colleague

The paper pins down a sharp 1.5n threshold on complexity that separates minimal from non-minimal transitive subshifts and extends Boshernitzan's ergodicity result.

read the letter

The main point is that every non-minimal transitive subshift meeting a mild aperiodicity condition has limsup(c_n(X) - 1.5n) = infinity, with examples showing the 1.5 cannot be raised. A quick corollary then forces minimality when limsup(c_n - n) = infinity but limsup(c_n - 1.5n) stays finite, and the same setup extends Boshernitzan's unique ergodicity result to the transitive case for a periodic measure. The 1.5n threshold and the transitive extension look new relative to the cited minimal-system work. The construction builds enough distinct words from non-minimality plus transitivity, with the aperiodicity condition keeping the count above the line; the examples hit the bound without breaking the condition, which gives the sharpness claim real weight. The proofs rest on explicit word-counting rather than circular reductions, and the stress-test finds no inconsistency in the liminf restrictions or the ergodicity corollary. The aperiodicity condition is weaker than minimality or uniform recurrence, so the result applies more broadly than earlier statements. The only real question is how often that condition holds in examples people actually care about, but the paper states it clearly and the logic does not depend on it being trivial. This is aimed at people working on subshift complexity and ergodic properties in symbolic dynamics. Anyone tracking Boshernitzan-type results or growth thresholds that force minimality will get direct use from the extensions. It deserves a serious referee because the claims are concrete, the examples back the bound, and the derivations check out on the available details.

Referee Report

0 major / 2 minor

Summary. The paper proves that every non-minimal transitive subshift X satisfying a mild aperiodicity condition has limsup (c_n(X) - 1.5n) = ∞. It constructs examples showing that 1.5 cannot be replaced by any larger constant. As a corollary, any transitive X with limsup (c_n(X) - n) = ∞ and limsup (c_n(X) - 1.5n) < ∞ must be minimal. It also establishes structural restrictions on transitive non-minimal X with liminf (c_n(X) - 2n) = -∞ that imply unique ergodicity with respect to a periodic measure, extending Boshernitzan's result from the minimal case.

Significance. If the central claims hold, the work sharpens the distinction between minimal and non-minimal transitive subshifts via complexity growth rates and provides a concrete threshold (1.5n) that is both sufficient for a minimality conclusion and optimal. The extension of unique ergodicity to the transitive setting is a direct strengthening of prior results. The explicit examples demonstrating sharpness constitute a falsifiable contribution that can be checked independently.

minor comments (2)

[Introduction] The precise statement of the mild aperiodicity condition should be recalled in the introduction (currently referenced only as 'mild' without a forward pointer to its definition).
[Section 2] Notation for the complexity function c_n(X) is introduced without an explicit reminder that it counts distinct factors of length n; a one-sentence definition would aid readers from adjacent areas.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript and for recommending acceptance. The referee's summary correctly identifies the central results on the complexity threshold for non-minimal transitive subshifts, the sharpness examples, the minimality corollary, and the extension of Boshernitzan's unique ergodicity result to the transitive setting.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper establishes its main result via explicit combinatorial constructions from non-minimality and transitivity, together with a separately defined mild aperiodicity condition that is independent of the target limsup statement. The sharpness examples are built directly rather than fitted, and the corollaries on unique ergodicity and liminf restrictions follow from the same arguments without reducing to self-citation chains or definitional loops. No load-bearing step equates a prediction to its input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Paper operates inside standard symbolic dynamics; no free parameters, new entities, or ad-hoc axioms are visible in the abstract.

axioms (1)

standard math Standard definitions and basic properties of subshifts, transitivity, minimality, and the complexity function c_n in topological dynamics.
The statements presuppose the usual framework of symbolic dynamical systems over finite alphabets.

pith-pipeline@v0.9.0 · 5672 in / 1205 out tokens · 23588 ms · 2026-05-24T21:11:02.285227+00:00 · methodology

On the complexity function for sequences which are not uniformly recurrent

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)