Brik's sequence: a strange recursion

Technical Summary: Brik's Sequence: A Strange Recursion

Problem Statement
This paper investigates the properties of a sequence of binary words $(B_i)_{i \ge 1}$ and the resulting infinite binary sequence $b$, generated by a specific recursive iteration proposed by Garo Brik in 2018. The sequence is defined by the base case $B_1 = 101$ and the recurrence relation $B_{i+1} = B_i C_i$ for $i \ge 1$, where $C_i$ is the suffix of $B_i$ obtained by removing its first $i$ symbols. Since $B_{i-1}$ is a prefix of $B_i$ for all $i \ge 2$, these words converge to a unique infinite sequence $b$. The paper seeks to characterize the combinatorial and arithmetic properties of $b$, including its recurrence, factor complexity, morphic nature, and the density of the symbol '1'.

Methodology
The analysis employs a combination of inductive proofs, combinatorial arguments on word factors, and analytic number theory techniques.

• Structural Analysis: The authors establish the length of the words $B_i$ and their suffix properties via trivial induction. They utilize the concept of "borders" (prefixes that are also suffixes) to prove that specific indices are "good," meaning $B_i$ is a border of $B_{\ell_i}$.
• Recurrence and Complexity: The paper analyzes the occurrence of factors within $b$ to determine recurrence properties. It characterizes the set of all valid factors by identifying forbidden substrings.
• Growth Analysis: The starting positions of specific patterns (specifically runs of $1$'s) are tracked using a recurrence relation, with growth rates analyzed using Knuth's tetration notation.
• Density Calculation: The density of $1$'s is derived by analyzing the number of $1$'s in prefixes of length $\ell_n = |B_n|$. The authors derive a limit formula involving the binary expansion of the sequence itself and use error term analysis ($E(N)$) to extend the limit from specific prefixes to arbitrary prefixes.
• Transcendence Proof: To determine the nature of the density limit $\alpha$, the paper applies a simplified version of the "stammering" criterion by Adamczewski and Bugeaud, which relates the repetition structure of a sequence to the transcendence of the number formed by its binary expansion.

Key Contributions and Results

1. Recurrence Properties:

   • The infinite word $b$ is proven to be recurrent (every finite factor appears infinitely often) but not uniformly recurrent.
   • The paper demonstrates that $b$ contains arbitrarily long runs of $1$'s ($1^n$ for all $n$), which precludes uniform recurrence. The starting position $r_n$ of the first occurrence of $1^n$ follows the recurrence $r_{n+1} = 2^{r_{n-2}} + r_n$ for $n \ge 2$, leading to extremely rapid growth (tetration).

2. Factor Complexity:

   • A complete characterization of the factors of $b$ is provided: a binary word is a factor of $b$ if and only if it contains no two consecutive $0$'s.
   • Consequently, the number of distinct factors of length $n$ is exactly $F_{n+2}$ (the $(n+2)$-th Fibonacci number). This establishes that $b$ has exponential factor complexity.

3. Non-Morphic Nature:

   • Based on the exponential factor complexity, the paper concludes that $b$ is not morphic. This follows from the result of Ehrenfeucht, Lee, and Rozenberg, which states that morphic sequences must have polynomial factor complexity (specifically $O(n^2)$).

4. Density of 1's:

   • The paper proves that the asymptotic density of $1$'s in $b$, denoted $\alpha = \lim_{n \to \infty} \frac{a(n)}{n}$, exists.
   • The value is given by the formula $\alpha = 2 - 2\sum_{i \ge 1} b_i 2^{-i}$, where $b_i$ is the $i$-th bit of the sequence.
   • The numerical value is approximately $0.64505878493452$.

5. Transcendence:

   • The density $\alpha$ is proven to be transcendental. The proof relies on showing that the associated number $\beta = \sum b_i 2^{-i}$ is transcendental using the stammering criterion. Since $\beta$ cannot be rational (as that would imply bounded factor complexity), and the sequence exhibits the required "stammering" structure ($B_{n+1}$ contains $B_n$ followed by a repetition of a suffix), $\beta$ (and thus $\alpha$) must be transcendental.

Significance and Claims
The paper presents a sequence that, while defined by a simple iterative rule, exhibits subtle and complex properties not immediately apparent. The primary significance lies in the discovery of a sequence that is recurrent but not uniformly recurrent, possesses exponential factor complexity, and generates a transcendental density of $1$'s. The authors note that the sequence appears in the OEIS (as A334820, missing the initial term) and highlight the interplay between the recursive definition and the resulting arithmetic properties.

The paper explicitly acknowledges that these results were obtained through experimentation with APL and collaboration with ChatGPT 5.5 in May 2026, with all claims subsequently rewritten and verified by the author. The work serves as a case study in the properties of recursively defined binary words and the application of transcendence criteria to combinatorial sequences.