AFTD Auto-Formalizing Theoretical Domains

fibonacci_string_attractor_iff_meets_basis

theoremverified

For any natural number n, assuming the inclusion-minimal factor coverages of F_n are exactly the coverages of the basis B_n (word_min_factor_coverages (fibonacci_word n) = {word_occurrence_coverage (fibonacci_word n) u | u ∈ fibonacci_attractor_basis n}), a position set Γ ⊆ [1, |F_n|] is a string attractor of F_n if and only if Γ intersects the occurrence coverage word_occurrence_coverage (fibonacci_word n) u for every basis word u ∈ fibonacci_attractor_basis n.

Statement

theorem fibonacci_string_attractor_iff_meets_basis (n : ℕ)
    (hbasis : word_min_factor_coverages (fibonacci_word n) =
      {word_occurrence_coverage (fibonacci_word n) u | u ∈ fibonacci_attractor_basis n})
    (Γ : Finset ℕ) (hΓ : Γ ⊆ Finset.Icc 1 (fibonacci_word n).length) :
    is_string_attractor (fibonacci_word n) Γ ↔
      ∀ u ∈ fibonacci_attractor_basis n, (Γ ∩ word_occurrence_coverage (fibonacci_word n) u).Nonempty
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 6
  • 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…
  • is_string_attractorA set Γ ⊆ [1, |w|] of positions is a string attractor of the finite word w if Γ ∩ Cov_w(x) ≠ ∅ for every nonempty factor x of w.
  • 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…
  • word_min_factor_coveragesH_min(w): the inclusion-minimal members of H(w), the family of factor coverages of w.
  • is_string_attractor_iff_forall_min_factor_coverageFor every finite word w and every Γ ⊆ [1, |w|], Γ is a string attractor of w if and only if Γ ∩ C ≠ ∅ for every inclusion-minimal factor…
  • 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

For every natural number n, assuming hypothesis 'hbasis'—that the set of inclusion-minimal factor coverages of the n-th Fibonacci word 'fibonacci_word n' equals the set of occurrence coverages of the words in 'fibonacci_attractor_basis n'—and for every finite set of natural numbers Γ such that Γ ⊆ {1, ..., |fibonacci_word n|}: Γ is a string attractor for 'fibonacci_word n' if and only if for every word u in 'fibonacci_attractor_basis n', the intersection of Γ with the occurrence coverage of u in 'fibonacci_word n' is nonempty.

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

A set of positions is a string attractor for a word if and only if it intersects every inclusion-minimal factor coverage of that word. Under the hypothesis that the minimal factor coverages of the n-th Fibonacci word are precisely the coverages of the words in the attractor basis, the attractor condition reduces to checking coverage intersection for elements of this basis. The equivalence is established by rewriting with this characterization and unpacking the set-builder definition of the basis coverages.

  1. Being a string attractor for the n-th Fibonacci word is equivalent to intersecting every coverage in the basis coverage family.

    Applying the lemma is_string_attractor_iff_forall_min_factor_coverage reduces the string attractor property to intersecting all inclusion-minimal factor coverages. Rewriting with the hypothesis hbasis replaces the set of minimal factor coverages with the set of coverages of the basis words, {word_occurrence_coverage (fibonacci_word n) u | u ∈ fibonacci_attractor_basis n}.

    line 8

    uses is_string_attractor_iff_forall_min_factor_coverage

      rw [is_string_attractor_iff_forall_min_factor_coverage _ _ hΓ, hbasis]
  2. If Γ intersects every set in the basis coverage family, then it intersects the occurrence coverage of each basis word u.

    This establishes the forward direction of the equivalence. For any basis word u ∈ fibonacci_attractor_basis n, its occurrence coverage is in the basis coverage family by definition, so the assumption that Γ meets all sets in the family immediately implies that Γ intersects the coverage of u.

    line 9

      refine ⟨fun h u hu => h _ ⟨u, hu, rfl⟩, ?_⟩
  3. Conversely, if Γ intersects the occurrence coverage of every basis word, then it intersects every set in the basis coverage family.

    For the reverse direction, let C be an arbitrary set in the basis coverage family. By definition of the set comprehension, C = word_occurrence_coverage (fibonacci_word n) u for some basis word u in the attractor basis. Applying the hypothesis to this u shows that Γ ∩ C is nonempty.

    lines 10–11

      rintro h C ⟨u, hu, rfl⟩
      exact h u hu
is_string_attractor_iff_forall_min_factor_coverage
A set of positions Γ is a string attractor for a word w if and only if Γ intersects every inclusion-minimal factor coverage of w.

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

/-- If the minimal factor coverages of F_n are the coverages of B_n, then Γ is a string attractor iff Γ meets every coverage in B_n. -/theorem fibonacci_string_attractor_iff_meets_basis (n : ℕ)    (hbasis : word_min_factor_coverages (fibonacci_word n) =      {word_occurrence_coverage (fibonacci_word n) u | u ∈ fibonacci_attractor_basis n})    (Γ : Finset ℕ) (hΓ : Γ ⊆ Finset.Icc 1 (fibonacci_word n).length) :    is_string_attractor (fibonacci_word n) Γ ↔      ∀ u ∈ fibonacci_attractor_basis n, (Γ ∩ word_occurrence_coverage (fibonacci_word n) u).Nonempty := by  rw [is_string_attractor_iff_forall_min_factor_coverage _ _ hΓ, hbasis]  refine ⟨fun h u hu => h _ ⟨u, hu, rfl⟩, ?_⟩  rintro h C ⟨u, hu, rfl⟩  exact h u hu
See it in the graphDiscuss this resultChallenge it