Theorem 4.1, pp.8–9 — over all tuples some answer is within factor of the nearest distance, and
ProvedDetANN.Supplement.theorem_4_1Let , let be finite, and let be a -balanced block system for (Definition 3.1) with . Let . For an ordered tuple (repeated indices allowed) the superblock is
Fix a query and a factor , and suppose that for every a point satisfies the local guarantee (11),
Theorem.
- Then
- In particular, if is bounded and , then : for every bound there is a constant such that for all , and integers .
This is the correctness guarantee of the exhaustive construction of §4: querying one low-dimensional structure per superblock and returning the best candidate in the original space gives approximation factor , which is for the parameters (12).
Formalization Note The exhaustive family is the published tuple-family framework (DetANN.TupleFamily) with tuples and ; the local guarantee is stated squared, which is equivalent for . The answers may depend on .
Differences from the source:
- generalization: standing assumptions of §3 ( a power of two, of size ) → any and any finite ; reason: Theorem 4.1 and its proof (§5) use only Definition 3.1 and averages over ; the paper's case is the special case.
- encoding: → some has for every ; reason: both minima are over finite nonempty sets (, and contains the ).
- encoding: (11) → for all ; reason: both sides nonnegative and .
- reading: "if is bounded and , then " → for every bound there is with for all , , ; reason: standard meaning of the -statement, with the constant depending only on the bound on ; the two-sided form is the stronger reading.
import Mathlib import Definitions.Def_DetANN_BalancedBlocks import Definitions.Def_DetANN_TupleFamily
namespace DetANN
namespace Supplement
/-- **Theorem 4.1** (Y. Feng, P. Indyk, *Deterministic Approximate Nearest Neighbors in High
Dimensions*, STOC 2027 submission (manuscript sha256 96f0ad57…), pp.8–9).
Let `A₁, …, A_d` be a `τ`-balanced block system for `P`, with `0 < τ < 1`, and let `s ≥ 2`. Suppose
that for every `ω ∈ [d]^s` a point `x_ω ∈ P` satisfies (11) with factor `α ≥ 1`. Then for every
query `q`, `min_ω ‖q − x_ω‖ ≤ C_{α,τ,s} · min_{x ∈ P} ‖q − x‖`, where
`C_{α,τ,s} = (α + √(2α²/(s − 1) + 12τ(1 + α)²))/√(1 − τ)`. In particular, if `α` is bounded and
`τ ≤ 1/2`, then `C_{α,τ,s} = α + O(s^{−1/2} + √τ)`.
**Formalization Note.**
* The exhaustive family of §4.1 is `S ω j = ω j` over all ordered tuples `ω : Fin s → Fin d`
(repetitions allowed), so `superNormSq A S ω z = ∑ⱼ ‖A_{ω j} z‖² = ‖A_ω z‖²`, blocks retained with
multiplicity. The local guarantee (11) is `DetANN.LocalGuarantee`, its squared form, equivalent for
`α ≥ 0`. The answers `x` are chosen after the query `q`, as in the paper.
* `min_ω ‖q − x_ω‖ ≤ C · min_{x∈P} ‖q − x‖` is written as: some `ω` has `‖q − x_ω‖ ≤ C‖q − y‖` for
every `y ∈ P` (both minima are over finite nonempty sets).
* `d ≥ 1` is the paper's standing assumption and is needed: for `d = 0` there is no tuple `ω`. The
other standing assumptions (`d` a power of two, `n ≥ d`) are not used by Theorem 4.1 and are
dropped; `P` is any finite set (nonempty because it contains the `x_ω`).
* "In particular": for every bound `A` there is `K` such that `|C_{α,τ,s} − α| ≤ K(s^{−1/2} + √τ)`
for all `α ∈ [1, A]`, `τ ∈ (0, 1/2]` and integers `s ≥ 2`; `s^{−1/2}` is `1/√s`. -/
theorem theorem_4_1 :
(∀ {d b s : ℕ}, 1 ≤ d → 2 ≤ s →
∀ τ α : ℝ, 0 < τ → τ < 1 → 1 ≤ α →
∀ (P : Finset (EuclideanSpace ℝ (Fin d)))
(A : Fin d → EuclideanSpace ℝ (Fin d) →ₗ[ℝ] EuclideanSpace ℝ (Fin b)),
IsBalancedBlockSystem τ P A →
∀ (q : EuclideanSpace ℝ (Fin d)) (x : (Fin s → Fin d) → EuclideanSpace ℝ (Fin d)),
(∀ ω, x ω ∈ P) →
LocalGuarantee A (fun (ω : Fin s → Fin d) (j : Fin s) => ω j) P q x α →
∃ ω : Fin s → Fin d, ∀ y ∈ P,
‖q - x ω‖ ≤
(α + Real.sqrt (2 * α ^ 2 / ((s : ℝ) - 1) + 12 * τ * (1 + α) ^ 2)) /
Real.sqrt (1 - τ) * ‖q - y‖) ∧
(∀ Abd : ℝ, ∃ K : ℝ, ∀ α τ : ℝ, 1 ≤ α → α ≤ Abd → 0 < τ → τ ≤ 1 / 2 →
∀ s : ℕ, 2 ≤ s →
|(α + Real.sqrt (2 * α ^ 2 / ((s : ℝ) - 1) + 12 * τ * (1 + α) ^ 2)) /
Real.sqrt (1 - τ) - α| ≤
K * (1 / Real.sqrt s + Real.sqrt τ)) := by sorry
end Supplement
end DetANN