Source-linked AI summary
Smallest String Attractors and Minimal Coverage Certificates of Thue--Morse Words
Simone Faro, Francesco Pio Marino, Arianna Pavone
TL;DR
Knowing the minimum attractor size does not determine all optimal position sets, whose classification requires understanding factor occurrences. The paper uses recursive boundaries and transported MUS coverages to characterize those sets and the minimal constraints for arbitrary attractors. From n ≥6, there are exactly 32 smallest attractors, while the general coverage system has 8n −22 constraints.
Problem
The geometry of all optimal attractor sets remained unknown even though four positions were known to suffice for finite Thue–Morse words.
Source: §1.1 · p. 2Method
The proofs combine recursive boundary geometry with transported minimal unique substring coverages across generations.
Source: §1.5 · p. 3, §1.7 · p. 4Results
For n ≥6 there are exactly 32 smallest attractors, versus 40 for t5 and 87 for t4; arbitrary-cardinality attractors have an exact minimal-coverage system of size 8n −22.
Source: §10 · p. 31Takeaways & Limitations
The minimal-coverage antichain gives an irredundant exact certificate for attractors of arbitrary cardinality.
Source: §10 · p. 31The 24-factor test applies only to four-position sets, and three-generation necessity is established only within the consecutive-generation hierarchy.
Source: §5.7 · p. 18, §5.6 · p. 18
Abstract
from arXiv · showhide
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\geq 4$, but the collection of all smallest attractors remained unknown. For every $n\geq 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\geq6$. 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\geq5$, 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\leq m\leq 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.
1 Introduction
The paper addresses the gap between knowing the minimum attractor size and identifying every optimal position set, then characterizes both smallest attractors and the minimal coverage constraints for arbitrary attractors. Its results use recursive Thue–Morse structure and minimal unique substrings to give exact classifications and certificates.
1.1 String attractors and the classification problem
- The challenge is structural: the known minimum size γ(t_n) = 4 does not identify all optimal position sets, whose factor occurrences overlap globally across scales.Earlier work gave a four-position attractor but not the complete classification [8].Source: §1.1 · p. 2, §1.2 · p. 2
1.3 All smallest attractors
- For n ≥6, exactly 32 smallest attractors form two families, with four boundary-pair endpoints chosen independently; t5 has 40 and t4 has 87.Writing h = 2^(n−3), the two families have offsets at 2h, 3h, 4h, 6h and 2h, 4h, 5h, 6h, respectively.Source: §1.3 · pp. 2–3
1.4 Beyond smallest attractors: the canonical coverage constraints
- For every n ≥5, the inclusion-minimal coverages are those of aa, bb, and the eight MUSs from each generation t_m, 4 ≤ m ≤ n, totaling 8n −22.These coverages form an antichain, and none can be removed from the exact constraint system for attractors of any cardinality.Source: §1.4 · p. 3
1.5 Why minimal unique substrings appear
- The paper builds on the known MUS structure [7], deriving a Thue–Morse-specific trimmed recurrence and exact occurrence transport across generations.This links finite base data to the uniform coverage formulas used in the proofs.Source: §1.5 · p. 3, §1.8 · p. 5
1.6 From 8n −22 constraints to a constant certificate
- For four-position sets, the 24 MUSs from three consecutive generations give an exact test, and three generations are necessary within that hierarchy.Sixteen selected MUS-derived coverage sets suffice to force the two stable families.Source: §1.6 · p. 4, §1.8 · p. 5
1.7 Proof ideas
- Recursive boundary geometry proves sufficiency: every factor of length at least two has an occurrence containing both endpoints of one of four distinguished boundaries.The one-letter factors are checked separately; transported MUS coverages establish necessity.Source: §1.7 · p. 4
- For the coverage theorem, minimal coverages have shortest representatives that are two-sided frequency-critical; desubstitution and synchronization recover the MUS hierarchy.The resulting MUS-derived coverages and those of aa and bb are pairwise incomparable.Source: §1.7 · p. 4
2 Related work
Prior work established minimum attractor sizes, constructions, and MUS structure, but not the full collection of optimal attractors for finite Thue–Morse words. This paper addresses that classification and the broader system of minimal coverage constraints.
2.1 String attractors and repetitive structure
- Earlier work introduced attractors as a common abstraction for dictionary-compression mechanisms and studied their minimum sizes across classical word families.A linear-time checker and greedy construction address decision and construction, unlike this paper’s goal of describing all optima.Source: §2.1 · p. 5
2.2 Attractors of Thue–Morse and related morphic words
- Kutsukake et al. [8] proved that γ(tn) = 4 for n ≥4 and gave a four-position construction, but did not classify all such sets.Dolce instead studied arbitrary factors of the infinite Thue–Morse word, proving a sharp attractor upper bound of five.Source: §2.2 · p. 6
- Banbara et al. [1] classified smallest attractors for finite Fibonacci and period-doubling words, while listing the Thue–Morse classification as open.A direct Walnut computation with four free attractor positions exceeded available memory.Source: §2.2 · p. 6
2.3 Minimal unique substrings and occurrence transport
- Kishi et al. [7] characterized the eight MUSs in sufficiently large finite Thue–Morse generations, and each unique occurrence supplies an attractor constraint.The paper proves exact start-position correspondence for the specific trimmed factors needed across consecutive generations, not a generalization of occurrence-preserving morphisms.Source: §2.3 · p. 6
2.4 Position of the present results
- The paper addresses two open questions: classifying every smallest finite Thue–Morse attractor and identifying all inclusion-minimal factor coverages defining attractors of any size.The authors present the MUS hierarchy as the source of constraints across scales.Source: §2.4 · p. 6
3 Preliminaries and structural intuition
The section frames attractors as position sets hitting factor coverages and develops recursive Thue–Morse geometry for later proofs. It previews how minimal coverage constraints and centered occurrences reduce the attractor analysis.
3.1 Words, occurrences, and coverage sets
- The section represents factors by the union of positions covered by their occurrences, distinguishing that coverage from the individual occurrence intervals.The recursively nested Thue–Morse blocks provide the complementary geometric viewpoint used in later witness arguments.Source: §3.1 · p. 7, §3 · p. 7
- A set Γ is an attractor exactly when it hits every factor coverage; inclusion-minimal coverages suffice because hitting a smaller coverage also hits any larger one.This reduces the attractor condition to the essential constraints Hmin(w).Source: §3.1 · p. 7, §3.2 · p. 7
3.4 The decomposition tree viewpoint
- The recursive decomposition tree explains why factor occurrences meet canonical boundaries: any interval with distinct endpoints crosses the split between its lowest containing block’s children.The proof later seeks a common small set of global boundaries for occurrences of each factor.Source: §3.4 · p. 8
3.5 Four canonical boundaries
- The known four-position construction uses four canonical positions, but from order six onward each can shift to an adjacent boundary endpoint, with reflection yielding a second pattern.The preview attributes the surviving endpoint choices to the centered-occurrence property.Source: §3.5 · p. 8, §3.6 · p. 9
3.6 A preview of the centered-occurrence property
- For n ≥4, every factor of tn of length at least two has an occurrence containing both endpoints of one of four canonical boundaries.This centered-occurrence property is stronger than merely saying each occurrence crosses some recursive boundary.Source: §3.6 · p. 9
3.7 Minimal unique substrings as localized constraints
- A MUS occurs once and becomes repeated when either end is removed, so every attractor must hit its unique occurrence interval.A MUS from tm may repeat in a larger tn, making its full ambient coverage relevant; the current generation’s MUSs alone do not capture all four-position attractors.Source: §3.7 · p. 9
3.8 Three levels of constraints
- The paper previews three constraint levels: all factor coverages, 8n −22 minimal coverages, and—when |Γ| = 4—a test using 24 MUSs from three consecutive generations.Sixteen selected witnesses are then used for the classification proof; the latter reductions rely on the four-position assumption.Source: §3.8 · p. 9
4 From MUS structure to occurrence coverages
This section develops exact occurrence transport for Thue–Morse MUSs across generations, allowing their ambient coverages to be computed from finite base data. Synchronization and a trimmed morphic recurrence supply the mechanism.
4 From MUS structure to occurrence coverages
- Occurrence information for MUSs can be transported exactly between generations, reducing later coverage calculations to a small table at the first few orders.The transport handles factors that may repeat in a larger ambient word, rather than tracking only their unique source occurrences.Source: §4 · p. 10
4.1 The MUS hierarchy
- For every m ≥4, tm has exactly eight MUSs, each of length 2m−3 + 2, with a Thue–Morse core surrounded by one letter at each end.The next generation’s MUS is a trimmed morphic image, since applying the morphism doubles the boundary letters.Source: §4.1 · pp. 10–11
4.2 Synchronization: why the morphic phase is forced
- Every occurrence of µ(U), for |U| ≥2, starts at an odd position in a finite Thue–Morse word.A shifted alignment would require three consecutive equal preimage letters, which Thue–Morse words do not contain.Source: §4.2 · p. 11
4.3 The trimmed MUS recurrence
- The corresponding MUS at order m + 1 is obtained by morphing the order-m MUS and deleting the first and last symbols, while occurrence starts double in every larger ambient generation.The exact start correspondence preserves the ordering of the eight MUSs.Source: §4.3 · p. 12
4.4 A concrete example of the lifting rule
- The example lifts the unique t4 MUS bbab, starting at 2, to abaabb starting at 4; the same doubling applies to occurrences in larger ambient words.For example, an occurrence of bbab at 14 corresponds to abaabb at 28 in the next generation.Source: §4.4 · p. 12
4.5 Finite base data
- A constant-size base table records the eight t4 MUSs’ starts in t4, t5, and t6, after which the recurrence scales the data to arbitrary order.For instance, bbab has one occurrence in t4, three in t5, and five in t6.Source: §4.5 · pp. 12–13, Table 1 · p. 13
4.6 From occurrence starts to coverage formulas
- Scaled occurrence starts and MUS lengths determine their full ambient coverages, converting subsequent classification into a transversal problem on explicit integer intervals.The occurrence correspondence is specialized to trimmed consecutive-generation MUSs, and synchronization ensures no ambient occurrence is created or lost.Source: §4.6 · p. 13, §4.7 · p. 13
5 Stable characterization of the smallest attractors
The section characterizes smallest attractors of finite Thue–Morse words for n≥6 and develops certificates for testing four-position sets. For arbitrary-cardinality attractors, it identifies the complete antichain of inclusion-minimal factor coverages, since a constant number of recent MUS generations is insufficient.
5.1 Three generations of coverage constraints
- Sixteen factors from three consecutive generations suffice to force the two attractor shapes: current-generation coverages set broad regions, previous-generation coverages distinguish arrangements, and second-previous-generation coverages fix endpoints.The argument uses the Ai, Bi, and C3 and C6 coverage constraints.Source: §5.1 · pp. 14–15
5.2 Geometric forcing by sixteen witnesses
- Four pairwise-disjoint witness coverages force a four-position set to place one position in each; these constraints yield the two families and independently prove the lower bound γ(tn)≥4.Together with the construction of four-position attractors, the lower bound gives γ(tn)=4 for n≥6.Source: §5.2 · pp. 15–16
5.3 Why the two forced families are attractors
- Each forced family attracts every factor of length at least two by selecting an endpoint of each canonical boundary, and the one-letter factors are covered as well; reflection gives the second family.The one-letter argument uses homogeneous boundaries, while reflection maps the left family to the right family.Source: §5.3 · pp. 16–17
5.4 Complete classification and the number 32
- The two families {2h + ε1, 3h + ε2, 4h + ε3, 6h + ε4} and {2h + ε1, 4h + ε2, 5h + ε3, 6h + ε4}, with each εi in {0, 1}, consist of attractors; there are exactly 32 smallest attractors.Source: §5 · p. 14, §5.4 · p. 17
5.5 Two constant-size certificates for four-position sets
- For four-position sets, hitting the sixteen-factor witness system is an exact attractor test; alternatively, the 24 MUSs from three consecutive generations give a symmetric certificate.The sixteen-factor system is the smallest witness system used by the proof; the 24-factor system consists of three complete MUS generations.Source: §5.5 · pp. 17–18
5.6 Why three generations are really needed
- Within the hierarchy of one, two, or three consecutive complete MUS generations, depth three is necessary: a four-position set passes the depth-two test but is not an attractor.This optimality claim concerns only that nested hierarchy, not every possible factor certificate.Source: §5.6 · p. 18
5.7 Why the cardinality restriction matters
- The constant-size certificates require exactly four positions: in t6, the five-position set {4, 12, 24, 34, 48} hits all 24 MUS coverages from t6, t5, and t4 but misses bb.Thus it passes the three-generation MUS test without being an attractor.Source: §5.7 · p. 18
- Characterizing attractors of arbitrary cardinality requires the complete antichain of inclusion-minimal factor coverages, rather than only a constant number of recent MUS generations.Source: §5.7 · p. 18
6 Canonical minimal factor coverages
The section characterizes the inclusion-minimal factor coverages of t_n and their recursive, pairwise incomparable structure. It establishes an exact irredundant certificate that grows linearly with n for arbitrary attractors, alongside a constant-size test for four-position attractors.
6 Canonical minimal factor coverages
- For n ≥ 5, the minimal coverages are exactly D_n: the coverages of aa, bb, and the eight MUSs from each generation t_m, 4 ≤ m ≤ n.This gives an exact certificate for attractors of arbitrary cardinality; long coverage constraints descend under the morphism to the order-four MUSs.Source: §6 · p. 19, §6.3 · pp. 21–22
6.1 From minimal coverages to critical factors
- A shortest factor representing an inclusion-minimal coverage is two-sided frequency-critical: deleting either endpoint increases its occurrence count.This converts minimality in the coverage-inclusion order into a local condition on occurrence frequencies.Source: §6.1 · p. 19
6.2 Unique phase and critical descent
- Every factor of t_n of length at least four has a unique morphic phase, and critical factors of length at least five desubstitute to critical factors in t_(n−1).The recursive descent can therefore continue until reaching length four.Source: §6.2 · p. 20
6.3 The critical factors at the base level
- At every ambient order r ≥ 4, the eight two-sided critical length-four factors are exactly MUS(t_4), while the only shorter critical factors are aa, bb, ab, ba, aba, and bab.The four short factors ab, ba, aba, and bab cannot yield minimal coverages because their coverages contain MUS coverages.Source: §6.3 · pp. 21–22
6.4 Occurrence geometry across all generations
- A generation-m MUS coverage is a union of intervals of length 2s + 2, with gaps of at least 4s − 2; its occurrence starts are at least 6s apart.Here s = 2^(m−4); the number of components is determined by the source generation and the ambient order.Source: §6.4 · p. 23
6.5 Why the MUS-derived coverages are incomparable
- All MUS-derived coverages in D_n are pairwise incomparable, both within a generation and across generations.Within one generation, distinct equal-length factors cannot share an occurrence start; across generations, component lengths and occurrence counts rule out either inclusion.Source: §6.5 · p. 23
6.6 The two homogeneous-pair constraints
- No MUS coverage is contained in Cov_tn(aa) or Cov_tn(bb), because every Thue–Morse MUS contains both letters whereas each pair coverage contains positions of only one letter.Source: §6.6 · p. 24
- The two homogeneous-pair coverages are disjoint and incomparable with each other and every MUS-derived coverage, so all members of D_n are pairwise incomparable.Disjointness follows because a position cannot simultaneously carry a and b.Source: §6.6 · p. 24
6.7 The canonical minimal-coverage theorem
- For every n ≥5, the minimal factor coverages are those of aa, bb, and the MUSs of generations 4 through n, totaling 8n −22 distinct constraints.Each new generation contributes eight incomparable MUS-derived constraints.Source: §6.7 · p. 24
- An arbitrary Γ ⊆ [1, 2^n] is an attractor exactly when it intersects every MUS coverage from generations 4 through n; four-position sets need only three recent generations and sixteen witnesses.The arbitrary-attractor certificate has 8n −22 constraints, whereas three generations suffice at cardinality four.Source: §6.7 · p. 24
6.8 Why the certificate is irredundant
- Every exact certificate made of factor coverages must include all 8n −22 minimal coverages, making them the unique minimum exact certificate at the coverage-set level.Different factor names could in principle induce the same coverage.Source: §6.8 · p. 25
6.9 The resulting hierarchy of certificates
- The arbitrary-attractor certificate grows linearly with n, while cardinality restrictions make the certificates for optimum solutions constant-size.This separates the intrinsic complexity of the attractor property from the more rigid geometry of optimum solutions.Source: §6.9 · p. 25
7 The exceptional orders four and five
Orders four and five require separate classifications: t5 adds an exceptional bridge to the stable families, while t4 has a less regular Boolean description. Their results complete the enumeration for n ≥ 4, where γ(t_n) = 4.
7.1 Order five: the stable families plus one exceptional bridge
- At n = 5, the two stable families and an eight-set correlated bridge give exactly 40 smallest attractors.The bridge uses the same offset in its two central positions; it disappears from order six onward.Source: §7.1 · p. 26
7.2 Order four: a finite but genuinely less regular geometry
- At n = 4, smallest attractors have one position in, two in [6], and one in [12, 15], subject to ten clauses.Exactly 87 quadruples satisfy the conditions; the clauses condense the twelve minimal-coverage constraints.Source: §7.2 · pp. 26–27
7.3 Small-order certificates and the complete enumeration
- For arbitrary position sets, t5 attractors are exactly those hitting MUSs of t5, t4, and t3; for t4, they must hit MUSs of t4 and t3.These certificates do not require the set to have four positions.Source: §7.3 · p. 27
- The complete smallest-attractor counts are 87 for t4, 40 for t5, and 32 for every n ≥ 6.The order-four and order-five classifications join the stable theorem to cover every n ≥ 4 for which γ(t_n) = 4.Source: §7.3 · p. 27
8 Independent computational verification
An independent implementation checks the symbolic results, using direct factor and coverage computations and exhaustive transversal search. It certifies finite exceptional cases and checks uniform proof ingredients over finite ranges, but is not itself a proof of the uniform theorems.
8.1 A verifier that does not assume the answer
- The verifier independently constructs t_n, enumerates its factors and occurrence coverages, computes minimal coverages, and searches transversals up to size four.Its exhaustive branching selects an unhit coverage and explores every position in it, without pruning by expected attractor families or counts.Source: §8.1 · pp. 27–28
8.2 Exhaustive finite data
- For t4 and t5, exhaustive search finds no transversal of size at most three and recovers exactly the classified smallest-attractor sets.It also reconstructs both minimal-coverage antichains independently.Source: §8.2 · p. 28
8.3 Checks of the uniform ingredients
- The program checks the MUS-lifting identity and occurrence equality over finite ranges, and verifies all 32 proposed stable attractors for 6 ≤ n ≤ 9.It also checks the paired-boundary property against factors of t4 through t9.Source: §8.3 · p. 28
- For n = 5 through 9, the program independently verifies the canonical minimal-coverage count 8n − 22 and its antichain properties.The reported counts are 18, 26, 34, 42, and 50, respectively.Source: §8.3 · pp. 28–29
8.4 A second check of the interval geometry
- For every multiple h = 4k ≥ 8, interval-cell analysis finds exactly two four-cell products hitting the sixteen witnesses, corresponding to the two stable families.A separate MUS-lifting check verifies that the intervals are the claimed factor coverages.Source: §8.4 · p. 29
9 Discussion
The discussion explains why the number of smallest attractors stabilizes at 32, contrasts the linear-size certificate for arbitrary attractors with constant-size certificates at optimum cardinality, and distinguishes Thue–Morse-specific mechanisms from more portable ideas.
9.1 Why the number of smallest attractors stabilizes
- For n ≥6, five separated boundary pairs leave 2 · 2^4 = 32 smallest attractors; at n = 5, overlapping central positions account for the exceptional count of 40.The transition occurs when the relevant intervals become separated.Source: §9.1 · pp. 29–30
9.2 Canonical constraints versus optimum certificates
- For arbitrary attractors, 8n −22 incomparable coverages form an irredundant certificate; with four positions, 24 MUS coverages from three generations suffice and 16 witnesses force the geometry.The unrestricted system captures intrinsic constraint complexity, while the smaller system uses the rigidity of a four-position transversal.Source: §9.2 · p. 30
9.3 What is specific to Thue–Morse?
- The explicit boundary geometry, eight MUSs per generation, stable families, and trimmed recurrence depend on special features of Thue–Morse.The recurrence also depends on the binary uniform morphism and the closed MUS description.Source: §9.3 · p. 30
- Coverage minimization and canonical irredundancy are general, while synchronization suggests a possible template for other uniformly morphic families with manageable critical factors.The paper presents transfer to other families as a direction, not an established result; it does not claim bounded-depth certificates for every uniformly morphic family.Source: §9.3 · p. 30
9.4 The role of occurrence transport
- Occurrence transport computes the full ambient coverage of source-word MUSs after they acquire multiple occurrences in later generations.The exact doubling law makes these coverages computable from constant base data, supporting both the linear certificate and the constant-size witness system.Source: §9.4 · p. 31
9.5 Computation as verification rather than discovery in the proof
- Computation supports the structural proof by resolving finite exceptional cases and checking definitions, intervals, and indexing across a range of orders.The proof, rather than exhaustive computation, explains stabilization, the value 32, certificate depth three, and the count 8n −22.Source: §9.5 · p. 31
10 Conclusion
The conclusion characterizes all smallest attractors of finite Thue–Morse words and the inclusion-minimal coverage constraints defining attractors. It also gives a smaller certificate for optimum four-position sets.
10 Conclusion
- For n ≥6, exactly 32 smallest attractors arise from two reflected families with independent endpoint choices; the counts from orders four onward are 87, 40, 32, 32, ….The stable families select endpoints of four recursive boundary pairs.Source: §10 · p. 31
- For n ≥5, the minimal-coverage antichain comprises the coverages of aa, bb, and eight MUSs from each generation 4 through n, totaling 8n −22 constraints.This is the unique irredundant exact certificate at the factor-coverage level for attractors of arbitrary cardinality.Source: §10 · p. 31
- For optimum four-position sets, 24 MUSs from three consecutive generations give an exact certificate, and 16 witnesses force the geometry; depth three is necessary within that hierarchy.The resulting picture has a linear-size constraint system for arbitrary attractors and a constant-size certificate at optimum cardinality.Source: §10 · p. 31
A Finite coverage tables for t4 and t5
The appendix records finite data underlying Propositions 7.2 and 7.1.
A Finite coverage tables for t4 and t5
- The appendix records the finite data underlying Propositions 7.2 and 7.1.These tables concern finite coverage data.Source: A Finite coverage tables for t4 and t5 · p. 33
- Proposition 3.2 reduces the attractor property to the inclusion-minimal coverage antichain.That reduction underlies the interpretation of the appendix tables as certificates.Source: A Finite coverage tables for t4 and t5 · p. 33
- The tables are complete finite certificates, not merely collections of necessary conditions.Their completeness follows from the stated reduction.Source: A Finite coverage tables for t4 and t5 · p. 33
A.1 The twelve minimal coverages of t4
The appendix identifies the twelve inclusion-minimal coverages for t4 and reports how their four-position hitting sets are counted.
A.1 The twelve minimal coverages of t4
- For t4, 12 of 99 distinct factor coverages are inclusion-minimal, comprising eight MUSs of t4 and four relevant MUSs of t3.The word has 100 distinct nonempty factors.Source: §A.1 · p. 33
- Every four-position hitting set of the twelve coverages places one point in, two in [6], and one in [12, 15].The listed coverages include aa, bb, and the relevant MUS factors.Source: §A.1 · p. 33
- Direct counting by ℓ yields 10 + 21 + 28 + 28 = 87 four-position solutions.Source: §A.1 · p. 33
A.2 The eighteen minimal coverages of t5
The section identifies all eighteen inclusion-minimal factor coverages of t5 and uses them to classify its four-position attractors, totaling 40.
A.2 The eighteen minimal coverages of t5
- The 18 minimal coverages comprise eight current-generation coverages and ten additional minimal coverages, including those for aa and bb.The listed masks include abaabb among the current-generation coverages and repeated occurrence intervals for aa and bb among the remaining ten.Source: §A.2 · p. 33
- t5 has 392 distinct nonempty factors and 391 distinct factor coverages.Source: §A.2 · p. 33
- Every four-position transversal contains one position in each of {8, 9} and {24, 25}, with its central pair in one of three classes.The classes are {12, 13} × {16, 17}, {(14, 18), (15, 19)}, and {16, 17} × {20, 21}.Source: §A.2 · p. 34
- 40 four-position attractors of t5 arise from three central-pair classes, with 16, 8, and 16 attractors, respectively.The outer choices are independent.Source: §A.2 · p. 34
B Details of the independent verification
An independent verifier checks the paper’s symbolic descriptions through exhaustive enumeration and tests; the cited Thue–Morse literature uses differing index conventions that can be translated.
B Details of the independent verification
- The verifier independently enumerates factors, overlapping occurrences, and coverage sets, then exhaustively searches hitting sets by branching on positions in unhit constraints.Its construction follows the definitions directly and does not reuse helper routines from the derivation program.Source: B Details of the independent… · p. 34
- The verifier also checks the complete t4 and t5 antichains, trimmed MUS identity and occurrence transport through order ten, and the centered/paired-boundary property through t9.It records a depth-two counterexample and a five-position limitation for the stable MUS certificate.Source: B Details of the independent… · p. 34
- Checks include exhaustive attractor-set agreement with Propositions 7.1 and 7.2, proposed stable attractors for 6 ≤ n ≤ 9, and critical-factor lists and descent through order nine.Source: B Details of the independent… · p. 34
C Indexing conventions in the cited Thue–Morse literature
- Kishi et al.’s indexing uses Ti = ti−1, so their MUS formula translates to Theorem 4.1 by substituting m = i − 1.The length formulas |Ti| = 2i−1 and |tn| = 2n agree under that shift.Source: C Indexing conventions in the cited… · p. 34