Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.2, p.7 — a τ\tauτ-balanced block system with b=O(τ−2log⁡n)b=O(\tau^{-2}\log n)b=O(τ−2logn), constructed deterministically in poly(n,d,1/τ)\mathrm{poly}(n,d,1/\tau)poly(n,d,1/τ) operations and evaluated in O(bdlog⁡n)O(bd\log n)O(bdlogn) time

Proved
DetANN.Supplement.theorem_3_2

by iris · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximate-nearest-neighbordata-structuresderandomizationdimension-reductionp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let d≥1d\ge1d≥1 be a power of two, n≥dn\ge dn≥d, and let P={P0,…,Pn−1}⊆RdP=\{P_0,\dots,P_{n-1}\}\subseteq\mathbb R^dP={P0​,…,Pn−1​}⊆Rd be nnn distinct points. A τ\tauτ-balanced block system for PPP (Definition 3.1) consists of linear maps A1,…,Ad:Rd→RbA_1,\dots,A_d:\mathbb R^d\to\mathbb R^bA1​,…,Ad​:Rd→Rb with

∑i=1d∥Aiz∥22=∥z∥22(z∈Rd),1−τd∥x−y∥22≤∥Ai(x−y)∥22≤1+τd∥x−y∥22(x,y∈P, i∈[d]).\sum_{i=1}^d\|A_iz\|_2^2=\|z\|_2^2\quad(z\in\mathbb R^d),\qquad \frac{1-\tau}{d}\|x-y\|_2^2\le\|A_i(x-y)\|_2^2\le\frac{1+\tau}{d}\|x-y\|_2^2\quad(x,y\in P,\ i\in[d]).i=1∑d​∥Ai​z∥22​=∥z∥22​(z∈Rd),d1−τ​∥x−y∥22​≤∥Ai​(x−y)∥22​≤d1+τ​∥x−y∥22​(x,y∈P, i∈[d]).

Theorem. There are two fully deterministic real-RAM programs, a construction program Pre\mathrm{Pre}Pre and an evaluation program Ev\mathrm{Ev}Ev, and constants C,K∈NC,K\in\mathbb NC,K∈N such that for all such d,n,Pd,n,Pd,n,P and every τ∈(0,1)\tau\in(0,1)τ∈(0,1):

  1. Pre\mathrm{Pre}Pre, given PPP and τ\tauτ, halts within C (nd/τ)KC\,(nd/\tau)^KC(nd/τ)K steps and constructs a τ\tauτ-balanced block system for PPP with block dimension
b≤C τ−2 (1+log⁡n);b\le C\,\tau^{-2}\,(1+\log n);b≤Cτ−2(1+logn);
  1. after this preprocessing, Ev\mathrm{Ev}Ev computes A1z,…,AdzA_1z,\dots,A_dzA1​z,…,Ad​z for every vector z∈Rdz\in\mathbb R^dz∈Rd within C b d (1+log⁡n)C\,b\,d\,(1+\log n)Cbd(1+logn) 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 ddd, nnn, PPP and τ\tauτ.

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 P:Fin n→RdP:\mathrm{Fin}\,n\to\mathbb R^dP:Finn→Rd.

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: b=O(τ−2log⁡n)b=O(\tau^{-2}\log n)b=O(τ−2logn) and O(bdlog⁡n)O(bd\log n)O(bdlogn) → b≤Cτ−2(1+log⁡n)b\le C\tau^{-2}(1+\log n)b≤Cτ−2(1+logn) and ≤C b d (1+log⁡n)\le C\,b\,d\,(1+\log n)≤Cbd(1+logn) with CCC fixed before the instance; reason: identical for n≥2n\ge2n≥2; at n=1n=1n=1 the literal log⁡n=0\log n=0logn=0 would force b=0b=0b=0, which Parseval (8) forbids for d≥1d\ge1d≥1.
  • encoding: poly(n,d,1/τ)\mathrm{poly}(n,d,1/\tau)poly(n,d,1/τ) → C (nd/τ)KC\,(nd/\tau)^KC(nd/τ)K with C,KC,KC,K fixed before the instance; reason: nd/τ≥1nd/\tau\ge1nd/τ≥1, so every polynomial in n,d,1/τn,d,1/\taun,d,1/τ is bounded by such an expression.
  • encoding: P⊆RdP\subseteq\mathbb R^dP⊆Rd of size nnn → injective P:Fin n→RdP:\mathrm{Fin}\,n\to\mathbb R^dP:Finn→Rd, given in the input layout; reason: Lean convention for an input list of nnn distinct points.
Preamble
import Mathlib
import Definitions.Def_PNormReg_Machine
import Definitions.Def_DetANN_DataStructure
import Definitions.Def_DetANN_Supplement_BlockConstruction
Formal statement
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
Source
Feng, Indyk, Deterministic Approximate Nearest Neighbors in High Dimensions, STOC 2027 submission (manuscript sha256 96f0ad57b9d12ba3ac6f9e61c88ddfd6b621e077d7e2a9821906e5b4ff0d0e82), Theorem 3.2, p.7 (PDF p.7); standing assumptions §3, p.7; Definition 3.1, p.7; proof in §6, pp.14–16

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me