Measure-Theoretically Mixing Subshifts of Minimal Word Complexity

Basic Information

• Paper ID: 2206.10047
• Title: Measure-Theoretically Mixing Subshifts of Minimal Word Complexity
• Author: Darren Creutz (Vanderbilt University)
• Classification: math.DS (Dynamical Systems)
• Publication Date: October 14, 2025
• Paper Link: https://arxiv.org/abs/2206.10047v5

Abstract

This paper resolves a long-standing open problem in the relationship between measure-theoretic dynamical complexity and symbolic complexity, determining the exact word complexity threshold at which measure-theoretic strong mixing occurs:

• For each superlinear function $f : \mathbb{N} \to \mathbb{N}$ (i.e., $f(q)/q \to \infty$), there exists a subshift admitting a (strong) mixing probability measure whose word complexity $p$ satisfies $p(q)/f(q) \to 0$.
• For subshifts with non-superlinear word complexity (i.e., $\liminf p(q)/q < \infty$), every ergodic probability measure is partially rigid.

Research Background and Motivation

Core Problem

The core problem investigated in this paper is: What is the precise relationship between measure-theoretic mixing properties and word complexity in symbolic dynamics?

Problem Significance

1. Theoretical Importance: This is a fundamental problem at the intersection of symbolic dynamics and ergodic theory, concerning the relationship between different measures of system complexity.
2. Long-Standing Open Problem: This question has remained open since Ferenczi's conjecture in 1995.
3. Complexity Theory: It reveals how word complexity precisely characterizes measure-theoretic properties in the zero-entropy setting.

Limitations of Existing Approaches

• Ferenczi initially conjectured that mixing transformations should have superpolynomial word complexity, but this was later refuted by his own counterexample.
• Adams proved that staircase transformations are mixing with quadratic word complexity.
• Previous work (including the author's collaboration with Pavlov and Rodock) could only construct examples between linear and quadratic complexity.

Research Motivation

To determine the precise boundary between mixing and non-mixing behavior, i.e., that superlinear word complexity is exactly the critical point at which measure-theoretic complex phenomena can occur.

Core Contributions

1. Determined the Exact Threshold for Mixing: Proved that superlinear word complexity is the exact critical condition for strong mixing to occur.
2. Constructed Quasi-Staircase Transformations: Introduced a new class of rank-one transformations capable of achieving word complexity arbitrarily close to linear.
3. Proved Optimality: Established a complete theory showing that non-superlinear complexity implies partial rigidity.
4. Revealed Structural Boundaries: Demonstrated a sharp transition from highly structured to highly complex behavior at the superlinear complexity threshold.

Methodology Details

Problem Formulation

Study the relationship between mixing properties of ergodic probability measures on subshifts $X \subset A^{\mathbb{Z}}$ and their word complexity function $p(q) = |L(X) \cap A^q|$.

Core Theorems

Theorem A: For each superlinear function $f: \mathbb{N} \to \mathbb{N}$, there exists a subshift admitting a strongly mixing probability measure whose word complexity $p$ satisfies $p(q)/f(q) \to 0$.

Theorem B: Every subshift with non-superlinear word complexity, equipped with an ergodic probability measure, is partially rigid.

Quasi-Staircase Transformation Construction

Definition

Given non-decreasing integer sequences $\{a_n\}$, $\{b_n\}$, $\{c_n\}$, a quasi-staircase transformation is a rank-one transformation with the following parameters:

• Cutting sequence: $r_n = a_n b_n$
• Spacer sequence: $s_{n,t} = c_n + \lfloor t/a_n \rfloor$ (for $0 \leq t < r_n$), $s_{n,r_n} = 0$

Symbolic Representation

• $B_1 = 0$
• $B_{n+1} = \left(\prod_{i=0}^{b_n-1} (B_n 1^{c_n+i})^{a_n}\right) B_n$

Height Sequence

$h_1 = 1$, $h_{n+1} = (a_n b_n + 1)h_n + a_n b_n c_n + \frac{1}{2}a_n b_n(b_n-1)$

Word Complexity Analysis

Characterization of Right-Special Words

Through detailed analysis of the right-special word structure of quasi-staircase transformations, a recursive relation for complexity is established:

$p(q) = 1 + q + \sum_{n=1}^{\infty} p_n(q)$

where $p_n(q)$ is the complexity contribution from the $n$-th level.

Complexity Upper Bound

Proposition 2.27: $p(q) \leq q\left(2 + \sum_{n=\rho(q)}^{\beta(q)} b_n\right)$

By carefully choosing parameter sequences, the complexity can be made arbitrarily close to linear.

Mixing Proof

Technical Innovations

1. Weighted Block Lemma: Generalizes the standard Blum-Hanson technique to the weighted case.
2. Previous Column Mixing: When $|y_n| \geq a_{n-1}\tilde{h}_{n-1}$, utilizes known mixing times of the previous tower.
3. Arithmetic Progression Structure: Handles "bad" times in the form of arithmetic progressions with controlled gaps.

Mixing Criterion

Theorem 4.1: Under appropriate convergence conditions, quasi-staircase transformations are mixing.

The proof is divided into several time intervals:

• $[a_n\tilde{h}_n, \tilde{h}_{n+1})$: Standard techniques
• $[\tilde{h}_n, b_n\tilde{h}_n)$: Weak power ergodicity
• $[b_n\tilde{h}_n, a_n\tilde{h}_n)$: Novel techniques for handling this case

Experimental Setup

Theoretical Verification

This is primarily a theoretical work, with main results verified through rigorous mathematical proofs.

Construction Examples

Theorem 3.3: For any function $f: \mathbb{N} \to \mathbb{N}$ satisfying $f(q) \to \infty$, there exists a quasi-staircase transformation whose complexity satisfies $p(q)/(qf(q)) \to 0$.

Construction method:

1. Set $d_n = \lfloor \sqrt[3]{f(n)} \rfloor$
2. Choose $b_n = \max(3, \sqrt[3]{f(n)})$
3. Set $a_n = 2n^2 + 2$

Experimental Results

Main Results

Positive Results (Theorem A)

Constructed mixing systems with word complexity arbitrarily close to linear:

• For any superlinear function $f$, there exists a mixing system with complexity $p$ satisfying $p(q)/f(q) \to 0$
• These systems are strongly mixing of all orders

Negative Results (Theorem B)

Proved restrictions on non-superlinear complexity:

• Every system with $\liminf p(q)/q < \infty$ is partially rigid
• Established a uniform rigidity constant $\delta_X > 0$

Technical Achievements

1. Optimality: Proved that superlinearity is the exact threshold for mixing
2. Constructivity: Provided explicit constructions of mixing systems
3. Completeness: Covered all possible complexity growth rates

Related Work

Historical Development

1. Ferenczi's Conjecture (1995): Initially conjectured that mixing requires superpolynomial complexity
2. Adams' Result (1998): Proved staircase transformations are mixing with quadratic complexity
3. CPR Work (2023): Constructed mixing examples with subquadratic but superlinear complexity

Related Theory

1. S-adic Systems: Equivalence between non-superlinear complexity systems and S-adic shifts
2. Cyr-Kra Results: Relationship between superlinear complexity and uncountable ergodic measures
3. Linear Complexity Structure: Known structural properties of linear complexity systems

Conclusions and Discussion

Main Conclusions

1. Exact Threshold: Superlinear word complexity is precisely the boundary for measure-theoretic strong mixing
2. Sharp Transition: A sudden transition from highly structured to highly complex behavior occurs at this threshold
3. Construction Method: Quasi-staircase transformations provide an effective method for achieving complexity arbitrarily close to linear

Theoretical Significance

• Completely resolves the long-standing open problem posed by Ferenczi
• Reveals deep connections between symbolic complexity and measure-theoretic properties
• Provides a new theoretical framework for studying zero-entropy dynamical systems

Limitations

1. Construction Complexity: The construction of quasi-staircase transformations involves complex parameter selection
2. Technical Requirements: The mixing proof requires multiple convergence conditions
3. Scope of Application: Primarily applicable to rank-one systems

Future Directions

1. Generalization to More General Systems: Study analogous problems for non-rank-one systems
2. Computational Complexity: Investigate algorithmic complexity of determining mixing
3. Application Exploration: Apply results to other dynamical systems problems

In-Depth Evaluation

Strengths

1. Complete Resolution of Important Problem: Thoroughly resolves a core open problem in the field
2. Significant Technical Innovation: Introduces multiple new proof techniques, particularly for handling "bad" times
3. Optimal Results: The established threshold is precise and cannot be further improved
4. Theoretical Depth: Reveals deep structural properties of complexity theory

Technical Contributions

1. Weighted Mixing Techniques: Generalizes classical mixing proof methods
2. Quasi-Staircase Construction: Provides a new class of rank-one transformations
3. Combinatorial Analysis: Refined analysis of word complexity

Shortcomings

1. Proof Complexity: Some technical proofs are relegated to appendices, affecting completeness
2. Multiple Parameter Conditions: Mixing requires multiple technical conditions
3. Limited Applications: Primarily limited to theoretical research with limited practical applications

Impact

1. Theoretical Contribution: Provides foundational results for symbolic dynamics and ergodic theory
2. Methodological Value: New proof techniques may be applicable to other problems
3. Completeness: Definitively resolves a fundamental problem with milestone significance

Applicable Scenarios

1. Symbolic Dynamics Research: Provides fundamental theoretical tools for the field
2. Complexity Theory: Offers new perspectives for understanding system complexity
3. Ergodic Theory: Provides new construction methods for mixing research

References

The paper cites key literature in the field, including:

• Ferenczi's pioneering work
• Adams' results on staircase transformations
• Cyr-Kra's work on counting ergodic measures
• The author's previous collaborative research with Pavlov and Rodock