Euler product for integer partitions
ProvedAnalyticCombinatorics.Ch1.CombClass.ogf_partitionsanalytic-combinatoricslean4ogfsymbolic-method
Let be the cardinality of the source type Nat.Partition n, whose elements are multisets of positive integers summing to . In formal power series over ,
The sums and product use coefficientwise formal-series convergence with discrete rational coefficients; this is not an analytic infinite-product assertion.
Preamble
import Definitions.Def_AnalyticCombinatorics_Ch1_OGF_Partitions
import Mathlib.Combinatorics.Enumerative.Partition.GenFun
import Mathlib.RingTheory.PowerSeries.Basic
import Mathlib.Data.Fintype.Card
set_option autoImplicit true
set_option relaxedAutoImplicit false
set_option maxSynthPendingDepth 3
/-!
# Ch1 §I.3 — Integer partitions and Euler's product (MSET flagship)
Flajolet & Sedgewick, Part A, Chapter I, §I.3. An integer partition of `n` is a
multiset of positive integers summing to `n` — i.e. an object of `MSET(ℙ)` of size
`n`. Its generating function is Euler's product
`P(z) = ∏_{m≥1} 1/(1 - z^m) = ∏_{m≥1} ∑_{j≥0} z^{m j}`.
We model the partition class with Mathlib's `Nat.Partition` (a `Fintype`), connect
its OGF to Mathlib's `Nat.Partition.genFun`, and push it to the explicit infinite
product. The literal Euler product is an explicit TODO in Mathlib's `GenFun`, so
this is genuinely new content; it is anchored on `#(Nat.Partition n)`. The infinite
product/sums use the X-adic (coefficientwise) topology on `ℚ⟦X⟧`.
-/
open AnalyticCombinatorics AnalyticCombinatorics.Ch1
open PowerSeries
open scoped PowerSeries.WithPiTopology
open PowerSeries.WithPiTopology
attribute [local instance] _root_.AnalyticCombinatorics.Ch1.instTopRatPartitions
local instance _root_.AnalyticCombinatorics.Ch1.instDiscRatPartitions : DiscreteTopology ℚ := ⟨rfl⟩
Formal statement
theorem AnalyticCombinatorics.Ch1.CombClass.ogf_partitions :
CombClass.partitions.ogf
= ∏' i, ∑' j, (X : ℚ⟦X⟧) ^ ((i + 1) * j) := by sorrySource
Human review
Confirmed by the mission captain (proposal self-audit).