Theorem 4.2 — the complete SFI taper window
OpenKMeansTaper.Supplement.theorem_4_2approximation-algorithmsinequalitiesk-meansp2o-gran-per-chapterp2o-plan-paperp2o-v1potential-functions
Define
Then is false for every . In particular it is false for every and for the original taper . Together with Proposition 4.1(ii), it is false for every . By Theorem 3.2 it holds at the exact IEEE-double taper .
This theorem bounds the parameter window of the SFI potential-function technique; it is not a hardness result for the rounding algorithm at .
Formalization Note The decimal is represented exactly as . The constant is the published rational , not . No upper bound is imposed on the universal upper-failure statement.
Differences from the source:
- encoding: decimal and the IEEE-double → the exact rationals and ; reason: exact arithmetic represents the printed constants without rounding ambiguity
- encoding: " is false" → ; 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)