Lemma 5.4, p.13 (§7.3 form) —
ProvedDetANN.lemma_5_4approximate-nearest-neighbordata-structuresderandomizationexpander-graphsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Throughout, a tuple family is a map on finite nonempty sets (tuples) and (occurrences) with uniform block frequencies: every block occurs times among the pairs . Choose uniformly and put . For answers and a point write , , , , and for the superblock of (repeated blocks counted with multiplicity). The local guarantee with factor is for every .
Let be a -balanced block system for with , let the answers satisfy the local guarantee with factor , and let . Then
It bounds the second moment of the returned points around , which controls the error term of Lemma 5.3.
Differences from the source:
- generalization: the walk family of §7 (and, in §5, the exhaustive family [d]^s); x⋆ a nearest neighbor of q → any finite tuple family with uniform block frequencies and nonempty Vtx, Occ; x⋆ any point of P; reason: §7.3 says the arguments use only uniform block frequencies and balance of differences; both families have uniform frequencies, and a nearest neighbor is a point of P
- encoding: expectations over the random choice of V and of an occurrence; the min-form local guarantee (11)/(25) → finite uniform averages over Vtx × Occ; the squared guarantee ‖𝒜_v(q − x_v)‖² ≤ α²‖𝒜_v(q − y)‖² for all y ∈ P; reason: the averages are the expectations; for α ≥ 0 and finite nonempty P the squared and min forms are equivalent
Preamble
import Mathlib import Definitions.Def_DetANN_BalancedBlocks import Definitions.Def_DetANN_TupleFamily
Formal statement
namespace DetANN
/-- **Lemma 5.4, in the §7.3 form** (Y. Feng, P. Indyk, *Deterministic Approximate Nearest Neighbors in High Dimensions*, STOC 2027
submission (manuscript sha256 96f0ad57…), §7.3, p.18; Lemma 5.4, p.13).
`E_V ‖x_V − x⋆‖² ≤ (1 + α)²/(1 − τ) · r²` with `r = ‖q − x⋆‖`.
**Formalization Note.** The family is any finite family of tuples `S : Vtx → Occ → Fin d` with
uniform block frequencies and nonempty `Vtx`, `Occ` (the paper: the exhaustive family `[d]^s` of §5
and the walk family of §7). Expectations are finite averages over `(V, O)` uniform on `Vtx × Occ`
(see `DetANN.TupleFamily`). `x⋆` is any point of `P`; the paper takes a nearest neighbor of `q`, and
the argument uses only `x⋆ ∈ P`. -/
theorem lemma_5_4 {d b : ℕ} {Vtx Occ : Type} [Fintype Vtx] [Fintype Occ] [Nonempty Vtx] [Nonempty Occ]
(τ α : ℝ) (hτ0 : 0 < τ) (hτ1 : τ < 1) (hα : 1 ≤ α)
(P : Finset (EuclideanSpace ℝ (Fin d)))
(A : Fin d → EuclideanSpace ℝ (Fin d) →ₗ[ℝ] EuclideanSpace ℝ (Fin b))
(hA : IsBalancedBlockSystem τ P A)
(S : Vtx → Occ → Fin d) (hS : UniformFreq S)
(q xs : EuclideanSpace ℝ (Fin d)) (hxs : xs ∈ P)
(x : Vtx → EuclideanSpace ℝ (Fin d)) (hx : ∀ v, x v ∈ P)
(hloc : LocalGuarantee A S P q x α) :
(Fintype.card Vtx : ℝ)⁻¹ * ∑ v, ‖x v - xs‖ ^ 2 ≤ (1 + α) ^ 2 / (1 - τ) * ‖q - xs‖ ^ 2 := by sorry
end DetANN
Source
Feng, Indyk, Deterministic Approximate Nearest Neighbors in High Dimensions, STOC 2027 submission (manuscript sha256 96f0ad57b9d12ba3ac6f9e61c88ddfd6b621e077d7e2a9821906e5b4ff0d0e82), §7.3, p.18 (PDF p.18); Lemma 5.4, p.13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.