Weighted Pólya enumeration with the group factor retained
ProvedAnalyticCombinatorics.Ch1.Polya.Weighted.weighted_polyaanalytic-combinatoricsgroup-actionspolya-enumerationsymbolic-methodweighted-counting
Let a finite group act on a finite set of positions . Let be a finite set of colors, a commutative ring, and a weight function. The induced action on colorings is . For each orbit of colorings under the full group, define using any representative . For , let be the orbits of positions under the cyclic subgroup generated by , and write for an orbit's cardinality. Then in ,
All sums and products are finite. This connects weights of coloring orbits to the cyclic orbit structure of each group element, without assuming that the scalar is invertible.
Preamble
import Definitions.Def_AnalyticCombinatorics_Ch1_Polya_Weighted
import Mathlib
set_option autoImplicit true
set_option relaxedAutoImplicit false
set_option maxSynthPendingDepth 3
/-!
# Weighted Pólya enumeration
This file proves the weighted fixed-coloring sum behind the cycle-index theorem
and packages it as a weighted Burnside/Pólya formula.
-/
open AnalyticCombinatorics AnalyticCombinatorics.Ch1 AnalyticCombinatorics.Ch1.Polya AnalyticCombinatorics.Ch1.Polya.Weighted
open scoped BigOperators
attribute [local instance] arrowAction
attribute [local instance] _root_.AnalyticCombinatorics.Ch1.Polya.Weighted.orbitRelDecidableRel
attribute [local instance] _root_.AnalyticCombinatorics.Ch1.Polya.Weighted.subtypeFintypeClassical
variable {G D C R : Type*} [Group G] [MulAction G D] [Fintype D] [DecidableEq D]
[Fintype C] [CommRing R]
Formal statement
theorem AnalyticCombinatorics.Ch1.Polya.Weighted.weighted_polya [Fintype G] :
(Fintype.card G : R) *
(∑ O : MulAction.orbitRel.Quotient G (D → C), orbitWeight (G := G) (D := D) w O) =
∑ g : G,
∏ σ : MulAction.orbitRel.Quotient (Subgroup.zpowers g) D,
∑ c : C, w c ^ Fintype.card σ.orbit := by sorrySource
Human review
Confirmed by the mission captain (proposal self-audit).