Theorem 5.6 — IMM leaf lower bound
OpenMonoABPWidth.Hierarchy.Supplement.theorem_5_6algebraic-complexitymonotone-computationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let , and let be any arbitrary-fan-in real monotone formula computing . Write for its multiplication depth and for its leaf count. For ,
At depth zero the proof extends the bound to for and for , thereby asserting that no such formula exists in the latter case. No syntactic homogeneity or fixed-depth restriction is imposed. This gives the exact IMM leaf lower bound independently of the retained mABP goal.
Differences from the source:
- encoding: finite variable sets, real nonnegative coefficients, and tree resources → Fin-indexed variables/children, NNReal labels, and recursively computed resources; reason: finite renaming preserves every instance and a scalar-variable leaf still costs one leaf
- 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
- encoding: positive-depth formula and the proof’s depth-zero extension → ENNReal.ofReal of the positive-depth expression, with an explicit zero-depth branch; reason: avoids interpreting 1/0 as zero and represents the proof’s infinite bound
Preamble
import Definitions.Def_MonoABPWidth_Hierarchy_Supplement_formulas import Definitions.Def_SetMultCost_imm open scoped BigOperators ENNReal
Formal statement
namespace MonoABPWidth.Hierarchy.Supplement
/-- Theorem 5.6, p.14 (PDF15); depth-zero extension from p.21 (PDF22).
No homogeneity, variable order, perfect-power length or fixed depth is assumed. -/
theorem theorem_5_6 (k n : ℕ) (hk : 1 ≤ k) (hn : 1 ≤ n)
(F : Formula (SetMultCost.IMMVar k n)) (hF : F.eval = SetMultCost.imm ℝ k n) :
immLeafLower k n F.mulDepth ≤ (F.leaves : ℝ≥0∞) := by sorry
end MonoABPWidth.Hierarchy.Supplement
Source
Julian Dörfler, Alexander Rogovskyy, STOC 2027 submission #927 (October 2026), Theorem 5.6, p.14, PDF15