Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Real p-families and monotone formula and branching-program classes

Definition
MonoABPWidth_Hierarchy_Supplement_families

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

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

A polynomial family f=(ft)t∈Nf=(f_t)_{t\in\mathbb N}f=(ft​)t∈N​ supplies a finite number m(t)m(t)m(t) of variables and a real polynomial ftf_tft​ in those variables. It is a p-family when m(t)m(t)m(t) and deg⁡ft\deg f_tdegft​ are polynomially bounded. A polynomial bound has the uniform form

s(t)≤C(t+1)afor all t∈N,s(t)\le C(t+1)^a\quad\text{for all }t\in\mathbb N,s(t)≤C(t+1)afor all t∈N,

with fixed natural C,aC,aC,a. Constants and exponents can depend on fixed theorem parameters, but not on ttt.

Membership in mVF\mathrm{mVF}mVF means that actual monotone trees computing ftf_tft​ have polynomial total gate count. Membership in mVFD\mathrm{mVF}_DmVFD​ additionally requires alternating trees of total depth at most DDD. Membership in mVBPW(t)\mathrm{mVBP}_{W(t)}mVBPW(t)​ means that the published affine-label mABPs computing ftf_tft​ have width at most W(t)W(t)W(t) and polynomial vertex count, where vertex count sums all layer sizes. All three classes include the p-family requirements. They are nonuniform: the definitions impose no algorithm for choosing the trees or programs.

The threshold for Theorem 6.4 is log⁡2t/(log⁡2log⁡2t)2\log_2 t/(\log_2\log_2 t)^2log2​t/(log2​log2​t)2. Its ordinary real-logarithm values at small indices have no effect on eventual little-o assertions. Renaming any finite variable set into Fin(m(t))\mathrm{Fin}(m(t))Fin(m(t)) preserves these classes.

Definition code
import Definitions.Def_MonoABPWidth_Hierarchy_Supplement_formulas
import Definitions.Def_MonoABPWidth_Hierarchy_branchingProgram

open scoped BigOperators ENNReal

namespace MonoABPWidth.Hierarchy.Supplement

/-- A uniform polynomial bound, with finite exceptions absorbed by C. -/
def PolynomiallyBounded (s : ℕ → ℕ) : Prop :=
  ∃ C a : ℕ, ∀ t : ℕ, s t ≤ C * (t + 1) ^ a

/-- Generic real polynomial families, before imposing resource or p-family bounds.
Every finite variable set can be renamed into Fin(nvars t). -/
structure PolynomialFamily where
  nvars : ℕ → ℕ
  poly : (t : ℕ) → MvPolynomial (Fin (nvars t)) ℝ

def PolynomialFamily.IsPFamily (f : PolynomialFamily) : Prop :=
  PolynomiallyBounded f.nvars ∧ PolynomiallyBounded (fun t => (f.poly t).totalDegree)

/-- Nonuniform polynomial gate count; no bound on depth. -/
def InMVF (f : PolynomialFamily) : Prop :=
  f.IsPFamily ∧ ∃ C a : ℕ, ∀ t : ℕ,
    ∃ F : Formula (Fin (f.nvars t)), F.eval = f.poly t ∧ F.size ≤ C * (t + 1) ^ a

/-- Bounded total depth, with the alternating convention of §2.3. -/
def InMVFDepth (D : ℕ) (f : PolynomialFamily) : Prop :=
  f.IsPFamily ∧ ∃ C a : ℕ, ∀ t : ℕ,
    ∃ F : Formula (Fin (f.nvars t)), F.eval = f.poly t ∧
      F.Alternating ∧ F.depth ≤ D ∧ F.size ≤ C * (t + 1) ^ a

/-- The source's vertex count, including both singleton endpoint layers. -/
def vertexCount {σ : Type} (A : MABP σ) : ℕ := ∑ i, A.layerSize i

/-- Full affine-label mABPs, polynomial vertex count and pointwise width bound. -/
def InMVBP (W : ℕ → ℕ) (f : PolynomialFamily) : Prop :=
  f.IsPFamily ∧ ∃ C a : ℕ, ∀ t : ℕ,
    ∃ A : MABP (Fin (f.nvars t)), A.output = f.poly t ∧
      A.width ≤ W t ∧ vertexCount A ≤ C * (t + 1) ^ a

/-- All logarithms in the width threshold of Theorem 6.4 are base two. -/
noncomputable def widthThreshold (t : ℕ) : ℝ :=
  Real.logb 2 (t : ℝ) / (Real.logb 2 (Real.logb 2 (t : ℝ))) ^ 2

end MonoABPWidth.Hierarchy.Supplement
Source
Julian Dörfler, Alexander Rogovskyy, STOC 2027 submission #927 (October 2026), §2.1–2.3, pp.4–5, PDF5–6; Theorem 6.4, p.16, PDF17

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