perm_cycle_gcd
def
The greatest common divisor of the cycle lengths of a permutation $\sigma$ on a finite type $\alpha$, where fixed points are counted as cycles of length 1.
Statement
def perm_cycle_gcd {α : Type*} [Fintype α] [DecidableEq α] (σ : Equiv.Perm α) : ℕ
- Defined in
- arXiv:2610.40342 Section 6
- Verified
- 31 Oct 2026
- Axioms
- none listed
- Used by 2
- perm_cycle_gcd_mult_countThe number of permutations of
Fin nwhose cycle-length gcd (fixed points counted as 1-cycles) is a multiple ofm. Equivalently (for… - perm_cycle_gcd_countThe number of permutations $\sigma$ of
Fin nwhose greatest common divisor of cycle lengthsperm_cycle_gcd \sigmaequals $g$, where…
- perm_cycle_gcd_mult_countThe number of permutations of
Read back from the Lean
For a finite type α with decidable equality and a permutation σ : Equiv.Perm α, perm_cycle_gcd σ is defined as the greatest common divisor (Multiset.gcd) of the multiset of all cycle lengths of σ (including 1-cycles), constructed by adding Fintype.card α - σ.support.card copies of 1 (one for each fixed point of σ) to σ.cycleType (the multiset of lengths of the non-trivial cycles of σ).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The greatest common divisor of all cycle lengths of a permutation, including fixed points. -/ def perm_cycle_gcd {α : Type*} [Fintype α] [DecidableEq α] (σ : Equiv.Perm α) : ℕ := Multiset.gcd (σ.cycleType + Multiset.replicate (Fintype.card α - σ.support.card) 1)