AFTD Auto-Formalizing Theoretical Domains

word_occurrence_coverage_nonempty

theoremverified

The coverage of a nonempty factor of w is nonempty.

Statement

theorem word_occurrence_coverage_nonempty {α : Type*} [DecidableEq α] {w x : List α}
    (hx : x ≠ []) (hxw : x <:+: w) : (word_occurrence_coverage w x).Nonempty
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 1

The proof, explained

To show that the coverage of a nonempty factor $x$ in $w$ is nonempty, we decompose $w$ as $s ++ x ++ t$ using the factor assumption. We then exhibit the 1-based starting position $|s| + 1$ as an element of the coverage set. Since $|x| > 0$, this position satisfies the index bounds for an occurrence of $x$, and the factor starting at $|s| + 1$ is identically $x$.

  1. Decomposing $w = s ++ x ++ t$, it suffices to show that the starting index $|s| + 1$ belongs to the coverage of $x$, where $|x| > 0$.

    Since $x$ is an infix (factor) of $w$ ($x <:+: w$), we can write $w = s ++ x ++ t$ for some prefix $s$ and suffix $t$. To show that the coverage of $x$ is nonempty, it suffices to exhibit an element in it; we choose the 1-based position $|s| + 1$ where this occurrence of $x$ begins. Furthermore, since $x$ is nonempty ($x \neq []$), its length is strictly positive by `List.length_pos_iff.2`.

    lines 3–5

    uses List.length_pos_iff.2

      obtain ⟨s, t, rfl⟩ := hxw
      refine ⟨s.length + 1, ?_⟩
      have hlen : 0 < x.length := List.length_pos_iff.2 hx
  2. Membership of $|s| + 1$ in the coverage set reduces to finding an occurrence of $x$ that covers $|s| + 1$.

    Unfolding `word_occurrence_coverage` and rewriting Finset membership with `Finset.mem_biUnion`, `Finset.mem_filter`, `Finset.mem_Icc`, and `List.length_append`, the goal becomes finding a valid starting position $a \in [1, |s| + |x| + |t|]$ where the factor of length $|x|$ is $x$, such that $|s| + 1 \in [a, a + |x| - 1]$.

    lines 6–7

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

      simp only [word_occurrence_coverage, Finset.mem_biUnion, Finset.mem_filter, Finset.mem_Icc,
        List.length_append]
  3. The occurrence at index $a = |s| + 1$ is valid and covers the index $|s| + 1$.

    We instantiate the occurrence position $a$ with $|s| + 1$. The inequalities $1 \le |s| + 1 \le |s| + |x| + |t|$ and $|s| + 1 \le (|s| + 1) + |x| - 1$ follow by linear arithmetic (`omega`) using $|x| > 0$, while $|s| + 1 \le |s| + 1$ holds by reflexivity (`le_rfl`). Finally, dropping $|s|$ elements from $s ++ x ++ t$ leaves $x ++ t$, and taking the first $|x|$ elements yields $x$, which is verified by list simplification (`simp`).

    lines 8–9

    uses le_rfl

      refine ⟨s.length + 1, ⟨⟨by omega, by omega⟩, ?_⟩, le_rfl, by omega⟩
      simp
List.length_pos_iff.2
A list has strictly positive length if it is nonempty.
word_occurrence_coverage
The set of indices covered by occurrences of a factor in a word, defined as the union of intervals $[p, p + |x| - 1]$ over all positions $p$ where $x$ occurs.
Finset.mem_biUnion
An element belongs to a indexed union of finsets if and only if it belongs to the component finset for some index in the base finset.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
Finset.mem_Icc
An element belongs to the closed interval $[a, b]$ if and only if it is between $a$ and $b$ inclusive.
List.length_append
The length of the concatenation of two lists is the sum of their lengths.
le_rfl
The partial order relation $\le$ is reflexive: $a \le a$.

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_nonempty {α : Type*} [DecidableEq α] {w x : List α}    (hx : x ≠ []) (hxw : x <:+: w) : (word_occurrence_coverage w x).Nonempty := by  obtain ⟨s, t, rfl⟩ := hxw  refine ⟨s.length + 1, ?_⟩  have hlen : 0 < x.length := List.length_pos_iff.2 hx  simp only [word_occurrence_coverage, Finset.mem_biUnion, Finset.mem_filter, Finset.mem_Icc,    List.length_append]  refine ⟨s.length + 1, ⟨⟨by omega, by omega⟩, ?_⟩, le_rfl, by omega⟩  simp
See it in the graphDiscuss this resultChallenge it