Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Canonical-input generation of all bounded-subset table keys with charged execution

Proved
StableMSR.Recovery.Compiler.CatalogCompose.canonical_subset_table_program

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

algorithmsformal-verification

For every fixed width w≥0w\ge0w≥0, there is a deterministic program of 7w+1447w+1447w+144 instructions which starts with only the canonical scalar inputs n,kn,kn,k. Let M=(n+1)wM=(n+1)^wM=(n+1)w. The program constructs a table of MMM records, each consisting of an nnn-cell subset key and one initialization payload. Every subset S⊆{0,…,n−1}S\subseteq\{0,\ldots,n-1\}S⊆{0,…,n−1} of cardinality at most www occurs as an exact characteristic key in this retained table, with payload zero; duplicate keys are allowed.

The table begins at integer address 2+(w+1)M+n2+(w+1)M+n2+(w+1)M+n. At termination its base and row count are returned in the designated registers, both scalar input cells are preserved, all real registers and memory are unchanged, and no oracle query or random-tape read has occurred. The program halts within

(8w+6)M+M[4M+11n+11w+(M+1)(11n+16)+47]+30(8w+6)M+M\bigl[4M+11n+11w+(M+1)(11n+16)+47\bigr]+30(8w+6)M+M[4M+11n+11w+(M+1)(11n+16)+47]+30

charged instructions, including the final halt. The code is chosen before n,kn,kn,k and the metric input; the statement includes w=0w=0w=0 and n=0n=0n=0.

This composes the bounded-word catalog generator and the full catalog-to-table sweep from the canonical input, removing the intermediate-catalog and supplied-layout hypotheses of the earlier sweep theorem. It supplies initialized subset-key records for the decomposition-search implementation. Filtering valid graph states, evaluating recurrence/DP values, deterministic geometric construction, and the complete clustering recovery program are separate obligations.

Preamble
import Definitions.Def_StableMSR_ComponentGraphMemory
open scoped Classical
open StableMSR.Recovery StableMSR.Recovery.Compiler
Formal statement
theorem StableMSR.Recovery.Compiler.CatalogCompose.canonical_subset_table_program (w : ℕ) :
    ∃ P : MinSumFPT.Program, DeterministicProgram P ∧ P.length = 7*w+144 ∧
      ∀ (n k : ℕ) (d : Point n → Point n → ℝ),
        ∃ steps ≤ (8*w+6)*(n+1)^w+(n+1)^w*(4*(n+1)^w+11*n+11*w+
          ((n+1)^w+1)*(11*n+16)+47)+30,
          let result := execute P n k d steps
          result.halted = true ∧ result.work = steps ∧
          result.queries = 0 ∧ result.tapePos = 0 ∧
          result.cfg.ptrs 5 = (((n+1)^w:ℕ):ℤ) ∧
          result.cfg.ptrs 2 = 2+((w+1)*(n+1)^w:ℕ)+(n:ℤ) ∧
          result.imem 0 = (n:ℤ) ∧ result.imem 1 = (k:ℤ) ∧
          (∀ S : Finset (Fin n), S.card ≤ w →
            ∃ a < (n+1)^w,
              (∀ v : Fin n, result.imem
                (2+((w+1)*(n+1)^w:ℕ)+(n:ℤ)+(a:ℤ)*((n:ℤ)+1)+(v.val:ℤ)) =
                  if v ∈ S then 1 else 0) ∧
              result.imem (2+((w+1)*(n+1)^w:ℕ)+(n:ℤ)+(a:ℤ)*((n:ℤ)+1)+(n:ℤ)) = 0) ∧
          result.cfg.regs = (initialStore n k).regs ∧
          result.cfg.mem = (initialStore n k).mem := by sorry
Source
Exact Sum-of-Radii Clustering under Any Constant Stability; mission 11d3e3d6-df23-4c6a-8fd7-fbb629791a9b; canonical-input subset-table construction supporting rational_recovery_program.

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