Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7.6 — permanent optimum asymptotic

Open
MonoABPWidth.Hierarchy.Supplement.theorem_7_6

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

algebraic-complexitymonotone-computationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

For each fixed integer d×≥2d_\times\ge2d×​≥2, let Opt⁡(n,d×)\operatorname{Opt}(n,d_\times)Opt(n,d×​) be the minimum leaf count over all real monotone formulas of multiplication depth exactly d×d_\timesd×​ computing per⁡n\operatorname{per}_npern​. Let ℓd×(n)=ln⁡∘(d×−1)(n)\ell_{d_\times}(n)=\ln^{\circ(d_\times-1)}(n)ℓd×​​(n)=ln∘(d×​−1)(n). Then

lim⁡n→∞Opt⁡(n,d×)1/nℓd×(n)=exp⁡(1).\lim_{n\to\infty}\frac{\operatorname{Opt}(n,d_\times)^{1/n}}{\ell_{d_\times}(n)}=\exp(1).n→∞lim​ℓd×​​(n)Opt(n,d×​)1/n​=exp(1).

This is the full two-sided optimum asymptotic ((e+o(1))ℓd×(n))n((e+o(1))\ell_{d_\times}(n))^n((e+o(1))ℓd×​​(n))n with leading constant eee, not a one-sided or logarithmic-order estimate. Theorem 7.5 ensures the optimum is finite at positive nnn; 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

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me