Even Reduced Abelian Complexity

Abstract

Two Thue-Morse letters decide the even-length gap in reduced abelian complexity.

Reduced abelian complexity counts the classes of factors of a given length, where collapsing each maximal constant run to one letter leaves words of equal length that rearrange into one another. For the Thue-Morse word the odd lengths already reduce to shorter ones. Campbell, Currie and Rampersad displayed a rule for the gap between lengths 4n and 4n+2 and left it unproved. That rule is proved here.

Indices and counts are natural numbers; the gap is taken in the integers and then read by absolute value. The letter t denotes the Thue-Morse word indexed from zero, so the two letters compared are at n and at 3n. R is the class count carried by the companion module, unchanged here. A factor with n edges spans n+1 positions, and its alternation count is the number of positions where the letter changes.

Definition 1.1 (Fewest alternations at a length).

$$\forall n\in \mathbb{N},\mathrm{minAlt}\left(n\right)=\underset{s\in \mathbb{N}}{\min }\mathrm{alt}\left(n,s\right)$$

Formalization. D5/S1/Words/Complexity/ThueMorseReducedAbelianEven.minAlternations (✓ std3).

Source. Repository-derived.

Commentary.

Over all starting positions, the alternation count attains a least value. The Thue-Morse word takes only finitely many run patterns at each length, so the range is a bounded set of natural numbers and the infimum is attained.

Definition 1.2 (Most alternations at a length).

$$\forall n\in \mathbb{N},\mathrm{maxAlt}\left(n\right)=\underset{s\in \mathbb{N}}{\max }\mathrm{alt}\left(n,s\right)$$

Formalization. D5/S1/Words/Complexity/ThueMorseReducedAbelianEven.maxAlternations (✓ std3).

Source. Repository-derived.

Commentary.

The same range has a greatest element, attained at some start. The two extremes bracket every alternation count occurring at that length.

Lemma 1.3 (Parity of the two extremes).

$$\forall n\in \mathbb{N},(\left(\mathrm{minAlt}\left(n\right)+\mathrm{maxAlt}\left(n\right)\right)\mathrm{mod}2=0)⟺t\left(n\right)=t\left(3\cdot n\right)$$

Proof. Machine-checked in Lean as D5/S1/Words/Complexity/ThueMorseReducedAbelianEven.alternation_extrema_parity (✓ std3). ∎

Source. Repository-derived.

Commentary.

Induct strongly on n. Splitting n by parity relates the extremes at n to those at half of n, using how the alternation count behaves when one letter is appended. The odd branch closes with a fact about three consecutive Thue-Morse letters. The statement is the step that carries the arithmetic of the word into the counting argument.

Theorem 1.4 (The even-length gap).

$$\forall n\in \mathbb{N},0<n⟹(t\left(n\right)=t\left(3\cdot n\right)⟹\left|R\left(4\cdot n+2\right)-R\left(4\cdot n\right)\right|=0)\wedge (t\left(n\right)\ne t\left(3\cdot n\right)⟹\left|R\left(4\cdot n+2\right)-R\left(4\cdot n\right)\right|=1)$$

Proof. Machine-checked in Lean as D5/S1/Words/Complexity/ThueMorseReducedAbelianEven.reducedAbelianComplexity_even_difference (✓ std3). ∎

Resolves. Problems/campbell-currie-rampersad-eq-11 (proved) by D5/S1/Words/Complexity/ThueMorseReducedAbelianEven.reducedAbelianComplexity_even_difference.

Citation. John M. Campbell, James Currie, Narad Rampersad (2025). Reduced complexities for sequences over finite alphabets. DOI: 10.48550/arXiv.2509.16034.

Commentary.

The alternation counts realised at a fixed length fill an interval, so the class count is the size of a weighted interval fixed by the two extremes. Moving the length from 4n to 4n+2 shifts that interval by a controlled amount, and the gap between the two counts collapses to the difference of the extremes taken modulo two. The previous parity statement then decides it. The hypothesis on n is needed: at n equal to zero the gap is two.

Consequence for sequence (10)

The journal version ends Section 3, on printed page 14, by asking for non-k-automaticity of sequence (10). That sequence is the full natural-valued reduced abelian complexity at positive factor lengths. The verified journal citation and exact source sentence are recorded in D5/L/Words/campbell2025reduced. The recurrence mechanism comes from the paper’s Theorem 1 and Lemmas 2–3; factor lengths do not shift when letter indices are translated from one to zero.

Here m(n) and M(n) abbreviate minAlternations n and maxAlternations n, and w(n) = M(n) - m(n). Their argument counts edges: they correspond to the paper’s extrema at length n+1. The existing kernel-checked extrema_bounds, extrema_even and extrema_odd in this frozen module give the following identities for every natural n. The bounds m(n) <= M(n) <= n justify normalizing the natural-number subtractions.

$$m\left(4\cdot n+1\right)=2\cdot n+m\left(n\right),M\left(4\cdot n+1\right)=2\cdot n+1+M\left(n\right)$$

$$w\left(4\cdot n+1\right)=w\left(n\right)+1,w\left(0\right)=0$$

The existing complexity_weighted formula counts the classes realised over all starts, using run counts from m(n)+1 to M(n)+1. Each run count r has weight 1 + (r mod 2), at least one, so

$$R\left(n+1\right)\ge w\left(n\right)+1$$

Set a_0 = 0 and a_(j+1) = 4a_j + 1. Induction gives w(a_j) = j, hence R(a_j+1) >= j+1 for every natural j. Thus R is unbounded on positive lengths. Every finite automaton with a natural-valued output map has a finite, bounded output range, so it cannot produce this sequence in any integer base k >= 2.

This is unboundedness, not convergence to infinity; the existing R(2^k+1) = 3 remains compatible. This argument is exposition from existing ingredients, with no separately kernel-checked nonautomaticity endpoint or typed resolution claim. The source-to-Lean correspondence rests on reading the definitions, not a machine proof of equivalence. The argument does not determine the nonzero sign in equation (11) or a full recursion; the Library note states the limits of the literature search and makes no priority claim.

References

• Truth anchor: D5/S1/Words/Complexity/ThueMorseReducedAbelianEven.alternation_extrema_parity
• Truth anchor: D5/S1/Words/Complexity/ThueMorseReducedAbelianEven.maxAlternations
• Truth anchor: D5/S1/Words/Complexity/ThueMorseReducedAbelianEven.minAlternations
• Truth anchor: D5/S1/Words/Complexity/ThueMorseReducedAbelianEven.reducedAbelianComplexity_even_difference
• Dependency: D5/S1/Words/Complexity/ThueMorseReducedAbelianOdd