Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Program blocks for the HPIM preprocessing program

Definition
DetANN_HPIMPreBlocks

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

approximate-nearest-neighborcomputational-geometrydata-structures

Vocabulary for building the preprocessing program of hpim_preprocessing out of blocks, on the PNormReg machine (definition PNormReg_Machine). In a state, III is the integer memory and RRR the real memory.

  1. Blocks. A block is a family blk:N→Program\mathrm{blk}:\mathbb N\to\mathrm{Program}blk:N→Program.
    • The code blk(o)\mathrm{blk}(o)blk(o) is placed at position ooo of a host program, so its jump targets are absolute (o+ko+ko+k).
    • IsBlock blk L says that every blk(o)\mathrm{blk}(o)blk(o) has length LLL and is a deterministic program (DetProgram).
    • A block specification is stated for every host QQQ that embeds blk(o)\mathrm{blk}(o)blk(o) at ooo.
  2. Frames.
    • KeepsLow s s' outP outR: the pointer and real registers with index <40<40<40 agree between sss and s′s's′, except the listed output registers.
    • WritesOnly Q s t W: every cell stored to in the first ttt steps of QQQ from sss satisfies WWW. Here (true,z)(\mathrm{true},z)(true,z) is real cell zzz and (false,z)(\mathrm{false},z)(false,z) is integer cell zzz.
  3. Local points. LocalPts s P says that P0,…,Pn−1∈RmP_0,\dots,P_{n-1}\in\mathbb R^mP0​,…,Pn−1​∈Rm are stored in sss:
    • pointer 111 is mmm and pointer 111111 is nnn;
    • the list at pointer 101010 holds global indices gi=I[p10+i]g_i=I[p_{10}+i]gi​=I[p10​+i];
    • point ggg starts at real address I[p12+g]I[p_{12}+g]I[p12​+g], so R[I[p12+gi]+j]=Pi(j)R[I[p_{12}+g_i]+j]=P_i(j)R[I[p12​+gi​]+j]=Pi​(j);
    • all addresses are ≥0\ge0≥0.
  4. Components. compMin P d i is the least index in the component of iii in the threshold graph at ddd, whose edges are {a,b}\{a,b\}{a,b} with ∥Pa−Pb∥≤d\|P_a-P_b\|\le d∥Pa​−Pb​∥≤d.
  5. Stored BSPs. BSPAt m s ilo ihi rlo rhi u T says that the BSP TTT (definition DetANN_HPIMBSP) is stored from integer address uuu, with all its integer cells in [ilo,ihi)[i_{lo},i_{hi})[ilo​,ihi​) and all its real cells in [rlo,rhi)[r_{lo},r_{hi})[rlo​,rhi​).
    • At node uuu: I[u]I[u]I[u] is 000 for a leaf and 111 for a cut, and I[u+1]I[u+1]I[u+1] is the real address of the node's box (lololo, then hihihi, mmm cells each).
    • A leaf has I[u+2]I[u+2]I[u+2] equal to 000 (OUT) or i+1i+1i+1 (IN iii).
    • A cut has its children at I[u+2]I[u+2]I[u+2] and I[u+3]I[u+3]I[u+3].
  6. Size of the HPIM tree. For the tree of definition DetANN_HPIMTree, treePts(Y,f,S)\mathrm{treePts}(Y,f,S)treePts(Y,f,S) is the total number of points over the tree on SSS with fuel fff:
treePts(f,S)={∣S∣f=0 or ∣S∣≤1,∣S∣+∑CtreePts(f−1,C)+treePts(f−1,R)otherwise,\mathrm{treePts}(f,S)=\begin{cases}|S|&f=0\text{ or }|S|\le1,\\ |S|+\sum_{C}\mathrm{treePts}(f-1,C)+\mathrm{treePts}(f-1,R)&\text{otherwise,}\end{cases}treePts(f,S)={∣S∣∣S∣+∑C​treePts(f−1,C)+treePts(f−1,R)​f=0 or ∣S∣≤1,otherwise,​

where CCC runs over the distinct components at rmedr_{\mathrm{med}}rmed​ and RRR is the set of representatives at 2rmed2r_{\mathrm{med}}2rmed​. Children with equal sets are counted once, because they are stored once.

Definition code
import Mathlib
import Definitions.Def_PNormReg_Machine
import Definitions.Def_PNormRegLib_Reloc
import Definitions.Def_DetANN_DataStructure
import Definitions.Def_DetANN_HPIMBSP
import Definitions.Def_DetANN_HPIMTree

/-!
# Program blocks for the HPIM preprocessing program

The preprocessing program of `DetANN.HPIM.hpim_preprocessing` is assembled from **blocks**. A block is
a family `blk : ℕ → Program` of fixed length `L`. Here `blk off` is the code placed at position `off`
of a host program, so its jump targets are absolute (`off + k`). A block specification holds in
*every* host `Q` that embeds `blk off` at `off` (`PNormRegLib.Embeds`). It starts at `pc = off` and
ends at `pc = off + L` without halting.

**Register convention.** Pointer and real registers `< 40` belong to the host. A block changes only
its listed output registers among them (`KeepsLow`). Registers `≥ 40` are free scratch for blocks.
The interface registers are:
* pointers:
  * `1` = `m`;
  * `10` = address of the local index list `S`;
  * `11` = `n`;
  * `12` = base of the point-address table;
  * `13`, `14` = tops of the integer and real scratch stacks (free cells lie *below* them);
  * `15`, `16` = integer and real heap pointers (free cells lie *at and above* them);
  * `17` = an address passed in or out;
* reals: `10` = a threshold or the median threshold, `11` = a radius `r`, `12` = a factor `c`.

**Memory convention.** Inputs and the heap live at addresses `≥ 0`. Scratch lives at addresses `< 0`.

* `IsBlock blk L`: every `blk off` has length `L` and is a `DetProgram`.
* `KeepsLow`, `WritesOnly`: register frame and write frame of a run segment.
* `LocalPts s pts`: the local points `pts` are stored in `s`. Their global indices are `I[S + i]`,
  and point `g` starts at real address `I[PA + g]`.
* `compMin P d i`: the least index of the component of `i` in the threshold graph at `d`.
* `BSPAt m s ilo ihi rlo rhi u T`: the BSP `T` is stored from integer address `u`, with all its
  integer cells in `[ilo, ihi)` and all its real cells in `[rlo, rhi)`.
* `treePts Y S f`: the total number of points over the HPIM tree on `S`. Children with equal sets
  under one node are counted once, because they are stored once.
-/

namespace DetANN.HPIM

open PNormReg

/-- `blk off` has length `L` and is a deterministic program, for every offset. -/
def IsBlock (blk : ℕ → Program) (L : ℕ) : Prop :=
  ∀ off, (blk off).length = L ∧ DetProgram (blk off)

/-- Host registers (`< 40`) are kept, except the listed output pointers `outP` and reals `outR`. -/
def KeepsLow (s s' : State) (outP outR : List ℕ) : Prop :=
  (∀ x < 40, x ∉ outP → s'.core.ptrs x = s.core.ptrs x) ∧
    (∀ x < 40, x ∉ outR → s'.core.regs x = s.core.regs x)

/-- Every cell stored to in the first `t` steps of `Q` from `s` satisfies `W`
(`(true, z)`: real cell `z`; `(false, z)`: integer cell `z`). -/
def WritesOnly (Q : Program) (s : State) (t : ℕ) (W : Bool × ℤ → Prop) : Prop :=
  ∀ c ∈ cellsWritten Q s t, W c

/-- The local points `pts` are stored in `s` (all addresses `≥ 0`). -/
def LocalPts {m n : ℕ} (s : State) (pts : Fin n → Fin m → ℝ) : Prop :=
  s.core.ptrs 1 = m ∧ s.core.ptrs 11 = n ∧ 0 ≤ s.core.ptrs 10 ∧ 0 ≤ s.core.ptrs 12 ∧
    ∀ i : Fin n, 0 ≤ s.integerMemory (s.core.ptrs 10 + i) ∧
      0 ≤ s.integerMemory (s.core.ptrs 12 + s.integerMemory (s.core.ptrs 10 + i)) ∧
      ∀ j : Fin m,
        s.core.mem (s.integerMemory (s.core.ptrs 12 + s.integerMemory (s.core.ptrs 10 + i)) + j) =
          pts i j

/-- The least index of the component of `i` in the threshold graph at `d`. -/
noncomputable def compMin {m n : ℕ} (P : Fin n → EuclideanSpace ℝ (Fin m)) (d : ℝ) (i : Fin n) : ℕ := by
  classical
  exact ((Finset.univ.filter (thrReach P d i)).min'
    ⟨i, Finset.mem_filter.2 ⟨Finset.mem_univ _, SimpleGraph.Reachable.refl _⟩⟩ : ℕ)

/-- The BSP `T` is stored from integer address `u`, inside the integer window `[ilo, ihi)` and the
real window `[rlo, rhi)`. A node at `u`: `I[u] = 0` (leaf) or `1` (cut); `I[u+1]` is the real address
of its box (`lo`: `m` cells, then `hi`: `m` cells). For a leaf, `I[u+2]` is `0` (OUT) or `i + 1`
(IN `i`). For a cut, `I[u+2]` and `I[u+3]` are the addresses of the left and right children. -/
inductive BSPAt (m : ℕ) (s : State) (ilo ihi rlo rhi : ℤ) : ℤ → BSP m → Prop
  | leaf (u : ℤ) (lo hi : Fin m → ℝ) (a : Option ℕ) :
      ilo ≤ u → u + 3 ≤ ihi → s.integerMemory u = 0 →
      rlo ≤ s.integerMemory (u + 1) → s.integerMemory (u + 1) + 2 * m ≤ rhi →
      (∀ j : Fin m, s.core.mem (s.integerMemory (u + 1) + j) = lo j) →
      (∀ j : Fin m, s.core.mem (s.integerMemory (u + 1) + m + j) = hi j) →
      s.integerMemory (u + 2) = (match a with | none => 0 | some i => (i : ℤ) + 1) →
      BSPAt m s ilo ihi rlo rhi u (.leaf lo hi a)
  | cut (u : ℤ) (lo hi : Fin m → ℝ) (l r : BSP m) :
      ilo ≤ u → u + 4 ≤ ihi → s.integerMemory u = 1 →
      rlo ≤ s.integerMemory (u + 1) → s.integerMemory (u + 1) + 2 * m ≤ rhi →
      (∀ j : Fin m, s.core.mem (s.integerMemory (u + 1) + j) = lo j) →
      (∀ j : Fin m, s.core.mem (s.integerMemory (u + 1) + m + j) = hi j) →
      BSPAt m s ilo ihi rlo rhi (s.integerMemory (u + 2)) l →
      BSPAt m s ilo ihi rlo rhi (s.integerMemory (u + 3)) r →
      BSPAt m s ilo ihi rlo rhi u (.cut lo hi l r)

/-- The total number of points over the HPIM tree on `S` with fuel `f` (the recursion of
`hpimNode`). The children of one node with the same set are counted once. -/
noncomputable def treePts {m N : ℕ} (Y : Fin N → EuclideanSpace ℝ (Fin m)) :
    ℕ → Finset (Fin N) → ℕ
  | 0, S => S.card
  | f + 1, S => by
    classical
    exact if S.card ≤ 1 then S.card else
      S.card + (∑ C ∈ Finset.univ.image (compBotOf Y S), treePts Y f C) + treePts Y f (repsOf Y S)

end DetANN.HPIM
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): the preprocessing program of DetANN.HPIM.hpim_preprocessing is assembled from these blocks. 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