Straight-line segments of the BSP construction block: carve and leaf
ProvedDetANN.HPIM.BD.carve_stepsapproximate-nearest-neighborcomputational-geometrydata-structures
Thirteen straight-line facts about the program 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 contain at offset (Embeds Q (bd off) off), and let be a non-halted state at the stated pc with pointer 1 and the stated hypotheses. Then after exactly the stated number of steps, the run of from :
- is at the stated pc (relative to ) 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 , and its
cellsWrittenset consists of the listed cells.
Pointer 1 holds , pointer 11 holds , and , denote pointers 13, 14 of .
- Carve start (3): pointers , , .
- Carve end (1): when .
- No low peel (7): when (reals 44, 45).
- Low peel (21): when : a cut node at with ; copy-and-set of the current box with index , value and code 2.
- Push the low slab (17): pushes ; copy-and-set of the current box with index and code 3.
- Continue (5): current box := the new box, current slot := node .
- No high peel (8): when .
- High peel (22): a cut node as in 4; copy-and-set with index , value and code 4.
- Push the high slab (18): pushes ; copy-and-set with index and code 5.
- Continue (6): current box := the new box, current slot := node , .
- Next axis (2): .
- Push the core (11): pushes .
- Leaf (12): writes the leaf node at and .
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.BDSource
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.