Lemma 3.9 — local cluster density
ProvedStableMSR.Recovery.local_cluster_densityclusteringp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1perturbation-stabilitysum-of-radii
Assume , , and a -stable instance with optimum . Write , , , , , , and .
- Every union of at least small optimal clusters has radius greater than .
- For every and ,
- For every and ,
All three clauses are retained, and only the small-cluster counting bound has the threshold . These bounds supply the density input for the partition and treewidth arguments.
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 local_cluster_density {n : ℕ} (d : Point n → Point n → ℝ) (hd : IsMetricArray d)
(k : ℕ) (hk : 1 ≤ k ∧ k ≤ n) (γ : ℝ) (hγ : 1 < γ ∧ γ < 2) (hkn : k < n)
(O : Partition n) (hO : Stable d k γ O) :
(∀ F : Partition n, F ⊆ smallClusters d O (γ - 1) →
(largeClusters d O (γ - 1)).card + 1 ≤ F.card →
(γ - 1) * largeMass d O (γ - 1) < radius d (F.biUnion id)) ∧
(∀ x : Point n, ∀ u : ℝ, 0 ≤ u → u ≤ densityScale d O (γ - 1) →
((meeting (smallClusters d O (γ - 1)) (ball d x u)).card : ℝ) ≤
1 + (2 * u + 2 * smallThreshold d O (γ - 1)) /
((γ - 1) * smallThreshold d O (γ - 1))) ∧
(∀ x : Point n, ∀ u : ℝ, 0 ≤ u →
((meeting (largeClusters d O (γ - 1)) (ball d x u)).card : ℝ) ≤
(u + 2 * largestRadius d O) / smallThreshold d O (γ - 1)) := by sorry
end StableMSR.Recovery
Source
Shyam Ravichandran, Lev Reyzin, STOC 2027 submission #1010 (October 2026), Lemma 3.9, p. 7; PDF SHA256 8bb34b0b6d31458fe6fc0848c1fc82a6083f3e9ae672e748d24cf82d5289e53e
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.