Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 10.5, eq. (51) — Qthr=Θ((τ+d)log⁡(1/δ)/d2)Q_{\mathrm{thr}}=\Theta((\tau+d)\log(1/\delta)/d^2)Qthr​=Θ((τ+d)log(1/δ)/d2) when r−dr-dr−d is bounded below

Open
FairReplay.Supplement.eq_51

by iris · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

fairness-testinginformation-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1sequential-testing

With r=1−p−s−τr=1-p-s-\taur=1−p−s−τ and X=τ+dd2log⁡1δX=\frac{\tau+d}{d^2}\log\frac1\deltaX=d2τ+d​logδ1​:

  1. for every ρ>0\rho>0ρ>0 and δ∈(0,1/2)\delta\in(0,1/2)δ∈(0,1/2) there are constants c,C>0c,C>0c,C>0 such that, for all P18 parameters (p>0p>0p>0, s≥0s\ge0s≥0, τ≥0\tau\ge0τ≥0, d>0d>0d>0, p+s+τ+d<1p+s+\tau+d<1p+s+τ+d<1) with r−d≥ρr-d\ge\rhor−d≥ρ,
c X ≤ Qthrpair ≤ Qthrcomp ≤ C X;c\,X\ \le\ Q_{\mathrm{thr}}^{\mathrm{pair}}\ \le\ Q_{\mathrm{thr}}^{\mathrm{comp}}\ \le\ C\,X;cX ≤ Qthrpair​ ≤ Qthrcomp​ ≤ CX;
  1. hence τ=O(d)\tau=O(d)τ=O(d) retains d−1d^{-1}d−1 scaling: for fixed p,sp,sp,s with p+s<1p+s<1p+s<1, δ\deltaδ and κ≥0\kappa\ge0κ≥0, both quantities are of order log⁡(1/δ)/d\log(1/\delta)/dlog(1/δ)/d for all small ddd and 0≤τ≤κd0\le\tau\le\kappa d0≤τ≤κd;
  2. and every fixed τ>0\tau>0τ>0 (with p+s+τ<1p+s+\tau<1p+s+τ<1) restores d−2d^{-2}d−2 scaling: both quantities are of order log⁡(1/δ)/d2\log(1/\delta)/d^2log(1/δ)/d2 for all small ddd.

QthrpairQ_{\mathrm{thr}}^{\mathrm{pair}}Qthrpair​ is the optimal null expected number of four-way rounds for the boundary pair, QthrcompQ_{\mathrm{thr}}^{\mathrm{comp}}Qthrcomp​ the same over testers correct for the whole composite problem (49).

Differences from the source:

  • reading: Q_thr(τ, d, δ) (no definition given) → two quantities, QthrPair (boundary pair) and QthrComp (composite problem (49)), both bounded; reason: both natural readings are covered; the sandwich Q^pair ≤ Q^comp is stated
  • reading: Θ(·) up to constants, if r − d is bounded below by a positive constant, as d → 0 → for every ρ > 0 constants c, C depending only on ρ and δ, uniformly over all P18 parameters with r − d ≥ ρ; reason: the uniform reading is the stronger one and implies the fixed-parameter asymptotics
  • encoding: τ = O(d) retains d⁻¹ scaling; fixed τ > 0 restores d⁻² → items 2 and 3 with explicit constants c, C, d₀ chosen before d; reason: the Θ convention of the published Theorem 10.4
  • encoding: Q (no displayed definition) → the infimum in [0, ∞] of the null expected stopping time over δ-correct testers; reason: the paper's own usage ("optimal expected null declared cost", p.20); the reading of the published Theorem 10.4
Preamble
import Mathlib
import Definitions.Def_FairReplay_Supplement_Qthr
Formal statement
namespace FairReplay.Supplement

/-- **Theorem 10.5, eq. (51), the thresholded phase transition** (Sah, Zhang, Lian, *Testing Fairness of Evolving Software under Uncertainty*, STOC 2027 submission (manuscript of 2026-11-03, sha256 e23940a0…), Theorem 10.5, eq. (51), p.16
(PDF p.18)): "If r − d is bounded below by a positive constant, then as d → 0 with δ fixed these bounds
give Qthr(τ, d, δ) = Θ((τ + d)/d² log 1/δ) (51) up to constants. Hence τ = 0 and, more generally,
τ = O(d) retain d−1 scaling, whereas every fixed τ > 0 restores d−2 scaling as d → 0."

With `r = 1 − p − s − τ` and `X = (τ + d) log(1/δ)/d²`:
1. for every `ρ > 0` and `δ ∈ (0, 1/2)` there are `c, C > 0` such that, for all P18 parameters
   (`p > 0`, `s ≥ 0`, `τ ≥ 0`, `d > 0`, `p + s + τ + d < 1`) with `r − d ≥ ρ`,
   `c X ≤ Q_thr^pair ≤ Q_thr^comp ≤ C X`;
2. (`τ = O(d)`) for fixed `p, s` with `p + s < 1`, `δ` and `κ ≥ 0`, there are `c, C, d₀ > 0` with
   `c log(1/δ)/d ≤ Q_thr^pair` and `Q_thr^comp ≤ C log(1/δ)/d` for all `d ∈ (0, d₀)` and `0 ≤ τ ≤ κ d`;
3. (fixed `τ > 0`) for fixed `p, s, τ` with `p + s + τ < 1` and `δ`, there are `c, C, d₀ > 0` with
   `c log(1/δ)/d² ≤ Q_thr^pair` and `Q_thr^comp ≤ C log(1/δ)/d²` for all `d ∈ (0, d₀)`.

**Formalization Note** The paper does not define `Q_thr`; both readings are bounded:
`Q_thr^pair` is the optimal null expected number of rounds for the boundary null against the
alternative, and `Q_thr^comp` the same over testers correct for the whole composite problem (49).
"Up to constants" is read uniformly: the constants depend only on `ρ` and `δ` (item 1). -/
theorem eq_51 :
    (∀ ρ δ : ℝ, 0 < ρ → 0 < δ → δ < 1 / 2 →
      ∃ c C : ℝ, 0 < c ∧ 0 < C ∧
        ∀ p s τ d : ℝ, 0 < p → 0 ≤ s → 0 ≤ τ → 0 < d → p + s + τ + d < 1 →
          ρ ≤ (1 - p - s - τ) - d →
          ENNReal.ofReal (c * ((τ + d) * Real.log (1 / δ) / d ^ 2)) ≤ QthrPair p s τ d δ ∧
          QthrPair p s τ d δ ≤ QthrComp p s τ d δ ∧
          QthrComp p s τ d δ ≤ ENNReal.ofReal (C * ((τ + d) * Real.log (1 / δ) / d ^ 2))) ∧
    (∀ p s δ κ : ℝ, 0 < p → 0 ≤ s → p + s < 1 → 0 < δ → δ < 1 / 2 → 0 ≤ κ →
      ∃ c C d₀ : ℝ, 0 < c ∧ 0 < C ∧ 0 < d₀ ∧
        ∀ d τ : ℝ, 0 < d → d < d₀ → 0 ≤ τ → τ ≤ κ * d →
          ENNReal.ofReal (c * Real.log (1 / δ) / d) ≤ QthrPair p s τ d δ ∧
          QthrComp p s τ d δ ≤ ENNReal.ofReal (C * Real.log (1 / δ) / d)) ∧
    (∀ p s τ δ : ℝ, 0 < p → 0 ≤ s → 0 < τ → p + s + τ < 1 → 0 < δ → δ < 1 / 2 →
      ∃ c C d₀ : ℝ, 0 < c ∧ 0 < C ∧ 0 < d₀ ∧
        ∀ d : ℝ, 0 < d → d < d₀ →
          ENNReal.ofReal (c * Real.log (1 / δ) / d ^ 2) ≤ QthrPair p s τ d δ ∧
          QthrComp p s τ d δ ≤ ENNReal.ofReal (C * Real.log (1 / δ) / d ^ 2)) := by sorry

end FairReplay.Supplement
Source
Sah, Zhang, Lian, Testing Fairness of Evolving Software under Uncertainty, STOC 2027 submission (manuscript of 2026-11-03, sha256 e23940a0a0f5960aedaf6aba60adc41e966efc604b6379b3180b06590610d025), Theorem 10.5, eq. (51), p.16 (PDF p.18)

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