The evaluation program computes the signed Hadamard blocks
ProvedDetANN.Supplement.Thm32.ev_blockapproximate-nearest-neighborprogram-verificationreal-ram
Let be a program that contains of definition DetANN_Supplement_EvProg at offset . Let , , and . Let be a running state at such that:
- pointer 0 holds , integer cell 0 holds and integer cell 1 holds ;
- real cell holds ;
- real cell holds .
Then for some , the run of from has halted after steps, its work has grown by , and for all , ,
This is the evaluation clause of DetANN.Supplement.IsBlockConstruction for the blocks of Theorem 3.2, in the layout that queryState produces. Since , the bound is with .
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
Formal statement
namespace DetANN.Supplement.Thm32
open PNormReg PNormRegLib DetANN
/-- **The program `ev` evaluates the signed Hadamard blocks.** Let `Q` contain `ev off` (definition
`DetANN_Supplement_EvProg`) at offset `off`, and let `s` be a running state at `off` with pointer `0`
equal to `0`, `L ≥ 1` in integer cell `0`, `2^k` in integer cell `1`, the sign `signOf (ξ ℓ r)` in real
cell `-2^k - 1 - (ℓ·2^k + r)` and the query coordinate `z r` in real cell `-1 - r`. Then within
`82·L·2^k·(1 + k)` steps the run halts, and real cell `j·L + ℓ` holds
`signedBlocks (sylvester k) L ξ j z ℓ`, i.e. `(A_j z)_ℓ` for the blocks of §6.1. -/
theorem ev_block :
∀ (Q : Program) (off : ℕ) (hE : Embeds Q (ev off) off) (k L : ℕ) (hL : 1 ≤ L)
(ξ : Fin L → Fin (2 ^ k) → Bool) (z : EuclideanSpace ℝ (Fin (2 ^ k))) (s : State)
(hpc : s.core.pc = off) (hh : s.halted = false) (h0 : s.core.ptrs 0 = 0)
(hLm : s.integerMemory 0 = L) (hd : s.integerMemory 1 = 2 ^ k)
(hsg : ∀ (ℓ : Fin L) (r : Fin (2 ^ k)),
s.core.mem (-(2 ^ k : ℤ) - 1 - ((ℓ : ℤ) * 2 ^ k + r)) = signOf (ξ ℓ r))
(hz : ∀ r : Fin (2 ^ k), s.core.mem (-1 - (r : ℤ)) = z r),
∃ t, t ≤ 82 * (L * 2 ^ k * (1 + k)) ∧ (run Q s detTape t).halted = true ∧
(run Q s detTape t).work = s.work + t ∧
∀ (j : Fin (2 ^ k)) (ℓ : Fin L),
(run Q s detTape t).core.mem ((j : ℤ) * L + ℓ) = signedBlocks (sylvester k) L ξ j z ℓ := 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 blocks of §6.1, p.14). The machine is PNormReg (definition PNormReg_Machine) with the conventions of DetANN_DataStructure; the fast Walsh–Hadamard transform is the standard in-place butterfly algorithm.