Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

(15)–(16) and the final chain — d(s′, t′_i) ≤ (1 + 1/(2r−1) + 3εr)·d_opt

Proved
ClosestString.PTAS.eq_15_16

by mikedeng1 · Oct 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmclosest-substringhamming-distancep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

Let s,fs,fs,f be strings of length LLL, t1,…,tnt_1,\dots,t_nt1​,…,tn​ and t1′,…,tn′t'_1,\dots,t'_nt1′​,…,tn′​ strings of length LLL, d≥0d\ge0d≥0 an integer with d(s,ti)≤dd(s,t_i)\le dd(s,ti​)≤d for every iii, QQQ a set of positions with complement PPP, r≥1r\ge1r≥1 and ε≥0\varepsilon\ge0ε≥0. Let s∗s^*s∗ be sss on PPP and fff on QQQ. Assume

  1. (Fact 1) dQ(tl,f)−dQ(tl,s)≤d/(2r−1)d^Q(t_l,f)-d^Q(t_l,s)\le d/(2r-1)dQ(tl​,f)−dQ(tl​,s)≤d/(2r−1) for every lll;
  2. ∣P∣≤r d|P|\le r\,d∣P∣≤rd;
  3. (Fact 2) d(s∗,ti′)≤d(s∗,ti)+2ε∣P∣d(s^*,t'_i)\le d(s^*,t_i)+2\varepsilon|P|d(s∗,ti′​)≤d(s∗,ti​)+2ε∣P∣ for every iii;
  4. xxx solves problem (8) for (t′,P,dQ(ti′,f))(t',P,d^Q(t'_i,f))(t′,P,dQ(ti′​,f)) within error ε∣P∣\varepsilon|P|ε∣P∣: d(ti′∣P,x)+d(ti′∣Q,f∣Q)≤d0+ε∣P∣d(t'_i|_P,x)+d(t'_i|_Q,f|_Q)\le d_0+\varepsilon|P|d(ti′​∣P​,x)+d(ti′​∣Q​,f∣Q​)≤d0​+ε∣P∣ for every iii, where d0=min⁡xmax⁡i(d(ti′∣P,x)+d(ti′∣Q,f∣Q))d_0=\min_x\max_i\big(d(t'_i|_P,x)+d(t'_i|_Q,f|_Q)\big)d0​=minx​maxi​(d(ti′​∣P​,x)+d(ti′​∣Q​,f∣Q​)).

Then the string s′s's′ with s′∣P=xs'|_P=xs′∣P​=x and s′∣Q=f∣Qs'|_Q=f|_Qs′∣Q​=f∣Q​ satisfies, for every iii,

d(s′,ti′) ≤ (1+12r−1+3εr)d.d(s',t'_i)\ \le\ \Big(1+\frac1{2r-1}+3\varepsilon r\Big)d.d(s′,ti′​) ≤ (1+2r−11​+3εr)d.

In the paper sss is an optimal center, d=doptd=d_{\mathrm{opt}}d=dopt​ and f=ti1f=t_{i_1}f=ti1​​; the chain passes through (15), d(s∗,ti′)≤(1+12r−1+2εr)doptd(s^*,t'_i)\le(1+\frac1{2r-1}+2\varepsilon r)d_{\mathrm{opt}}d(s∗,ti′​)≤(1+2r−11​+2εr)dopt​, and (16). It is the deterministic core of Theorem 9.

Differences from the source:

  • reading: (15)–(16) are steps of the proof of Theorem 9 that combine Fact 1, |P| ≤ r d_opt, Fact 2 and the solver's error → a deterministic implication whose premises are those four facts; reason: the paper proves the premises separately (Lemma 1, proof of Theorem 7, Fact 2, Lemma 6); the chain is the step that combines them
  • generalization: Fact 1: |{j ∈ Q | t_{i1}[j] ≠ t_l[j] and t_{i1}[j] ≠ s[j]}| ≤ d_opt/(2r−1) → d^Q(t_l, f) − d^Q(t_l, s) ≤ d/(2r−1); reason: the paper's Fact 1 implies this form, which is the one (15) uses ("d(s∗, ti) = d^P(s, ti) + d^Q(ti1, ti) ≤ d(s, ti) + d_opt/(2r−1)")
  • generalization: s optimal, t_i, t′i substrings of s_i, f = t{i1}, r ≥ 2, ε > 0 → arbitrary strings, any radius bound d, r ≥ 1, ε ≥ 0; reason: the chain uses only the four premises; the paper's setting is a special case
Preamble
import Mathlib
import Definitions.Def_ClosestString_PTAS_Algorithm
Formal statement
namespace ClosestString.PTAS

/-- **(15)–(16) and the final chain** (proof of Theorem 9, Li, Ma & Wang, arXiv:cs/0002012v1,
pp. 11–12), deterministic, for arbitrary strings of length `L`: let `s` be a center with
`d(s, t_i) ≤ d` for all `i`, `f` (the paper's `t_{i1}`) a string, `Q` a position set with
complement `P`, `r ≥ 1`, `ε ≥ 0`, and assume Fact 1 (`d^Q(t_l, f) − d^Q(t_l, s) ≤ d/(2r−1)`),
`|P| ≤ r d`, and Fact 2's event `d(s∗, t′_i) ≤ d(s∗, t_i) + 2ε|P|` with `s∗ = s` on `P`, `f` on `Q`.
If `x` solves problem (8) for `(t′, P, d^Q(t′_i, f))` within error `ε|P|`, then
`s′ = x` on `P`, `f` on `Q` satisfies `d(s′, t′_i) ≤ (1 + 1/(2r−1) + 3εr) d` for every `i`. -/
theorem eq_15_16 {A : Type*} [Fintype A] [DecidableEq A] [Nonempty A] {n L : ℕ}
    (s f : Fin L → A) (t t' : Fin n → Fin L → A) (d : ℕ) (hd : ∀ i, hammingDist s (t i) ≤ d)
    (Q : Finset (Fin L)) (r : ℕ) (hr : 1 ≤ r)
    (hFact1 : ∀ l, (distOn Q (t l) f : ℝ) - distOn Q (t l) s ≤ d / (2 * (r : ℝ) - 1))
    (hP : Qᶜ.card ≤ r * d) (ε : ℝ) (hε : 0 ≤ ε)
    (hFact2 : ∀ i, (hammingDist (splice Qᶜ s f) (t' i) : ℝ)
      ≤ hammingDist (splice Qᶜ s f) (t i) + 2 * ε * Qᶜ.card)
    (x : Fin L → A)
    (hx : ∀ i, (distOn Qᶜ (t' i) x : ℝ) + distOn Q (t' i) f
      ≤ opt8 t' Qᶜ (fun i => distOn Q (t' i) f) + ε * Qᶜ.card) :
    ∀ i, (hammingDist (splice Qᶜ x f) (t' i) : ℝ)
      ≤ (1 + 1 / (2 * (r : ℝ) - 1) + 3 * ε * r) * d := by sorry

end ClosestString.PTAS
Source
Li, Ma & Wang, On the Closest String and Substring Problems, arXiv:cs/0002012v1, p. 11, eq. (15) and p. 12, eq. (16) and the final chain of the proof of Theorem 9
Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 24, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me