AFTD Auto-Formalizing Theoretical Domains

word_occurrence_coverage_subset

theoremverified

Every coverage Cov_w(x) is a set of positions of w, i.e. contained in [1, |w|].

Statement

theorem word_occurrence_coverage_subset {α : Type*} [DecidableEq α] (w x : List α) :
    word_occurrence_coverage w x ⊆ Finset.Icc 1 w.length
Source
Sanity lemma for word_occurrence_coverage (arXiv:2610.10950 (Smallest String Attractors and Minimal Coverage Certificates of Thue–Morse Words), Sec. 3.1).
Verified
12 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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…
Used by 4

The proof, explained

To show that every position in the coverage of x in w lies in [1, |w|], we consider an arbitrary position q in the coverage and obtain an occurrence start position p ∈ [1, |w|] such that q ∈ [p, p + |x| - 1]. Taking lengths of both sides of the occurrence match equation shows that |x| ≤ |w| - (p - 1), meaning the occurrence cannot extend beyond the end of w. Linear arithmetic then immediately establishes 1 ≤ q ≤ |w|.

  1. Every element q of the coverage belongs to an interval [p, p + |x| - 1] for some occurrence start position p ∈ [1, |w|], and it suffices to show 1 ≤ q ≤ |w|.

    Let q be an arbitrary position in the coverage of x in w. By expanding the definition of coverage as the union of intervals [p, p + |x| - 1] over all p ∈ [1, |w|] satisfying take(|x|, drop(p - 1, w)) = x, we obtain a witness position p such that 1 ≤ p ≤ |w|, the occurrence equation holds, and p ≤ q ≤ p + |x| - 1. The goal reduces to showing 1 ≤ q ≤ |w|.

    lines 3–6

    uses word_occurrence_coverage, Finset.mem_biUnion, Finset.mem_filter, Finset.mem_Icc

      intro q hq
      simp only [word_occurrence_coverage, Finset.mem_biUnion, Finset.mem_filter,
        Finset.mem_Icc] at hq ⊢
      obtain ⟨p, ⟨⟨hp1, hpw⟩, hocc⟩, hpq, hqx⟩ := hq
  2. min(|x|, |w| - (p - 1)) = |x|

    Taking the length of both sides of the occurrence equation take(|x|, drop(p - 1, w)) = x yields |take(|x|, drop(p - 1, w))| = |x|. Rewriting the left-hand side with the formulas for the length of a prefix (List.length_take) and the length of a suffix (List.length_drop) produces min(|x|, |w| - (p - 1)) = |x|.

    lines 7–8

    uses congrArg, List.length_take, List.length_drop

      have hlen := congrArg List.length hocc
      rw [List.length_take, List.length_drop] at hlen
  3. 1 ≤ q ≤ |w|

    From min(|x|, |w| - (p - 1)) = |x|, we have |x| ≤ |w| - (p - 1), which implies p + |x| - 1 ≤ |w|. Combined with p ≤ q ≤ p + |x| - 1 and 1 ≤ p, this yields 1 ≤ q ≤ |w|. Linear integer arithmetic (omega) closes the goal.

    line 9

      omega
word_occurrence_coverage
The definition of word occurrence coverage: the union of intervals [p, p + |x| - 1] over all positions p ∈ [1, |w|] at which x occurs in w.
Finset.mem_biUnion
An element b belongs to a union of finsets ⋃_{a ∈ s} t(a) if and only if there is some a ∈ s such that b ∈ t(a).
Finset.mem_filter
An element a belongs to {x ∈ s | p(x)} if and only if a ∈ s and p(a) holds.
Finset.mem_Icc
An element x belongs to the closed discrete interval [a, b] if and only if a ≤ x and x ≤ b.
congrArg
Equality is preserved under function application: if a₁ = a₂, then f(a₁) = f(a₂).
List.length_take
The length of the prefix obtained by taking the first i elements of a list l is min(i, |l|).
List.length_drop
The length of the suffix obtained by dropping the first i elements of a list l is |l| - i.

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

theorem word_occurrence_coverage_subset {α : Type*} [DecidableEq α] (w x : List α) :    word_occurrence_coverage w x ⊆ Finset.Icc 1 w.length := by  intro q hq  simp only [word_occurrence_coverage, Finset.mem_biUnion, Finset.mem_filter,    Finset.mem_Icc] at hq ⊢  obtain ⟨p, ⟨⟨hp1, hpw⟩, hocc⟩, hpq, hqx⟩ := hq  have hlen := congrArg List.length hocc  rw [List.length_take, List.length_drop] at hlen  omega
See it in the graphDiscuss this resultChallenge it