Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Straight-line segments of the BSP construction block: carve and leaf

Proved
DetANN.HPIM.BD.carve_steps

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

approximate-nearest-neighborcomputational-geometrydata-structures

Thirteen straight-line facts about the program bd\mathrm{bd}bd of definition DetANN_HPIMBuildProg: the carve loop and the leaf node. Here the current box is at pointer 54, the current slot in pointer 55, the core box at pointer 48 and the axis in pointer 53.

Every conjunct has the same shape. Let QQQ contain bd(o)\mathrm{bd}(o)bd(o) at offset ooo (Embeds Q (bd off) off), and let sss be a non-halted state at the stated pc with 1≤1\le1≤ pointer 1 and the stated hypotheses. Then after exactly the stated number ttt of steps, the run of QQQ from sss:

  • is at the stated pc (relative to ooo) and has not halted;
  • has the stated values in the changed registers and cells;
  • leaves all other pointer and real registers and all other real and integer cells unchanged;
  • has work s.work+ts.\mathrm{work}+ts.work+t, and its cellsWritten set consists of the listed cells.

Pointer 1 holds mmm, pointer 11 holds nnn, and ZZZ, RRR denote pointers 13, 14 of sss.

  1. Carve start 280→283280\to283280→283 (3): pointers 54:=p4354:=p_{43}54:=p43​, 55:=p4455:=p_{44}55:=p44​, 53:=053:=053:=0.
  2. Carve end 283→372283\to372283→372 (1): when k≥mk\ge mk≥m.
  3. No low peel 283→326283\to326283→326 (7): when tlok−lok≤0tlo_k-lo_k\le0tlok​−lok​≤0 (reals 44, 45).
  4. Low peel 283→258283\to258283→258 (21): when tlok−lok>0tlo_k-lo_k>0tlok​−lok​>0: 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; copy-and-set of the current box with index m+km+km+k, value tloktlo_ktlok​ and code 2.
  5. Push the low slab 304→258304\to258304→258 (17): pushes [new box,node+2,link][\text{new box},\text{node}+2,\text{link}][new box,node+2,link]; copy-and-set of the current box with index kkk and code 3.
  6. Continue 321→326321\to326321→326 (5): current box := the new box, current slot := node +3+3+3.
  7. No high peel 326→370326\to370326→370 (8): when hik−thik≤0hi_k-thi_k\le0hik​−thik​≤0.
  8. High peel 326→258326\to258326→258 (22): a cut node as in 4; copy-and-set with index kkk, value thikthi_kthik​ and code 4.
  9. Push the high slab 348→258348\to258348→258 (18): pushes [new box,node+3,link][\text{new box},\text{node}+3,\text{link}][new box,node+3,link]; copy-and-set with index m+km+km+k and code 5.
  10. Continue 366→283366\to283366→283 (6): current box := the new box, current slot := node +2+2+2, k:=k+1k:=k+1k:=k+1.
  11. Next axis 370→283370\to283370→283 (2): k:=k+1k:=k+1k:=k+1.
  12. Push the core 372→34372\to34372→34 (11): pushes [p54,p55,link][p_{54},p_{55},\text{link}][p54​,p55​,link].
  13. Leaf 383→34383\to34383→34 (12): writes the leaf node [0,p43,p61][0,p_{43},p_{61}][0,p43​,p61​] at Z−3Z-3Z−3 and I[p44]:=Z−3I[p_{44}]:=Z-3I[p44​]:=Z−3.
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 carve_steps :
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 280) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 3).core.pc = off + 283 ∧ (run Q s detTape 3).halted = false ∧ (run Q s detTape 3).core.ptrs 53 = 0 ∧ (run Q s detTape 3).core.ptrs 54 = s.core.ptrs 43 ∧ (run Q s detTape 3).core.ptrs 55 = s.core.ptrs 44 ∧ (∀ x, x ≠ 53 → x ≠ 54 → x ≠ 55 → (run Q s detTape 3).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 3).core.regs = s.core.regs ∧ (run Q s detTape 3).core.mem = s.core.mem ∧ (run Q s detTape 3).integerMemory = s.integerMemory ∧ (run Q s detTape 3).work = s.work + 3 ∧ cellsWritten Q s 3 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 283) (hh : s.halted = false) (hb0 : s.core.ptrs 1 ≤ s.core.ptrs 53) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 1).core.pc = off + 372 ∧ (run Q s detTape 1).halted = false ∧ (run Q s detTape 1).core.ptrs = s.core.ptrs ∧ (run Q s detTape 1).core.regs = s.core.regs ∧ (run Q s detTape 1).core.mem = s.core.mem ∧ (run Q s detTape 1).integerMemory = s.integerMemory ∧ (run Q s detTape 1).work = s.work + 1 ∧ cellsWritten Q s 1 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (tl lo : ℝ) (s : State) (hpc : s.core.pc = off + 283) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 48 + s.core.ptrs 53) = tl) (fr1 : s.core.mem (s.core.ptrs 54 + s.core.ptrs 53) = lo) (hb0 : s.core.ptrs 53 < s.core.ptrs 1) (hb1 : (tl - lo) ≤ 0) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 7).core.pc = off + 326 ∧ (run Q s detTape 7).halted = false ∧ (run Q s detTape 7).core.ptrs 57 = s.core.ptrs 54 + s.core.ptrs 53 ∧ (∀ x, x ≠ 57 → (run Q s detTape 7).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 7).core.regs 44 = tl ∧ (run Q s detTape 7).core.regs 45 = lo ∧ (run Q s detTape 7).core.regs 54 = (tl - lo) ∧ (∀ x, x ≠ 44 → x ≠ 45 → x ≠ 54 → (run Q s detTape 7).core.regs x = s.core.regs x) ∧ (run Q s detTape 7).core.mem = s.core.mem ∧ (run Q s detTape 7).integerMemory = s.integerMemory ∧ (run Q s detTape 7).work = s.work + 7 ∧ cellsWritten Q s 7 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (tl lo : ℝ) (s : State) (hpc : s.core.pc = off + 283) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 48 + s.core.ptrs 53) = tl) (fr1 : s.core.mem (s.core.ptrs 54 + s.core.ptrs 53) = lo) (hb0 : s.core.ptrs 53 < s.core.ptrs 1) (hb1 : ¬ (tl - lo) ≤ 0) (hm1 : 1 ≤ s.core.ptrs 1) (hx0 : s.core.ptrs 13 ≤ s.core.ptrs 55),
      (run Q s detTape 21).core.pc = off + 258 ∧ (run Q s detTape 21).halted = false ∧ (run Q s detTape 21).core.ptrs 13 = s.core.ptrs 13 - 4 ∧ (run Q s detTape 21).core.ptrs 50 = s.core.ptrs 54 ∧ (run Q s detTape 21).core.ptrs 51 = s.core.ptrs 1 + s.core.ptrs 53 ∧ (run Q s detTape 21).core.ptrs 52 = s.core.ptrs 13 - 4 ∧ (run Q s detTape 21).core.ptrs 57 = s.core.ptrs 13 - 3 ∧ (run Q s detTape 21).core.ptrs 58 = 2 ∧ (∀ x, x ≠ 13 → x ≠ 50 → x ≠ 51 → x ≠ 52 → x ≠ 57 → x ≠ 58 → (run Q s detTape 21).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 21).core.regs 44 = tl ∧ (run Q s detTape 21).core.regs 45 = lo ∧ (run Q s detTape 21).core.regs 54 = (tl - lo) ∧ (∀ x, x ≠ 44 → x ≠ 45 → x ≠ 54 → (run Q s detTape 21).core.regs x = s.core.regs x) ∧ (run Q s detTape 21).core.mem = s.core.mem ∧ (run Q s detTape 21).integerMemory (s.core.ptrs 13 - 4) = s.core.ptrs 68 ∧ (run Q s detTape 21).integerMemory (s.core.ptrs 13 - 3) = s.core.ptrs 54 ∧ (run Q s detTape 21).integerMemory (s.core.ptrs 55) = s.core.ptrs 13 - 4 ∧ (∀ z, z ≠ s.core.ptrs 13 - 4 → z ≠ s.core.ptrs 13 - 3 → z ≠ s.core.ptrs 55 → (run Q s detTape 21).integerMemory z = s.integerMemory z) ∧ (run Q s detTape 21).work = s.work + 21 ∧ ∀ c ∈ cellsWritten Q s 21, c = (false, s.core.ptrs 13 - 4) ∨ c = (false, s.core.ptrs 13 - 3) ∨ c = (false, s.core.ptrs 55)) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 304) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 17).core.pc = off + 258 ∧ (run Q s detTape 17).halted = false ∧ (run Q s detTape 17).core.ptrs 13 = s.core.ptrs 13 - 3 ∧ (run Q s detTape 17).core.ptrs 42 = s.core.ptrs 13 - 3 ∧ (run Q s detTape 17).core.ptrs 50 = s.core.ptrs 54 ∧ (run Q s detTape 17).core.ptrs 51 = s.core.ptrs 53 ∧ (run Q s detTape 17).core.ptrs 57 = s.core.ptrs 13 - 1 ∧ (run Q s detTape 17).core.ptrs 58 = 3 ∧ (run Q s detTape 17).core.ptrs 62 = s.core.ptrs 52 + 2 ∧ (∀ x, x ≠ 13 → x ≠ 42 → x ≠ 50 → x ≠ 51 → x ≠ 57 → x ≠ 58 → x ≠ 62 → (run Q s detTape 17).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 17).core.regs = s.core.regs ∧ (run Q s detTape 17).core.mem = s.core.mem ∧ (run Q s detTape 17).integerMemory (s.core.ptrs 13 - 3) = s.core.ptrs 56 ∧ (run Q s detTape 17).integerMemory (s.core.ptrs 13 - 2) = s.core.ptrs 52 + 2 ∧ (run Q s detTape 17).integerMemory (s.core.ptrs 13 - 1) = s.core.ptrs 42 ∧ (∀ z, z ≠ s.core.ptrs 13 - 3 → z ≠ s.core.ptrs 13 - 2 → z ≠ s.core.ptrs 13 - 1 → (run Q s detTape 17).integerMemory z = s.integerMemory z) ∧ (run Q s detTape 17).work = s.work + 17 ∧ ∀ c ∈ cellsWritten Q s 17, c = (false, s.core.ptrs 13 - 3) ∨ c = (false, s.core.ptrs 13 - 2) ∨ c = (false, s.core.ptrs 13 - 1)) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 321) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 5).core.pc = off + 326 ∧ (run Q s detTape 5).halted = false ∧ (run Q s detTape 5).core.ptrs 54 = s.core.ptrs 56 ∧ (run Q s detTape 5).core.ptrs 55 = s.core.ptrs 52 + 3 ∧ (∀ x, x ≠ 54 → x ≠ 55 → (run Q s detTape 5).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 5).core.regs = s.core.regs ∧ (run Q s detTape 5).core.mem = s.core.mem ∧ (run Q s detTape 5).integerMemory = s.integerMemory ∧ (run Q s detTape 5).work = s.work + 5 ∧ cellsWritten Q s 5 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (th hi : ℝ) (s : State) (hpc : s.core.pc = off + 326) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 48 + s.core.ptrs 53 + s.core.ptrs 1) = th) (fr1 : s.core.mem (s.core.ptrs 54 + s.core.ptrs 53 + s.core.ptrs 1) = hi) (hb0 : (hi - th) ≤ 0) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 8).core.pc = off + 370 ∧ (run Q s detTape 8).halted = false ∧ (run Q s detTape 8).core.ptrs 57 = s.core.ptrs 54 + s.core.ptrs 53 + s.core.ptrs 1 ∧ (∀ x, x ≠ 57 → (run Q s detTape 8).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 8).core.regs 44 = th ∧ (run Q s detTape 8).core.regs 46 = hi ∧ (run Q s detTape 8).core.regs 54 = (hi - th) ∧ (∀ x, x ≠ 44 → x ≠ 46 → x ≠ 54 → (run Q s detTape 8).core.regs x = s.core.regs x) ∧ (run Q s detTape 8).core.mem = s.core.mem ∧ (run Q s detTape 8).integerMemory = s.integerMemory ∧ (run Q s detTape 8).work = s.work + 8 ∧ cellsWritten Q s 8 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (th hi : ℝ) (s : State) (hpc : s.core.pc = off + 326) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 48 + s.core.ptrs 53 + s.core.ptrs 1) = th) (fr1 : s.core.mem (s.core.ptrs 54 + s.core.ptrs 53 + s.core.ptrs 1) = hi) (hb0 : ¬ (hi - th) ≤ 0) (hm1 : 1 ≤ s.core.ptrs 1) (hx0 : s.core.ptrs 13 ≤ s.core.ptrs 55),
      (run Q s detTape 22).core.pc = off + 258 ∧ (run Q s detTape 22).halted = false ∧ (run Q s detTape 22).core.ptrs 13 = s.core.ptrs 13 - 4 ∧ (run Q s detTape 22).core.ptrs 50 = s.core.ptrs 54 ∧ (run Q s detTape 22).core.ptrs 51 = s.core.ptrs 53 ∧ (run Q s detTape 22).core.ptrs 52 = s.core.ptrs 13 - 4 ∧ (run Q s detTape 22).core.ptrs 57 = s.core.ptrs 13 - 3 ∧ (run Q s detTape 22).core.ptrs 58 = 4 ∧ (∀ x, x ≠ 13 → x ≠ 50 → x ≠ 51 → x ≠ 52 → x ≠ 57 → x ≠ 58 → (run Q s detTape 22).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 22).core.regs 44 = th ∧ (run Q s detTape 22).core.regs 46 = hi ∧ (run Q s detTape 22).core.regs 54 = (hi - th) ∧ (∀ x, x ≠ 44 → x ≠ 46 → x ≠ 54 → (run Q s detTape 22).core.regs x = s.core.regs x) ∧ (run Q s detTape 22).core.mem = s.core.mem ∧ (run Q s detTape 22).integerMemory (s.core.ptrs 13 - 4) = s.core.ptrs 68 ∧ (run Q s detTape 22).integerMemory (s.core.ptrs 13 - 3) = s.core.ptrs 54 ∧ (run Q s detTape 22).integerMemory (s.core.ptrs 55) = s.core.ptrs 13 - 4 ∧ (∀ z, z ≠ s.core.ptrs 13 - 4 → z ≠ s.core.ptrs 13 - 3 → z ≠ s.core.ptrs 55 → (run Q s detTape 22).integerMemory z = s.integerMemory z) ∧ (run Q s detTape 22).work = s.work + 22 ∧ ∀ c ∈ cellsWritten Q s 22, c = (false, s.core.ptrs 13 - 4) ∨ c = (false, s.core.ptrs 13 - 3) ∨ c = (false, s.core.ptrs 55)) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 348) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 18).core.pc = off + 258 ∧ (run Q s detTape 18).halted = false ∧ (run Q s detTape 18).core.ptrs 13 = s.core.ptrs 13 - 3 ∧ (run Q s detTape 18).core.ptrs 42 = s.core.ptrs 13 - 3 ∧ (run Q s detTape 18).core.ptrs 50 = s.core.ptrs 54 ∧ (run Q s detTape 18).core.ptrs 51 = s.core.ptrs 1 + s.core.ptrs 53 ∧ (run Q s detTape 18).core.ptrs 57 = s.core.ptrs 13 - 1 ∧ (run Q s detTape 18).core.ptrs 58 = 5 ∧ (run Q s detTape 18).core.ptrs 62 = s.core.ptrs 52 + 3 ∧ (∀ x, x ≠ 13 → x ≠ 42 → x ≠ 50 → x ≠ 51 → x ≠ 57 → x ≠ 58 → x ≠ 62 → (run Q s detTape 18).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 18).core.regs = s.core.regs ∧ (run Q s detTape 18).core.mem = s.core.mem ∧ (run Q s detTape 18).integerMemory (s.core.ptrs 13 - 3) = s.core.ptrs 56 ∧ (run Q s detTape 18).integerMemory (s.core.ptrs 13 - 2) = s.core.ptrs 52 + 3 ∧ (run Q s detTape 18).integerMemory (s.core.ptrs 13 - 1) = s.core.ptrs 42 ∧ (∀ z, z ≠ s.core.ptrs 13 - 3 → z ≠ s.core.ptrs 13 - 2 → z ≠ s.core.ptrs 13 - 1 → (run Q s detTape 18).integerMemory z = s.integerMemory z) ∧ (run Q s detTape 18).work = s.work + 18 ∧ ∀ c ∈ cellsWritten Q s 18, c = (false, s.core.ptrs 13 - 3) ∨ c = (false, s.core.ptrs 13 - 2) ∨ c = (false, s.core.ptrs 13 - 1)) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 366) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 6).core.pc = off + 283 ∧ (run Q s detTape 6).halted = false ∧ (run Q s detTape 6).core.ptrs 53 = s.core.ptrs 53 + 1 ∧ (run Q s detTape 6).core.ptrs 54 = s.core.ptrs 56 ∧ (run Q s detTape 6).core.ptrs 55 = s.core.ptrs 52 + 2 ∧ (∀ x, x ≠ 53 → x ≠ 54 → x ≠ 55 → (run Q s detTape 6).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 6).core.regs = s.core.regs ∧ (run Q s detTape 6).core.mem = s.core.mem ∧ (run Q s detTape 6).integerMemory = s.integerMemory ∧ (run Q s detTape 6).work = s.work + 6 ∧ cellsWritten Q s 6 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 370) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 2).core.pc = off + 283 ∧ (run Q s detTape 2).halted = false ∧ (run Q s detTape 2).core.ptrs 53 = s.core.ptrs 53 + 1 ∧ (∀ x, x ≠ 53 → (run Q s detTape 2).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 2).core.regs = s.core.regs ∧ (run Q s detTape 2).core.mem = s.core.mem ∧ (run Q s detTape 2).integerMemory = s.integerMemory ∧ (run Q s detTape 2).work = s.work + 2 ∧ cellsWritten Q s 2 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 372) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 11).core.pc = off + 34 ∧ (run Q s detTape 11).halted = false ∧ (run Q s detTape 11).core.ptrs 13 = s.core.ptrs 13 - 3 ∧ (run Q s detTape 11).core.ptrs 42 = s.core.ptrs 13 - 3 ∧ (run Q s detTape 11).core.ptrs 57 = s.core.ptrs 13 - 1 ∧ (∀ x, x ≠ 13 → x ≠ 42 → x ≠ 57 → (run Q s detTape 11).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 11).core.regs = s.core.regs ∧ (run Q s detTape 11).core.mem = s.core.mem ∧ (run Q s detTape 11).integerMemory (s.core.ptrs 13 - 3) = s.core.ptrs 54 ∧ (run Q s detTape 11).integerMemory (s.core.ptrs 13 - 2) = s.core.ptrs 55 ∧ (run Q s detTape 11).integerMemory (s.core.ptrs 13 - 1) = s.core.ptrs 42 ∧ (∀ z, z ≠ s.core.ptrs 13 - 3 → z ≠ s.core.ptrs 13 - 2 → z ≠ s.core.ptrs 13 - 1 → (run Q s detTape 11).integerMemory z = s.integerMemory z) ∧ (run Q s detTape 11).work = s.work + 11 ∧ ∀ c ∈ cellsWritten Q s 11, c = (false, s.core.ptrs 13 - 3) ∨ c = (false, s.core.ptrs 13 - 2) ∨ c = (false, s.core.ptrs 13 - 1)) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 383) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1) (hx0 : s.core.ptrs 13 ≤ s.core.ptrs 44),
      (run Q s detTape 12).core.pc = off + 34 ∧ (run Q s detTape 12).halted = false ∧ (run Q s detTape 12).core.ptrs 13 = s.core.ptrs 13 - 3 ∧ (run Q s detTape 12).core.ptrs 52 = s.core.ptrs 13 - 3 ∧ (run Q s detTape 12).core.ptrs 57 = s.core.ptrs 13 - 1 ∧ (∀ x, x ≠ 13 → x ≠ 52 → x ≠ 57 → (run Q s detTape 12).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 12).core.regs = s.core.regs ∧ (run Q s detTape 12).core.mem = s.core.mem ∧ (run Q s detTape 12).integerMemory (s.core.ptrs 13 - 3) = s.core.ptrs 69 ∧ (run Q s detTape 12).integerMemory (s.core.ptrs 13 - 2) = s.core.ptrs 43 ∧ (run Q s detTape 12).integerMemory (s.core.ptrs 13 - 1) = s.core.ptrs 61 ∧ (run Q s detTape 12).integerMemory (s.core.ptrs 44) = s.core.ptrs 13 - 3 ∧ (∀ z, z ≠ s.core.ptrs 13 - 3 → z ≠ s.core.ptrs 13 - 2 → z ≠ s.core.ptrs 13 - 1 → z ≠ s.core.ptrs 44 → (run Q s detTape 12).integerMemory z = s.integerMemory z) ∧ (run Q s detTape 12).work = s.work + 12 ∧ ∀ c ∈ cellsWritten Q s 12, c = (false, s.core.ptrs 13 - 3) ∨ c = (false, s.core.ptrs 13 - 2) ∨ c = (false, s.core.ptrs 13 - 1) ∨ c = (false, s.core.ptrs 44)) := 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