Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Eq. (51) and the majority bound — B≥329log⁡1δB\ge\frac{32}9\log\frac1{\delta}B≥932​logδ1​ odd batches give error ≤e−9B/32≤δ\le e^{-9B/32}\le\delta≤e−9B/32≤δ

Proved
DesignTest.eq_51

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

p2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1property-testingquantum-informationsample-complexitystate-designs

Let δ∈(0,1/2)\delta\in(0,1/2)δ∈(0,1/2) and let BBB be an odd integer with

B≥329log⁡1δ.B\ge\frac{32}{9}\log\frac1\delta .B≥932​logδ1​.

Let X1,…,XBX_1,\dots,X_BX1​,…,XB​ be independent random variables with values in {0,1}\{0,1\}{0,1} (the error indicators of BBB independent batches) and means EXb≤1/8\mathbb E X_b\le1/8EXb​≤1/8. Then the majority vote errs with probability

Pr⁡[∑b=1BXb≥B2]≤exp⁡[−2B(12−18)2]=e−9B/32≤δ.\Pr\Big[\sum_{b=1}^{B}X_b\ge\frac B2\Big]\le\exp\Big[-2B\Big(\frac12-\frac18\Big)^2\Big]=e^{-9B/32}\le\delta .Pr[b=1∑B​Xb​≥2B​]≤exp[−2B(21​−81​)2]=e−9B/32≤δ.

This is the amplification step that turns the constant-error batch of Theorem 4.11 into a tester with failure probability δfail\delta_{\mathrm{fail}}δfail​ at a cost of O(log⁡(1/δfail))O(\log(1/\delta_{\mathrm{fail}}))O(log(1/δfail​)) batches.

Formalization Note The indicators live on an arbitrary probability space and are measurable, independent in the sense of Mathlib's iIndepFun, and almost surely {0,1}\{0,1\}{0,1}-valued.

Differences from the source:

  • generalization: B is the smallest odd integer with B ≥ (32/9) log(1/δ_fail) → every odd B with B ≥ (32/9) log(1/δ); reason: the smallest such B is one of them
  • generalization: batch error indicators with values in {0, 1} → measurable random variables that are {0, 1}-valued almost surely; reason: everywhere {0,1}-valued indicators are a special case
  • encoding: the majority error → Pr[Σ_b X_b ≥ B/2]; reason: for odd B the majority errs exactly when at least B/2 batches err
Preamble
import Mathlib

set_option autoImplicit false
Formal statement
namespace DesignTest

open MeasureTheory ProbabilityTheory

/-- **Equation (51) and the majority bound** (amplification). A. Kawachi, Y. Nakata, Y. Takeuchi,
*Testing State and Unitary Designs*, STOC 2027 submission (sha256 e2f0a429…), proof of Theorem 4.5,
eq. (51), p.34, and the following display, p.35; cited in the proof of Theorem 4.11, p.39.

Let `δ ∈ (0, 1/2)` and let `B` be an odd integer with `B ≥ (32/9) log(1/δ)`. If `X_1, …, X_B` are
independent `{0,1}`-valued random variables (the batch error indicators) with means at most `1/8`, the
majority errs with probability `Pr[Σ_b X_b ≥ B/2] ≤ exp(−2B(1/2 − 1/8)²) = exp(−9B/32) ≤ δ`.

**Formalization Note.** The indicators live on an arbitrary probability space; independence is Mathlib's
`iIndepFun`; `{0,1}`-valued is required almost surely. -/
theorem eq_51 (δ : ℝ) (hδ0 : 0 < δ) (hδ1 : δ < 1 / 2) (B : ℕ) (hBodd : Odd B)
    (hB : 32 / 9 * Real.log (1 / δ) ≤ (B : ℝ)) {Ω : Type} [MeasurableSpace Ω] (P : Measure Ω)
    [IsProbabilityMeasure P] (X : Fin B → Ω → ℝ) (hmeas : ∀ b, Measurable (X b))
    (hind : iIndepFun X P) (h01 : ∀ b, ∀ᵐ ω ∂P, X b ω = 0 ∨ X b ω = 1)
    (hmean : ∀ b, ∫ ω, X b ω ∂P ≤ 1 / 8) :
    P {ω | (B : ℝ) / 2 ≤ ∑ b, X b ω} ≤ ENNReal.ofReal (Real.exp (-(9 * (B : ℝ) / 32))) ∧
      Real.exp (-(9 * (B : ℝ) / 32)) ≤ δ := by sorry

end DesignTest
Source
Kawachi–Nakata–Takeuchi, Testing State and Unitary Designs, STOC 2027 submission (sha256 e2f0a429…), proof of Theorem 4.5, eq. (51), p.34, and the display following it, p.35; cited in the proof of Theorem 4.11, p.39
Human review
  • Endorsed by Shuze Chen · Nov 11, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · 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