Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Straight-line segments of the BSP construction block: core box, sides, split and copy

Proved
DetANN.HPIM.BD.split_steps

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

approximate-nearest-neighborcomputational-geometrydata-structures

Twenty-one straight-line facts about the program bd\mathrm{bd}bd of definition DetANN_HPIMBuildProg: the core box, the longest sides, the split and the copy-and-set subroutine.

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. Core exit 134→161134\to161134→161 (1): when j≥mj\ge mj≥m.
  2. Core step 134→134134\to134134→134 (27): coordinate jjj of qqq becomes [max⁡(qj−2r,loj),min⁡(qm+j+2r,hij)][\max(q_j-2r,lo_j),\min(q_{m+j}+2r,hi_j)][max(qj​−2r,loj​),min(qm+j​+2r,hij​)], where [lo,hi][lo,hi][lo,hi] is the task box at pointer 43.
  3. Sides start 161→172161\to172161→172 (11): reals 51, 52 := the side 0 of qqq and of the task box; j:=1j:=1j:=1.
  4. Sides exit 172→197172\to197172→197 (1).
  5. Sides step 172→172172\to172172→172 (25): reals 51, 52 take the maximum with side jjj.
  6. Carve 197→280197\to280197→280 (3): when 2σ51−σ52≤02\sigma_{51}-\sigma_{52}\le02σ51​−σ52​≤0.
  7. Split 197→201197\to201197→201 (4): otherwise; axis 53:=053:=053:=0.
  8. Axis, next 201→201201\to201201→201 (9): when side k<σ52k<\sigma_{52}k<σ52​: k:=k+1k:=k+1k:=k+1.
  9. Axis, found 201→210201\to210201→210 (7): when σ52≤\sigma_{52}\leσ52​≤ side kkk: reals 44,45:=lok,hik44,45:=lo_k,hi_k44,45:=lok​,hik​.
  10. Split node 210→258210\to258210→258 (16): real 44:=(lok+hik)/244:=(lo_k+hi_k)/244:=(lok​+hik​)/2; a cut node [1,p][1,p][1,p] at Z−4Z-4Z−4 with I[slot]:=Z−4I[\text{slot}]:=Z-4I[slot]:=Z−4; copy-and-set of the task box with index m+km+km+k and code 0.
  11. Left push 226→258226\to258226→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 task box with index kkk and code 1.
  12. Right push 243→34243\to34243→34 (15): pushes [new box,node+3,link][\text{new box},\text{node}+3,\text{link}][new box,node+3,link].
  13. Copy head 258→261258\to261258→261 (3): pointers 14,56:=R−2m14,56:=R-2m14,56:=R−2m, 46:=046:=046:=0.
  14. Copy step 261→261261\to261261→261 (7): when i<2mi<2mi<2m, real cell p56+ip_{56}+ip56​+i gets the value of p50+ip_{50}+ip50​+i.
  15. Copy exit 261→268261\to268261→268 (1). 16–21. Set and return, codes 0–5 268→226,243,304,321,348,366268\to226,243,304,321,348,366268→226,243,304,321,348,366 (3, 5, 7, 9, 11, 12 steps): real cell p56+p51p_{56}+p_{51}p56​+p51​ gets real 44, then the return by the code in pointer 58.
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 split_steps :
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 134) (hh : s.halted = false) (hb0 : s.core.ptrs 1 ≤ s.core.ptrs 46) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 1).core.pc = off + 161 ∧ (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) (mn lo mx hi : ℝ) (s : State) (hpc : s.core.pc = off + 134) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 48 + s.core.ptrs 46) = mn) (fr1 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 46) = lo) (fr2 : s.core.mem (s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1) = mx) (fr3 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 46 + s.core.ptrs 1) = hi) (hb0 : s.core.ptrs 46 < s.core.ptrs 1) (hm1 : 1 ≤ s.core.ptrs 1) (hx0 : s.core.ptrs 48 < s.core.ptrs 43),
      (run Q s detTape 27).core.pc = off + 134 ∧ (run Q s detTape 27).halted = false ∧ (run Q s detTape 27).core.ptrs 46 = s.core.ptrs 46 + 1 ∧ (run Q s detTape 27).core.ptrs 50 = s.core.ptrs 43 + s.core.ptrs 46 + s.core.ptrs 1 ∧ (run Q s detTape 27).core.ptrs 57 = s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1 ∧ (∀ x, x ≠ 46 → x ≠ 50 → x ≠ 57 → (run Q s detTape 27).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 27).core.regs 44 = (mx + s.core.regs 49) ∧ (run Q s detTape 27).core.regs 45 = hi ∧ (run Q s detTape 27).core.regs 47 = ((((mx + s.core.regs 49) + hi) - Real.sqrt (((mx + s.core.regs 49) - hi) * ((mx + s.core.regs 49) - hi))) / s.core.regs 53) ∧ (run Q s detTape 27).core.regs 54 = Real.sqrt (((mx + s.core.regs 49) - hi) * ((mx + s.core.regs 49) - hi)) ∧ (∀ x, x ≠ 44 → x ≠ 45 → x ≠ 47 → x ≠ 54 → (run Q s detTape 27).core.regs x = s.core.regs x) ∧ (run Q s detTape 27).core.mem (s.core.ptrs 48 + s.core.ptrs 46) = ((((mn - s.core.regs 49) + lo) + Real.sqrt (((mn - s.core.regs 49) - lo) * ((mn - s.core.regs 49) - lo))) / s.core.regs 53) ∧ (run Q s detTape 27).core.mem (s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1) = ((((mx + s.core.regs 49) + hi) - Real.sqrt (((mx + s.core.regs 49) - hi) * ((mx + s.core.regs 49) - hi))) / s.core.regs 53) ∧ (∀ z, z ≠ s.core.ptrs 48 + s.core.ptrs 46 → z ≠ s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1 → (run Q s detTape 27).core.mem z = s.core.mem z) ∧ (run Q s detTape 27).integerMemory = s.integerMemory ∧ (run Q s detTape 27).work = s.work + 27 ∧ ∀ c ∈ cellsWritten Q s 27, c = (true, s.core.ptrs 48 + s.core.ptrs 46) ∨ c = (true, s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1)) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (a0 b0 c0 d0 : ℝ) (s : State) (hpc : s.core.pc = off + 161) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 48) = a0) (fr1 : s.core.mem (s.core.ptrs 48 + s.core.ptrs 1) = b0) (fr2 : s.core.mem (s.core.ptrs 43) = c0) (fr3 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 1) = d0) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 11).core.pc = off + 172 ∧ (run Q s detTape 11).halted = false ∧ (run Q s detTape 11).core.ptrs 46 = 1 ∧ (run Q s detTape 11).core.ptrs 57 = s.core.ptrs 43 + s.core.ptrs 1 ∧ (∀ x, x ≠ 46 → x ≠ 57 → (run Q s detTape 11).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 11).core.regs 44 = c0 ∧ (run Q s detTape 11).core.regs 45 = d0 ∧ (run Q s detTape 11).core.regs 51 = (b0 - a0) ∧ (run Q s detTape 11).core.regs 52 = (d0 - c0) ∧ (∀ x, x ≠ 44 → x ≠ 45 → x ≠ 51 → x ≠ 52 → (run Q s detTape 11).core.regs x = s.core.regs x) ∧ (run Q s detTape 11).core.mem = s.core.mem ∧ (run Q s detTape 11).integerMemory = s.integerMemory ∧ (run Q s detTape 11).work = s.work + 11 ∧ cellsWritten Q s 11 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 172) (hh : s.halted = false) (hb0 : s.core.ptrs 1 ≤ s.core.ptrs 46) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 1).core.pc = off + 197 ∧ (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) (a b c d : ℝ) (s : State) (hpc : s.core.pc = off + 172) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 48 + s.core.ptrs 46) = a) (fr1 : s.core.mem (s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1) = b) (fr2 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 46) = c) (fr3 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 46 + s.core.ptrs 1) = d) (hb0 : s.core.ptrs 46 < s.core.ptrs 1) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 25).core.pc = off + 172 ∧ (run Q s detTape 25).halted = false ∧ (run Q s detTape 25).core.ptrs 46 = s.core.ptrs 46 + 1 ∧ (run Q s detTape 25).core.ptrs 57 = s.core.ptrs 43 + s.core.ptrs 46 + s.core.ptrs 1 ∧ (∀ x, x ≠ 46 → x ≠ 57 → (run Q s detTape 25).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 25).core.regs 44 = c ∧ (run Q s detTape 25).core.regs 45 = d ∧ (run Q s detTape 25).core.regs 47 = (d - c) ∧ (run Q s detTape 25).core.regs 51 = (((s.core.regs 51 + (b - a)) + Real.sqrt ((s.core.regs 51 - (b - a)) * (s.core.regs 51 - (b - a)))) / s.core.regs 53) ∧ (run Q s detTape 25).core.regs 52 = (((s.core.regs 52 + (d - c)) + Real.sqrt ((s.core.regs 52 - (d - c)) * (s.core.regs 52 - (d - c)))) / s.core.regs 53) ∧ (run Q s detTape 25).core.regs 54 = Real.sqrt ((s.core.regs 52 - (d - c)) * (s.core.regs 52 - (d - c))) ∧ (∀ x, x ≠ 44 → x ≠ 45 → x ≠ 47 → x ≠ 51 → x ≠ 52 → x ≠ 54 → (run Q s detTape 25).core.regs x = s.core.regs x) ∧ (run Q s detTape 25).core.mem = s.core.mem ∧ (run Q s detTape 25).integerMemory = s.integerMemory ∧ (run Q s detTape 25).work = s.work + 25 ∧ cellsWritten Q s 25 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 197) (hh : s.halted = false) (hb0 : ((s.core.regs 51 + s.core.regs 51) - s.core.regs 52) ≤ 0) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 3).core.pc = off + 280 ∧ (run Q s detTape 3).halted = false ∧ (run Q s detTape 3).core.ptrs = s.core.ptrs ∧ (run Q s detTape 3).core.regs 54 = ((s.core.regs 51 + s.core.regs 51) - s.core.regs 52) ∧ (∀ x, x ≠ 54 → (run Q s detTape 3).core.regs x = s.core.regs x) ∧ (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 + 197) (hh : s.halted = false) (hb0 : ¬ ((s.core.regs 51 + s.core.regs 51) - s.core.regs 52) ≤ 0) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 4).core.pc = off + 201 ∧ (run Q s detTape 4).halted = false ∧ (run Q s detTape 4).core.ptrs 53 = 0 ∧ (∀ x, x ≠ 53 → (run Q s detTape 4).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 4).core.regs 54 = ((s.core.regs 51 + s.core.regs 51) - s.core.regs 52) ∧ (∀ x, x ≠ 54 → (run Q s detTape 4).core.regs x = s.core.regs x) ∧ (run Q s detTape 4).core.mem = s.core.mem ∧ (run Q s detTape 4).integerMemory = s.integerMemory ∧ (run Q s detTape 4).work = s.work + 4 ∧ cellsWritten Q s 4 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (a b : ℝ) (s : State) (hpc : s.core.pc = off + 201) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 53) = a) (fr1 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 53 + s.core.ptrs 1) = b) (hb0 : ¬ (s.core.regs 52 - (b - a)) ≤ 0) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 9).core.pc = off + 201 ∧ (run Q s detTape 9).halted = false ∧ (run Q s detTape 9).core.ptrs 53 = s.core.ptrs 53 + 1 ∧ (run Q s detTape 9).core.ptrs 57 = s.core.ptrs 43 + s.core.ptrs 53 + s.core.ptrs 1 ∧ (∀ x, x ≠ 53 → x ≠ 57 → (run Q s detTape 9).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 9).core.regs 44 = a ∧ (run Q s detTape 9).core.regs 45 = b ∧ (run Q s detTape 9).core.regs 47 = (b - a) ∧ (run Q s detTape 9).core.regs 54 = (s.core.regs 52 - (b - a)) ∧ (∀ x, x ≠ 44 → x ≠ 45 → x ≠ 47 → x ≠ 54 → (run Q s detTape 9).core.regs x = s.core.regs x) ∧ (run Q s detTape 9).core.mem = s.core.mem ∧ (run Q s detTape 9).integerMemory = s.integerMemory ∧ (run Q s detTape 9).work = s.work + 9 ∧ cellsWritten Q s 9 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (a b : ℝ) (s : State) (hpc : s.core.pc = off + 201) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 53) = a) (fr1 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 53 + s.core.ptrs 1) = b) (hb0 : (s.core.regs 52 - (b - a)) ≤ 0) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 7).core.pc = off + 210 ∧ (run Q s detTape 7).halted = false ∧ (run Q s detTape 7).core.ptrs 57 = s.core.ptrs 43 + s.core.ptrs 53 + s.core.ptrs 1 ∧ (∀ x, x ≠ 57 → (run Q s detTape 7).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 7).core.regs 44 = a ∧ (run Q s detTape 7).core.regs 45 = b ∧ (run Q s detTape 7).core.regs 47 = (b - a) ∧ (run Q s detTape 7).core.regs 54 = (s.core.regs 52 - (b - a)) ∧ (∀ x, x ≠ 44 → x ≠ 45 → x ≠ 47 → 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) (s : State) (hpc : s.core.pc = off + 210) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1) (hx0 : s.core.ptrs 13 ≤ s.core.ptrs 44),
      (run Q s detTape 16).core.pc = off + 258 ∧ (run Q s detTape 16).halted = false ∧ (run Q s detTape 16).core.ptrs 13 = s.core.ptrs 13 - 4 ∧ (run Q s detTape 16).core.ptrs 50 = s.core.ptrs 43 ∧ (run Q s detTape 16).core.ptrs 51 = s.core.ptrs 1 + s.core.ptrs 53 ∧ (run Q s detTape 16).core.ptrs 52 = s.core.ptrs 13 - 4 ∧ (run Q s detTape 16).core.ptrs 57 = s.core.ptrs 13 - 3 ∧ (run Q s detTape 16).core.ptrs 58 = 0 ∧ (∀ x, x ≠ 13 → x ≠ 50 → x ≠ 51 → x ≠ 52 → x ≠ 57 → x ≠ 58 → (run Q s detTape 16).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 16).core.regs 44 = ((s.core.regs 44 + s.core.regs 45) / s.core.regs 53) ∧ (∀ x, x ≠ 44 → (run Q s detTape 16).core.regs x = s.core.regs x) ∧ (run Q s detTape 16).core.mem = s.core.mem ∧ (run Q s detTape 16).integerMemory (s.core.ptrs 13 - 4) = s.core.ptrs 68 ∧ (run Q s detTape 16).integerMemory (s.core.ptrs 13 - 3) = s.core.ptrs 43 ∧ (run Q s detTape 16).integerMemory (s.core.ptrs 44) = s.core.ptrs 13 - 4 ∧ (∀ z, z ≠ s.core.ptrs 13 - 4 → z ≠ s.core.ptrs 13 - 3 → z ≠ s.core.ptrs 44 → (run Q s detTape 16).integerMemory z = s.integerMemory z) ∧ (run Q s detTape 16).work = s.work + 16 ∧ ∀ c ∈ cellsWritten Q s 16, c = (false, s.core.ptrs 13 - 4) ∨ c = (false, s.core.ptrs 13 - 3) ∨ c = (false, s.core.ptrs 44)) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 226) (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 43 ∧ (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 = 1 ∧ (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 + 243) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 15).core.pc = off + 34 ∧ (run Q s detTape 15).halted = false ∧ (run Q s detTape 15).core.ptrs 13 = s.core.ptrs 13 - 3 ∧ (run Q s detTape 15).core.ptrs 42 = s.core.ptrs 13 - 3 ∧ (run Q s detTape 15).core.ptrs 57 = s.core.ptrs 13 - 1 ∧ (run Q s detTape 15).core.ptrs 62 = s.core.ptrs 52 + 3 ∧ (∀ x, x ≠ 13 → x ≠ 42 → x ≠ 57 → x ≠ 62 → (run Q s detTape 15).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 15).core.regs = s.core.regs ∧ (run Q s detTape 15).core.mem = s.core.mem ∧ (run Q s detTape 15).integerMemory (s.core.ptrs 13 - 3) = s.core.ptrs 56 ∧ (run Q s detTape 15).integerMemory (s.core.ptrs 13 - 2) = s.core.ptrs 52 + 3 ∧ (run Q s detTape 15).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 15).integerMemory z = s.integerMemory z) ∧ (run Q s detTape 15).work = s.work + 15 ∧ ∀ c ∈ cellsWritten Q s 15, 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 + 258) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 3).core.pc = off + 261 ∧ (run Q s detTape 3).halted = false ∧ (run Q s detTape 3).core.ptrs 14 = s.core.ptrs 14 - s.core.ptrs 60 ∧ (run Q s detTape 3).core.ptrs 46 = 0 ∧ (run Q s detTape 3).core.ptrs 56 = s.core.ptrs 14 - s.core.ptrs 60 ∧ (∀ x, x ≠ 14 → x ≠ 46 → x ≠ 56 → (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) (x : ℝ) (s : State) (hpc : s.core.pc = off + 261) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 50 + s.core.ptrs 46) = x) (hb0 : s.core.ptrs 46 < s.core.ptrs 60) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 7).core.pc = off + 261 ∧ (run Q s detTape 7).halted = false ∧ (run Q s detTape 7).core.ptrs 46 = s.core.ptrs 46 + 1 ∧ (run Q s detTape 7).core.ptrs 57 = s.core.ptrs 56 + s.core.ptrs 46 ∧ (∀ x, x ≠ 46 → x ≠ 57 → (run Q s detTape 7).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 7).core.regs 55 = x ∧ (∀ x, x ≠ 55 → (run Q s detTape 7).core.regs x = s.core.regs x) ∧ (run Q s detTape 7).core.mem (s.core.ptrs 56 + s.core.ptrs 46) = x ∧ (∀ z, z ≠ s.core.ptrs 56 + s.core.ptrs 46 → (run Q s detTape 7).core.mem z = s.core.mem z) ∧ (run Q s detTape 7).integerMemory = s.integerMemory ∧ (run Q s detTape 7).work = s.work + 7 ∧ ∀ c ∈ cellsWritten Q s 7, c = (true, s.core.ptrs 56 + s.core.ptrs 46)) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 261) (hh : s.halted = false) (hb0 : s.core.ptrs 60 ≤ s.core.ptrs 46) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 1).core.pc = off + 268 ∧ (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) (s : State) (hpc : s.core.pc = off + 268) (hh : s.halted = false) (hb0 : s.core.ptrs 58 ≤ s.core.ptrs 69) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 3).core.pc = off + 226 ∧ (run Q s detTape 3).halted = false ∧ (run Q s detTape 3).core.ptrs 57 = s.core.ptrs 56 + s.core.ptrs 51 ∧ (∀ x, x ≠ 57 → (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.ptrs 56 + s.core.ptrs 51) = s.core.regs 44 ∧ (∀ z, z ≠ s.core.ptrs 56 + s.core.ptrs 51 → (run Q s detTape 3).core.mem z = s.core.mem z) ∧ (run Q s detTape 3).integerMemory = s.integerMemory ∧ (run Q s detTape 3).work = s.work + 3 ∧ ∀ c ∈ cellsWritten Q s 3, c = (true, s.core.ptrs 56 + s.core.ptrs 51)) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 268) (hh : s.halted = false) (hb0 : s.core.ptrs 69 < s.core.ptrs 58) (hb1 : s.core.ptrs 58 ≤ 1) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 5).core.pc = off + 243 ∧ (run Q s detTape 5).halted = false ∧ (run Q s detTape 5).core.ptrs 57 = 1 ∧ (∀ x, x ≠ 57 → (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.ptrs 56 + s.core.ptrs 51) = s.core.regs 44 ∧ (∀ z, z ≠ s.core.ptrs 56 + s.core.ptrs 51 → (run Q s detTape 5).core.mem z = s.core.mem z) ∧ (run Q s detTape 5).integerMemory = s.integerMemory ∧ (run Q s detTape 5).work = s.work + 5 ∧ ∀ c ∈ cellsWritten Q s 5, c = (true, s.core.ptrs 56 + s.core.ptrs 51)) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 268) (hh : s.halted = false) (hb0 : s.core.ptrs 69 < s.core.ptrs 58) (hb1 : 1 < s.core.ptrs 58) (hb2 : s.core.ptrs 58 ≤ 2) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 7).core.pc = off + 304 ∧ (run Q s detTape 7).halted = false ∧ (run Q s detTape 7).core.ptrs 57 = 2 ∧ (∀ x, x ≠ 57 → (run Q s detTape 7).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 7).core.regs = s.core.regs ∧ (run Q s detTape 7).core.mem (s.core.ptrs 56 + s.core.ptrs 51) = s.core.regs 44 ∧ (∀ z, z ≠ s.core.ptrs 56 + s.core.ptrs 51 → (run Q s detTape 7).core.mem z = s.core.mem z) ∧ (run Q s detTape 7).integerMemory = s.integerMemory ∧ (run Q s detTape 7).work = s.work + 7 ∧ ∀ c ∈ cellsWritten Q s 7, c = (true, s.core.ptrs 56 + s.core.ptrs 51)) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 268) (hh : s.halted = false) (hb0 : s.core.ptrs 69 < s.core.ptrs 58) (hb1 : 1 < s.core.ptrs 58) (hb2 : 2 < s.core.ptrs 58) (hb3 : s.core.ptrs 58 ≤ 3) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 9).core.pc = off + 321 ∧ (run Q s detTape 9).halted = false ∧ (run Q s detTape 9).core.ptrs 57 = 3 ∧ (∀ x, x ≠ 57 → (run Q s detTape 9).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 9).core.regs = s.core.regs ∧ (run Q s detTape 9).core.mem (s.core.ptrs 56 + s.core.ptrs 51) = s.core.regs 44 ∧ (∀ z, z ≠ s.core.ptrs 56 + s.core.ptrs 51 → (run Q s detTape 9).core.mem z = s.core.mem z) ∧ (run Q s detTape 9).integerMemory = s.integerMemory ∧ (run Q s detTape 9).work = s.work + 9 ∧ ∀ c ∈ cellsWritten Q s 9, c = (true, s.core.ptrs 56 + s.core.ptrs 51)) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 268) (hh : s.halted = false) (hb0 : s.core.ptrs 69 < s.core.ptrs 58) (hb1 : 1 < s.core.ptrs 58) (hb2 : 2 < s.core.ptrs 58) (hb3 : 3 < s.core.ptrs 58) (hb4 : s.core.ptrs 58 ≤ 4) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 11).core.pc = off + 348 ∧ (run Q s detTape 11).halted = false ∧ (run Q s detTape 11).core.ptrs 57 = 4 ∧ (∀ x, 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.ptrs 56 + s.core.ptrs 51) = s.core.regs 44 ∧ (∀ z, z ≠ s.core.ptrs 56 + s.core.ptrs 51 → (run Q s detTape 11).core.mem z = s.core.mem z) ∧ (run Q s detTape 11).integerMemory = s.integerMemory ∧ (run Q s detTape 11).work = s.work + 11 ∧ ∀ c ∈ cellsWritten Q s 11, c = (true, s.core.ptrs 56 + s.core.ptrs 51)) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 268) (hh : s.halted = false) (hb0 : s.core.ptrs 69 < s.core.ptrs 58) (hb1 : 1 < s.core.ptrs 58) (hb2 : 2 < s.core.ptrs 58) (hb3 : 3 < s.core.ptrs 58) (hb4 : 4 < s.core.ptrs 58) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 12).core.pc = off + 366 ∧ (run Q s detTape 12).halted = false ∧ (run Q s detTape 12).core.ptrs 57 = 4 ∧ (∀ x, 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.ptrs 56 + s.core.ptrs 51) = s.core.regs 44 ∧ (∀ z, z ≠ s.core.ptrs 56 + s.core.ptrs 51 → (run Q s detTape 12).core.mem z = s.core.mem z) ∧ (run Q s detTape 12).integerMemory = s.integerMemory ∧ (run Q s detTape 12).work = s.work + 12 ∧ ∀ c ∈ cellsWritten Q s 12, c = (true, s.core.ptrs 56 + s.core.ptrs 51)) := 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