AFTD Auto-Formalizing Theoretical Domains

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 n whose cycle-length gcd (fixed points counted as 1-cycles) is a multiple of m. Equivalently (for…
  • perm_cycle_gcd_countThe number of permutations $\sigma$ of Fin n whose greatest common divisor of cycle lengths perm_cycle_gcd \sigma equals $g$, where…

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)
See it in the graphDiscuss this resultChallenge it