Finite group actions on colorings
DefinitionAnalyticCombinatorics_Ch1_Polya_Enumerationanalytic-combinatoricsgroup-actionslean4polya-enumeration
Let a group act on a position set , and let be a color set. A coloring fixed by is identified with a function from the position orbits of the cyclic subgroup generated by to . Colorings carry the action . The definitions also give the translation action on , written with the additive group in multiplicative notation, together with its transitivity and cancellation properties. This action is defined for every natural ; finite counting applications impose a nonzero modulus separately.
Definition code
import Mathlib
set_option autoImplicit true
set_option relaxedAutoImplicit false
set_option maxSynthPendingDepth 3
/-!
# Pólya enumeration, unweighted form
This file gives the fixed-coloring count behind the unweighted Pólya enumeration
formula, then applies Burnside's lemma from Mathlib.
-/
namespace AnalyticCombinatorics.Ch1.Polya
open scoped BigOperators
attribute [local instance] arrowAction
noncomputable local instance orbitRelDecidableRel {H X : Type*} [Group H] [MulAction H X] :
DecidableRel (MulAction.orbitRel H X).r :=
Classical.decRel _
noncomputable local instance subtypeFintypeClassical {X : Type*} [Fintype X] (p : X → Prop) :
Fintype {x // p x} :=
@Subtype.fintype X p (Classical.decPred p) inferInstance
section General
variable {G D C : Type*} [Group G] [MulAction G D] [Fintype D] [DecidableEq D] [Fintype C]
/-- A coloring fixed by `g` is the same thing as a function on the orbits of `⟨g⟩`. -/
noncomputable def fixedColoringEquiv (g : G) :
{f : D → C // g • f = f} ≃
(MulAction.orbitRel.Quotient (Subgroup.zpowers g) D → C) where
toFun f q :=
Quotient.liftOn' q f.1 fun a b hab => by
rw [MulAction.orbitRel_apply, MulAction.mem_orbit_iff] at hab
rcases hab with ⟨x, hx⟩
have hxfix : (x : G) • f.1 = f.1 :=
smul_eq_self_of_mem_zpowers x.2 f.2
have hvalue := congr_fun hxfix a
have hinv : (x : G)⁻¹ • a = b := by
rw [← hx]
simp [MulAction.subgroup_smul_def]
change f.1 ((x : G)⁻¹ • a) = f.1 a at hvalue
have hconst : f.1 b = f.1 a := by
simpa [hinv] using hvalue
exact hconst.symm
invFun F :=
⟨fun d => F (Quotient.mk'' d), by
funext d
change F (Quotient.mk'' (g⁻¹ • d)) = F (Quotient.mk'' d)
congr 1
apply Quotient.sound'
rw [MulAction.orbitRel_apply, MulAction.mem_orbit_iff]
refine ⟨⟨g⁻¹, ?_⟩, ?_⟩
· exact Subgroup.inv_mem (Subgroup.zpowers g) (Subgroup.mem_zpowers g)
· simp [MulAction.subgroup_smul_def]⟩
left_inv f := by
ext d
rfl
right_inv F := by
funext q
induction q using Quotient.inductionOn'
rfl
end General
section Necklaces
open Multiplicative
/-- The multiplicative wrapper of `ZMod n` acts on `ZMod n` by additive translation. -/
instance zmodTranslationMulAction (n : ℕ) : MulAction (Multiplicative (ZMod n)) (ZMod n) where
smul k x := k.toAdd + x
one_smul x := by
change (0 : ZMod n) + x = x
simp
mul_smul k l x := by
change (k.toAdd + l.toAdd) + x = k.toAdd + (l.toAdd + x)
rw [add_assoc]
@[simp]
theorem zmodTranslation_smul (n : ℕ) (k x : ZMod n) :
(Multiplicative.ofAdd k : Multiplicative (ZMod n)) • x = k + x :=
rfl
@[simp]
theorem zmodTranslation_smul_toAdd (n : ℕ) (k : Multiplicative (ZMod n)) (x : ZMod n) :
k • x = k.toAdd + x :=
rfl
instance zmodTranslationIsPretransitive (n : ℕ) :
MulAction.IsPretransitive (Multiplicative (ZMod n)) (ZMod n) where
exists_smul_eq x y := by
refine ⟨Multiplicative.ofAdd (y - x), ?_⟩
simp [sub_eq_add_neg, add_comm]
instance zmodTranslationIsCancelSMul (n : ℕ) :
IsCancelSMul (Multiplicative (ZMod n)) (ZMod n) where
left_cancel' k x y h := by
change k.toAdd + x = k.toAdd + y at h
exact add_left_cancel h
right_cancel' k l x h := by
apply Multiplicative.toAdd.injective
change k.toAdd + x = l.toAdd + x at h
exact add_right_cancel h
end Necklaces
end AnalyticCombinatorics.Ch1.Polya
Source