Theorem 7.6 — permanent optimum asymptotic
OpenMonoABPWidth.Hierarchy.Supplement.theorem_7_6algebraic-complexitymonotone-computationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
For each fixed integer , let be the minimum leaf count over all real monotone formulas of multiplication depth exactly computing . Let . Then
This is the full two-sided optimum asymptotic with leading constant , not a one-sided or logarithmic-order estimate. Theorem 7.5 ensures the optimum is finite at positive ; iterated logarithms are positive eventually. No rate or uniformity in growing depth is claimed.
Differences from the source:
- encoding: optimal leaves ((e+o(1)) ln iterated d-1 times(n))^n → Tendsto of the nth root divided by iterated natural log to exp(1); reason: this is the full two-sided asymptotic; the true feasible-set optimum is finite for positive n by Theorem 7.5, so conversion to real loses no value
- encoding: optimal leaf count under the alternating convention of §2.3 → permanentOpt takes the infimum over all computing formula trees of exact multiplication depth d; reason: contracting adjacent gates and then padding with unary alternating gates preserves leaves and restores exact multiplication depth d; hence the alternating and unrestricted optima agree
Preamble
import Definitions.Def_MonoABPWidth_Hierarchy_Supplement_permanent open scoped BigOperators ENNReal
Formal statement
namespace MonoABPWidth.Hierarchy.Supplement
/-- Theorem 7.6, p.22 (PDF23): the full two-sided optimal-leaf
asymptotic with leading constant exp(1), for each fixed multiplication depth. -/
theorem theorem_7_6 (d : ℕ) (hd : 2 ≤ d) :
Filter.Tendsto (fun n : ℕ =>
(permanentOpt n d).toReal ^ (1 / (n : ℝ)) / iteratedLog d (n : ℝ))
Filter.atTop (nhds (Real.exp 1)) := by sorry
end MonoABPWidth.Hierarchy.Supplement
Source
Julian Dörfler, Alexander Rogovskyy, STOC 2027 submission #927 (October 2026), Theorem 7.6, p.22, PDF23