Theorem 3.2, p.7 — a -balanced block system with , constructed deterministically in operations and evaluated in time
ProvedDetANN.Supplement.theorem_3_2Let be a power of two, , and let be distinct points. A -balanced block system for (Definition 3.1) consists of linear maps with
Theorem. There are two fully deterministic real-RAM programs, a construction program and an evaluation program , and constants such that for all such and every :
- , given and , halts within steps and constructs a -balanced block system for with block dimension
- after this preprocessing, computes for every vector within steps.
"Constructs" and "computes" are in the sense of the block-construction semantics DetANN.Supplement.BlockConstruction: the maps are those whose coordinates the evaluation program outputs. The same programs and constants serve every , , and .
This is the dimension-reduction primitive of the paper: it supplies the blocks on which both the exhaustive construction (§4) and the expander construction (§7) build their low-dimensional nearest-neighbor structures.
Formalization Note The machine is the published PNormReg.Machine restricted to deterministic programs (no coin, no real power, rational literals), with the input layout and second-program start state of DetANN.DataStructure. The point set is an injective list .
Differences from the source:
- reading: "one can deterministically construct … arithmetic operations … time" (no machine named) → one pair of deterministic programs on the published real RAM, time = executed instructions, the maps being those output by the evaluation program; reason: the paper names no machine; each instruction does at most one arithmetic operation, so a step bound is at least as strong as an operation bound.
- encoding: and → and with fixed before the instance; reason: identical for ; at the literal would force , which Parseval (8) forbids for .
- encoding: → with fixed before the instance; reason: , so every polynomial in is bounded by such an expression.
- encoding: of size → injective , given in the input layout; reason: Lean convention for an input list of distinct points.
import Mathlib import Definitions.Def_PNormReg_Machine import Definitions.Def_DetANN_DataStructure import Definitions.Def_DetANN_Supplement_BlockConstruction
namespace DetANN
namespace Supplement
/-- **Theorem 3.2** (Y. Feng, P. Indyk, *Deterministic Approximate Nearest Neighbors in High
Dimensions*, STOC 2027 submission (manuscript sha256 96f0ad57…), p.7).
Given `P ⊆ ℝ^d` and `τ ∈ (0, 1)`, one can deterministically construct a `τ`-balanced block system with
`b = O(τ^{−2} log n)`. The construction takes `poly(n, d, 1/τ)` arithmetic operations. After
preprocessing, all `d` maps can be evaluated on a vector in `O(b d log n)` time.
**Formalization Note.** One pair of deterministic programs `Pre` (construction) and `Ev`
(evaluation) and constants `C, K` serve every instance: they are chosen before `d`, `n`, the points
and `τ` (`τ` is an input of `Pre`, in real cell `0`). The paper's standing assumptions (§3, p.7) are
kept: `d` a power of two (hence `d ≥ 1`), `n ≥ d`, and `n` distinct points (`P` injective).
`poly(n, d, 1/τ)` is `C·(n·d/τ)^K`, equivalent since `n·d/τ ≥ 1`; `log n` is read as `1 + log n`
(natural log) in both the bound on `b` and the evaluation time, which avoids `log 1 = 0` at `n = 1` and
changes nothing for `n ≥ 2`. Construction and evaluation semantics are those of
`DetANN.Supplement.IsBlockConstruction`. -/
theorem theorem_3_2 :
∃ Pre Ev : PNormReg.Program, DetProgram Pre ∧ DetProgram Ev ∧
∃ C K : ℕ, ∀ d n : ℕ, (∃ k : ℕ, d = 2 ^ k) → d ≤ n →
∀ P : Fin n → EuclideanSpace ℝ (Fin d), Function.Injective P →
∀ τ : ℝ, 0 < τ → τ < 1 →
IsBlockConstruction Pre Ev P τ
((C : ℝ) * ((n : ℝ) * d / τ) ^ K)
((C : ℝ) * τ⁻¹ ^ 2 * (1 + Real.log n))
(fun b => (C : ℝ) * b * d * (1 + Real.log n)) := by sorry
end Supplement
end DetANN