Low complexity binary words avoiding $(5/2)^+$-powers

Basic Information

• Paper ID: 2506.19050
• Title: Low complexity binary words avoiding $(5/2)^+$-powers
• Authors: James Currie, Narad Rampersad
• Categories: math.CO (Combinatorics), cs.FL (Formal Languages)
• Publication Date: October 13, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2506.19050

Abstract

Rote sequences are infinite sequences containing exactly $2n$ factors of length $n$ for each $n \geq 1$. Shallit and Shur, as well as Ollinger and Shallit, proved the existence of Rote sequences avoiding $(5/2)^+$-powers, which is optimal. This paper provides a structural theorem for Rote sequences avoiding $(5/2)^+$-powers, confirming a conjecture of Ollinger and Shallit.

Research Background and Motivation

Core Problem

This research addresses two fundamental concepts in combinatorial word theory: power avoidance and factor complexity. Specifically, it aims to characterize all binary infinite sequences avoiding $(5/2)^+$-powers with minimal complexity ($2n$).

Problem Significance

1. Theoretical importance: Power avoidance and factor complexity are foundational concepts in combinatorial word theory, and their interrelationship is a central research direction in the field
2. Structural theory: Similar to the classical Restivo-Salemi structural theorem for overlap-free sequences, this research establishes new structural theorems
3. Conjecture verification: Confirms an important conjecture by Ollinger and Shallit regarding the structure of Rote sequences

Limitations of Existing Research

• Although Shallit and Shur, and Ollinger and Shallit proved the existence and optimality of Rote sequences avoiding $(5/2)^+$-powers, a complete structural characterization was lacking
• Existing work provided only concrete construction examples without general structural theorems

Research Motivation

To establish a complete structural theorem, analogous to the Restivo-Salemi theorem's characterization of overlap-free binary sequences, providing theoretical foundations for understanding power avoidance properties of low-complexity sequences.

Core Contributions

1. Introduced the concepts of proper and antiproper sequences: Defined two important subclasses of ternary sequences
2. Established the first structural theorem: Characterized the recursive structure of proper and antiproper sequences
3. Proved the second structural theorem: Completely characterized the structure of Rote sequences avoiding $(5/2)^+$-powers
4. Verified the Ollinger-Shallit conjecture: Provided complete structural characterization involving morphisms $f$ and $g$
5. Provided computational verification: Verified the correctness of key lemmas through backtracking search

Detailed Methodology

Task Definition

Input: Binary infinite sequence $w$Constraints:

1. $w$ is a Rote sequence (factor complexity equals $2n$)
2. $w$ avoids $(5/2)^+$-powers

Output: Structural characterization of $w$, i.e., proving that $w$ can be expressed as morphisms acting on proper or antiproper sequences

Key Definitions

Proper and Antiproper Sequences

For ternary sequences $u \in \Sigma_3^*$, define the Parikh vector $\pi(u) = [|u|_0, |u|_1, |u|_2]$.

Proper sequences satisfy:

1. Do not contain factor $xyxyx$ where $\pi(x) > \pi(y)$
2. Do not contain factors: $00, 11, 22, 20, 10101, 2121, 10210210$

Antiproper sequences: Their reversal is a proper sequence

Key Morphisms

Define morphisms $f: \Sigma_3^* \to \Sigma_3^*$ and $h: \Sigma_3^* \to \Sigma_3^*$:

• $f(0) = 0121$, $f(1) = 021$, $f(2) = 01$
• $h(0) = 1210$, $h(1) = 120$, $h(2) = 10$

Define morphism $g: \Sigma_3^* \to \Sigma_2^*$:

• $g(0) = 011$, $g(1) = 0$, $g(2) = 01$

Core Technical Methods

1. Factor Analysis Method

Through detailed analysis of length-4 factors that must be contained in binary sequences avoiding $(5/2)^+$-powers, the fundamental structural constraints of such sequences were determined.

Key Lemmas:

• Lemma 1: Any infinite binary sequence avoiding $(5/2)^+$-powers must contain factors $0110$ and $1001$
• Lemma 3: Sequences with factor complexity $\leq 2n$ avoiding $(5/2)^+$-powers must contain factors $0011$ and $1100$

2. Backtracking Search Verification

Computer programs implementing backtracking search algorithms verified key lemmas through constructive proofs, determining the necessity of constraint conditions.

3. Recursive Structure Analysis

Proved that proper and antiproper sequences possess self-similar recursive structures that can be characterized through morphisms $f$ and $h$.

Experimental Setup

Computational Verification Method

The paper implements a backtracking search algorithm in Python to verify key lemmas:

def fhpf(w): # Check if sequence w avoids 5/2+ powers
    p=1
    while (5*p<2*len(w)):
        if (w[(-(p+1)//2)-p:]==w[(-(p+1)//2)-2*p:-p]):
            return(False)
        p=p+1
    return(True)

Verification Contents

1. Lemma 1 verification: The longest sequence not containing $0110$ and avoiding $(5/2)^+$-powers has length 14
2. Lemma 2 verification: Verified that at least 3 elements from set $C = \{0010, 0100, 1011, 1101\}$ must appear
3. Lemma 3 verification: Detailed verification for each element in set $A$
4. Lemma 4 verification: Verified constraint conditions for 17 specific sequences of length 9

Experimental Results

Main Results

Theorem 1 (First Structural Theorem)

1. For proper sequence $u \in \Sigma_3^{\omega}$, some suffix has the form $f(v)$ where $v$ is a proper sequence
2. For antiproper sequence $u \in \Sigma_3^{\omega}$, some suffix has the form $h(v)$ where $v$ is an antiproper sequence

Theorem 2 (Second Structural Theorem)

Rote sequences avoiding $(5/2)^+$-powers fall into four cases with length-4 factor sets:

1. $F = \{0110, 1001, 0011, 1100, 0010, 0100, 1101, 1010\}$
2. $\bar{F}$ (complement of $F$)
3. $F^R$ (reversal of $F$)
4. $\overline{F^R}$ (complement of reversal of $F$)

In each case, some suffix of $w$ can be expressed as $g(f^n(u))$ or $g(h^n(u))$ where $u$ is a proper sequence.

Computational Verification Results

• Longest $(5/2)^+$-power-avoiding sequence not containing $0110$: length 14
• Longest sequence not containing two elements from $C$: length 44
• Longest sequence not containing $0011$ and some element from $A$: length 31
• Maximum sequence lengths under various constraints fall within expected ranges

Related Work

Classical Results

1. Restivo-Salemi Theorem: Characterizes the structure of overlap-free binary sequences using the Thue-Morse morphism
2. Sturmian Sequence Theory: Fibonacci sequences avoid $(5+\sqrt{5})/2$-powers, which is optimal among Sturmian sequences

Recent Progress

1. Shallit-Shur Work: Established the research framework for relationships between power avoidance and factor complexity
2. Ollinger-Shallit Work: Constructed concrete examples of Rote sequences avoiding $(5/2)^+$-powers
3. Dvořáková et al. Work: Proved that $g(f^{\omega}(0))$ avoids $(5/2)^+$-powers and is a Rote sequence

Contribution of This Paper

This paper provides a complete structural theorem, analogous to the Restivo-Salemi theorem's role in overlap-free sequences, filling a theoretical gap.

Conclusions and Discussion

Main Conclusions

1. Complete characterization: Provides complete structural characterization of all Rote sequences avoiding $(5/2)^+$-powers
2. Conjecture confirmation: Verifies the Ollinger-Shallit conjecture regarding the action of morphisms $f$ and $g$
3. Methodological innovation: Combines combinatorial arguments with computational verification, providing rigorous proofs

Limitations

1. Computational dependence: Some key lemmas rely on computer verification; while results are reliable, purely theoretical proofs are lacking
2. Specific exponent: Results apply only to $(5/2)^+$-powers; generalization to other exponents requires further research
3. Binary restriction: Main results focus on binary sequences; ternary cases remain to be explored

Future Directions

1. Ternary generalization: Explore relationships between complexity $2n+1$ and power avoidance in ternary sequences
2. Other exponents: Study structural properties of low-complexity sequences avoiding other power exponents
3. Algorithmic applications: Apply structural theorems to sequence generation and recognition algorithms

In-Depth Evaluation

Strengths

1. Theoretical completeness: Provides complete structural characterization, resolving an important open problem
2. Rigorous methodology: Combines theoretical analysis with computational verification, ensuring reliable proofs
3. Technical innovation: The concepts of proper/antiproper sequences demonstrate originality
4. Practical value: Structural theorems provide theoretical tools for construction and analysis of related sequences

Weaknesses

1. Proof complexity: Some lemma proofs rely on extensive case analysis; more elegant approaches may exist
2. Computational verification: Critical steps depend on computer search, reducing theoretical purity
3. Generalizability: The potential for extending results to other parameters or alphabets is not sufficiently clear

Impact

1. Theoretical contribution: Provides new structural theorems for combinatorial word theory with significant theoretical value
2. Methodological significance: Demonstrates the effectiveness of combining theoretical analysis with computational verification
3. Subsequent research: Provides new perspectives and tools for related problem investigations

Applicable Scenarios

1. Theoretical research: Combinatorial word theory and formal language theory research
2. Sequence analysis: Construction and analysis of infinite sequences with specific properties
3. Algorithm design: Generation algorithms for sequences avoiding specific patterns

References

The paper cites important works in the field, including:

• Restivo & Salemi's classical structural theorem for overlap-free sequences
• Shallit & Shur's pioneering work on relationships between power avoidance and complexity
• Ollinger & Shallit's recent research on repetition thresholds of Rote sequences
• Carpi & de Luca's classical results on Sturmian sequences

Overall Assessment: This is a high-quality theoretical paper that resolves an important problem in combinatorial word theory, provides complete structural characterization, verifies important conjectures, and makes significant contributions to the field. Although some proofs rely on computational verification, the overall methodology is rigorous and results are reliable, establishing a solid foundation for subsequent research.