The dedupe table is the difference set of Theorem 3.2
ProvedDetANN.Supplement.Thm32.dedup_set_specapproximate-nearest-neighborprogram-verificationreal-ram
Let be injective and let be the finset of the list (definition DetANN_Supplement_PreDedup). Then
- ;
- for distinct points of , or ;
- equals the length of the list;
- if then .
These are the hypotheses on of theorem_3_2_greedy.
Preamble
import Mathlib import Definitions.Def_PNormReg_Machine import Definitions.Def_DetANN_DataStructure import Definitions.Def_PNormRegLib_Reloc import Definitions.Def_DetANN_Sylvester import Definitions.Def_DetANN_SignedBlocks import Definitions.Def_DetANN_Supplement_EvProg import Definitions.Def_DetANN_Supplement_PreProg import Definitions.Def_DetANN_Supplement_PreDedup
Formal statement
namespace DetANN.Supplement.Thm32
open PNormReg PNormRegLib DetANN
/-- **The dedupe table is the difference set of Theorem 3.2.** For injective `P`, the finset of
`ddList (ptSeq P) n` has no zero vector, contains `y - z` or `z - y` for all distinct points `y, z`,
has as many elements as the list has entries, and is nonempty when `n ≥ 2`. These are the hypotheses on
`𝒟` of `theorem_3_2_greedy`. -/
theorem dedup_set_spec :
∀ {d : ℕ} {n : ℕ} (P : Fin n → EuclideanSpace ℝ (Fin d)) (hP : Function.Injective P),
(∀ v ∈ (ddList (ptSeq P) n).toFinset, v ≠ 0) ∧
(∀ y ∈ Finset.univ.image P, ∀ z ∈ Finset.univ.image P, y ≠ z →
y - z ∈ (ddList (ptSeq P) n).toFinset ∨ z - y ∈ (ddList (ptSeq P) n).toFinset) ∧
(ddList (ptSeq P) n).toFinset.card = (ddList (ptSeq P) n).length ∧
(2 ≤ n → 1 ≤ (ddList (ptSeq P) n).toFinset.card) := by sorry
end DetANN.Supplement.Thm32Source
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.