Newton coefficients (20), , the good set , block counts of the singleton completion, binomial weights
DefinitionQMomentMatch_FirstBound_Supplement_NewtonCoeffmoment-matchingp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1polynomialsquantum-query-complexity
This file adds the objects of §4 of the paper that the base definitions do not contain. Throughout, , , and ; is the averaged acceptance probability of a fixed -query algorithm (the base definition hAcc), and for and , appends as last coordinate.
- Exponents. for integers , so , and .
- Newton coefficients of a function on :
- The functions and their Newton coefficients (eq. (20)): for , and
- The good set , through its indicator .
- The singleton completion of : the frequency vector of step 2 of Definition 2.1 for the multiplicities (non-zero entries of , completed by singletons and padded with zeros). Its number of -blocks is the number of entries equal to : counts the -blocks and the -blocks; and .
- Binomial weights .
These objects are the vocabulary of Lemmas 3.3, 3.6, 4.1, 4.8 and 4.9, which bound the Newton coefficients of in the proof of Theorem 2.6.
Formalization Note is set to for ; this value never enters, since is only used for . is set to when (the range is then empty); the paper uses it only for . is fixed inside and , as in the base distribution .
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Query
import Definitions.Def_QMomentMatch_FirstBound_Basic
import Definitions.Def_QMomentMatch_FirstBound_InducedDist
/-!
# Newton coefficients `d_ℓ(w)`, the exponents `α_j`, the good set `G`, block counts of the
singleton completion, and binomial weights
Kayal, Magniez, Sen, Szabó, *Quantum Query Lower Bounds from Classical Moment Matching*,
STOC 2027 submission #564, Lemma 3.3 (p. 16), Lemma 3.6 (p. 17), §4.1 eq. (20) (p. 24),
Lemma 4.9 (p. 32).
Conventions (as in the base files). `S = {0} ∪ [A]` is `Fin (A + 1)`; `m = ⌊N/2⌋` is `N / 2`;
`w ∈ S^{m−1}` is `w : Fin (N / 2 - 1) → Fin (A + 1)` and `(w, s)` is `appendLast w s`;
`h(z) = Pr_{f ∼ D_{c(z)}}[A^f = 1]` is the base `hAcc`.
-/
namespace QMomentMatch.FirstBound.Supplement
open QAlgorithms QMomentMatch.FirstBound
/-- p. 24: `α_j = 1 − 2^{1−j}` (an integer power of `2`, so `α_1 = 0`, `α_2 = 1/2`, …). -/
noncomputable def alpha (j : ℕ) : ℝ :=
1 - (2 : ℝ) ^ ((1 : ℤ) - (j : ℤ))
/-- Lemma 3.3 (p. 16) and eq. (20) (p. 24): the `ℓ`-th Newton coefficient
`d_ℓ = ∑_{s=0}^{ℓ} (−1)^{ℓ−s} (ℓ choose s) q(s)` of a function `q` on the integers `0, 1, 2, …`. -/
noncomputable def newtonCoeff (q : ℕ → ℝ) (ℓ : ℕ) : ℝ :=
∑ s ∈ Finset.range (ℓ + 1), (-1 : ℝ) ^ (ℓ - s) * ((ℓ.choose s : ℕ) : ℝ) * q s
/-- p. 24: `q_w(s) = h(w, s)` for `s ∈ S = {0, …, A}`, with `m = ⌊N/2⌋` and `h` the acceptance
probability of the `T`-query algorithm `alg` (output map `out`) averaged over `D_{c(w,s)}`.
Arguments `s > A` (outside `S`) are given the value `0`; they never occur below, because
`d_ℓ(w)` is used only for `ℓ ≤ A`. -/
noncomputable def qW {N : ℕ} [NeZero N] {W : Type*} [Fintype W] [DecidableEq W] {T : ℕ}
(alg : QueryAlg (Fin N) (ZMod N) W T) (out : (Fin N × ZMod N) × W → Bool)
{A : ℕ} (w : Fin (N / 2 - 1) → Fin (A + 1)) (s : ℕ) : ℝ :=
if h : s < A + 1 then hAcc alg out (appendLast (m := N / 2) w (⟨s, h⟩ : Fin (A + 1))) else 0
/-- Eq. (20), p. 24: the Newton coefficients `d_ℓ(w) = ∑_{s=0}^{ℓ} (−1)^{ℓ−s} (ℓ choose s) q_w(s)`
(`0 ≤ ℓ ≤ A`). -/
noncomputable def newtonW {N : ℕ} [NeZero N] {W : Type*} [Fintype W] [DecidableEq W] {T : ℕ}
(alg : QueryAlg (Fin N) (ZMod N) W T) (out : (Fin N × ZMod N) × W → Bool)
{A : ℕ} (w : Fin (N / 2 - 1) → Fin (A + 1)) (ℓ : ℕ) : ℝ :=
newtonCoeff (qW alg out w) ℓ
/-- p. 24: the indicator `1_G(w)` of the good set `G = {w ∈ S^{m−1} : ∑_i w_i ≤ 3N/4}`
(a real inequality). -/
noncomputable def goodInd (N : ℕ) {A n : ℕ} (w : Fin n → Fin (A + 1)) : ℝ :=
if (∑ i, (((w i : ℕ)) : ℝ)) ≤ 3 * (N : ℝ) / 4 then 1 else 0
/-- Lemma 4.9, p. 32 (and §4.2.1, p. 26): the completion `c(w, ℓ)` of `(w, ℓ)` with singletons,
i.e. the frequency vector of Definition 2.1 step 2 for the multiplicities `(w, ℓ)`, as the multiset
of its entries (the base `drawsFreq`). -/
def completion (N : ℕ) {A : ℕ} (w : Fin (N / 2 - 1) → Fin (A + 1)) (ℓ : Fin (A + 1)) :
Multiset ℕ :=
drawsFreq N (appendLast (m := N / 2) w ℓ)
/-- Lemma 4.9, p. 32: the number of `j`-blocks of the completion `c(w, ℓ)`, i.e. the number of its
entries equal to `j` (`ρ` is the case `j = ℓ`, `b_j` the case `1 ≤ j < ℓ`). -/
def blockCount (N : ℕ) {A : ℕ} (w : Fin (N / 2 - 1) → Fin (A + 1)) (ℓ : Fin (A + 1)) (j : ℕ) :
ℕ :=
(completion N w ℓ).count j
/-- Lemma 4.9, p. 32: `n_* = min_{1 ≤ j < ℓ} n_j` with `n_j = 1 + b_j`. (The index range is
nonempty exactly when `ℓ ≥ 2`, which Lemma 4.9 assumes; the value `1` for `ℓ ≤ 1` is never
used.) -/
def nStar (N : ℕ) {A : ℕ} (w : Fin (N / 2 - 1) → Fin (A + 1)) (ℓ : Fin (A + 1)) : ℕ :=
if h : (Finset.Ico 1 (ℓ : ℕ)).Nonempty then
(Finset.Ico 1 (ℓ : ℕ)).inf' h fun j => 1 + blockCount N w ℓ j
else 1
/-- Lemma 3.6, p. 17: the binomial probability `Pr[Bin(n, a) = k] = (n choose k) a^k (1−a)^{n−k}`
(zero for `k > n`). -/
noncomputable def binomPmf (n : ℕ) (a : ℝ) (k : ℕ) : ℝ :=
((n.choose k : ℕ) : ℝ) * a ^ k * (1 - a) ^ (n - k)
end QMomentMatch.FirstBound.Supplement
Source
Chandrima Kayal, Frédéric Magniez, Sayantan Sen, Dániel Szabó, STOC 2027 submission #564 (October 2026), Lemma 3.3 p. 16, Lemma 3.6 p. 17, §4.1 eq. (20) p. 24, Lemma 4.9 p. 32