The subroutine EVAL of the construction program computes the conditional expectation of Lemma 6.2
ProvedDetANN.Supplement.Thm32.eval_specapproximate-nearest-neighborprogram-verificationreal-ram
Let contain (definition DetANN_Supplement_PreProg) at offset . Let with , a sign index , , a duplicate-free list of nonzero vectors of , signs , and integers , , with and . Write and .
Let be a running state at (the entry of EVAL) with:
- pointer 50 equal to the return flag and pointer 48 equal to ;
- pointers equal to ;
- pointers equal to ;
- pointers – equal to the array bases ;
- reals equal to ;
- in memory: the Sylvester columns , the table (definition
DetANN_Supplement_PreDedup), the factorials for , and (definitionDetANN_Supplement_Greedy).
Then for some the run of from is, after steps, at if and at if , has not halted, and
Moreover:
- only pointers –– and reals – change;
- only the real cells in change;
- the integer memory is unchanged, and the work grows by exactly .
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_SignChoice import Definitions.Def_DetANN_Supplement_PreProg import Definitions.Def_DetANN_Supplement_PreDedup import Definitions.Def_DetANN_Supplement_Greedy
Formal statement
namespace DetANN.Supplement.Thm32
open PNormReg PNormRegLib DetANN
/-- **The subroutine `EVAL` of `pre` computes the conditional expectation of Lemma 6.2.** Called at
`off + 206` with return flag `ret ∈ {0, 1}` in pointer `50` and the sign index `kk` in pointer `48`, with
the Sylvester columns at `Hb`, the duplicate-free table `l` of nonzero vectors at `Db`, the factorials
`i!` (`i ≤ 4p₀`) at `t0` and the signs `ξ` in their cells, it returns to `off + 194` (`ret = 0`) or
`off + 198` (`ret = 1`) within `evalB |l| 2^k L p₀` steps with
`lemma62Expr (sylvester k) L τ p₀ l.toFinset (prefixMask L 2^k (kk+1)) ξ` in real `13`. It changes only
scratch registers and the scratch arrays `[t0 + 4p₀ + 1, t0 + 3(4p₀+1) + 4(2p₀+1))`. -/
theorem eval_spec :
∀ (Q : Program) (off : ℕ) (q : ℚ) (hE : Embeds Q (pre q off) off) (k L p₀ kk : ℕ) (hL : 1 ≤ L)
(hkk : kk < L * 2 ^ k) (τ : ℝ) (hτ : 0 < τ) (l : List (EuclideanSpace ℝ (Fin (2 ^ k))))
(hl : l.Nodup) (hl0 : ∀ v ∈ l, v ≠ 0) (ξ : Fin L → Fin (2 ^ k) → Bool) (Hb Db t0 ret : ℤ)
(hHD : Hb + ((2 ^ k * 2 ^ k : ℕ) : ℤ) ≤ Db) (hDt : Db + ((l.length * 2 ^ k : ℕ) : ℤ) ≤ t0)
(hH0 : 0 ≤ Hb) (hret : ret = 0 ∨ ret = 1) (s : State)
(hpc : s.core.pc = off + 206) (hh : s.halted = false)
(h0 : s.core.ptrs 0 = 0) (h1 : s.core.ptrs 1 = 1) (h3 : s.core.ptrs 3 = ((2 ^ k : ℕ) : ℤ))
(h14 : s.core.ptrs 14 = L) (h15 : s.core.ptrs 15 = -((2 ^ k : ℕ) : ℤ) - 1)
(h24 : s.core.ptrs 24 = Hb) (h26 : s.core.ptrs 26 = Db)
(h27 : s.core.ptrs 27 = Db + ((l.length * 2 ^ k : ℕ) : ℤ))
(h36 : s.core.ptrs 36 = 2 * (p₀ : ℤ)) (h37 : s.core.ptrs 37 = 2 * (p₀ : ℤ) + 1)
(h39 : s.core.ptrs 39 = 4 * (p₀ : ℤ) + 1) (h40 : s.core.ptrs 40 = t0)
(h41 : s.core.ptrs 41 = t0 + (4 * (p₀ : ℤ) + 1))
(h42 : s.core.ptrs 42 = t0 + 2 * (4 * (p₀ : ℤ) + 1))
(h43 : s.core.ptrs 43 = t0 + 3 * (4 * (p₀ : ℤ) + 1))
(h44 : s.core.ptrs 44 = t0 + 3 * (4 * (p₀ : ℤ) + 1) + (2 * (p₀ : ℤ) + 1))
(h45 : s.core.ptrs 45 = t0 + 3 * (4 * (p₀ : ℤ) + 1) + 2 * (2 * (p₀ : ℤ) + 1))
(h46 : s.core.ptrs 46 = t0 + 3 * (4 * (p₀ : ℤ) + 1) + 3 * (2 * (p₀ : ℤ) + 1))
(h48 : s.core.ptrs 48 = kk) (h50 : s.core.ptrs 50 = ret)
(h5 : s.core.regs 5 = τ) (h6 : s.core.regs 6 = 0) (h7 : s.core.regs 7 = 1)
(hcol : ∀ r j : Fin (2 ^ k), s.core.mem (Hb + (((r : ℕ) * 2 ^ k + j : ℕ) : ℤ)) = sylvester k j r)
(hT : TableAt s.core.mem Db l)
(hF : ∀ i : ℕ, i < 4 * p₀ + 1 → s.core.mem (t0 + i) = (i.factorial : ℝ))
(hS : SignsAt s.core.mem L k ξ),
∃ t, t ≤ evalB l.length (2 ^ k) L p₀ ∧
(ret = 0 → (run Q s detTape t).core.pc = off + 194) ∧
(ret = 1 → (run Q s detTape t).core.pc = off + 198) ∧
(run Q s detTape t).halted = false ∧
(run Q s detTape t).core.regs 13 =
lemma62Expr (sylvester k) L τ p₀ l.toFinset (prefixMask L (2 ^ k) (kk + 1)) ξ ∧
(∀ y, y ≠ 5 → y ≠ 10 → y ≠ 11 → y ≠ 12 → y ≠ 16 → y ≠ 17 → y ≠ 18 → y ≠ 19 → y ≠ 20 →
y ≠ 31 → (y < 51 ∨ 58 < y) → (run Q s detTape t).core.ptrs y = s.core.ptrs y) ∧
(∀ y, y ≠ 0 → y ≠ 1 → (y < 13 ∨ 24 < y) → (run Q s detTape t).core.regs y = s.core.regs y) ∧
(∀ z, (z < t0 + (4 * (p₀ : ℤ) + 1) ∨
t0 + 3 * (4 * (p₀ : ℤ) + 1) + 4 * (2 * (p₀ : ℤ) + 1) ≤ z) →
(run Q s detTape t).core.mem z = s.core.mem z) ∧
(run Q s detTape t).integerMemory = s.integerMemory ∧
(run Q s detTape t).work = s.work + t := 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 the conditional expectation of Lemma 6.2). The machine is PNormReg (definition PNormReg_Machine) with the conventions of DetANN_DataStructure.