Proof of Theorem 7 — |P| ≤ r·d_opt: an r-tuple disagrees on at most r·d_opt positions
ProvedClosestString.PTAS.card_diff_leclosest-stringcombinatoricshamming-distancep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be strings of one length, a string of that length and with for every . For any indices (repetitions allowed) let be the positions where do not all agree. Then
At every position of at least one of the strings differs from the center. The bound is used in the proof of Theorem 9 (p. 11) to turn the additive error into .
Differences from the source:
- generalization: s an optimal center, d_opt its radius, an r-element subset of the strings → any center c, any radius bound d, any r-tuple of indices (repetitions allowed), any r ≥ 0; reason: the argument uses only d(u_i, c) ≤ d; the paper's subsets and Theorem 9's tuples (with u = t) are special cases
- encoding: positions 1..m, indices 1..n, s_{i1} → 0-based Fin m, Fin n; s_{i1} is u (idx 0); reason: relabelling; changes no instance
Preamble
import Mathlib import Definitions.Def_ClosestString_PTAS_Basic
Formal statement
namespace ClosestString.PTAS
/-- **`|P| ≤ r × d_opt`** (proof of Theorem 7, Li, Ma & Wang, arXiv:cs/0002012v1, p. 7; used again
in the proof of Theorem 9, p. 11): for any strings `u_1, …, u_n` of one length, any center `c` with
`d(u_i, c) ≤ d` for all `i`, and any `r`-tuple of indices `idx`, the positions where
`u_{idx 0}, …, u_{idx (r-1)}` do not all agree number at most `r · d`. -/
theorem card_diff_le {A : Type*} [DecidableEq A] {n m : ℕ} (u : Fin n → Fin m → A)
(c : Fin m → A) (d : ℕ) (hd : ∀ i, hammingDist (u i) c ≤ d) (r : ℕ) (idx : Fin r → Fin n) :
(agreeSet u idx)ᶜ.card ≤ r * d := by sorry
end ClosestString.PTAS
Source
Li, Ma & Wang, On the Closest String and Substring Problems, arXiv:cs/0002012v1, p. 7, proof of Theorem 7 (restated as "|P| ≤ r d_opt" in the proof of Theorem 9, p. 11)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.