Eq. (45) —
ProvedFairReplay.eq_45fairness-testinginformation-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1sequential-testing
Fix with and put . As ,
there are constants (depending on ) such that for every .
Together with (34) this gives the four-way lower bound of order .
Differences from the source:
- encoding: K_edge = d + O(d²) as d → 0 → ∃ C d₀ > 0, ∀ d ∈ (0, d₀), |r log(r/(r − d)) − d| ≤ C d²; reason: the definition of O(·) at 0⁺ with r fixed
Preamble
import Mathlib
Formal statement
namespace FairReplay
/-- **Eq. (45), K_edge = d + O(d²)** (Sah, Zhang, Lian, *Testing Fairness of Evolving Software under Uncertainty*, STOC 2027
submission (manuscript of 2026-11-03, sha256 e23940a0…), proof of Theorem 10.4, eq. (45), p.15 (PDF p.17)):
"Finally, K_edge = d + O(d²), (45)" where K_edge = r log(r/(r − d)) (40) and r = 1 − p − s.
For fixed `p, s > 0` with `p + s < 1` and `r = 1 − p − s`, there are constants `C, d₀ > 0` with
`|r log(r/(r − d)) − d| ≤ C d²` for every `d ∈ (0, d₀)`.
**Formalization Note** The `O(d²)` as `d → 0` is written out with explicit constants chosen before
`d` (they depend only on `p, s`). -/
theorem eq_45 (p s : ℝ) (hp : 0 < p) (hs : 0 < s) (hps : p + s < 1) :
∃ C d₀ : ℝ, 0 < C ∧ 0 < d₀ ∧ ∀ d : ℝ, 0 < d → d < d₀ →
|(1 - p - s) * Real.log ((1 - p - s) / ((1 - p - s) - d)) - d| ≤ C * d ^ 2 := by sorry
end FairReplay
Source
Sah, Zhang, Lian, Testing Fairness of Evolving Software under Uncertainty, STOC 2027 submission (manuscript of 2026-11-03, sha256 e23940a0a0f5960aedaf6aba60adc41e966efc604b6379b3180b06590610d025), proof of Theorem 10.4, eq. (45), p.15 (PDF p.17)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.