Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A total binary verifier for sum-of-radii instability

Definition
StableMSR_Recovery_Supplement_BinaryVerifier

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

algorithmsclusteringcomputational-complexity

The algorithm reconstructs canonical candidate fields, validates the source metric and both labelings, checks the applicable perturbation inequalities, and compares the two exact sums of radii. It compares equality of partitions independently of the label names. Every iteration is bounded by the length of a decoded list, including on malformed inputs.

Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_Languages

set_option autoImplicit false

namespace StableMSR.Recovery.Supplement.BinaryVerifier

/-- The pending field and all subsequent fields, including the final unfinished field. -/
def fields : Bits → Bits × List Bits
  | [] | [_] => ([],[])
  | true :: b :: w => let r := fields w; (b :: r.1,r.2)
  | false :: _ :: w => let r := fields w; ([],r.1 :: r.2)

def digits : Bits → ℕ
  | [] => 0
  | b :: w => b.toNat + 2*digits w

/-- The terminating field marker creates a trailing empty field. Canonical re-encoding
    checks both delimiter bits and the normalized binary representation. -/
def numbers (w : Bits) : List ℕ :=
  let r := fields w
  ((r.1 :: r.2).dropLast).map digits

abbrev Data := ℕ × ℕ × List ℚ × List ℕ
abbrev Witness := List ℚ × List ℕ

def numAt (ns : List ℕ) (i : ℕ) := ns[i]?.getD 0

def ratHead (ns : List ℕ) : ℚ :=
  let a := (numAt ns 1 : ℚ)
  (if numAt ns 0 = 0 then a else -a) / (numAt ns 2 : ℚ)

def triples (ns : List ℕ) : List ℚ :=
  ((List.range ns.length).take (ns.length/3)).map (fun i => ratHead (ns.drop (3*i)))

def unpackWitness (n : ℕ) (ns : List ℕ) : Witness :=
  (triples (ns.take (3*(n*n))), ns.drop (3*(n*n)))

def unpackData (ns : List ℕ) : Data :=
  let n := numAt ns 0
  (n,numAt ns 1,unpackWitness n (ns.drop 2))

def dataFields (v : Data) : List ℕ := [v.1,v.2.1] ++ v.2.2.1.flatMap ratNumbers ++ v.2.2.2

def witnessFields (W : Witness) : List ℕ := W.1.flatMap ratNumbers ++ W.2

def specified (v : Data) : SpecifiedInput := ⟨⟨v.1,v.2.1,v.2.2.1⟩,v.2.2.2⟩

def witness (W : Witness) : RationalWitness := ⟨W.1,W.2⟩

/-- The outer loop is always bounded by the length of the decoded list, even if $k$ is malformed. -/
def classes (k : ℕ) (lab : List ℕ) : List ℕ := (List.range lab.length).take k

def members (lab : List ℕ) (j : ℕ) : List ℕ :=
  (List.range lab.length).filter (fun i => decide (numAt lab i = j))

def labelsOK (k : ℕ) (lab : List ℕ) : Bool :=
  lab.all (fun j => decide (j < k)) && (classes k lab).all (fun j => !(members lab j).isEmpty)

def distAt (n : ℕ) (ds : List ℚ) (i j : ℕ) : ℚ := ds[i*n+j]?.getD 0

def triangle (n : ℕ) (ds : List ℚ) (pts : List ℕ) : Bool :=
  pts.all fun i => pts.all fun j => pts.all fun l =>
    decide (distAt n ds i l ≤ distAt n ds i j + distAt n ds j l)

def metricOK (n : ℕ) (ds : List ℚ) (pts : List ℕ) : Bool :=
  (pts.all fun i => pts.all fun j =>
    ((decide (distAt n ds i j = 0)) == (decide (i = j))) &&
      decide (distAt n ds i j = distAt n ds j i)) && triangle n ds pts

def valid (v : Data) : Bool :=
  decide (v.2.2.1.length = v.1*v.1) && decide (1 ≤ v.2.1) && decide (v.2.1 ≤ v.1) &&
  decide (v.2.2.2.length = v.1) && labelsOK v.2.1 v.2.2.2 &&
  metricOK v.1 v.2.2.1 (List.range v.2.2.2.length)

def perturbOK (metric : Bool) (γ : ℚ) (n : ℕ) (ds ps : List ℚ) (pts : List ℕ) : Bool :=
  (pts.all fun i => pts.all fun j =>
    decide (distAt n ps i j = distAt n ps j i) && decide (distAt n ds i j ≤ distAt n ps i j) &&
    decide (distAt n ps i j ≤ γ*distAt n ds i j)) && (!metric || triangle n ps pts)

def samePartition (a b : List ℕ) : Bool :=
  (List.range a.length).all fun i => (List.range a.length).all fun j =>
    (decide (numAt a i = numAt a j)) == (decide (numAt b i = numAt b j))

def hi (xs : List ℚ) := xs.max?.getD 0

def lo (xs : List ℚ) := xs.min?.getD 0

def blockRadius (n : ℕ) (ds : List ℚ) (C : List ℕ) : ℚ :=
  lo (C.map fun c => hi (C.map fun i => distAt n ds c i))

def total (n k : ℕ) (ds : List ℚ) (lab : List ℕ) : ℚ :=
  ((classes k lab).map fun j => blockRadius n ds (members lab j)).sum

def competitive (metric : Bool) (γ : ℚ) (v : Data) (w : Witness) : Bool :=
  decide (w.1.length = v.1*v.1) && decide (w.2.length = v.1) && labelsOK v.2.1 w.2 &&
  perturbOK metric γ v.1 v.2.2.1 w.1 (List.range v.2.2.2.length) &&
  !samePartition v.2.2.2 w.2 && decide (total v.1 v.2.1 w.1 w.2 ≤ total v.1 v.2.1 w.1 v.2.2.2)

/-- A total checker. Every synthesized input or witness is compared with its canonical encoding. -/
def check (metric : Bool) (xy : Bits × Bits) : Bool :=
  let ns := numbers xy.1
  let γ := ratHead ns
  let v := unpackData (ns.drop 3)
  let w := unpackWitness v.1 (numbers xy.2)
  (packNats (ratNumbers γ ++ dataFields v) == xy.1) &&
  (packNats (witnessFields w) == xy.2) && decide (1 ≤ γ) && valid v && competitive metric γ v w

/-- The input-side test used when specializing the uniform checker to a fixed factor. -/
def specifiedOK (raw : Bits) : Bool :=
  let v := unpackData (numbers raw)
  (packNats (dataFields v) == raw) && valid v

end StableMSR.Recovery.Supplement.BinaryVerifier
Source
Shyam Ravichandran and Lev Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Appendix C, Lemma C.3 and Theorem 5.1. https://arxiv.org/abs/2611.03547

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