Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6.1 — fixed-history probe lower bound and finite-parameter estimates

Open
DOPriorityQueue.Construction.Supplement.theorem_6_1

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

differential-obliviousnessp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1priority-queueprobability

For an eventually bounded family εn\varepsilon_nεn​ and a family δn→0\delta_n\to0δn​→0, there is a threshold uniform over horizons, memory sizes, priority universes and implementations. For all nnn beyond it, all 2n≤T2n\le T2n≤T, 1≤M≤n/21\le M\le n/21≤M≤n/2, and all priority domains containing [n][n][n], consider an exact online opaque-token queue with at most MMM 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 X∈[n]nX\in[n]^nX∈[n]n, hence one fixed history σ(X)\sigma(X)σ(X) of exactly 2n2n2n operations, for which

EQ[P(σ(X))]≥nlog⁡2n32log⁡2(M+2).\mathbb E_Q[P(\sigma(X))]\ge\frac{n\log_2n}{32\log_2(M+2)}.EQ​[P(σ(X))]≥32log2​(M+2)nlog2​n​.

The expectation is over internal randomness alone; the history is selected before the random tape. This gives the printed Ω(nlog⁡n/log⁡(M+2))\Omega(n\log n/\log(M+2))Ω(nlogn/log(M+2)) bound on an O(n)O(n)O(n)-operation history. All MMM 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 ε,δ\varepsilon,\deltaε,δ:

EX,Q[P]≥n(log⁡2n−2−γn)log⁡2(2(M+2))−2n,P≥n−M on every execution,\mathbb E_{X,Q}[P]\ge\frac{n(\log_2n-2-\gamma_n)}{\log_2(2(M+2))}-2n,\qquad P\ge n-M\text{ on every execution},EX,Q​[P]≥log2​(2(M+2))n(log2​n−2−γn​)​−2n,P≥n−M on every execution,

where γn=(ε+1)/ln⁡2+δlog⁡2n/(1−e−1)\gamma_n=(\varepsilon+1)/\ln2+\delta\log_2n/(1-e^{-1})γn​=(ε+1)/ln2+δlog2​n/(1−e−1). Infinite expected probes are included. The threshold depends on the privacy families, never on T,MT,MT,M 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
Preamble
import Definitions.Def_DOPriorityQueue_Construction_Supplement_LowerBound

set_option autoImplicit false
Formal statement
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
Source
Zimai Guo, Cheng Hong, Zhechen Li, STOC 2027 submission #538 (October 2026), p. 27; proof pp. 28–30, Theorem 6.1

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me