AFTD Auto-Formalizing Theoretical Domains

fibonacci_attractor_basis_seven_coverage_distinct

theoremverified

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`.

  1. 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.

    line 4

      decide

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

/-- 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
See it in the graphDiscuss this resultChallenge it