The repetition count of the signed Hadamard blocks
ProvedDetANN.Supplement.Thm32.reps_specapproximate-nearest-neighborprogram-verificationreal-ram
- For with and : .
- For : if then .
- For : if for all , then .
So the chosen by pre is the repetition count of a constant , and .
Preamble
import Mathlib import Definitions.Def_PNormReg_Machine import Definitions.Def_DetANN_DataStructure import Definitions.Def_PNormRegLib_Reloc import Definitions.Def_DetANN_Sylvester import Definitions.Def_DetANN_SignedBlocks import Definitions.Def_DetANN_Supplement_EvProg import Definitions.Def_DetANN_Supplement_PreProg import Definitions.Def_DetANN_Supplement_PreDedup
Formal statement
namespace DetANN.Supplement.Thm32
open PNormReg PNormRegLib DetANN
/-- **The repetition count.** `numReps (L·τ²/p₀) τ p₀ = L`; this constant is `≥ q` when `q·p₀ ≤ L·τ²`;
and the least power of two `2^m` with `2^m·τ² ≥ c` is at most `max 1 (2c/τ²)`. -/
theorem reps_spec :
(∀ (L p0 : ℕ) (τ : ℝ), 0 < τ → 0 < p0 → numReps ((L : ℝ) * τ ^ 2 / p0) τ p0 = L) ∧
(∀ (L p0 : ℕ) (τ q : ℝ), 0 < p0 → q * p0 ≤ L * (τ * τ) → q ≤ (L : ℝ) * τ ^ 2 / p0) ∧
(∀ (m : ℕ) (c τ : ℝ), 0 < τ → (∀ m' : ℕ, m' < m → 2 ^ m' * (τ * τ) < c) →
(2 : ℝ) ^ m ≤ max 1 (2 * c / (τ * τ))) := by sorry
end DetANN.Supplement.Thm32Source
Original, written for the mission 'Deterministic Approximate Nearest Neighbors in High Dimensions' as part of a proof of DetANN.Supplement.theorem_3_2 (Feng, Indyk, STOC 2027 submission, Theorem 3.2, p.7; the construction of §6.1, p.14, and Lemma 6.2). The machine is PNormReg (definition PNormReg_Machine) with the conventions of DetANN_DataStructure.