Lemma 5.4 — IMM formula construction
OpenMonoABPWidth.Hierarchy.Supplement.lemma_5_4algebraic-complexitymonotone-computationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
For integers , and , there exists an alternating arbitrary-fan-in real monotone formula computing with an addition gate at its root, addition depth exactly , and
The front factor is the original , including when is not a perfect power. This construction supports Theorem 5.10 and is not a step in the proof of the retained goal.
Differences from the source:
- encoding: finite variable sets, real nonnegative coefficients, and tree resources → Fin-indexed variables/children, NNReal labels, and recursively computed resources; reason: finite renaming preserves every instance and a scalar-variable leaf still costs one leaf
Preamble
import Definitions.Def_MonoABPWidth_Hierarchy_Supplement_formulas import Definitions.Def_SetMultCost_imm open scoped BigOperators ENNReal
Formal statement
namespace MonoABPWidth.Hierarchy.Supplement
/-- Lemma 5.4, p.14 (PDF15): exact leaf count, exact addition depth,
and an addition root, including the non-perfect-power lengths. -/
theorem lemma_5_4 (k n d : ℕ) (hk : 2 ≤ k) (hn : 1 ≤ n) (hd : 1 ≤ d) :
∃ F : Formula (SetMultCost.IMMVar k n), F.eval = SetMultCost.imm ℝ k n ∧
F.Alternating ∧ F.addDepth = d ∧ F.leaves = immLeafUpper k n d ∧ F.addRoot := by sorry
end MonoABPWidth.Hierarchy.Supplement
Source
Julian Dörfler, Alexander Rogovskyy, STOC 2027 submission #927 (October 2026), Lemma 5.4, p.14, PDF15