What are all the smallest string attractors of Fibonacci, period-doubling, and Thue-Morse words?

An attractor is a set of positions every substring crosses

A string attractor of a string T is a set of positions Γ such that every nonempty substring of T has at least one occurrence that crosses a position in Γ. In other words, no substring is confined to a gap between chosen positions: each one can be read off an occurrence that passes through a marked index. The smallest size such a set can have is written γ(T), and the paper's object of study is not that size but the full collection of sets that achieve it, denoted A(T).

This distinction matters because the sizes were already settled. Earlier work established that Fibonacci words and period-doubling words of length at least 2 have smallest attractor size 2, and that Thue-Morse words of length at least 25 have smallest attractor size 4. What was missing was a description of every position set attaining those sizes. The paper supplies that description for all three families, and the answer turns out to differ enormously between families that share the same size.

The paper also notes why the quantity is worth pinning down: dictionary compression algorithms can be viewed as procedures that compute string attractors, and γ(T) bounds all dictionary compression measures from below. Computing γ(T) for an arbitrary string is NP-hard, which is part of why explicitly characterized families are useful reference cases.

Equal attractor size hides very different numbers of attractors

The headline comparison is between families whose smallest attractor size is identical. Fibonacci words and period-doubling words both have γ = 2, yet the nth Fibonacci word has 2^(n−4) + 2^⌈n/2⌉ − 2 distinct smallest attractors for n ≥ 7, a count that grows with the word's length, while the nth period-doubling word has exactly two for n ≥ 2, a constant. Thue-Morse words sit at size 4 with exactly 32 smallest attractors for n ≥ 6, again constant.

So the size of the smallest attractor does not determine how many smallest attractors exist. The authors state this explicitly and add that they do not yet have a clear interpretation of what this count captures; they suggest it may support finer-grained notions of repetitiveness. That is the authors' framing of an open question, not a demonstrated application.

The concrete period-doubling answer is compact enough to state directly: for n ≥ 3, the two smallest attractors of the nth period-doubling word D_n are the position pairs {3·2^(n−3), 6·2^(n−3)} and {4·2^(n−3), 6·2^(n−3)}. Both pairs share the position 6·2^(n−3) and differ only in the first coordinate.

Fibonacci attractors are counted by a recursive formula

For Fibonacci words, defined by F_0 = b, F_1 = a and F_n = F_(n−1)F_(n−2), the paper gives a recursive formula rather than a closed list, because the number of pairs grows. The formula describes 2^(n−4) + 2^⌈n/2⌉ − 2 distinct position pairs as the smallest attractors of F_n for every n ≥ 7. The exponent structure shows why a recursion is the natural presentation: the count roughly doubles every four orders while picking up an extra term tied to the parity of n.

The characterization rests on occurrences of singular words inside the Fibonacci word. The paper's proof organizes the attractor pairs through the positions where copies of F_(n−1) and its reverse occur, together with offsets and a separate case for a distinguished set of positions; the accompanying figures display all smallest attractors of F_8 and F_9 as horizontally aligned dot pairs, with colors marking which part of the argument accounts for each pair.

A useful anchor is that one smallest attractor was already known in closed form. Earlier work on standard Sturmian words gives the pair {f_(n−1) − 1, f_(n−1)}, where f_(n−1) is the length of F_(n−1); the paper explains that the alternative candidate {f_(n−2) − 1, f_(n−2)} fails because the length-f_(n−1) suffix of F_n occurs uniquely and no occurrence of it crosses a position in that pair. The new result is everything else beyond this single known pair.

Period-doubling and Thue-Morse proofs halve positions down one order

For period-doubling and Thue-Morse words the paper uses a shared proof scheme. The nth period-doubling word is D_0 = a with D_n = φ(D_(n−1)) under φ(a) = ab, φ(b) = aa; the nth Thue-Morse word is T_0 = a with T_n = μ(T_(n−1)) under μ(a) = ab, μ(b) = ba. In both cases every smallest attractor of the nth word is shown to project, by halving its positions, onto a smallest attractor of the (n−1)st word.

That projection reduces the whole characterization to ruling out a constant number of candidate positions, and the exclusions are done with short substrings. In the Thue-Morse case the paper lists specific short witnesses, such as bbaaba, babbabaabb, aabbabaaba, abaababbaa, bbaababbab and babbaa, each showing that a particular boundary candidate cannot belong to an attractor. Because these witnesses are short, any occurrence crossing the relevant boundary must be a substring of a small, fixed set of surrounding blocks.

The induction then closes: if an attractor of T_k contained an element outside the described family, an attractor of T_(k−1) outside the corresponding family would exist, contradicting the induction hypothesis. The base case n = 6 is confirmed by brute force, and the count for n ≥ 6 follows as 32.

A theorem prover independently confirms the three characterizations

The paper does not rely on the combinatorial proofs alone. Using the Walnut theorem prover, the authors build automata that accept representations of attractor positions together with the prefix length, for period-doubling, Fibonacci and Thue-Morse words. Positions are encoded in binary for period-doubling and Thue-Morse words and in Zeckendorf representation for Fibonacci words, and the automata read several tracks in parallel: one track per attractor position plus a length track.

The Thue-Morse automaton for four positions has 1440 states, and its construction took around 6.5 hours on an Intel Xeon Platinum 8462Y+ processor at 2.8 GHz using 705 GiB of memory; the strategy metacommand CCLS was needed because the default determinization strategy did not finish. The authors then construct separate automata directly from their own theorems and check, by breadth-first search on the product automaton, that each accepts exactly the same language over the stated order ranges.

This is a mechanical confirmation, and the authors are explicit about its epistemic status: it depends on the correctness of Walnut and of the simple automata constructions, and it would not by itself explain why the statements hold, which is what the combinatorial proofs provide. The verification scripts and Walnut commands are reported as publicly available.

The formulas cover whole words, not arbitrary prefixes

Each result carries an explicit order threshold: n ≥ 7 for Fibonacci words, n ≥ 2 for the period-doubling formula as stated in the abstract (with the pair formula given for n ≥ 3), and n ≥ 6 for Thue-Morse words. Lower orders are not covered by the formulas; the paper lists their smallest attractors separately in a figure for completeness. Readers should therefore not read the formulas as statements about small words.

A second boundary is the object being characterized. The results concern whole words F_n, D_n and T_n, not arbitrary prefixes of the underlying infinite sequences. The paper names the prefix question as an open problem, alongside characterizing all smallest bidirectional macro schemes and all smallest straight-line programs for the same families, and extending the characterization to other standard Sturmian words, which include the Fibonacci words.

There is also a scope note on prior results that the paper relies on: the size-2 claim for Fibonacci and period-doubling words and the size-4 claim for Thue-Morse words come from earlier work, including a Walnut-based analysis of prefixes of automatic sequences. The contribution here is the complete enumeration of the minimizing sets, not a re-derivation of the minimum sizes.

The count, not the size, separates these word families

The paper's most decision-relevant claim is a comparison internal to its own results: knowing that γ(F_n) = γ(D_n) = 2 tells you nothing about how many minimizing position sets exist, because the Fibonacci count grows as 2^(n−4) + 2^⌈n/2⌉ − 2 while the period-doubling count stays at two. Thue-Morse words show a third pattern, a fixed 32 sets at size 4. Anyone using these families as test cases for attractor-based compression or indexing should therefore treat the number of smallest attractors as a separate parameter from the minimum size.

The authors are careful about what this parameter means. They state that they do not yet have a clear interpretation of what the number of smallest attractors captures, and they present its understanding as an open and interesting question that may allow finer-grained types of repetitiveness. The paper's contribution is the exact enumeration and the contrast it exposes, not a demonstrated consequence for compression performance.

The paper also reports that a concurrent independent work by Faro, Marino and Pavone obtained the same Thue-Morse characterization by a different route, deriving it from positions covered by occurrences of minimal unique substrings across three consecutive Thue-Morse words rather than by induction on the order. The agreement of two derivations is the strongest reason to treat the 32-set result as settled.

Sources used in this answer