Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Real monotone formula trees and their exact resources

Definition
MonoABPWidth_Hierarchy_Supplement_formulas

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

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

A real monotone formula is a finite rooted tree. Each leaf is either a nonnegative real constant or a nonnegative real scalar multiple of a variable. Each internal gate adds or multiplies a positive finite number of children; unary gates are permitted. Evaluation uses polynomial sum and product. Leaves have depth zero and count as one gate and one leaf. For an internal gate with children FiF_iFi​,

s(F)=1+∑is(Fi),λ(F)=∑iλ(Fi),d(F)=1+max⁡id(Fi).s(F)=1+\sum_i s(F_i),\qquad \lambda(F)=\sum_i\lambda(F_i),\qquad d(F)=1+\max_i d(F_i).s(F)=1+i∑​s(Fi​),λ(F)=i∑​λ(Fi​),d(F)=1+imax​d(Fi​).

Addition depth and multiplication depth count their respective gates along the longest path. Alternation forbids adjacent internal gates of the same type. Root predicates distinguish the two operations. This generic tree model imposes neither homogeneity nor an order on variables.

Two numerical functions also record the IMM leaf bounds: the lower expression nkd(n1/d−1)n k^{d(n^{1/d}-1)}nkd(n1/d−1) for d>0d>0d>0, extended to nnn at d=0,n≤1d=0,n\le1d=0,n≤1 and +∞+\infty+∞ at d=0,n≥2d=0,n\ge2d=0,n≥2, and the integer upper count nkd(⌈n1/d⌉−1)n k^{d(\lceil n^{1/d}\rceil-1)}nkd(⌈n1/d⌉−1) for d≥1d\ge1d≥1. These functions do not constrain formula trees or their evaluation.

Definition code
import Definitions.Def_MonoABPWidth_Hierarchy_polynomials

open scoped BigOperators ENNReal

namespace MonoABPWidth.Hierarchy.Supplement

/-- §2.3: finite arbitrary-fan-in monotone formula trees. Internal gates have
positive fan-in, including unary gates. Constants include zero. A scalar-variable
leaf counts as one leaf and has depth zero. -/
inductive Formula (σ : Type) where
  | constant (c : NNReal)
  | variable (c : NNReal) (x : σ)
  | add (arity : ℕ) (child : Fin (arity + 1) → Formula σ)
  | mul (arity : ℕ) (child : Fin (arity + 1) → Formula σ)

noncomputable def Formula.eval {σ : Type} : Formula σ → MvPolynomial σ ℝ
  | .constant c => MvPolynomial.C (c : ℝ)
  | .variable c x => MvPolynomial.C (c : ℝ) * MvPolynomial.X x
  | .add _ f => ∑ i, (f i).eval
  | .mul _ f => ∏ i, (f i).eval

def Formula.leaves {σ : Type} : Formula σ → ℕ
  | .constant _ | .variable _ _ => 1
  | .add _ f | .mul _ f => ∑ i, (f i).leaves

def Formula.size {σ : Type} : Formula σ → ℕ
  | .constant _ | .variable _ _ => 1
  | .add _ f | .mul _ f => 1 + ∑ i, (f i).size

def Formula.depth {σ : Type} : Formula σ → ℕ
  | .constant _ | .variable _ _ => 0
  | .add _ f | .mul _ f => 1 + Finset.univ.sup (fun i => (f i).depth)

def Formula.addDepth {σ : Type} : Formula σ → ℕ
  | .constant _ | .variable _ _ => 0
  | .add _ f => 1 + Finset.univ.sup (fun i => (f i).addDepth)
  | .mul _ f => Finset.univ.sup (fun i => (f i).addDepth)

def Formula.mulDepth {σ : Type} : Formula σ → ℕ
  | .constant _ | .variable _ _ => 0
  | .add _ f => Finset.univ.sup (fun i => (f i).mulDepth)
  | .mul _ f => 1 + Finset.univ.sup (fun i => (f i).mulDepth)

def Formula.addRoot {σ : Type} : Formula σ → Prop
  | .add _ _ => True
  | _ => False

def Formula.mulRoot {σ : Type} : Formula σ → Prop
  | .mul _ _ => True
  | _ => False

/-- Alternation of adjacent internal gate types; leaves have no gate type. -/
def Formula.Alternating {σ : Type} : Formula σ → Prop
  | .constant _ | .variable _ _ => True
  | .add _ f => ∀ i, ¬ (f i).addRoot ∧ (f i).Alternating
  | .mul _ f => ∀ i, ¬ (f i).mulRoot ∧ (f i).Alternating

/-- The exact positive-depth expression of Theorem 5.6, extended as in its proof
on p.21 to depth zero: n for n≤1, and infinity otherwise. -/
noncomputable def immLeafLower (k n d : ℕ) : ℝ≥0∞ :=
  if d = 0 then (if n ≤ 1 then (n : ℝ≥0∞) else ⊤)
  else ENNReal.ofReal ((n : ℝ) * (k : ℝ) ^
    ((d : ℝ) * ((n : ℝ) ^ (1 / (d : ℝ)) - 1)))

/-- Exact integer leaf count of Lemma 5.4; d≥1 is its domain. -/
noncomputable def immLeafUpper (k n d : ℕ) : ℕ :=
  n * k ^ (d * (Nat.ceil ((n : ℝ) ^ (1 / (d : ℝ))) - 1))

end MonoABPWidth.Hierarchy.Supplement
Source
Julian Dörfler, Alexander Rogovskyy, STOC 2027 submission #927 (October 2026), §2.3, p.5, PDF6; Lemma 5.4 and Theorem 5.6, p.14, PDF15; depth-zero extension p.21, PDF22

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