Permanent, independent leaf optimum, and ordered-composition recurrence
DefinitionMonoABPWidth_Hierarchy_Supplement_permanentFor the generic real matrix, define
The true optimum is the infimum of leaf counts of actual monotone trees computing this polynomial with multiplication depth exactly . It is if there is no feasible formula. This definition uses no recurrence.
Separately define the candidate function and, for ,
Mathlib's finite type of ordered positive compositions supplies every decomposition, including a single part and unbalanced parts. The multinomial coefficient uses exact integer division. At depth zero set for and otherwise, as in the proof. Only positive is used in the permanent theorems; the recurrence has an unused empty-composition extension at . Finally is the -fold composition of natural logarithm. This separates the actual optimum from both the proposed recurrence and its claimed asymptotic.
import Definitions.Def_MonoABPWidth_Hierarchy_Supplement_formulas
open scoped BigOperators ENNReal
namespace MonoABPWidth.Hierarchy.Supplement
/-- §7, p.22: the permanent of the generic real n×n matrix. -/
noncomputable def permanent (n : ℕ) : MvPolynomial (Fin n × Fin n) ℝ :=
∑ π : Equiv.Perm (Fin n), ∏ i : Fin n, MvPolynomial.X (i, π i)
/-- True optimum over actual formulas, independent of any recurrence. The empty
feasible set has infimum +infinity in ENNReal. -/
noncomputable def permanentOpt (n d : ℕ) : ℝ≥0∞ :=
⨅ F : {F : Formula (Fin n × Fin n) // F.eval = permanent n ∧ F.mulDepth = d},
(F.val.leaves : ℝ≥0∞)
/-- The finite ordered-composition recurrence in Theorem 7.5, with d=0 extended
as on p.22. Composition n contains every ordered positive composition, including
the single part n for n>0. Its finite nonempty minimum never uses a default value. -/
noncomputable def permanentL : ℕ → ℕ → ℝ≥0∞
| n, 0 => if n ≤ 1 then (n : ℝ≥0∞) else ⊤
| n, 1 => (n * n.factorial : ℕ)
| n, d + 2 => Finset.univ.inf' Finset.univ_nonempty (fun c : Composition n =>
(n.factorial / (c.blocks.map Nat.factorial).prod : ℕ) *
(c.blocks.map (fun m => permanentL m (d + 1))).sum)
/-- Composition of natural log (d−1) times, not a power or a change of base. -/
noncomputable def iteratedLog (d : ℕ) (x : ℝ) : ℝ := (Real.log^[d - 1]) x
end MonoABPWidth.Hierarchy.Supplement