Lemma A.4 — dyadic scale and successful partition
ProvedStableMSR.Recovery.Supplement.partition_scale_successclusteringp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1perturbation-stability
Let , let , and let be the -stable optimum of the finite metric input. Write , , , , and . If , then . Otherwise there is an integer such that obeys
and RandomPartitions contains a partition splitting at most large clusters with probability at least . This probability is over its single uniform order; every prescribed midpoint radius is enumerated. The constants are , , and , with and .
The statement includes both scale selection and the full probability guarantee.
Differences from the source:
- encoding: Finite ordered metric input and unordered exact-k partitions → Fin n points, real metric arrays, and finite sets of nonempty disjoint blocks; reason: Input-order relabelling preserves every source instance and partition; base published definitions are reused without extra conditions
- encoding: log_2 sigma <= j <= ceil(log_2 n) → Natural j with 9 <= j <= the natural ceiling of logb 2 n; reason: sigma = 512 = 2^9 and n >= 2 under the section hypotheses, so the index sets agree
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_Partitions set_option autoImplicit false open scoped Classical
Formal statement
namespace StableMSR.Recovery.Supplement
theorem partition_scale_success {n k : ℕ} (d : Point n → Point n → ℝ) (γ : ℝ) (O : Partition n)
(hk : 1 ≤ k) (hkn : k < n) (hd : IsMetricArray d) (hγ : 1 < γ ∧ γ < 2)
(hO : Stable d k γ O) :
(densityScale d O (γ - 1) < sigma * largestRadius d O →
(largeClusters d O (γ - 1)).card ≤ fewBound (γ - 1)) ∧
(sigma * largestRadius d O ≤ densityScale d O (γ - 1) →
∃ j : ℕ, 9 ≤ j ∧ j ≤ ⌈Real.logb 2 n⌉₊ ∧
let L := (2 : ℝ) ^ j * largestRadius d O
sigma * largestRadius d O ≤ L ∧ L ≤ densityScale d O (γ - 1) ∧
densityScale d O (γ - 1) < 2 * L ∧ largeMass d O (γ - 1) / L < 8 / (γ - 1) ∧
(orderLaw (netVertices d (largestRadius d O) L))
{π | ∃ Q ∈ randomPartitions d (γ - 1) (largestRadius d O) L π,
splitCount d O (γ - 1) Q ≤ splitBound (γ - 1)} ≥ (1 / 3 : ENNReal)) := by sorry
end StableMSR.Recovery.Supplement
Source
Shyam Ravichandran, Lev Reyzin, STOC 2027 submission #1010 (October 2026), Lemma A.4, p. 20; PDF SHA256 8bb34b0b6d31458fe6fc0848c1fc82a6083f3e9ae672e748d24cf82d5289e53e