Theorem 6.1 — uniform asymptotic and pointwise lower-bound targets
DefinitionDOPriorityQueue_Construction_Supplement_LowerBoundLet be eventually bounded and let as . The asymptotic target chooses a threshold before the horizon , memory size , word size , universe or implementation. For every beyond it, with , and , every exact terminating opaque-token queue with insertion-field replacement privacy has a fixed vector such that
Only implementation randomness remains in this expectation. The history has exactly calls, so this is the source's witness. The factor follows from the two regimes of the proof on page 30.
The accompanying finite-parameter target retains equation (15) and the pathwise storage bound:
Expectations take values in . A negative real lower bound is embedded as zero, an equivalent convention for a nonnegative quantity. All word sizes are allowed, a strengthening of the printed regime. These targets retain both the large and small ratio regimes and impose no finite-mean assumption.
import Definitions.Def_DOPriorityQueue_Construction_Supplement_Opaque
set_option autoImplicit false
namespace DOPriorityQueue.Construction.Supplement
/-- Equation (15), valid also for infinite expected probes, and the pathwise
storage bound used in the small log(n)/log(M+2) regime (p. 30). -/
noncomputable def PointwiseLowerBound : Prop :=
∀ (n T U M w : ℕ) (Q : OpaqueProgram w M) (ε δ : ℝ),
2 ≤ n → 2 * n ≤ T → 1 ≤ M → 2 * M ≤ n → n ≤ U →
opaqueCorrect Q T U → insertionDO (opaqueKernel Q) T U ε δ →
ENNReal.ofReal
((n : ℝ) * (Real.logb 2 n - 2 - gamma n ε δ) /
Real.logb 2 (2 * (M + 2 : ℕ)) - 2 * n) ≤
mixedProbes (opaqueKernel Q) (fun i : Fin n => i.val) ∧
(∀ (X : Fin n → Fin n) fuel coins r,
opaqueRun Q fuel (opaqueInitial Q) coins
(experimentHistory (fun i : Fin n => i.val) X) = some r →
n - M ≤ probeCount r.traces)
/-- Theorem 6.1's asymptotic quantifiers. Epsilon is eventually bounded and
delta tends to zero as n grows; the threshold is independent of T, M, word size,
priority bound, and implementation. A single fixed X is selected before coins.
The proof's two regimes give the explicit uniform factor 1/32. The assertion
holds for every word size, strengthening the stated Θ(log T) setting. -/
noncomputable def LowerBoundTarget : Prop :=
∀ ε δ : ℕ → ℝ,
(∃ E : ℝ, ∀ᶠ n : ℕ in Filter.atTop, ε n ≤ E) →
Filter.Tendsto δ Filter.atTop (nhds 0) →
∃ N : ℕ, 2 ≤ N ∧ ∀ n : ℕ, N ≤ n →
∀ (T U M w : ℕ) (Q : OpaqueProgram w M),
2 * n ≤ T → 1 ≤ M → 2 * M ≤ n → n ≤ U →
opaqueCorrect Q T U → insertionDO (opaqueKernel Q) T U (ε n) (δ n) →
∃ X : Fin n → Fin n,
ENNReal.ofReal ((n : ℝ) * Real.logb 2 n / (32 * Real.logb 2 (M + 2 : ℕ))) ≤
expectedProbes (opaqueKernel Q) (experimentHistory (fun i : Fin n => i.val) X)
end DOPriorityQueue.Construction.Supplement