minsky_papert_symmetrization
ProvedMinsky–Papert symmetrization.
For every multivariate real polynomial of total degree , there exists a univariate polynomial of degree such that for every integer ,
where is the Hamming weight and denotes evaluation at the -vector .
The multiplicative formulation avoids division by zero in the (vacuous) range , where and the right-hand side is also empty; for the binomial coefficient is positive and so is uniquely determined by the slice average.
Proof idea: average over the symmetric group acting on coordinates to get a symmetric polynomial of total degree . On any Boolean input, depends only on the Hamming weight, and the slice values are interpolated by a univariate polynomial of degree — explicitly, the value at integer comes from the -th elementary-symmetric expansion of .
Standard tool of the polynomial method (Minsky–Papert 1969 §1.5; Nisan–Szegedy 1994).
import Mathlib.Algebra.MvPolynomial.Basic
import Mathlib.Algebra.MvPolynomial.Eval
import Mathlib.Algebra.MvPolynomial.Degrees
import Mathlib.Algebra.Polynomial.Basic
import Mathlib.Algebra.Polynomial.Degree.Defs
import Mathlib.Algebra.Polynomial.Eval.Defs
import Mathlib.Data.Fintype.Pi
import Mathlib.Data.Real.Basic
import Mathlib.Data.Nat.Choose.Basic
/-!
# Minsky–Papert symmetrization
For any multivariate real polynomial `p : ℝ[X_1, …, X_b]` of total degree
`≤ d`, the function obtained by *averaging* `p` over the Hamming-weight-`t`
slice of the Boolean cube `{0,1}^b` extends to a univariate polynomial of
degree `≤ d`. This is the crucial dimensionality-reduction step in the
Nisan–Szegedy proof of `bs(f) ≤ 2 · deg(f)²`.
Stated multiplicatively (`Q(t) · (b choose t) = sum`) to avoid the division-by-
zero pathology when `t > b` (`b.choose t = 0`); for `t ≤ b`, `b.choose t > 0`
and so `Q(t)` is determined by the sum.
Left as a platform leaf — DEFERRED. Will be tackled in a separate session.
-/
open MvPolynomial
/-- **Minsky–Papert (1969) symmetrization.** For any multivariate polynomial
`p : ℝ[X_1, …, X_b]`, there exists a univariate polynomial `Q` of natDegree
`≤ p.totalDegree` such that for every integer `t ∈ {0, 1, …, b}`,
`Q(t) · (b choose t)` equals the sum of `p` evaluated at all weight-`t`
0/1-vectors. -/theorem minsky_papert_symmetrization
{b : ℕ} (p : MvPolynomial (Fin b) ℝ) :
∃ Q : Polynomial ℝ,
Q.natDegree ≤ p.totalDegree ∧
∀ t : ℕ, t ≤ b →
Q.eval (t : ℝ) * ((b.choose t : ℕ) : ℝ) =
∑ y ∈ (Finset.univ : Finset (Fin b → Bool)).filter
(fun y => ((Finset.univ : Finset (Fin b)).filter
(fun i => y i = true)).card = t),
MvPolynomial.eval (fun i => if y i then (1 : ℝ) else 0) p := by sorry