Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Deterministic recovery program at each fixed rational stability parameter

Open
StableMSR.Recovery.rational_recovery_program

by lreyzin · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

clusteringperturbation-stabilitysum-of-radii

There are absolute positive integers a,ba,ba,b such that, for every rational ε∈(0,1)\varepsilon\in(0,1)ε∈(0,1), one can choose a finite admissible deterministic program PPP before seeing any input instance. For every finite real metric ddd on nnn points and every 1≤k≤n1\le k\le n1≤k≤n, the actual interpreter execution of PPP halts within

a nbE(ε)a\,n^{bE(\varepsilon)}anbE(ε)

steps and charged work, where EEE is the exact Table 2 parameter envelope. Its output assigns each point a label in {0,…,k−1}\{0,\ldots,k-1\}{0,…,k−1} and uses every label. If the instance has a (1+ε)(1+\varepsilon)(1+ε)-stable optimum under arbitrary symmetric perturbations, the decoded output equals that optimum.

The constants a,ba,ba,b are independent of ε,n,k,d\varepsilon,n,k,dε,n,k,d. The same halting and output guarantees hold on unstable inputs, and the n=k=1n=k=1n=k=1 case is included. The program receives only the canonical inputs n,k,dn,k,dn,k,d, with the two unused scalar slots fixed to zero; neither a stable optimum nor a certificate is input advice.

This is the remaining program-construction obligation for the recovery theorem, covering the deterministic search, local solver, order-family enumeration, and their implementation costs. The separate output-decoding lemma supplies feasibility from the validated labels; the separate parameter bound and rational calibration extend this statement to every real stability factor.

Preamble
import Definitions.Def_StableMSR_Recovery_Execution

set_option autoImplicit false
open scoped Classical
Formal statement
namespace StableMSR.Recovery

/-- Uniform deterministic programs for rational stability parameters. The program
is selected before any input instance, and its charged interpreter execution
writes all k nonempty cluster labels. -/
theorem rational_recovery_program :
    ∃ a b : ℕ, 0 < a ∧ 0 < b ∧
      ∀ ε₀ : ℚ, 0 < ε₀ → ε₀ < 1 →
        ∃ P : MinSumFPT.Program, DeterministicProgram P ∧
          ∀ (n k : ℕ) (d : Point n → Point n → ℝ),
            1 ≤ k → k ≤ n → IsMetricArray d →
            ∃ t ≤ a * n ^ (b * parameterEnvelope (ε₀ : ℝ)),
              let s := execute P n k d t
              s.halted = true ∧
                s.work ≤ a * n ^ (b * parameterEnvelope (ε₀ : ℝ)) ∧
                ValidLabels n k s ∧
                ∀ O, Stable d k (1 + (ε₀ : ℝ)) O → outputPartition n k s = O := by sorry

end StableMSR.Recovery
Source
Ravichandran and Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547v1, https://arxiv.org/html/2611.03547v1, Theorem 1.1; Section 4.4; Appendices A.4-A.6 and B; Appendix A.5 final paragraph (fixed rational parameter reduction).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me