Totient formula for the ordinary cycle construction
ProvedAnalyticCombinatorics.Ch1.CombClass.ogf_cycanalytic-combinatoricslean4ogfsymbolic-method
For a graded class of finite sets, write and . Assume . A size- cycle is a rotation orbit of a word indexed by , for some , whose letters are -objects of total size . Let and let be Euler’s totient function. Then
Substitution by is formal power-series substitution. The zero-size hypothesis and coefficientwise topology are part of this result.
Preamble
import Definitions.Def_AnalyticCombinatorics_Ch1_OGF_CycleOGF
import Mathlib.RingTheory.PowerSeries.Substitution
import Mathlib.RingTheory.PowerSeries.PiTopology
import Mathlib.Topology.Instances.Rat
import Mathlib.Algebra.Ring.Periodic
import Mathlib.Data.Fintype.EquivFin
import Mathlib.Data.Fintype.Sigma
import Mathlib.Data.Nat.Totient
import Mathlib.Data.ZMod.Basic
import Mathlib.Data.ZMod.QuotientGroup
import Mathlib.GroupTheory.Coset.Card
import Mathlib.GroupTheory.GroupAction.Quotient
import Mathlib.GroupTheory.QuotientGroup.Defs
import Mathlib.NumberTheory.Divisors
import Mathlib.Algebra.BigOperators.NatAntidiagonal
import Mathlib.RingTheory.PowerSeries.Basic
import Mathlib.Data.Fintype.Card
set_option autoImplicit true
set_option relaxedAutoImplicit false
set_option maxSynthPendingDepth 3
/-!
# Ch1 §I.2 — The cycle construction OGF layer
This file connects the Burnside count for cycle necklaces to the ordinary
generating function identity
`CYC(C)(z) = ∑_{d ≥ 1} φ(d)/d * mlog(C(z^d))`.
-/
open AnalyticCombinatorics AnalyticCombinatorics.Ch1
open scoped BigOperators PowerSeries.WithPiTopology
open PowerSeries
open PowerSeries.WithPiTopology
attribute [local instance] _root_.AnalyticCombinatorics.Ch1.instTopRatCycleOGF
local instance _root_.AnalyticCombinatorics.Ch1.instDiscRatCycleOGF : DiscreteTopology ℚ := ⟨rfl⟩
Formal statement
theorem AnalyticCombinatorics.Ch1.CombClass.ogf_cyc
(C : CombClass) (hC0 : C.counts 0 = 0) :
C.cyc.ogf = cycRHS C := by sorrySource
Human review
Confirmed by the mission captain (proposal self-audit).