arxiv: 2605.07542 · v1 · submitted 2026-05-08 · 🧮 math.CO · cs.DM· cs.FL· math.NT

Recognition: 2 theorem links

· Lean Theorem

Brik's sequence: a strange recursion

Jeffrey Shallit

Authors on Pith no claims yet

Pith reviewed 2026-05-11 02:51 UTC · model grok-4.3

classification 🧮 math.CO cs.DMcs.FLmath.NT

keywords infinite binary wordsrecurrencefactor complexitymorphic wordstranscendental densitycombinatorics on wordsrecurrent sequences

0 comments

The pith

The infinite binary sequence built from the recursion B_{i+1} = B_i C_i is recurrent but not uniformly recurrent, possesses exponential factor complexity, is non-morphic, and has a transcendental density of 1's.

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

The paper defines an infinite binary word b as the limit of finite words starting from B_1 = 101 and extending each B_{i+1} by appending the suffix of B_i after its first i symbols. It establishes that every finite factor of b appears infinitely often, yet the distances between successive appearances of some factors are unbounded. The number of distinct factors of each length grows exponentially, b cannot arise from a morphism applied to another infinite word, and the proportion of 1's in longer and longer prefixes converges to a transcendental real number. These properties matter because they provide a concrete example separating recurrent words from uniformly recurrent ones and from morphic words that usually exhibit more regular growth and algebraic densities.

Core claim

The sequence b, obtained as the infinite limit of the words B_i where B_1 = 101 and B_{i+1} = B_i C_i with C_i equal to B_i minus its initial i symbols, is recurrent yet not uniformly recurrent, has exponential factor complexity, is not morphic, and admits a well-defined density of the symbol 1 that is a transcendental number.

What carries the argument

The recursive construction of the words B_i by appending the appropriate suffix of the current word after removing its first i symbols, guaranteeing that each B_i is a proper prefix of all later B_j and the sequence converges to the infinite word b.

If this is right

Every finite factor of b occurs at infinitely many positions in the infinite word.
For some factors the gaps between consecutive occurrences become arbitrarily large.
The number of distinct factors of length n in b grows exponentially in n.
No morphism generates b from another infinite word.
The limit of the proportion of 1's in the prefixes of b exists and equals a transcendental real number.

Where Pith is reading between the lines

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

Similar recursive constructions starting from other short binary seeds may produce further examples that separate the same classes of sequences.
The transcendental density implies that b lies outside the class of sequences whose symbol frequencies can be computed from finite automata or pure morphic substitutions.
The construction supplies a new explicit witness for the existence of recurrent non-uniformly recurrent words with exponential complexity that are not morphic.

Load-bearing premise

The recursive construction B_{i+1} = B_i C_i produces a well-defined infinite word whose factors and densities can be analyzed using standard combinatorial arguments without hidden dependencies on unstated parameters.

What would settle it

An explicit calculation showing that the density of 1's is an algebraic number, or that the factor complexity function p(n) grows slower than exponentially for arbitrarily large n, or that a uniform recurrence modulus exists for every factor.

read the original abstract

We study the properties of the sequence of words $(B_i)$, where $B_1 = 101$ and $B_{i+1} = B_i C_i$ for $i \geq 1$, where $C_i$ is $B_i$ with the first $i$ symbols removed, and the infinite binary sequence ${\bf b} = 10101101011011101 \cdots$ of which all the $B_i$ are prefixes. We show that $\bf b$ is recurrent, but not uniformly recurrent; it has exponential factor complexity; it is not morphic; and the density of $1$'s exists and is transcendental.

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

Shallit gives an explicit recursive construction for a binary word that is recurrent but not uniformly recurrent, with exponential complexity, non-morphic, and transcendental 1-density.

read the letter

Shallit has put together a recursive construction for a binary infinite word that is recurrent but not uniformly recurrent, has exponential complexity, is not morphic, and has a transcendental density of 1s. The definition is straightforward. B1 is 101, and each next block appends the tail of the current block after dropping the first i positions. Lengths grow as L_{i+1} = 2L_i - i, with the nice closed form 2^{i-1} + i + 1. The infinite word is just the one that has every finite B_i as a prefix. This setup lets the paper apply standard tools from combinatorics on words to get the results. Return words or similar show recurrence without uniform recurrence. Factor counting gives the exponential complexity. Attempts at de-substitution or automaton recognition fail for morphicity. The density limit is computed explicitly and shown transcendental. The work is clean on the combinatorial side, with no hidden parameters or circular reasoning. The closed form for lengths makes the proofs more concrete. The only potential soft spot is in the transcendence argument, which probably uses some specific number theory result. Without seeing the exact steps it is hard to judge, but the stress test suggests it holds up. Readers interested in examples that separate classes of sequences in combinatorics on words will find this useful. It is a single, computable object with several properties lined up. The paper is worth a serious referee. The claims are checkable and the construction is explicit. I recommend sending it for peer review.

Referee Report

0 major / 3 minor

Summary. The manuscript defines a recursively constructed sequence of finite binary words with B_1 = 101 and B_{i+1} = B_i C_i, where C_i is the suffix of B_i of length |B_i| - i. The infinite word b is the unique infinite word having every B_i as a prefix. The authors prove that b is recurrent but not uniformly recurrent, possesses exponential factor complexity, is not morphic, and that the density of the symbol 1 exists and equals a transcendental number.

Significance. If the proofs are correct, the paper supplies an explicit, parameter-free example of a binary infinite word combining recurrence without uniform recurrence, exponential complexity, non-morphicity, and a transcendental symbol density. Such combinations are uncommon in the combinatorics-on-words literature, where most studied words are either morphic or have sublinear complexity. The closed-form length formula L_i = 2^{i-1} + i + 1 and the direct combinatorial arguments for the listed properties constitute a clear strength.

minor comments (3)

The recursive definition in the introduction would be easier to follow if the first four or five explicit B_i (with lengths) were displayed in a small table or enumerated list immediately after the definition.
In the section establishing the density of 1's, the limit argument for the existence of the density should explicitly reference the closed-form expression for L_i to make the convergence rate transparent.
The proof that b is not morphic would benefit from a one-sentence reminder of the precise definition of morphic words being used (e.g., image under a morphism of a fixed point of another morphism).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the recommendation for minor revision. The referee's summary correctly reflects the main contributions of the paper regarding the recurrence properties, complexity, morphicity, and symbol density of the infinite word b.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper provides an explicit, parameter-free recursive definition: B_1 = 101 and B_{i+1} = B_i C_i where C_i is the suffix of B_i of length |B_i| - i. Lengths satisfy the recurrence L_{i+1} = 2 L_i - i with closed form L_i = 2^{i-1} + i + 1 (verifiable by induction, and L_i > i holds). The infinite word b is defined as the unique word having every B_i as a prefix. All properties (recurrence vs. uniform recurrence, exponential factor complexity, non-morphicity, existence and transcendence of the density of 1's) are derived from this structure using standard combinatorial-on-words techniques such as return words, Rauzy graphs, de-substitution, and direct limit arguments on the nested prefixes. No step reduces a claimed result to a fitted parameter, self-referential equation, or load-bearing self-citation; the central claims have independent content from the explicit construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on the explicit recursive definition of the sequence together with standard background definitions from combinatorics on words; no free parameters, ad-hoc axioms, or new entities are introduced.

axioms (1)

standard math Standard definitions and basic properties of factors, recurrence, factor complexity, morphic words, and density in infinite words
Invoked throughout to state and prove the listed properties of b.

pith-pipeline@v0.9.0 · 5401 in / 1194 out tokens · 37847 ms · 2026-05-11T02:51:56.261362+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear
B1=101 and B_{i+1}=B_i C_i where C_i is B_i with first i symbols removed; b recurrent but not uniformly recurrent; exponential factor complexity; density of 1's transcendental
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
lengths L_i = 2^{i-1} + i + 1; no two consecutive 0's; alpha = 2 - 2 sum b_i 2^{-i}

Reference graph

Works this paper leans on

5 extracted references · 5 canonical work pages

[1]

Adamczewski and Y

B. Adamczewski and Y. Bugeaud. On the complexity of algebraic numbers I. Expansions in integer bases.Ann. Math.165(2007), 547–565

work page 2007
[2]

Allouche and J

J.-P. Allouche and J. Shallit.Automatic Sequences: Theory, Applications, Generaliza- tions. Cambridge University Press, 2003

work page 2003
[3]

Ehrenfeucht, K

A. Ehrenfeucht, K. P. Lee, and G. Rozenberg. Subword complexities of various classes of deterministic developmental languages without interaction.Theor. Comput. Sci.1 (1975), 59–75

work page 1975
[4]

D. E. Knuth. Mathematics and computer science: coping with finiteness.Science194 (1976), 1235–1242

work page 1976
[5]

N. J. A. Sloane et al. The On-Line Encyclopedia of Integer Sequences. Electronic resource, available athttps://oeis.org. 6

work page