Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5.2 — A cutoff for exact prefetching

Proved
DOPriorityQueue.Construction.lemma_5_2

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

differential-obliviousnessp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1priority-queueword-ram

Let V≥1V\ge1V≥1 and let the live records have distinct encoded keys forming a finite set L⊆[V]={1,…,V}L\subseteq[V]=\{1,\ldots,V\}L⊆[V]={1,…,V}. Write Q(x)=∣{k∈L:k≤x}∣Q(x)=|\{k\in L: k\le x\}|Q(x)=∣{k∈L:k≤x}∣. Let B,E≥0B,E\ge0B,E≥0 be integers and suppose an estimate Q^\hat QQ^​ satisfies

∥Q^−Q∥∞=max⁡x∈[V]∣Q^(x)−Q(x)∣≤2E.\|\hat Q-Q\|_\infty=\max_{x\in[V]}|\hat Q(x)-Q(x)|\le 2E.∥Q^​−Q∥∞​=x∈[V]max​∣Q^​(x)−Q(x)∣≤2E.

If x∈[V]x\in[V]x∈[V] is the smallest integer satisfying Q^(x)≥B+2E\hat Q(x)\ge B+2EQ^​(x)≥B+2E, then

B≤Q(x)≤B+4E+1.B\le Q(x)\le B+4E+1.B≤Q(x)≤B+4E+1.

If no such xxx exists, the cutoff is VVV and the total number of live records is less than B+4EB+4EB+4E.

In the construction, BBB is the epoch length and E=KZ+BE=KZ+BE=KZ+B the insertion-count error, and the first crossing found by the segment-tree search supplies a key prefix containing at least BBB and at most O(B)O(B)O(B) 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
  • Endorsed by Shuze Chen · Nov 11, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 11, 2026

    Confirmed by the mission captain (proposal self-audit).

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