Theorem 6.1 — tightness: some ≤ n-leaf De Morgan formula needs coefficient ℓ1-norm 2^{Ω(√n)} for every 1/3-approximating polynomial
OpenDeMorganApprox.Main.Supplement.theorem_6_1A De Morgan formula on input variables has and gates and literal leaves or ; its size is the number of leaf occurrences. For a real polynomial in variables, denotes its coefficient -norm in the -monomial basis after multilinearization on the Boolean cube (§3.1).
Theorem (tightness of the coefficient bound). There is an absolute constant such that for all sufficiently large there is a Boolean function computed by a De Morgan formula with at most leaves with the following property: every real polynomial in the input variables satisfying
also satisfies
No restriction is placed on the degree of , and need not be multilinear.
The theorem shows that the coefficient bound of Theorem 1.1 (the goal of this mission) cannot be improved beyond the constant in the exponent, even if the degree bound is dropped.
Formalization Note The is one constant chosen before , the formula and ; "for all sufficiently large " is "there is such that for all ". The number of variables and the formula are existential, as in the theorem. ranges over all of MvPolynomial (Fin m) ℝ; Boolean inputs are evaluated at their real points, and is coeffL1 (multilinearize P). Since multilinearization only merges coefficients, this is at most the raw coefficient sum coeffL1 P, so the statement also gives the lower bound on the raw sum.
Differences from the source:
- encoding: Ω(√n) in the exponent → one constant c > 0 quantified before n, the formula and P, with exponent c·√n; reason: the standard reading of Ω, the same reading the published goal uses for its O(√n).
- encoding: Boolean function F computed by a De Morgan formula with at most n leaves → a formula φ : Formula m with φ.leaves ≤ n, F = φ.eval, m existential; reason: the published negation-normal-form encoding of §3.1, which the base mission's definitions fix.
- encoding: ‖P‖₁, the coefficient ℓ1-norm in the {0,1}-monomial basis after multilinearization → coeffL1 (multilinearize P); reason: this is the §3.1 definition verbatim; for multilinear P it is coeffL1 P.
import Mathlib import Definitions.Def_DeMorganApprox_Main_Basic import Definitions.Def_DeMorganApprox_Main_Supplement_Multilinearize
namespace DeMorganApprox.Main.Supplement
open DeMorganApprox.Main
/-- Theorem 6.1 (tightness of the coefficient bound), PDF p. 29 (printed p. 27). One absolute
constant `c > 0` for the `Ω(√n)`, chosen before `n`, the formula and `P`; `P` is any real
polynomial (no multilinearity, no degree bound), and `‖P‖₁` is the paper's §3.1 norm: the
coefficient ℓ1-norm of `P` after multilinearization on the Boolean cube. -/
theorem theorem_6_1 :
∃ c : ℝ, 0 < c ∧ ∃ N : ℕ, ∀ n : ℕ, N ≤ n →
∃ (m : ℕ) (φ : Formula m), φ.leaves ≤ n ∧
∀ P : MvPolynomial (Fin m) ℝ,
(∀ x : Fin m → Bool, |MvPolynomial.eval (boolPoint x) P - boolVal (φ.eval x)| ≤ 1 / 3) →
(2 : ℝ) ^ (c * Real.sqrt (n : ℝ)) ≤ coeffL1 (multilinearize P) := by sorry
end DeMorganApprox.Main.Supplement