Theorem 6.1 — fixed-history probe lower bound and finite-parameter estimates
OpenDOPriorityQueue.Construction.Supplement.theorem_6_1For an eventually bounded family and a family , there is a threshold uniform over horizons, memory sizes, priority universes and implementations. For all beyond it, all , , and all priority domains containing , consider an exact online opaque-token queue with at most private words, including registers and retained answers. Every execution terminates, tokens first arrive at their insertions, and answers return from private memory. Only insertion-record replacement privacy is assumed, with public operation types fixed.
There is one fixed vector , hence one fixed history of exactly operations, for which
The expectation is over internal randomness alone; the history is selected before the random tape. This gives the printed bound on an -operation history. All in the stated range and both probe-ratio regimes are retained. Arbitrary free local computations are permitted.
The statement also includes the finite-parameter estimates used in the proof, for every admissible finite :
where . Infinite expected probes are included. The threshold depends on the privacy families, never on or the implementation. This companion theorem is the independent lower bound; it is not a step in the proof of the retained construction goal.
Differences from the source:
- generalization: w=Theta(log T) balls-and-bins queues → all word sizes in the larger opaque controller model, with atomic free numeric maps and public numeric initialization; reason: the proof uses only token conservation and M private slots and covers every source implementation
- generalization: an asymptotic Omega bound on an O(n)-operation fixed history → a fixed history of exactly 2n calls with coefficient 1/32, plus equation (15) and the pathwise n-M bound; reason: page 30 proves the pointwise estimates and both ratio regimes give the uniform factor 1/32; no source conclusion is removed
- encoding: epsilon=O(1), delta=o(1) → eventually bounded epsilon_n and delta_n tending to zero as n tends to infinity, with a threshold before every admissible T,M,U,w and queue; reason: makes the asymptotic and uniform quantifiers explicit without imposing n=Theta(T)
- encoding: fixed distinct opaque tokens and priorities in [n] → canonical natural token labels and Fin n priorities shifted by one; reason: token relabeling and index translation preserve every instance; no token identity is available to the controller
- encoding: expectations possibly infinite and signed finite-parameter lower bound → extended nonnegative sums and ofReal of real lower bounds; reason: handles infinite probes and maps negative lower bounds to the equivalent zero bound
import Definitions.Def_DOPriorityQueue_Construction_Supplement_LowerBound set_option autoImplicit false
namespace DOPriorityQueue.Construction.Supplement /-- Guo--Hong--Li, p. 27, Theorem 6.1, with the finite-parameter bounds from its proof on p. 30. The fixed history has exactly 2n operations. -/ theorem theorem_6_1 : LowerBoundTarget ∧ PointwiseLowerBound := by sorry end DOPriorityQueue.Construction.Supplement