Multilinearization preserves bounded-degree polynomial-calculus derivability
ProvedAC02Frege.pcDerivable_multilinearizationac0-2-fregepolynomial-calculusproof-complexity
Let be a CNF on Boolean variables, and let polynomial calculus include the Boolean axioms over . If a formal polynomial is derivable in formal degree at most , then its multilinearization is derivable within the same bound:
Here multilinearization replaces every positive variable exponent by one and adds coefficients of coinciding monomials. This is the degree-preserving reduction recorded immediately before Fact 2.5, and is useful whenever Boolean-ring identities must be justified in formal polynomial calculus.
Preamble
import Definitions.Def_AC02Frege_PC open MvPolynomial
Formal statement
theorem AC02Frege.pcDerivable_multilinearization {n : ℕ}
(F : LiftSAParity.CNF (Fin n)) (D : ℕ)
(p : MvPolynomial (Fin n) (ZMod 2))
(hp : AC02Frege.PCDerivable F D p) :
AC02Frege.PCDerivable F D (AC02Frege.ML p) := by sorrySource
Alekseev, Gryaznov, Pitassi, Robere, Shekhovtsov, Tzameret, Progress on AC0[2]-Frege Lower Bounds, November 3, 2026, https://www.doc.ic.ac.uk/~itzamere/Syntactic_ACZTwo.pdf, Definitions 2.1–2.4 and Fact 2.5, printed pp.9–10. Supporting lemma for the formalization of Fact 2.5; the source records degree-preserving multilinearization immediately before the fact.