Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A fixed charged program for bitmap cardinality and least vertex

Proved
StableMSR.Recovery.Compiler.BitmapStats.bitmap_statistics_program

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

algorithmsformal-verification

There is one deterministic program with 191919 instructions that scans an ordinary zero–one bitmap of a subset C⊆{0,…,n−1}C\subseteq\{0,\ldots,n-1\}C⊆{0,…,n−1}. It initializes its own counters and halts in exactly

9n+89n+89n+8

charged interpreter steps, including every branch, loop test, and the final halt. Register 181818 contains ∣C∣|C|∣C∣. Register 191919 contains the least vertex of CCC when CCC is nonempty, and the sentinel nnn exactly when CCC is empty. The reported index always lies between 000 and nnn.

The theorem covers n=0n=0n=0, arbitrary initial counters, arbitrary bitmap addresses, arbitrary distance oracles and tapes, and arbitrary initial work counters. Both integer and real memory, all real registers, the input registers, and oracle/tape counts are preserved. Only the fixed scratch and output pointer registers may change. No cardinality or minimum is supplied as input advice.

This provides the executable cardinality and representative-index primitive needed to organize component states in decomposition search. It does not itself implement subset ranking, table lookup, or the complete clustering recovery program.

Preamble
import Definitions.Def_StableMSR_ComponentGraphMemory
open scoped Classical
open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.ComponentMemory
Formal statement
theorem StableMSR.Recovery.Compiler.BitmapStats.bitmap_statistics_program :
    ∃ P : MinSumFPT.Program, DeterministicProgram P ∧ P.length = 19 ∧
      ∀ (N n : ℕ) (d : Point N → Point N → ℝ) (ω : ℕ → ℝ)
        (s : Store) (C : Finset (Fin n)) (w : ℕ),
        s.ptrs 6 = (n : ℤ) → Bitmap s.imem (s.ptrs 3) C →
        ∃ t : Store,
          t.ptrs 18 = (C.card : ℤ) ∧
          (t.ptrs 19 = (n : ℤ) ↔ C = ∅) ∧
          (C.Nonempty → ∃ v ∈ C, t.ptrs 19 = (v.val : ℤ) ∧
            ∀ u ∈ C, v.val ≤ u.val) ∧
          (0 ≤ t.ptrs 19 ∧ t.ptrs 19 ≤ (n : ℤ)) ∧
          (∀ j : ℕ, j ≠ 0 → j ≠ 18 → j ≠ 19 → j ≠ 20 →
            j ≠ 21 → j ≠ 22 → t.ptrs j = s.ptrs j) ∧
          t.regs = s.regs ∧ t.mem = s.mem ∧ t.imem = s.imem ∧
          t.queries = s.queries ∧ t.tapePos = s.tapePos ∧ t.output = s.output ∧
          (MinSumFPT.step P d ω)^[9*n+8] (s.state 0 w) =
            t.haltedState 18 (w+(9*n+8)) 0 := by sorry
Source
Exact Sum-of-Radii Clustering under Any Constant Stability; Prove2Me mission 11d3e3d6-df23-4c6a-8fd7-fbb629791a9b; concrete state-size and representative-index primitive for 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