A closed form for the reduced abelian complexity of the Thue–Morse word, and the five open problems of Campbell, Currie and Rampersad

Abstract

Campbell, Currie and Rampersad recently introduced the reduced factor and abelian complexity functions of an infinite word: length-n factors are counted after every maximal block of equal letters has been collapsed to a single letter, up to equality (respectively, up to permutation) of the collapsed words. They evaluate both functions for the paperfolding word and the reduced factor complexity ρʳᵉᵈₜ of the Thue–Morse word t, and close with five printed questions about the reduced abelian complexity ρ^(ab,red)ₜ: an apparent halving identity, an apparent dichotomy |ρ^(ab,red)ₜ(4n+2) - ρ^(ab,red)ₜ(4n)| ∈ {0,1} governed by tₙ₊₁ = t₃ₙ₊₁, the sign of that difference, a recursion for ρ^(ab,red)ₜ(4n), and non-k-automaticity. We give a closed form. Writing mₙ and Mₙ for the least and greatest number of alternations in a length-n factor of t and Λₙ = Mₙ - mₙ + 1 = ρʳᵉᵈₜ(n)/2, 2 ρ^(ab,red)ₜ(n) = 3Λₙ + varepsilonₙ, qquad varepsilonₙ = 0 & Λₙ even, (-1)^(mₙ) & Λₙ odd. From it we prove the halving identity and the dichotomy; we evaluate the sign of the difference as (-1)^(mₙ₊₁), with m mod 2 given by an explicit O(log n) rule, equivalently by a four-state base-4 automaton, and we report two exhaustive searches that find no closed form of simpler shape; we give the recursion for ρ^(ab,red)ₜ(4n) and hence a full recursion for ρ^(ab,red)ₜ on the state (Λₙ, mₙ mod 2), which the value ρ^(ab,red)ₜ(n) alone does not carry. The fifth question is settled as printed: the sequence is unbounded, hence has infinite range, hence is not k-automatic for any k. Outside the formal development we record that the strengthening a reader reaches for is false: ρ^(ab,red)ₜ is 2-regular, its 2-kernel spanning an 11-dimensional space over ℚ. One caveat is uniform and is stated with every result below. All theorems are about the closed form widehat(ρ)(n) = (3Λₙ + varepsilonₙ)/2 built from the (mₙ,Mₙ) recursion of Campbell–Currie–Rampersad, and all are machine-checked in Lean 4 for that function. The identification widehat(ρ)(n) = ρ^(ab,red)ₜ(n) is checked by direct computation for 1 ≤ n ≤ 64 and, in general, rests on that recursion together with the two structural facts established inside their proof of the recursion for ρʳᵉᵈₜ — the run counts of the length-n factors fill the whole interval [mₙ+1, Mₙ+1], and t is closed under complement — which we cite and do not reprove.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-09-07 03:53 UTC

   File fingerprint

   777713fe3a2244cb50f48ee9a6a648d0e03c1f30930aaaa364de52f31f9d7ebe