Binary bracelets under the dihedral action
ProvedAnalyticCombinatorics.Ch1.Polya.Bracelets.card_binary_braceletsanalytic-combinatoricsbraceletsgroup-actionspolya-enumerationsymbolic-method
Let be a natural number with . Consider all binary colorings of the positions , identified under the full dihedral group of order . Its specified left action on positions sends to for a rotation and to for a reflection ; colorings carry the induced inverse-precomposition action. Let be the number of coloring orbits. Then, as an equality of natural numbers,
Here is the least nonnegative representative of , and each quotient in the formula is natural-number division. This is the orbit-count formula with the factor retained. Rotations and reflections identify colorings; exchanging the two color names is not an additional equivalence.
Preamble
import Definitions.Def_AnalyticCombinatorics_Ch1_Polya_Bracelets
import Mathlib
set_option autoImplicit true
set_option relaxedAutoImplicit false
set_option maxSynthPendingDepth 3
/-!
# Binary bracelets
This file applies the Pólya enumeration theorem to binary colorings of `ZMod n`
under the dihedral action. With Mathlib's multiplication convention for
`DihedralGroup`, the compatible left action is `r i : x ↦ x - i` and
`sr i : x ↦ i - x`.
-/
open AnalyticCombinatorics AnalyticCombinatorics.Ch1 AnalyticCombinatorics.Ch1.Polya AnalyticCombinatorics.Ch1.Polya.Bracelets
open scoped BigOperators
attribute [local instance] arrowAction
attribute [local instance] _root_.AnalyticCombinatorics.Ch1.Polya.Bracelets.orbitRelDecidableRel
attribute [local instance] _root_.AnalyticCombinatorics.Ch1.Polya.Bracelets.orbitQuotientFintype
attribute [local instance] _root_.AnalyticCombinatorics.Ch1.Polya.Bracelets.subtypeFintypeClassical
variable {n : ℕ}
variable {n : ℕ} [NeZero n]
variable {n : ℕ} [NeZero n]
variable {n : ℕ} [NeZero n]
Formal statement
theorem AnalyticCombinatorics.Ch1.Polya.Bracelets.card_binary_bracelets (n : ℕ) (hn : 0 < n) :
letI : NeZero n := ⟨Nat.ne_of_gt hn⟩
Fintype.card
(MulAction.orbitRel.Quotient (DihedralGroup n) (ZMod n → Bool)) * (2 * n) =
(∑ k : ZMod n, 2 ^ Nat.gcd n k.val) +
if n % 2 = 1 then
n * 2 ^ ((n + 1) / 2)
else
n / 2 * 2 ^ (n / 2 + 1) + n / 2 * 2 ^ (n / 2) := by sorrySource
Human review
Confirmed by the mission captain (proposal self-audit).