§3.1 — multilinearization of a real polynomial on the Boolean cube
DefinitionDeMorganApprox_Main_Supplement_MultilinearizeLet be a real polynomial in the variables , written in the monomial basis as . Its multilinearization is obtained by replacing every monomial with , i.e. lowering every positive exponent to , and keeping the coefficient:
Coefficients of monomials that become identical are added. Since for and , agrees with on the Boolean cube, and it is multilinear.
The paper's coefficient -norm (§3.1) is the sum of the absolute values of the coefficients of in the -monomial basis after multilinearization on the Boolean cube, i.e. . With the published coefficient sum coeffL1 of the base mission's definitions, this is coeffL1 (multilinearize P); for a polynomial that is already multilinear the two coincide.
Formalization Note The exponent vector is a finitely supported map , and the new exponent vector is with every entry replaced by .
import Mathlib
import Definitions.Def_DeMorganApprox_Main_Basic
namespace DeMorganApprox.Main.Supplement
/-- Multilinearization on the Boolean cube (§3.1, PDF p. 10): every monomial `∏ xᵢ^{sᵢ}` is
replaced by `∏_{sᵢ ≥ 1} xᵢ` (exponent `min sᵢ 1`), keeping its coefficient; coefficients of
monomials that become identical add up. The result agrees with `P` on `{0,1}^σ`. -/
noncomputable def multilinearize {σ : Type} (P : MvPolynomial σ ℝ) : MvPolynomial σ ℝ :=
∑ s ∈ P.support, MvPolynomial.monomial (s.mapRange (fun k => min k 1) (by simp)) (P.coeff s)
end DeMorganApprox.Main.Supplement