Subword complexity of digit expansions
DefinitionBorelNormality_ComplexityThe subword complexity of an infinite digit sequence over the alphabet is the function counting the distinct blocks of consecutive digits that occur somewhere in . For a real number , the complexity of its base- expansion is the complexity of its digit sequence.
This is the complexity function of Adamczewski–Bugeaud (On the complexity of algebraic numbers I, Ann. of Math. 165 (2007), §2). A sequence normal in base satisfies for every ; their Theorem 1 proves for irrational algebraic numbers. The definition is reusable in combinatorics on words and transcendence.
Formalization Note. seqComplexity filters the finite set Normal.strs b n of length- words by the existence of a positive occurrence count Normal.count s w N; complexity specialises to Normal.digit b x. Classical decidability is used for the filter; both definitions are noncomputable.
import Mathlib
import Definitions.Def_Normal_Core
set_option autoImplicit false
open scoped Classical
namespace BorelNormality
/-- The subword complexity `p(n)` of a digit sequence `s` over base `b`: the number of
distinct words of length `n` over `{0, …, b-1}` that occur somewhere in `s`. -/
noncomputable def seqComplexity (b : ℕ) (s : ℕ → ℕ) (n : ℕ) : ℕ :=
((Normal.strs b n).filter (fun w => ∃ N : ℕ, 0 < Normal.count s w N)).card
/-- The complexity function of the base-`b` expansion of a real number `x`. -/
noncomputable def complexity (b : ℕ) (x : ℝ) (n : ℕ) : ℕ :=
seqComplexity b (Normal.digit b x) n
end BorelNormality
Read-back
What the Lean code literally says, in plain math · GLM (Z.ai), same-agent blind pass — not an independent sub-agent
Two definitions. seqComplexity b s n is the cardinality of the finite set obtained from Normal.strs b n — the set of all lists of length with entries in , which for is the singleton containing the empty list — by keeping exactly those words for which there exists with Normal.count s w N > 0, i.e. occurs at some position of (equivalently, occurs somewhere in ; overlapping occurrences are counted). complexity b x n is seqComplexity b (digit b x) n, where digit b x n = \lfloor x \cdot b^{n+1} \rfloor \bmod b is the -st digit after the point of in base . Edge values: for the result is (the empty word occurs in every sequence); for and the word set is empty and the result is ; for only the all-zero word exists, so the result is at most . The filter uses classical decidability; both definitions are noncomputable.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.