Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A charged program deciding the tight-boundary equality

Proved
StableMSR.Recovery.Compiler.TightBoundaryProgram.tight_boundary_program

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

algorithmsformal-verification

There is one deterministic program with 616161 instructions that constructs the external boundary of a set CCC and decides whether it equals a supplied candidate set SSS. Its input is an ordinary directed edge array of length mmm for a simple graph on nnn vertices, characteristic bitmaps for CCC and SSS, and a separate writable boundary bitmap. The edge representation is sound and complete in both orientations; order and duplicates are unrestricted.

The program clears and constructs

NG(C)={v∉C:∃u∈C,  G(u,v)},N_G(C)=\{v\notin C:\exists u\in C,\;G(u,v)\},NG​(C)={v∈/C:∃u∈C,G(u,v)},

then compares its actual bitmap against the supplied bitmap for SSS. It returns the canonical flag 111 exactly when S=NG(C)S=N_G(C)S=NG​(C) and 000 otherwise, preserving the constructed boundary bitmap. The entire composed run, including pointer redirection/restoration and one halt, costs exactly

15n+17m+2115n+17m+2115n+17m+21

charged interpreter steps. The source, candidate, and edge arrays must be separate from the writable output, whose initial contents are unrestricted. All integer memory outside the boundary bitmap, all real registers and memory, original input addresses/dimensions, and oracle/tape counts are preserved. Empty graphs and empty sets are covered. The equality is decided by actual instructions, rather than supplied as a certificate. This verifies the tight-boundary comparison used by decomposition search; it does not by itself test the other conditions for a valid search state or implement the whole recovery algorithm.

Preamble
import Definitions.Def_StableMSR_ComponentGraphMemory
import Mathlib.Combinatorics.SimpleGraph.Basic
open scoped Classical
open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.ComponentMemory
Formal statement
theorem StableMSR.Recovery.Compiler.TightBoundaryProgram.tight_boundary_program :
    ∃ P : MinSumFPT.Program, DeterministicProgram P ∧ P.length = 61 ∧
    ∀ (n : ℕ) (d : Point n → Point n → ℝ) (G : SimpleGraph (Fin n))
      (C S : Finset (Fin n)) (es : List (Fin n × Fin n)) (s : Store),
      s.ptrs 5 = (es.length:ℤ) → s.ptrs 6 = (n:ℤ) →
      Bitmap s.imem (s.ptrs 3) C → Bitmap s.imem (s.ptrs 17) S →
      EdgeEncoding s.imem (s.ptrs 2) es →
      Separate (n := n) (s.ptrs 3) (s.ptrs 4) →
      Separate (n := n) (s.ptrs 17) (s.ptrs 4) →
      EdgesSeparate (s.ptrs 2) (s.ptrs 4) es →
      (∀ e ∈ es, G.Adj e.1 e.2) → (∀ u v, G.Adj u v → (u,v) ∈ es) →
      ∀ (ω : ℕ → ℝ) (work : ℕ),
      let B := Finset.univ.filter (fun v : Fin n => v ∉ C ∧ ∃ u ∈ C, G.Adj u v)
      let result := (MinSumFPT.step P d ω)^[15*n+17*es.length+21] (s.state 0 work)
      result.halted = true ∧ result.work = work+(15*n+17*es.length+21) ∧
      result.queries = s.queries ∧ result.tapePos = s.tapePos ∧
      result.cfg.mem = s.mem ∧ result.cfg.regs = s.regs ∧
      result.cfg.ptrs 18 = (if S = B then 1 else 0) ∧
      (result.cfg.ptrs 18 = 1 ↔ S = B) ∧
      (∀ v : Fin n, result.imem (address (s.ptrs 4) v) =
        if v ∉ C ∧ (∃ u ∈ C, G.Adj u v) then 1 else 0) ∧
      (∀ x : ℤ, (∀ v : Fin n, x ≠ address (s.ptrs 4) v) → result.imem x = s.imem x) ∧
      (∀ j : ℕ, (2 ≤ j ∧ j ≤ 6 ∨ j = 17) → result.cfg.ptrs j = s.ptrs j) := by sorry
Source
Exact Sum-of-Radii Clustering under Any Constant Stability; Prove2Me mission 11d3e3d6-df23-4c6a-8fd7-fbb629791a9b; executable comparisons and state-table lookup 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