Theorem 7.2 (corrected: positive degree) — compatible-weight lower bound
OpenMonoABPWidth.Hierarchy.Supplement.theorem_7_2algebraic-complexitymonotone-computationp2o-batch-stoc27sp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a monotone real polynomial of positive degree , with any compatible weight and growth function from §7. Let satisfy both
Every arbitrary-fan-in monotone formula computing then satisfies
Depth zero and infinite lower bounds remain allowed. Growth bounds concern relevant polynomials, and relevance means with monotone . This is the generic lower-bound framework, not a specialization to support cardinality or the permanent recurrence.
Differences from the source:
- correction: degree n without an explicit positive-degree qualification → 1 ≤ totalDegree p; reason: the proof treats n=1 and n>1 only; for p=1, w=G=1, L(0,d)=2 and L(n,d)=0 for n>0 satisfy both source inequalities but the one-leaf constant formula violates the claimed bound
- reading: growth is first described for all polynomials, then for relevant polynomials in §7 → growth bounds on relevant monotone polynomials and weight axioms on monotone polynomials; reason: uses the explicit relevance-based context of the framework rather than a bound on unrelated polynomials
- encoding: a lower-bound function that may take infinity → an arbitrary ENNReal-valued nonnegative lower-bound function; reason: negative lower bounds are trivial; their positive parts satisfy the same inequalities, while +infinity must remain representable
- generalization: bounded-depth formulas are assumed alternating without loss of generality in §2.3 → the universal lower bound also ranges over nonalternating trees; reason: contracting consecutive gates preserves leaves and never increases multiplication depth; the displayed bound is nonincreasing in depth
- generalization: a polynomial in a finite set of variables → any ambient variable type with finitely supported polynomials and finite formula trees; reason: each polynomial and formula uses finitely many variables; restricting the weight and growth data to those variables recovers the finite-variable source setting
Preamble
import Definitions.Def_MonoABPWidth_Hierarchy_Supplement_weights open scoped BigOperators ENNReal
Formal statement
namespace MonoABPWidth.Hierarchy.Supplement
/-- Theorem 7.2, p.20 (PDF21), with both (7.3) and (7.4) and arbitrary
compatible weight/growth/lower-bound functions. Positive degree is the domain of
the lower-bound argument. Depth zero remains allowed. -/
theorem theorem_7_2 {σ : Type} (p : MvPolynomial σ ℝ)
(hp : MonotonePolynomial p) (hn : 1 ≤ p.totalDegree)
(w : PolynomialWeight σ) (Gr : ℕ → NNReal)
(hc : Compatible p w Gr) (L : ℕ → ℕ → ℝ≥0∞)
(hL : LowerBoundConditions Gr L) (F : Formula σ) (hF : F.eval = p) :
L p.totalDegree F.mulDepth ≤ (F.leaves : ℝ≥0∞) := by sorry
end MonoABPWidth.Hierarchy.Supplement
Source
Julian Dörfler, Alexander Rogovskyy, STOC 2027 submission #927 (October 2026), Theorem 7.2, p.20, PDF21