(26), p.18 (Lemma 5.2 form) — for any tuple family
ProvedDetANN.eq_26approximate-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 , let , and put . Then
This bounds the projected error and the within-block variance; it is (26) for the walk family and (17)–(18) of Lemma 5.2 for the exhaustive family.
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
/-- **(26), the Lemma 5.2 form** (Y. Feng, P. Indyk, *Deterministic Approximate Nearest Neighbors in High Dimensions*, STOC 2027
submission (manuscript sha256 96f0ad57…), §7.3, p.18; Lemma 5.2, (17)–(18), p.11).
With `T_i = ‖A_i(q − x⋆ − a_i)‖²` and `r = ‖q − x⋆‖`:
`∑_i T_i + (1 − τ)𝒱 ≤ α² r²`; in particular `𝒱 ≤ α² r²/(1 − τ)` and `∑_i T_i + 𝒱 ≤ α² r²/(1 − τ)`.
**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 eq_26 {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 α) :
∑ i, ‖A i (q - xs - condMean S x xs i)‖ ^ 2 + (1 - τ) * withinVar S x xs ≤
α ^ 2 * ‖q - xs‖ ^ 2 ∧
withinVar S x xs ≤ α ^ 2 * ‖q - xs‖ ^ 2 / (1 - τ) ∧
∑ i, ‖A i (q - xs - condMean S x xs i)‖ ^ 2 + withinVar S x xs ≤
α ^ 2 * ‖q - xs‖ ^ 2 / (1 - τ) := by sorry
end DetANN
Source
Feng, Indyk, Deterministic Approximate Nearest Neighbors in High Dimensions, STOC 2027 submission (manuscript sha256 96f0ad57b9d12ba3ac6f9e61c88ddfd6b621e077d7e2a9821906e5b4ff0d0e82), (26), §7.3, p.18 (PDF p.18); Lemma 5.2, (17)–(18), p.11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.