Lemma 3.5 — split perturbation
ProvedStableMSR.Recovery.split_perturbationclusteringp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1perturbation-stabilitysum-of-radii
Let be any nonsingleton subset of a finite real metric, with radius , and let . There are an optimal center , a point , and one symmetric -perturbation that changes only internal pairs of , such that
The perturbation need not be a metric. Both radius statements use the same perturbation. This is the local construction used in the merge-and-split inequality.
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 split_perturbation {n : ℕ} (d : Point n → Point n → ℝ)
(hd : IsMetricArray d) (γ : ℝ) (hγ : 1 < γ)
(C : Cluster n) (hC : 2 ≤ C.card) :
∃ c p : Point n, OptimalCenter d C c ∧ p ∈ C ∧ p ≠ c ∧
∃ d' : Point n → Point n → ℝ, Perturbation d γ d' ∧
(∀ x y, ¬ (x ∈ C ∧ y ∈ C) → d' x y = d x y) ∧
radius d' C = γ * radius d C ∧ radius d' (C.erase p) ≤ radius d C := by sorry
end StableMSR.Recovery
Source
Shyam Ravichandran, Lev Reyzin, STOC 2027 submission #1010 (October 2026), Lemma 3.5, p. 5; PDF SHA256 8bb34b0b6d31458fe6fc0848c1fc82a6083f3e9ae672e748d24cf82d5289e53e
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.