Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The deduplicated difference table of the construction program

Definition
DetANN_Supplement_PreDedup

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

approximate-nearest-neighborprogram-verificationreal-ram

Definitions describing the dedupe step of the program pre (definition DetANN_Supplement_PreProg).

  • ddStep(l,v)\mathrm{ddStep}(l,v)ddStep(l,v) appends vvv to the list lll unless v∈lv\in lv∈l.
  • ddJ\mathrm{ddJ}ddJ and ddI\mathrm{ddI}ddI are the inner loop over jjj and the outer loop over iii; ddList(x,n)\mathrm{ddList}(x,n)ddList(x,n) starts from the empty list and applies ddStep\mathrm{ddStep}ddStep to xi−xjx_i-x_jxi​−xj​ for the pairs i<j<ni<j<ni<j<n in lexicographic order.
  • ptSeq(P)\mathrm{ptSeq}(P)ptSeq(P) is the sequence i↦Pii\mapsto P_ii↦Pi​ for i<ni<ni<n and 000 otherwise, for P:Fin n→RdP:\mathrm{Fin}\,n\to\mathbb R^dP:Finn→Rd.
  • TableAt(mem,Db,l)\mathrm{TableAt}(\mathrm{mem},D_b,l)TableAt(mem,Db​,l) says that entry mmm of lll is stored in the real cells Db+md,…,Db+md+d−1D_b+md,\dots,D_b+md+d-1Db​+md,…,Db​+md+d−1.
  • pairB(d,Lm)=10d+10+Lm(12d+8)\mathrm{pairB}(d,L_m)=10d+10+L_m(12d+8)pairB(d,Lm​)=10d+10+Lm​(12d+8) is the step bound of one pair for a table of at most LmL_mLm​ entries.
Definition code
import Mathlib

/-!
# Milestone 21 (`DetANN.Supplement.theorem_3_2`): the dedupe of the construction program

The differences `x i - x j` (`i < j < n`) are appended in order to a list, skipping those already
present (`ddStep`, `ddJ`, `ddI`, `ddList`); `ptSeq P` lists the points of `P` by index; `TableAt mem Db l`
says that entry `m` of `l` is stored at the real cells `Db + m·d, …, Db + m·d + d - 1`; `pairB` is the
step bound of one pair.
-/

namespace DetANN.Supplement.Thm32

variable {d : ℕ}

/-- Append `v` unless it is already present. -/
noncomputable def ddStep (l : List (EuclideanSpace ℝ (Fin d))) (v : EuclideanSpace ℝ (Fin d)) :
    List (EuclideanSpace ℝ (Fin d)) :=
  if v ∈ l then l else l ++ [v]

/-- The inner loop: `j, j+1, …, j+kk-1`. -/
noncomputable def ddJ (x : ℕ → EuclideanSpace ℝ (Fin d)) (i : ℕ) :
    ℕ → ℕ → List (EuclideanSpace ℝ (Fin d)) → List (EuclideanSpace ℝ (Fin d))
  | _, 0, l => l
  | j, kk + 1, l => ddJ x i (j + 1) kk (ddStep l (x i - x j))

/-- The outer loop: `i, i+1, …, i+kk-1`, each with `j` from `i+1` to `n-1`. -/
noncomputable def ddI (x : ℕ → EuclideanSpace ℝ (Fin d)) (n : ℕ) :
    ℕ → ℕ → List (EuclideanSpace ℝ (Fin d)) → List (EuclideanSpace ℝ (Fin d))
  | _, 0, l => l
  | i, kk + 1, l => ddI x n (i + 1) kk (ddJ x i (i + 1) (n - (i + 1)) l)

/-- The table after all pairs `i < j < n`, starting from the empty list. -/
noncomputable def ddList (x : ℕ → EuclideanSpace ℝ (Fin d)) (n : ℕ) : List (EuclideanSpace ℝ (Fin d)) :=
  ddI x n 0 n []

/-- The points as a sequence indexed by `ℕ`. -/
noncomputable def ptSeq {n : ℕ} (P : Fin n → EuclideanSpace ℝ (Fin d)) (i : ℕ) : EuclideanSpace ℝ (Fin d) :=
  if h : i < n then P ⟨i, h⟩ else 0

/-- The list `l` is stored at `Db`, entry `m` at `Db + m·d`. -/
def TableAt (mem : ℤ → ℝ) (Db : ℤ) (l : List (EuclideanSpace ℝ (Fin d))) : Prop :=
  ∀ (m : ℕ) (v : EuclideanSpace ℝ (Fin d)), l[m]? = some v → ∀ c : Fin d,
    mem (Db + ((m * d + c : ℕ) : ℤ)) = v c

/-- The step bound of one pair `(i, j)` of the dedupe loop, for a table of at most `Lm` entries. -/
def pairB (d Lm : ℕ) : ℕ := 10 * d + 10 + Lm * (12 * d + 8)

end DetANN.Supplement.Thm32
Source
Original, written for the mission 'Deterministic Approximate Nearest Neighbors in High Dimensions' as part of a proof of DetANN.Supplement.theorem_3_2 (Feng, Indyk, STOC 2027 submission, Theorem 3.2, p.7; the construction of §6.1, p.14, and Lemma 6.2). 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