Abelian Complexity in Minimal Subshifts

1 Introduction

• Abelian complexity alone cannot characterize ultimate periodicity: Sturmian words and 01∞ both have constant Abelian complexity 2.Subword complexity does provide a characterization of ultimately periodic words.Source: §1 · p. 3
• Abelian complexity is bounded exactly for words that are C-balanced for some positive integer C.The introduction also notes that a word with subword complexity ρ(n) = 2n + 1 can have unbounded Abelian complexity.Source: §1 · p. 4
• The introduction presents a characterization of the Thue–Morse subshift using the two complexity functions together.Theorem 4 concerns recurrent words and the subshift generated by the Thue–Morse fixed point.Source: §1 · p. 4
• Two positive solutions to Rauzy’s question are introduced, including a result for aperiodic balanced words over {0, 1, 2}.A second result begins with an arbitrary aperiodic infinite binary word and its image.Source: §1 · p. 4
• Every infinite word with bounded Abelian complexity contains an Abelian k-power for every positive integer k.An Abelian k-power consists of k non-empty, pairwise Abelian-equivalent blocks.Source: §1 · pp. 4–5
• For every Sturmian word and positive integer k, each position has an Abelian k-power with one of two possible Abelian periods.In particular, every Sturmian word begins with an Abelian k-power for every positive integer k.Source: §1 · p. 5

• Abelian complexity at each length is the number of distinct Parikh vectors represented by the word’s factors of that length.Source: §2 · p. 5
• For equal-length factors, a gap of c between Parikh-vector coordinates guarantees factors realizing every intermediate coordinate value.Source: §2 · p. 5
• Abelian complexity is bounded exactly when a word is C-balanced for some positive C; C-balance limits each Parikh-vector coordinate to at most C+1 values.A word bounded by K is (K−1)-balanced.Source: §2 · p. 5
• For a k-letter alphabet, maximal Abelian complexity counts compositions of n into k nonnegative parts, and Abelian complexity is O(n^(k−1)).Source: §2 · p. 6
• The examples separate the two measures: one word has exponential subword but linear Abelian complexity, while another has maximal Abelian and linear subword complexity.Source: §2 · p. 6

3 Abelian Complexity of the Thue-Morse Word

• Subword complexity distinguishes the Thue–Morse subshift among words sharing the Thue–Morse Abelian complexity.Source: §3 · p. 7
• Among aperiodic binary words, Abelian complexity 2 at odd lengths and 3 at positive even lengths holds exactly for words of the form µ(ω′), 0µ(ω′), or 1µ(ω′).Source: §3 · p. 7
• For even-length factors n = 2k, the Parikh vectors are (k, k), (k −1, k + 1), and (k + 1, k −1).Source: §3 · p. 8
• The converse characterization fails for ultimately periodic words: (01)∞ has the required morphic form but not the Thue–Morse Abelian complexity.Source: §3 · p. 9

4 Two Answers to a Question of G. Rauzy

• For each p ≥ 3, prefixing a Sturmian word with (p −1)(p −2) . . . 2 yields Abelian complexity p, giving an answer to Rauzy’s question at p = 3.Source: §4 · p. 9
• If an aperiodic binary word is mapped by f(0) = 012 and f(1) = 021, its image has constant Abelian complexity 3.Source: §4 · p. 11
• The section asks whether a recurrent infinite word can have Abelian complexity 3 at every positive length and reports the authors’ suspicion that the answer is no.Source: §4 · p. 11

5 Bounded Abelian Complexity

• Every infinite word on a finite alphabet with bounded Abelian complexity contains an Abelian k-power for every positive integer k.Source: §5 · p. 11
• Van der Waerden’s theorem supplies an arithmetic progression of equal colors, which the proof uses to obtain consecutive equal-length blocks with equal Parikh vectors.Source: §5 · p. 13
• Any infinite word that avoids Abelian k-powers for some positive integer k is arbitrarily imbalanced, meaning it is not C balanced for any positive integer C.Source: §5 · p. 13
• The section asks whether every uniformly recurrent infinite word with bounded Abelian complexity begins with an Abelian k-power for each positive integer k.Source: §5 · p. 13

6 Abelian repetitions in Sturmian words

• For every Sturmian word and positive integer k, each position begins an Abelian k-power with period ℓ1 or ℓ2.In particular, every Sturmian word begins in an Abelian k-power for every positive integer k.Source: §6 · p. 14
• A single fixed Abelian period at every position would force a word to be ultimately periodic, so the two-period allowance is optimal.The theorem contrasts with Sturmian words whose initial critical exponent is 2.Source: §6 · p. 14
• A characteristic word cα is associated with an irrational α between 0 and 1, and a Sturmian word has the same factors as such a word.Source: §6 · p. 14
• The proof reduces to characteristic words and chooses between continued-fraction denominators q_n and q_n+1 as the Abelian period.The choice depends on which interval contains {iα}.Source: §6 · p. 18
• The property does not characterize Sturmian words: it also holds for f(ω), where ω is Sturmian and f(0)=00 and f(1)=01.Source: §6 · p. 18