The order of a permutation is the lcm of its cycle lengths
ProvedFamousTheorems.perm_order_lcm_cycle_type_7bThe order of a permutation is the lcm of its cycle lengths. Let be a permutation of a finite set, written as a product of disjoint cycles of lengths . Then the order of is .
This is used to compute the orders of elements of symmetric groups, for instance in card shuffling, and it leads to Landau's function , the maximal order of an element of . It holds because disjoint cycles commute and a cycle of length has order .
Formalization note. Mathlib's Equiv.Perm.lcm_cycleType. σ.cycleType is the multiset of lengths of the nontrivial cycles, and Multiset.lcm is its least common multiple, equal to for the identity.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem perm_order_lcm_cycle_type_7b {α : Type*} [Fintype α] [DecidableEq α] (σ : Equiv.Perm α) : σ.cycleType.lcm = orderOf σ := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Equiv.Perm.lcm_cycleType`. Proof here reduces to that Mathlib result.