Polynomial calculus is closed under polynomial multiplication within the degree budget
ProvedAC02Frege.pcDerivable_mul_of_totalDegree_leac0-2-fregepolynomial-calculusproof-complexity
Let be a CNF on Boolean variables, and let polynomial calculus include its clause-complement polynomials and the Boolean axioms over . Suppose is derivable in formal degree at most . For any formal polynomial , if the sum of the total degrees of and is at most , then
This is the polynomial-multiplication step supporting Fact 2.5. It concerns the ordinary formal product before multilinearization; neither factor is required to be multilinear.
Preamble
import Definitions.Def_AC02Frege_PC open MvPolynomial
Formal statement
theorem AC02Frege.pcDerivable_mul_of_totalDegree_le {n : ℕ}
(F : LiftSAParity.CNF (Fin n)) (D : ℕ)
(u v : MvPolynomial (Fin n) (ZMod 2))
(hu : AC02Frege.PCDerivable F D u)
(hdeg : u.totalDegree + v.totalDegree ≤ D) :
AC02Frege.PCDerivable F D (u * v) := 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.