Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Composite parts of the BSP construction block: the split and the two peels

Proved
DetANN.HPIM.BD.peel_specs

by milia · Nov 17, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximate-nearest-neighborcomputational-geometrydata-structures

Three composite facts about the program bd\mathrm{bd}bd of definition DetANN_HPIMBuildProg, stated with Env, BoxAt and Fr from the same definition. In each, QQQ contains bd(o)\mathrm{bd}(o)bd(o) at offset ooo, sss is not halted, Env s pts r c Z0 holds and 1≤m1\le m1≤m. ZZZ, RRR are pointers 13, 14 of sss.

  1. Split (from 197, when ¬(2σ51−σ52≤0)\neg(2\sigma_{51}-\sigma_{52}\le0)¬(2σ51​−σ52​≤0), real 52 holds σ(lo,hi)\sigma(lo,hi)σ(lo,hi) of the task box at pointer 43, Z≤p44Z\le p_{44}Z≤p44​ and R≤p43R\le p_{43}R≤p43​). Some t≤37m+91t\le37m+91t≤37m+91 and kkk with longestAxis(lo,hi)=k\mathrm{longestAxis}(lo,hi)=klongestAxis(lo,hi)=k bring the run to 34 (not halted). With μ=(lok+hik)/2\mu=(lo_k+hi_k)/2μ=(lok​+hik​)/2:
    • there is a cut node [1,p43][1,p_{43}][1,p43​] at Z−4Z-4Z−4, with I[p44]=Z−4I[p_{44}]=Z-4I[p44​]=Z−4;
    • the left half (lo,hi[k↦μ])(lo,hi[k\mapsto\mu])(lo,hi[k↦μ]) is stored at R−2mR-2mR−2m and the right half (lo[k↦μ],hi)(lo[k\mapsto\mu],hi)(lo[k↦μ],hi) at R−4mR-4mR−4m;
    • the entries [R−2m,Z−2,p42][R-2m,Z-2,p_{42}][R−2m,Z−2,p42​] at Z−7Z-7Z−7 and [R−4m,Z−1,Z−7][R-4m,Z-1,Z-7][R−4m,Z−1,Z−7] at Z−10Z-10Z−10 are pushed, with pointers 13,42:=Z−1013,42:=Z-1013,42:=Z−10 and 14:=R−4m14:=R-4m14:=R−4m;
    • the constant registers, pointers below 13 and between 14 and 42, 59, 60, 68, 69, and reals below 44 and 49, 50, 53 are kept;
    • real cells outside [R−4m,R)[R-4m,R)[R−4m,R) and integer cells outside [Z−10,Z)∪{p44}[Z-10,Z)\cup\{p_{44}\}[Z−10,Z)∪{p44​} are kept, and the writes stay in these windows.
  2. Low peel (from 283 with axis k<mk<mk<m, the current box [lo,hi][lo,hi][lo,hi] at pointer 54 and the core [tlo,thi][tlo,thi][tlo,thi] at pointer 48, when lok<tloklo_k<tlo_klok​<tlok​; the current slot p55p_{55}p55​ satisfies Z≤p55<0Z\le p_{55}<0Z≤p55​<0, and p54,p48≥Rp_{54},p_{48}\ge Rp54​,p48​≥R, Z≤0Z\le0Z≤0, R≤0R\le0R≤0). Some t≤28m+80t\le28m+80t≤28m+80 gives Fr Q s s′ t {p55}\mathrm{Fr}\,Q\,s\,s'\,t\,\{p_{55}\}FrQss′t{p55​}, the pc 326, Env for s′s's′, and:
    • pointers 13,42:=Z−713,42:=Z-713,42:=Z−7, 14:=R−4m14:=R-4m14:=R−4m, 54:=R−4m54:=R-4m54:=R−4m, 55:=Z−155:=Z-155:=Z−1, with 48 and 53 kept;
    • a cut node [1,p54][1,p_{54}][1,p54​] at Z−4Z-4Z−4, with I[p55]=Z−4I[p_{55}]=Z-4I[p55​]=Z−4;
    • the entry [R−2m,Z−2,p42][R-2m,Z-2,p_{42}][R−2m,Z−2,p42​] at Z−7Z-7Z−7;
    • the low slab (lo,hi[k↦tlok])(lo,hi[k\mapsto tlo_k])(lo,hi[k↦tlok​]) at R−2mR-2mR−2m and the rest (lo[k↦tlok],hi)(lo[k\mapsto tlo_k],hi)(lo[k↦tlok​],hi) at R−4mR-4mR−4m.
  3. High peel (from 326, when hik>thikhi_k>thi_khik​>thik​; same hypotheses). The same as 2, except that the pc is 283, the axis is k+1k+1k+1, the current slot is Z−2Z-2Z−2, the entry is [R−2m,Z−1,p42][R-2m,Z-1,p_{42}][R−2m,Z−1,p42​], the high slab (lo[k↦thik],hi)(lo[k\mapsto thi_k],hi)(lo[k↦thik​],hi) is at R−2mR-2mR−2m and the rest (lo,hi[k↦thik])(lo,hi[k\mapsto thi_k])(lo,hi[k↦thik​]) is at R−4mR-4mR−4m.
Preamble
import Mathlib
import Definitions.Def_DetANN_HPIMBuildProg
import Definitions.Def_PNormReg_Machine
import Definitions.Def_PNormRegLib_Exec
import Definitions.Def_DetANN_DataStructure
import Definitions.Def_PNormRegLib_Reloc
import Definitions.Def_DetANN_HPIMBuild
import Definitions.Def_DetANN_HPIMPreBlocks
Formal statement
namespace DetANN.HPIM.BD

open PNormReg PNormRegLib DetANN DetANN.HPIM

theorem peel_specs :
    (∀ {m n : ℕ} (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (pts : Fin n → Fin m → ℝ) (r c : ℝ) (Z0 : ℤ) (hm : 1 ≤ m) (lo hi : Fin m → ℝ) (s : State) (hpc : s.core.pc = off + 197) (hh : s.halted = false) (hEnv : Env s pts r c Z0) (h52 : s.core.regs 52 = sigma lo hi) (hc : ¬ (s.core.regs 51 + s.core.regs 51 - s.core.regs 52 ≤ 0)) (hB : BoxAt s (s.core.ptrs 43) lo hi) (hsl : s.core.ptrs 13 ≤ s.core.ptrs 44) (hp : s.core.ptrs 14 ≤ s.core.ptrs 43),
      ∃ (t : ℕ) (s' : State) (k : Fin m), run Q s detTape t = s' ∧ t ≤ 37 * m + 91 ∧ longestAxis lo hi = some k ∧ s'.core.pc = off + 34 ∧ s'.halted = false ∧ s'.core.ptrs 13 = s.core.ptrs 13 - 10 ∧ s'.core.ptrs 14 = s.core.ptrs 14 - 4 * m ∧ s'.core.ptrs 42 = s.core.ptrs 13 - 10 ∧ s'.integerMemory (s.core.ptrs 13 - 4) = 1 ∧ s'.integerMemory (s.core.ptrs 13 - 3) = s.core.ptrs 43 ∧ s'.integerMemory (s.core.ptrs 44) = s.core.ptrs 13 - 4 ∧ s'.integerMemory (s.core.ptrs 13 - 7) = s.core.ptrs 14 - 2 * m ∧ s'.integerMemory (s.core.ptrs 13 - 6) = s.core.ptrs 13 - 2 ∧ s'.integerMemory (s.core.ptrs 13 - 5) = s.core.ptrs 42 ∧ s'.integerMemory (s.core.ptrs 13 - 10) = s.core.ptrs 14 - 4 * m ∧ s'.integerMemory (s.core.ptrs 13 - 9) = s.core.ptrs 13 - 1 ∧ s'.integerMemory (s.core.ptrs 13 - 8) = s.core.ptrs 13 - 7 ∧ BoxAt s' (s.core.ptrs 14 - 2 * m) lo (setCoord hi k ((lo k + hi k) / 2)) ∧ BoxAt s' (s.core.ptrs 14 - 4 * m) (setCoord lo k ((lo k + hi k) / 2)) hi ∧ (∀ x, (x < 13 ∨ (14 < x ∧ x < 42) ∨ x = 40 ∨ x = 59 ∨ x = 60 ∨ x = 68 ∨ x = 69) → s'.core.ptrs x = s.core.ptrs x) ∧ (∀ x, (x < 44 ∨ x = 49 ∨ x = 50 ∨ x = 53) → s'.core.regs x = s.core.regs x) ∧ (∀ z, (z < s.core.ptrs 14 - 4 * m ∨ s.core.ptrs 14 ≤ z) → s'.core.mem z = s.core.mem z) ∧ (∀ z, (z < s.core.ptrs 13 - 10 ∨ s.core.ptrs 13 ≤ z) → z ≠ s.core.ptrs 44 → s'.integerMemory z = s.integerMemory z) ∧ s'.work = s.work + t ∧ (∀ w ∈ cellsWritten Q s t, (w.1 = false ∧ ((s.core.ptrs 13 - 10 ≤ w.2 ∧ w.2 < s.core.ptrs 13) ∨ w.2 = s.core.ptrs 44)) ∨ (w.1 = true ∧ s.core.ptrs 14 - 4 * m ≤ w.2 ∧ w.2 < s.core.ptrs 14))) ∧
    (∀ {m n : ℕ} (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (pts : Fin n → Fin m → ℝ) (r c : ℝ) (Z0 : ℤ) (hm : 1 ≤ m) (s : State) (hpc : s.core.pc = off + 283) (hh : s.halted = false) (hEnv : Env s pts r c Z0) (k : ℕ) (hk : k < m) (h53 : s.core.ptrs 53 = k) (tlo thi lo hi : Fin m → ℝ) (hQ : BoxAt s (s.core.ptrs 48) tlo thi) (hB : BoxAt s (s.core.ptrs 54) lo hi) (hlow : lo ⟨k, hk⟩ < tlo ⟨k, hk⟩) (hcsl : s.core.ptrs 13 ≤ s.core.ptrs 55) (hcb : s.core.ptrs 14 ≤ s.core.ptrs 54) (hq : s.core.ptrs 14 ≤ s.core.ptrs 48) (hZ : s.core.ptrs 13 ≤ 0) (hcsl0 : s.core.ptrs 55 < 0) (hR : s.core.ptrs 14 ≤ 0),
      ∃ (t : ℕ) (s' : State), Fr Q s s' t (fun z => z = s.core.ptrs 55) ∧ t ≤ 28 * m + 80 ∧ s'.core.pc = off + 326 ∧ s'.halted = false ∧ Env s' pts r c Z0 ∧ s'.core.ptrs 13 = s.core.ptrs 13 - 7 ∧ s'.core.ptrs 14 = s.core.ptrs 14 - 4 * m ∧ s'.core.ptrs 42 = s.core.ptrs 13 - 7 ∧ s'.core.ptrs 48 = s.core.ptrs 48 ∧ s'.core.ptrs 53 = k ∧ s'.core.ptrs 54 = s.core.ptrs 14 - 4 * m ∧ s'.core.ptrs 55 = s.core.ptrs 13 - 1 ∧ s'.integerMemory (s.core.ptrs 13 - 4) = 1 ∧ s'.integerMemory (s.core.ptrs 13 - 3) = s.core.ptrs 54 ∧ s'.integerMemory (s.core.ptrs 55) = s.core.ptrs 13 - 4 ∧ s'.integerMemory (s.core.ptrs 13 - 7) = s.core.ptrs 14 - 2 * m ∧ s'.integerMemory (s.core.ptrs 13 - 6) = s.core.ptrs 13 - 2 ∧ s'.integerMemory (s.core.ptrs 13 - 5) = s.core.ptrs 42 ∧ BoxAt s' (s.core.ptrs 14 - 2 * m) lo (setCoord hi k (tlo ⟨k, hk⟩)) ∧ BoxAt s' (s.core.ptrs 14 - 4 * m) (setCoord lo k (tlo ⟨k, hk⟩)) hi) ∧
    (∀ {m n : ℕ} (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (pts : Fin n → Fin m → ℝ) (r c : ℝ) (Z0 : ℤ) (hm : 1 ≤ m) (s : State) (hpc : s.core.pc = off + 326) (hh : s.halted = false) (hEnv : Env s pts r c Z0) (k : ℕ) (hk : k < m) (h53 : s.core.ptrs 53 = k) (tlo thi lo hi : Fin m → ℝ) (hQ : BoxAt s (s.core.ptrs 48) tlo thi) (hB : BoxAt s (s.core.ptrs 54) lo hi) (hhigh : hi ⟨k, hk⟩ > thi ⟨k, hk⟩) (hcsl : s.core.ptrs 13 ≤ s.core.ptrs 55) (hcb : s.core.ptrs 14 ≤ s.core.ptrs 54) (hq : s.core.ptrs 14 ≤ s.core.ptrs 48) (hZ : s.core.ptrs 13 ≤ 0) (hcsl0 : s.core.ptrs 55 < 0) (hR : s.core.ptrs 14 ≤ 0),
      ∃ (t : ℕ) (s' : State), Fr Q s s' t (fun z => z = s.core.ptrs 55) ∧ t ≤ 28 * m + 80 ∧ s'.core.pc = off + 283 ∧ s'.halted = false ∧ Env s' pts r c Z0 ∧ s'.core.ptrs 13 = s.core.ptrs 13 - 7 ∧ s'.core.ptrs 14 = s.core.ptrs 14 - 4 * m ∧ s'.core.ptrs 42 = s.core.ptrs 13 - 7 ∧ s'.core.ptrs 48 = s.core.ptrs 48 ∧ s'.core.ptrs 53 = k + 1 ∧ s'.core.ptrs 54 = s.core.ptrs 14 - 4 * m ∧ s'.core.ptrs 55 = s.core.ptrs 13 - 2 ∧ s'.integerMemory (s.core.ptrs 13 - 4) = 1 ∧ s'.integerMemory (s.core.ptrs 13 - 3) = s.core.ptrs 54 ∧ s'.integerMemory (s.core.ptrs 55) = s.core.ptrs 13 - 4 ∧ s'.integerMemory (s.core.ptrs 13 - 7) = s.core.ptrs 14 - 2 * m ∧ s'.integerMemory (s.core.ptrs 13 - 6) = s.core.ptrs 13 - 1 ∧ s'.integerMemory (s.core.ptrs 13 - 5) = s.core.ptrs 42 ∧ BoxAt s' (s.core.ptrs 14 - 2 * m) (setCoord lo k (thi ⟨k, hk⟩)) hi ∧ BoxAt s' (s.core.ptrs 14 - 4 * m) lo (setCoord hi k (thi ⟨k, hk⟩))) := by sorry

end DetANN.HPIM.BD
Source
Original, written for the mission 'Deterministic Approximate Nearest Neighbors in High Dimensions' as part of a floor-free proof of DetANN.lemma_3_3 (Feng, Indyk, STOC 2027 submission, Lemma 3.3, p.7). These are pieces of the BSP construction block of DetANN.HPIM.build_block, split out so that each proof fits the verifier's time limit. The machine is PNormReg (definition PNormReg_Machine) with the conventions of DetANN_DataStructure.

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