Theorem 23 — for all total Boolean functions
ProvedApproxDegComp.theorem_23approximate-degreeboolean-functionscomposition-theoremp2o-gran-per-chapterp2o-plan-paperp2o-v1polynomial-methodquery-complexity
There is an absolute constant such that for all and all total Boolean functions and ,
where is the block composition .
The matching upper bound is known, so this states that approximate degree composes multiplicatively up to constants for all total functions.
Formalization Note is a single constant chosen before . Block of an input on is (OAI.Paper320.compose). Constant or and or are included.
Differences from the source:
- reading: d̃eg(f∘g) = Ω(d̃eg(f)d̃eg(g)) → ∃ c > 0 such that for all n, m, f, g: c·d̃eg(f)·d̃eg(g) ≤ d̃eg(f∘g); reason: the meaning of Ω with one absolute constant, uniform over n, m, f, g
Preamble
import Mathlib import Definitions.Def_ApproxDegComp_approxDeg import Definitions.Def_OAI_Combinatorics_Sensitivity_Composition
Formal statement
namespace ApproxDegComp
/-- **Theorem 23 (Composition Theorem)**, p.22 (proof pp.23–24).
Pednekar–Podder, *On the Composition Theorem for Approximate Degree, Randomized and Exact
Quantum Query Complexity*, STOC 2027 submission (manuscript sha256 b9a66c7f…), Theorem 23, p.22: "Let f : {0, 1}ⁿ → {0, 1} and g : {0, 1}^m → {0, 1} be arbitrary total
Boolean functions. Then d̃eg(f ∘ g) = Ω(d̃eg(f) d̃eg(g))."
**Formalization Note** `Ω(·)` is one absolute constant `c > 0`, chosen before `n, m, f, g`.
`f ∘ g` is the block composition `OAI.Paper320.compose f g` on `Fin n × Fin m`, whose coordinate
`(i, j)` is bit `j` of block `i` (Definition 1 with total `f, g`). Constant `f` or `g` and
`n = 0`, `m = 0` are included. -/
theorem theorem_23 : ∃ c : ℝ, 0 < c ∧ ∀ (n m : ℕ) (f : (Fin n → Bool) → Bool)
(g : (Fin m → Bool) → Bool),
c * (approxDeg f : ℝ) * (approxDeg g : ℝ) ≤ (approxDeg (OAI.Paper320.compose f g) : ℝ) := by sorry
end ApproxDegComp
Source
Pednekar–Podder, On the Composition Theorem for Approximate Degree, Randomized and Exact Quantum Query Complexity, STOC 2027 submission (manuscript sha256 b9a66c7fdb2afdb57851f3734661cd2140455987b17e2a1e2400586be814092b), Theorem 23, p.22 (proof pp.23–24)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.