A finite RAM enumerates all ordered ball-cover certificates
ProvedStableMSR.Recovery.CartesianBallRows.cartesian_row_machinealgorithmsclustering
The program writes two base-n digits per block for each row. Integer division uses repeated subtraction. An extra sentinel row detects completion without using an exponentiation instruction. The charged bound is n to an absolute constant times k+1.
Preamble
import Definitions.Def_StableMSR_CartesianBallRows open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.OracleQueries StableMSR.Recovery.BallCoverCatalog StableMSR.Recovery.CartesianBallRows
Formal statement
theorem StableMSR.Recovery.CartesianBallRows.cartesian_row_machine : ∃a b : ℕ,0 < a ∧ 0 < b ∧ ∃cmd : Cmd,
∀ (n k : ℕ) (d : Point n→Point n→ℝ),1 ≤ k → k ≤ n →
∃s z,Executes d cmd (initialStore n k) s z ∧ z ≤ a*n^(b*(k+1)) ∧
let x := worldOf k (rows n k) d s
Ready x s ∧ pairs x := by
sorry
Source
Shyam Ravichandran and Lev Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Algorithm 1 and Theorem 1.1. Finite deterministic RAM implementation and ball-cover certification.