Theorem 6.4 — one family beyond slowly growing widths
OpenMonoABPWidth.Hierarchy.Supplement.theorem_6_4algebraic-complexitymonotone-computationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
There exists one real p-family computable by monotone formulas of polynomial total gate count such that, for every natural-valued width function satisfying the following little-o condition,
The quantifier order is . No monotonicity, divergence, or eventual lower bound on is assumed. Formula depth is unrestricted. This places a single formula family beyond every width class in the specified regime.
Differences from the source:
- encoding: one p-family outside all widths in the stated little-o class → one PolynomialFamily followed by every natural-valued W with IsLittleO atTop; reason: the order of quantifiers and the squared base-two iterated-log denominator are preserved; finite initial values do not affect little-o
Preamble
import Definitions.Def_MonoABPWidth_Hierarchy_Supplement_families open scoped BigOperators ENNReal
Formal statement
namespace MonoABPWidth.Hierarchy.Supplement
/-- Theorem 6.4, p.16 (PDF17): one family works for every little-o width
function. No monotonicity or eventual positive lower bound is imposed on W. -/
theorem theorem_6_4 : ∃ f : PolynomialFamily, InMVF f ∧
∀ W : ℕ → ℕ,
Asymptotics.IsLittleO Filter.atTop (fun t => (W t : ℝ)) widthThreshold →
¬ InMVBP W f := by sorry
end MonoABPWidth.Hierarchy.Supplement
Source
Julian Dörfler, Alexander Rogovskyy, STOC 2027 submission #927 (October 2026), Theorem 6.4, p.16, PDF17