§4.1, p.28 — the Pelagic outputs carry squared Fourier mass at least
ProvedPelagicFF.pelagic_mass_gecommunication-complexityfourier-analysisp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information
Let . Then the frequencies satisfying the Pelagic condition (9) carry at least three quarters of the squared Fourier mass:
Since measuring the state returns with probability , this is the success guarantee of the quantum protocol; in particular is total.
Formalization Note is sign ∘ H for a Bool-valued H.
Differences from the source:
- encoding: Boolean functions with values in {−1,1} → Bool-valued functions read through OAI.Cotype.sign (false ↦ 1, true ↦ −1); reason: a bijection of value sets; same instances
Preamble
import Mathlib import Definitions.Def_PelagicFF_PFF open OAI.Cotype open Classical
Formal statement
namespace PelagicFF
/-- **The Pelagic mass bound (§4.1, p.28).** For every Boolean function `h : {0,1}ⁿ → {−1,1}`, the
total squared Fourier mass of the frequencies `y` satisfying the Pelagic condition (9) is at least
`1 − 1/8 − 1/8 = 3/4`.
arXiv:2610.05585 (held version, sha256 4564aef3…), §4.1, p.28: "The total squared Fourier mass of
all y which satisfy both inequalities is therefore at least 1 − 1/8 − 1/8 = 3/4."
**Formalization Note.** `h` is `sign ∘ H` for a `Bool`-valued `H`; the Fourier coefficient is
`OAI.Cotype.fourier`. -/
theorem pelagic_mass_ge (n : ℕ) (H : (Fin n → Bool) → Bool) :
(3 : ℝ) / 4 ≤ ∑ y ∈ Finset.univ.filter (fun y => IsPelagic (fun x => sign (H x)) y),
OAI.Cotype.fourier (fun x => sign (H x)) y ^ 2 := by sorry
end PelagicFF
Source
Anselm, Ding, Gilboa, Grewal, Optimal and Verifiable Quantum Advantages in Communication Complexity, arXiv:2610.05585 (held version, sha256 4564aef3…), §4.1, p.28
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.