Theorem 7.5 — exact permanent optimum
OpenMonoABPWidth.Hierarchy.Supplement.theorem_7_5algebraic-complexitymonotone-computationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let and be integers. Define and use all ordered positive compositions in
There exists a real monotone formula computing with multiplication depth exactly and exactly leaves. Every real monotone formula computing that polynomial with the same multiplication depth has at least leaves. Thus the independently defined true optimum equals this recurrence. Both attainment and the universal lower bound are included; the minimum is not restricted to balanced compositions.
Differences from the source:
- encoding: positive matrix dimension and minimum over every ordered positive composition → Fin n variables, the complete finite type Composition n, and extended nonnegative leaf counts; reason: the multinomial quotient is exact integer division, all compositions including one part are retained, and unary gates permit exact depth at the degree-one endpoint
- 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: attainment by a bounded-depth formula under the alternating convention of §2.3 → the existential witness is allowed to be any formula tree of the stated exact multiplication depth; reason: contracting adjacent gates preserves leaves and can only reduce multiplication depth; unary alternating gates restore the stated exact multiplication depth without adding leaves, so an alternating witness follows with the same leaf count
Preamble
import Definitions.Def_MonoABPWidth_Hierarchy_Supplement_permanent open scoped BigOperators ENNReal
Formal statement
namespace MonoABPWidth.Hierarchy.Supplement
/-- Theorem 7.5, p.22 (PDF23): exact attainment and universal optimality
of the independent ordered-composition recurrence. -/
theorem theorem_7_5 (n d : ℕ) (hn : 1 ≤ n) (hd : 2 ≤ d) :
(∃ F : Formula (Fin n × Fin n), F.eval = permanent n ∧
F.mulDepth = d ∧ (F.leaves : ℝ≥0∞) = permanentL n d) ∧
(∀ F : Formula (Fin n × Fin n), F.eval = permanent n → F.mulDepth = d →
permanentL n d ≤ (F.leaves : ℝ≥0∞)) := by sorry
end MonoABPWidth.Hierarchy.Supplement
Source
Julian Dörfler, Alexander Rogovskyy, STOC 2027 submission #927 (October 2026), Theorem 7.5, p.22, PDF23