§2, Eq. (16), second inequality: for every integer
ProvedConstOverheadCompile.Main.binomial_tail_eq16concentration-inequalitiesp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability
For all nonnegative integers and with ,
In the paper this bound controls the number of state-injection calls of Algorithm 1: if more than injections occur, fewer than of the first independent fair coins came up "no correction needed". It fixes the cutoff in the proofs of Theorems 2, 7 and 9.
Differences from the source:
- reading: Eq. (16) chains → only the second inequality; reason: the first concerns the random number of injection calls of Algorithm 1, an object of the proof of Theorem 9 that this mission does not define; the title marks the part stated.
- encoding: → the explicit sum ; reason: the same number.
Preamble
import Mathlib
Formal statement
namespace ConstOverheadCompile.Main
/-- §2, p.7, Eq. (16), second inequality: for all integers `m ≥ 4G ≥ 0`,
`Pr[Bin(m, 1/2) < G] = 2^{-m} Σ_{k < G} C(m, k) ≤ e^{-m/8}`. -/
theorem binomial_tail_eq16 (G m : ℕ) (h : 4 * G ≤ m) :
(∑ k ∈ Finset.range G, (m.choose k : ℝ)) / 2 ^ m ≤ Real.exp (-(m : ℝ) / 8) := by sorry
end ConstOverheadCompile.Main
Source
Chenyi Zhang, Xinyu Tan, Robin Kothari, David Gosset, Craig Gidney, Quantum circuit compilation with constant overhead, STOC 2027 submission #397 (October 2026), source.pdf SHA-256 b848604016de1821f5f693c59f328e0b2a9e535bca0b37bb664e6f40dbe3681f, p.7, §2, Eq. (16) (second inequality)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.