Cloitre's Self-Generating Sequence

Basic Information

• Paper ID: 2501.00784
• Title: Cloitre's Self-Generating Sequence
• Author: Jeffrey Shallit (University of Waterloo)
• Classification: math.CO cs.DM cs.FL math.NT
• Publication Date: January 3, 2025
• Paper Link: https://arxiv.org/abs/2501.00784

Abstract

In 2009, Benoit Cloitre introduced a special self-generating sequence $(a_n)_{n\geq 1} = 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, \ldots$ with the property that the sum of all terms in the $n$-th run equals twice the $n$-th term of the sequence. This paper establishes a connection between this sequence and the paper-folding sequence, and proves Cloitre's conjecture regarding the density of the digit 1 in the sequence.

Research Background and Motivation

Research Questions

The core problems addressed in this paper are:

1. The relationship between this sequence and known mathematical objects (paper-folding sequences)
2. The asymptotic density problem of the digit 1 in the sequence

Significance of the Problem

Self-generating sequences hold an important position in combinatorial mathematics, exhibiting complex structural properties while relating to multiple mathematical branches. The study of Cloitre's sequence is significant for:

• Extending understanding of self-generating sequence properties
• Establishing new connections with classical sequences such as paper-folding sequences
• Providing new applications of automata theory in sequence analysis

Limitations of Existing Research

Existing research on similar sequences (such as the Oldenburger-Kolakoski sequence) indicates that the asymptotic properties of such sequences are often difficult to analyze. For instance, whether the density of 1's in the Oldenburger-Kolakoski sequence equals 1/2 remains an open conjecture.

Research Motivation

Cloitre proposed in OEIS entry A157196 a conjecture that the density of 1's in this sequence is 2/3, which provides a clear objective for this research.

Core Contributions

1. Established new sequence connections: First discovered the deep connection between Cloitre's self-generating sequence and the regular paper-folding sequence
2. Proved the density conjecture: Rigorously proved Cloitre's conjecture that the density of 1's in the sequence is 2/3
3. Provided precise bounds: Proved that $0 \leq 3g_n - 2n \leq 4$, where $g_n$ is the count of 1's in the first $n$ terms
4. Developed automata methods: Employed finite automata and Walnut software to provide a computational verification framework for sequence analysis
5. Extended to general cases: Generalized results to arbitrary paper-folding sequences

Methodology Details

Problem Definition

Study of the Cloitre sequence $(a_n)_{n\geq 1}$, defined by the following self-generating rule:

• The sequence takes values in the alphabet {1,2}
• Begins with $a_1 = 1$
• The sum of all elements in the $n$-th run equals $2a_n$

Core Methodological Framework

1. Sequence Construction Chain

The paper constructs a series of interrelated sequences:

• Regular paper-folding sequence $(p_n)$
• Binary version $(q_n)$, satisfying $p_n = (-1)^{q_n}$
• First-order difference sequence $(d_n)$
• Absolute value sequence $(d'_n)$
• Run-ending positions $(e'_n)$
• Final derivation of $(b_n) = (a_n)$

2. Automata Representation

Each sequence can be represented by a finite automaton:

• DFAO (Deterministic Finite Automaton with Output): Used for sequences taking finite values
• Synchronized automata: Used for sequences taking integer values
• All automata use least significant bit first binary representation

3. Walnut Verification Framework

Formal verification using Walnut software:

eval q_test "?lsd_2 An (Q[2*n]=Q[n] & Q[4*n+1]=@0 & Q[4*n+3]=@1)":

Technical Innovations

1. Paper-Folding Sequence Connection

Innovatively discovered the connection between Cloitre's sequence and paper-folding sequences: $q_{2n} = q_n, \quad q_{4n+1} = 0, \quad q_{4n+3} = 1$

2. Conjecture-Verification Strategy

For complex sequences (such as run-ending positions), adopted a "conjecture automaton then verify" strategy, which is an effective approach for handling automatic sequences.

3. Multi-Layer Sequence Analysis

Decomposed complex self-generating properties into tractable automata computations through construction of multiple intermediate sequences.

Experimental Setup

Computational Tools

• Walnut Software: Used for automata computation and formal verification
• Finite Automata: All sequences represented and computed through automata
• OEIS Database: Used for sequence verification and comparison

Verification Methods

1. Automata Correctness Verification: Verify automata correctness through multiple condition checks
2. Recurrence Relation Verification: Verify that sequences satisfy their recurrence relations
3. Boundary Condition Checking: Verify initial conditions and special cases

Implementation Details

• Least significant bit first binary representation
• Automata with state counts ranging from 4 to 32
• All computations formally verified by Walnut

Experimental Results

Main Theorem Proof

Theorem 2: Let $g_n$ be the count of 1's in the sequence $a_1a_2\cdots a_n$, then: $0 \leq 3g_n - 2n \leq 4$ Therefore $\lim_{n\to\infty} g_n/n = 2/3$.

Key Verification Results

1. Sequence Consistency: Verified that $b_n = a_n$, confirming that the constructed sequence is indeed Cloitre's sequence
2. Self-Generating Property: Verified that $\sigma_n = 2b_n$, where $\sigma_n$ is the sum of the $n$-th run
3. Run Lengths: Proved that run lengths can only be 1, 2, or 4
4. Density Bounds: Verified density bounds through a 16-state automaton

Additional Findings

Proved that the sequence $w_n = \min\{t \geq 1 : e'_t \geq n\}$ is OEIS sequence A091960, satisfying:

• $w_1 = 1$
• $w_{2n} = w_{2n-1} + (w_n \bmod 2)$
• $w_{2n+1} = w_{2n} + 1$

Related Work

Main Related Sequences

1. Oldenburger-Kolakoski Sequence: $k := 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, \ldots$
   • The $n$-th term equals the length of the $n$-th run
   • The density problem for 1's remains unsolved
2. Dekking Sequence: $1, 3, 3, 3, 1, 1, 1, 3, 3, 3, \ldots$
   • The run-length sequence equals the sequence itself
   • Can be understood as a fixed point of morphisms
3. Paper-Folding Sequence: Generated by iterative paper-folding
   • Has deep connections with binary representation
   • Can be computed using finite automata

Uniqueness of This Paper's Contribution

Cloitre's sequence is more tractable than the Oldenburger-Kolakoski sequence because it has a subtle but explicit connection with binary representation, making the automata method particularly effective.

Conclusions and Discussion

Main Conclusions

1. Density Theorem: Rigorously proved that the density of 1's in Cloitre's sequence is 2/3
2. Structural Connections: Established deep connections with paper-folding sequences
3. Computational Framework: Demonstrated the power of automata methods in sequence analysis

Generality of the Method

Section 7 of the paper shows that all results can be generalized to arbitrary paper-folding sequences, although in the general case there is no obvious analogue of the self-generating property.

Future Directions

1. Investigate connections between other self-generating sequences and classical sequences
2. Develop more general automata analysis frameworks
3. Explore applications in other mathematical branches

In-Depth Evaluation

Strengths

1. Methodological Innovation: Cleverly combines automata theory with sequence analysis
2. Rigor: All results are formally verified
3. Completeness: Not only proves the main conjecture but also discovers additional structural properties
4. Extensibility: Methods generalize to broader classes of sequences

Technical Highlights

1. Conjecture-Verification Strategy: Provides a practical method for analyzing complex automatic sequences
2. Multi-Layer Sequence Construction: Simplifies analysis of complex properties through intermediate sequences
3. Computational Verification: Use of Walnut software ensures reliability of results

Limitations

1. Computational Complexity: Some automata have numerous states, potentially limiting analysis of more complex sequences
2. Conjecture Dependence: Some automata require conjecture before verification, lacking systematic construction methods
3. Generalization Constraints: While generalizable to arbitrary paper-folding sequences, the self-generating property is lost

Impact

1. Theoretical Contribution: Provides new analytical tools for self-generating sequence research
2. Methodological Value: Demonstrates application of computer-assisted proofs in combinatorial mathematics
3. Practical Utility: Provides a template for research on related sequences in OEIS

Applicable Scenarios

This method is particularly suitable for:

• Analysis of sequences related to binary representation
• Research on automatic sequences with recursive structure
• Combinatorial sequences requiring precise density analysis

References

The paper cites 14 important references covering classical works in automatic sequence theory, paper-folding sequences, Kolakoski sequences, and related fields, providing a solid theoretical foundation for the research.