Lemma 5.2 — A cutoff for exact prefetching
ProvedDOPriorityQueue.Construction.lemma_5_2differential-obliviousnessp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1priority-queueword-ram
Let and let the live records have distinct encoded keys forming a finite set . Write . Let be integers and suppose an estimate satisfies
If is the smallest integer satisfying , then
If no such exists, the cutoff is and the total number of live records is less than .
In the construction, is the epoch length and the insertion-count error, and the first crossing found by the segment-tree search supplies a key prefix containing at least and at most live records.
Differences from the source:
- generalization: the live keys of the core and the parameters B, E = KZ + B of Section 4.1 → any finite set of distinct keys in [V], any natural numbers B, E and any integer-valued estimate on [V]; reason: the core's live keys are distinct elements of [V] and its B, E are natural numbers, so the statement specializes to the source's
Preamble
import Mathlib set_option autoImplicit false
Formal statement
namespace DOPriorityQueue.Construction
/-- Guo--Hong--Li, STOC 2027 submission #538 (October 2026), p. 21, Lemma 5.2.
`live` is the set of distinct encoded keys of live records in `[V] = {1, …, V}`,
`Q x = #{k ∈ live | k ≤ x}`, and `Qhat` is within `2E` of `Q` on `[V]`.
If `x ∈ [V]` is the smallest with `Qhat x ≥ B + 2E`, then `B ≤ Q x ≤ B + 4E + 1`;
if there is no such `x`, the total number of live records is below `B + 4E`. -/
theorem lemma_5_2 (V B E : ℕ) (hV : 1 ≤ V) (live : Finset ℕ)
(hlive : ∀ k ∈ live, 1 ≤ k ∧ k ≤ V) (Qhat : ℕ → ℤ)
(hest : ∀ x, 1 ≤ x → x ≤ V →
|Qhat x - ((live.filter (· ≤ x)).card : ℤ)| ≤ 2 * (E : ℤ)) :
(∀ x, 1 ≤ x → x ≤ V → (B : ℤ) + 2 * E ≤ Qhat x →
(∀ y, 1 ≤ y → y < x → Qhat y < (B : ℤ) + 2 * E) →
B ≤ (live.filter (· ≤ x)).card ∧
(live.filter (· ≤ x)).card ≤ B + 4 * E + 1) ∧
((∀ x, 1 ≤ x → x ≤ V → Qhat x < (B : ℤ) + 2 * E) →
live.card < B + 4 * E) := by sorry
end DOPriorityQueue.Construction
Source
Zimai Guo, Cheng Hong, Zhechen Li, STOC 2027 submission #538 (October 2026), p. 21, Lemma 5.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.