Proof of Lemma 8, p. 17 — every text character has a sampled occurrence
ProvedGagieRIndex.Kmers.sampled_characterburrows-wheeler-transformp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1strings
Let be a terminated text with a suffix array and BWT run-boundary samples. Every text character appears at a sampled text position:
This is the single-character base case of the primary-occurrence statement in Lemma 8.
Formalization Note The index is required to lie in ; the sampled set consists of text positions, not suffix-array cells.
Preamble
import Mathlib import Definitions.Def_GagieRIndex_Locate_Core
Formal statement
namespace GagieRIndex.Kmers
theorem sampled_character (n σ : ℕ) (T SA : ℕ → ℕ)
(hT : GagieRIndex.Locate.IsText n σ T) (hSA : GagieRIndex.Locate.IsSuffixArray n T SA)
(i : ℕ) (hi : 1 ≤ i) (hin : i ≤ n) :
∃ i' ∈ GagieRIndex.Locate.sampled n T SA, T i' = T i := by sorry
end GagieRIndex.Kmers
Source
Gagie, Navarro, Prezza, Fully-Functional Suffix Trees and Optimal Text Searching in BWT-runs Bounded Space, arXiv:1809.02792v2, p. 17, proof of Lemma 8, second sentence
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.