The Fine–Wilf periodicity lemma
ProvedFamousTheorems.fine_wilf_periodicity_lemmaThe Fine–Wilf periodicity lemma. Let be a word with periods and , and suppose . Then is also a period of .
A word has period if whenever both positions exist. Fine and Wilf proved this in 1965, and the length bound is sharp. The lemma is fundamental in combinatorics on words and in string-matching algorithms.
Formalization note. Mathlib's List.HasPeriod.gcd. Words are lists, and w.HasPeriod p says that has period . Natural-number subtraction is truncated, which does not matter here since .
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem fine_wilf_periodicity_lemma {α : Type*} {w : List α} {p q : ℕ} (hp : w.HasPeriod p) (hq : w.HasPeriod q)
(hlen : p + q - Nat.gcd p q ≤ w.length) :
w.HasPeriod (Nat.gcd p q) := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `List.HasPeriod.gcd`. Proof here reduces to that Mathlib result.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.