Smallest String Attractors and Minimal Coverage Certificates of Thue--Morse Words
Abstract
String attractors provide a compact way of representing the complete factor structure of a word: a set of positions is an attractor if every distinct factor has at least one occurrence crossing one of the selected positions. Although the minimum attractor size is known for several classical families of words, describing \emph{all} optimal attractors is typically much more difficult, since it requires understanding the geometry of all factor occurrences rather than constructing a single optimal solution. We give a complete description for the finite Thue--Morse words. Earlier work proved that four positions are necessary and sufficient for every order n≥ 4, but the collection of all smallest attractors remained unknown. For every n≥ 6, writing h=2n−3, we prove that the smallest attractors are exactly the two reflected families where the four offsets are chosen independently from {0,1}. Hence there are exactly $32$ smallest attractors for every n≥6. The initial cases are genuinely exceptional: t5 has $40$ smallest attractors and t4 has $87$. We also study the attractor condition independently of optimality. For every n≥5, we characterize the complete antichain of inclusion-minimal factor coverages of tn. It consists precisely of the coverages of aa, bb, and the eight minimal unique substrings of every generation tm, 4≤ m≤ n. Thus there are exactly 8n−22 canonical constraints, forming an irredundant exact certificate for attractors of arbitrary cardinality. When attention is restricted to four-position sets, this linear-size system collapses to a constant one: it is enough to test the $24$ minimal unique substrings coming from three consecutive generations, and sixteen of these already force the two optimal families. We also show that three generations are necessary within this natural consecutive-generation hierarchy.
Related
- String attractors and bi-infinite words
- Matroid-Aware Spectral Certificates for Multiplicative Coverage Approximation
- Resonance transformations for the (2,2p+1) minimal string via x−y swap: a proof of Artemev's conjecture
- The smallest Mealy automaton of intermediate growth
- The integrability of sesqui-regular graphs with smallest eigenvalue at least −3
BibTeX
@misc{faro2026smallest,
title = {{Smallest String Attractors and Minimal Coverage Certificates of Thue--Morse Words}},
author = {Simone Faro and Francesco Pio Marino and Arianna Pavone},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10950},
eprint = {2610.10950},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10950},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Smallest String Attractors and Minimal Coverage Certificates of Thue--Morse Words
AU - Simone Faro
AU - Francesco Pio Marino
AU - Arianna Pavone
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10950
UR - https://arxiv.org/abs/2610.10950
AB - String attractors provide a compact way of representing the complete factor structure of a word: a set of positions is an attractor if every distinct factor has at least one occurrence crossing one of the selected positions. Although the minimum attractor size is known for several classical families of words, describing \emph{all} optimal attractors is typically much more difficult, since it requires understanding the geometry of all factor occurrences rather than constructing a single optimal solution. We give a complete description for the finite Thue--Morse words. Earlier work proved that four positions are necessary and sufficient for every order n≥ 4, but the collection of all smallest attractors remained unknown. For every n≥ 6, writing h=2^n−3, we prove that the smallest attractors are exactly the two reflected families where the four offsets are chosen independently from {0,1}. Hence there are exactly $32$ smallest attractors for every n≥6. The initial cases are genuinely exceptional: t_5 has $40$ smallest attractors and t_4 has $87$. We also study the attractor condition independently of optimality. For every n≥5, we characterize the complete antichain of inclusion-minimal factor coverages of t_n. It consists precisely of the coverages of aa, bb, and the eight minimal unique substrings of every generation t_m, 4≤ m≤ n. Thus there are exactly 8n−22 canonical constraints, forming an irredundant exact certificate for attractors of arbitrary cardinality. When attention is restricted to four-position sets, this linear-size system collapses to a constant one: it is enough to test the $24$ minimal unique substrings coming from three consecutive generations, and sixteen of these already force the two optimal families. We also show that three generations are necessary within this natural consecutive-generation hierarchy.
ER -