Theorem 1.5 — parity decision tree depth bounded by
OpenParityDegreeDepth.Main.Supplement.theorem_1_5boolean-functionscomplexity-theoryfourier-analysisp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let have algebraic-normal-form degree exactly , and let be its Boolean phase. Write for the least depth of a parity decision tree computing exactly (each internal node queries a nonzero parity ), and for the threshold weight of : the least spectral norm of a real function with for all . Then
The statement holds for every and every , with exactly this coefficient. Since (take ), it strengthens the first inequality of the mission's main theorem, Theorem 1.3, which has in place of .
Formalization Note , the degree and are those of the mission's published operational context; is the infimum of witness spectral norms, which is at least , so the logarithm is evaluated on a positive argument.
Differences from the source:
- encoding: D⊕(f) → parityDepth (phase p), the least depth of an exact parity decision tree in the published Context; reason: the same quantity
- encoding: W(f) defined as a minimum → the real infimum of the same set of witness spectral norms; reason: the minimum is attained (paper's remark after Definition C.1), so the values agree
- encoding: p of degree exactly d ≥ 2 → anfDegree p = d in WithBot ℕ, d : ℕ with 2 ≤ d, exponent 2*d − 1 in ℕ; reason: the natural-number subtraction is exact because d ≥ 2
- encoding: log₂ → logTwo x = Real.log x / Real.log 2; reason: the argument W(f) ≥ 1 is positive, so this is the base-two logarithm
Preamble
import Mathlib import Definitions.Def_ParityDegreeDepth_Main_Context import Definitions.Def_ParityDegreeDepth_Main_Supplement_ThresholdWeight open scoped BigOperators noncomputable section
Formal statement
namespace ParityDegreeDepth.Main.Supplement
open ParityDegreeDepth.Main
/-- Zhang, STOC 2027 submission #798, Theorem 1.5, PDF p. 4 (printed p. 3); proof §C.1,
PDF p. 26 (printed p. 25). SHA-256
02e6bad861054e233c6877aa352d0014cf84172cde536433dd6e24588277680b.
Under the hypotheses of Theorem 1.3 (exact ANF degree `d ≥ 2`, `f = (-1)^p`, every `n`),
`D⊕(f) ≤ 1 + ((2^(2d-1) - 5)/3) log₂ W(f)`. -/
theorem theorem_1_5 (n d : ℕ) (p : Vec n (ZMod 2) → ZMod 2)
(hd : 2 ≤ d) (hp : anfDegree p = (d : WithBot ℕ)) :
(parityDepth (phase p) : ℝ) ≤
1 + ((2 : ℝ) ^ (2 * d - 1) - 5) / 3 * logTwo (thresholdWeight (phase p)) := by sorry
end ParityDegreeDepth.Main.Supplement
Source
Shengyu Zhang, STOC 2027 submission #798 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/798.pdf, SHA-256 02e6bad861054e233c6877aa352d0014cf84172cde536433dd6e24588277680b, Theorem 1.5, PDF p. 4 (printed p. 3); hypotheses of Theorem 1.3, PDF p. 3 (printed p. 2); proof §C.1, PDF p. 26 (printed p. 25).