Lemma 3.4 — restriction of the unique optimum
ProvedStableMSR.Recovery.optimum_restrictionclusteringp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1perturbation-stabilitysum-of-radii
Let be the unique optimal exact- partition in an arbitrary finite metric. If is a nonempty union of its whole clusters, let denote those clusters and . Then
Stability is not required. Centers remain inside their own clusters. This is the uniqueness statement needed to identify a feasible local table entry with the restricted global optimum.
Differences from the source:
- encoding: An arbitrary finite real metric space with fixed input order and unordered clusters → Points are Fin n; clusters and unordered partitions are finite sets; metric arrays are Mathlib metric distances; reason: Relabelling preserves every finite ordered instance, all distance values, and every unordered partition
Preamble
import Definitions.Def_StableMSR_Recovery_Geometry set_option autoImplicit false open scoped Classical
Formal statement
namespace StableMSR.Recovery
theorem optimum_restriction {n : ℕ} (d : Point n → Point n → ℝ) (hd : IsMetricArray d)
(k : ℕ) (hk : 1 ≤ k ∧ k ≤ n)
(O : Partition n) (hO : UniqueOptimal d Finset.univ k O)
(W : Cluster n) (hW : W.Nonempty) (halign : Aligned O W) :
UniqueOptimal d W (restrictPartition O W).card (restrictPartition O W) := by sorry
end StableMSR.Recovery
Source
Shyam Ravichandran, Lev Reyzin, STOC 2027 submission #1010 (October 2026), Lemma 3.4, p. 5; PDF SHA256 8bb34b0b6d31458fe6fc0848c1fc82a6083f3e9ae672e748d24cf82d5289e53e
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.