fibonacci_attractor_basis_seven_coverage_distinct
The cardinality of the image under word_occurrence_coverage (fibonacci_word 7) of fibonacci_attractor_basis 7 is 7, showing that all 7 candidate basis words have distinct occurrence coverages in F_7.
Statement
theorem fibonacci_attractor_basis_seven_coverage_distinct :
((fibonacci_attractor_basis 7).image (word_occurrence_coverage (fibonacci_word 7))).card = 7- Source
- arXiv:2610.10950 Smallest String Attractors and Minimal Coverage Certificates of Thue--Morse Words
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- fibonacci_attractor_basisFor a natural number n, fibonacci_attractor_basis n is the finite set (Finset (List Bool)) formed by the union of: (1) the image under…
- word_occurrence_coverageThe coverage Cov_w(x) of a word x in a finite word w: the union of the intervals [p, p+|x|−1] over all (1-based) occurrence starts p of x…
- fibonacci_wordThe sequence of binary Fibonacci words F_n over Bool, defined by F_0 = [false], F_1 = [false, true], and F_{n+2} = F_{n+1} ++ F_n.
Read back from the Lean
The cardinality of the set of position-coverage sets in the 7th Fibonacci word (fibonacci_word 7) generated by the elements of the Fibonacci attractor basis for $n = 7$ (fibonacci_attractor_basis 7) is equal to 7.
Equivalently: mapping each word in fibonacci_attractor_basis 7 to the set of 1-based indices in fibonacci_word 7 covered by occurrences of that word produces a collection of sets of cardinality 7 (meaning that all basis words yield pairwise distinct non-empty coverage sets).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem asserts that the candidate attractor basis words for the 7th Fibonacci word F_7 have pairwise distinct occurrence coverages, yielding an image set of cardinality 7. Since all objects are finite lists and sets with decidable equality, the proof proceeds entirely by direct computational reflection using `decide`.
The cardinality of the image of the attractor basis under the occurrence coverage function in F_7 is 7. automation
All definitions involved—the Fibonacci word F_7, the 7 attractor basis words (6 singular words and 1 boundary word), their occurrence coverages, and the resulting finite set operations—are finite and effective. The decision procedure `decide` evaluates the expression by pure computation, establishing that the 7 coverage sets are pairwise distinct and hence their image has cardinality 7.
decide
- The entire proof is discharged by computational evaluation via `decide`, calculating the finite lists, their occurrence coverages, and the cardinality of the resulting set directly.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The occurrence coverages of the 7 candidate basis words in B_7 are pairwise distinct in F_7. -/theorem fibonacci_attractor_basis_seven_coverage_distinct : ((fibonacci_attractor_basis 7).image (word_occurrence_coverage (fibonacci_word 7))).card = 7 := by decide