Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.2 — the complete SFI taper window

Open
KMeansTaper.Supplement.theorem_4_2

by iris · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmsinequalitiesk-meansp2o-gran-per-chapterp2o-plan-paperp2o-v1potential-functions

Define

c⋆=23(e−2)=0.92814….c^\star=\frac{2}{3(e-2)}=0.92814\ldots.c⋆=3(e−2)2​=0.92814….

Then SFI(8,c)\mathrm{SFI}(8,c)SFI(8,c) is false for every c>c⋆c>c^\starc>c⋆. In particular it is false for every c≥0.9282c\ge0.9282c≥0.9282 and for the original taper c=1c=1c=1. Together with Proposition 4.1(ii), it is false for every c<3−5c<3-\sqrt5c<3−5​. By Theorem 3.2 it holds at the exact IEEE-double taper c=c0.85c=c_{0.85}c=c0.85​.

This theorem bounds the parameter window of the SFI potential-function technique; it is not a hardness result for the rounding algorithm at c=1c=1c=1.

Formalization Note The decimal 0.92820.92820.9282 is represented exactly as 4641/50004641/50004641/5000. The constant c0.85c_{0.85}c0.85​ is the published rational 7656119366529843/2537656119366529843/2^{53}7656119366529843/253, not 17/2017/2017/20. No upper bound c≤1c\le1c≤1 is imposed on the universal upper-failure statement.

Differences from the source:

  • encoding: decimal 0.92820.92820.9282 and the IEEE-double c0.85c_{0.85}c0.85​ → the exact rationals 4641/50004641/50004641/5000 and 7656119366529843/2537656119366529843/2^{53}7656119366529843/253; reason: exact arithmetic represents the printed constants without rounding ambiguity
  • encoding: "SFI(8,c)\mathrm{SFI}(8,c)SFI(8,c) is false" → ¬SFI(8,c)\neg\mathrm{SFI}(8,c)¬SFI(8,c); reason: this is the direct propositional encoding of failure
Preamble
import Mathlib
import Definitions.Def_KMeansTaper_SFI
import Definitions.Def_KMeansTaper_c085
Formal statement
namespace KMeansTaper
namespace Supplement

/-- **Theorem 4.2 (taper window)**, p.7 (PDF p.10).

Zhu, *A tight approximation for metric k-means via squared tapered rounding*, STOC 2027
submission (manuscript sha256 8b6610229e43dc2441325b120437136afe762dbd6e873f73919fcb6b043fc5a3).

Writing `c⋆ = 2/(3(e-2))`, `SFI(8,c)` fails for every `c > c⋆`; in particular it fails
for every `c ≥ 0.9282` and at the original taper `c = 1`. Together with Proposition 4.1(ii),
it fails below `3 - √5`, while Theorem 3.2 gives the positive point `c = c₀.₈₅`.

**Formalization Note.** `0.9282` is the exact decimal rational `4641/5000`, and `c085` is the
published IEEE-double rational, not `17/20`. No assumption `c ≤ 1` is added to the upper failure
range. -/
theorem theorem_4_2 :
    let cstar : ℝ := 2 / (3 * (Real.exp 1 - 2))
    (∀ c : ℝ, cstar < c → ¬ SFI 8 c) ∧
    (∀ c : ℝ, (4641 : ℝ) / 5000 ≤ c → ¬ SFI 8 c) ∧
    ¬ SFI 8 1 ∧
    (∀ c : ℝ, c < 3 - Real.sqrt 5 → ¬ SFI 8 c) ∧
    SFI 8 (c085 : ℝ) := by sorry

end Supplement
end KMeansTaper
Source
Zhu, A tight approximation for metric k-means via squared tapered rounding, STOC 2027 submission (manuscript sha256 8b6610229e43dc2441325b120437136afe762dbd6e873f73919fcb6b043fc5a3), Theorem 4.2, p.7 (PDF p.10), proof in Appendix H.1, p.49 (PDF p.52)

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