Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Free-action orbit count

Definition
OddOrder_GroupTheory_FreeActionOrbitCount

by burkh4rt · Nov 12, 2026 · Mathlib 0df444a (Lean v4.33.1)

feit-thompsonfinite-groupsgroup-theoryishida-odd-order

A purely combinatorial fact used for Peterfalvi (9.1), the kernel fixed-point-free count (†) in step 3d.3a. A finite group Γ\GammaΓ of order d>1d>1d>1 acting on a finite nonempty type of size nnn with exactly 1+(n−1)/d1+(n-1)/d1+(n−1)/d orbits (and d∣n−1d\mid n-1d∣n−1) has every orbit of size 111 or ddd, and at most one fixed point.

The main result is orbit_trivial_or_free_of_card_orbits, with companion statements on orbit sizes dividing the group order (orbit–stabiliser), fixed points having singleton orbits, and divisibility from a free-off-unique-fixed action. The bundle consists of lemmas only.

The bundle also proves 4 supporting lemmas used by later statements.

Definition code
/-
Copyright (c) 2026 Yawara Ishida. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yawara Ishida
-/
-- From github.com/yawara/odd-order @ 20a6fccbb63c (Apache-2.0; LICENSE at that commit):
--   OddOrder/GroupTheory/FreeActionOrbitCount.lean
-- Generated for Prove2Me by deleting declarations; the remaining commands are verbatim except:
-- `private` dropped where another file uses the declaration, and a solution's main theorem
-- renamed `_root_.solution` (platform convention).
import Mathlib.GroupTheory.GroupAction.Quotient
import Mathlib.GroupTheory.GroupAction.Basic
import Mathlib.GroupTheory.Index
import Mathlib.SetTheory.Cardinal.Finite
import Mathlib.Data.Set.Card
import Mathlib.Algebra.Order.BigOperators.Group.Finset
import Mathlib.Algebra.BigOperators.Ring.Finset

open MulAction

namespace OddOrder.GroupTheory.FreeActionOrbitCount

variable {Γ S : Type*} [Group Γ] [Finite Γ] [Finite S] [MulAction Γ S]

omit [Finite Γ] [Finite S] in
/-- Each orbit's cardinality divides the group order (orbit–stabiliser). -/
theorem card_orbit_dvd_card_group (x : S) : Nat.card (orbit Γ x) ∣ Nat.card Γ := by
  rw [Nat.card_congr (orbitEquivQuotientStabilizer Γ x)]
  exact (stabilizer Γ x).index_dvd_card

/-- A proper divisor `s` of `d` satisfies `2 * s ≤ d` (its cofactor is `≥ 2`). -/
theorem two_mul_le_of_dvd_of_lt {s d : ℕ} (hdvd : s ∣ d) (_hpos : 0 < s) (hlt : s < d) :
    2 * s ≤ d := by
  obtain ⟨k, rfl⟩ := hdvd
  have hk : 2 ≤ k := by
    by_contra hk
    have : k = 0 ∨ k = 1 := by omega
    rcases this with rfl | rfl
    · simp at hlt
    · simp at hlt
  calc 2 * s ≤ k * s := by gcongr
    _ = s * k := mul_comm k s

omit [Finite Γ] [Finite S] in
/-- A fixed point has a singleton orbit. -/
theorem orbit_eq_singleton_of_mem_fixedPoints {x : S} (hx : x ∈ fixedPoints Γ S) :
    orbit Γ x = {x} := by
  ext w
  simp only [Set.mem_singleton_iff, mem_orbit_iff]
  constructor
  · rintro ⟨g, rfl⟩; exact (mem_fixedPoints.mp hx) g
  · rintro rfl; exact ⟨1, one_smul _ _⟩

omit [Finite Γ] in
set_option backward.isDefEq.respectTransparency false in
/-- **Free-action orbit count.**  If a finite group `Γ` of order `d > 1` acts on a finite nonempty
type `S` of size `n`, with exactly `1 + (n − 1) / d` orbits and `d ∣ n − 1`, then every orbit has
size `1` or `d`, and there is at most one fixed point.  (For Peterfalvi (9.1): the count carried
over from the free-on-nontrivial-classes side forces freeness on the nontrivial simples.) -/
theorem orbit_trivial_or_free_of_card_orbits [Nonempty S]
    (hd : 1 < Nat.card Γ)
    (horb : Nat.card (orbitRel.Quotient Γ S) = 1 + (Nat.card S - 1) / Nat.card Γ)
    (hdvd : Nat.card Γ ∣ Nat.card S - 1) :
    (∀ x : S, Nat.card (orbit Γ x) = 1 ∨ Nat.card (orbit Γ x) = Nat.card Γ) ∧
      (∀ x y : S, x ∈ fixedPoints Γ S → y ∈ fixedPoints Γ S → x = y) := by
  classical
  set d := Nat.card Γ with hd_def
  have : Fintype (orbitRel.Quotient Γ S) := Fintype.ofFinite _
  have hn_pos : 1 ≤ Nat.card S := Nat.card_pos
  -- per-orbit cardinality facts.
  have hs_dvd : ∀ ω : orbitRel.Quotient Γ S, Nat.card ω.orbit ∣ d := by
    intro ω
    obtain ⟨a, rfl⟩ := Quotient.mk''_surjective ω
    rw [orbitRel.Quotient.orbit_mk]
    exact card_orbit_dvd_card_group a
  have hs_pos : ∀ ω : orbitRel.Quotient Γ S, 0 < Nat.card ω.orbit := by
    intro ω
    obtain ⟨a, rfl⟩ := Quotient.mk''_surjective ω
    rw [orbitRel.Quotient.orbit_mk]
    have : Nonempty (orbit Γ a) := ⟨⟨a, mem_orbit_self a⟩⟩
    have : Finite (orbit Γ a) := Set.finite_coe_iff.mpr (Set.toFinite _)
    exact Nat.card_pos
  have hs_le : ∀ ω : orbitRel.Quotient Γ S, Nat.card ω.orbit ≤ d :=
    fun ω => Nat.le_of_dvd (by omega) (hs_dvd ω)
  -- the partition sum and the count hypothesis give the defect sum `∑ (d - sω) = d - 1`.
  have hsum : ∑ ω : orbitRel.Quotient Γ S, Nat.card ω.orbit = Nat.card S := by
    have : ∀ ω : orbitRel.Quotient Γ S, Finite ω.orbit :=
      fun ω => Set.finite_coe_iff.mpr (Set.toFinite _)
    rw [← Nat.card_sigma]
    exact Nat.card_congr (selfEquivSigmaOrbits' Γ S).symm
  have hdm : d * Nat.card (orbitRel.Quotient Γ S) = Nat.card S + (d - 1) := by
    have hc : d * ((Nat.card S - 1) / d) = Nat.card S - 1 := Nat.mul_div_cancel' hdvd
    rw [horb, mul_add, mul_one, hc]; omega
  have hdefect : ∑ ω : orbitRel.Quotient Γ S, (d - Nat.card ω.orbit) = d - 1 := by
    have h1 : ∑ ω : orbitRel.Quotient Γ S, ((d - Nat.card ω.orbit) + Nat.card ω.orbit)
        = ∑ _ω : orbitRel.Quotient Γ S, d :=
      Finset.sum_congr rfl fun ω _ => Nat.sub_add_cancel (hs_le ω)
    rw [Finset.sum_add_distrib, hsum, Finset.sum_const, Finset.card_univ, smul_eq_mul,
      ← Nat.card_eq_fintype_card, mul_comm, hdm] at h1
    omega
  -- the "proper" orbits (size `< d`).
  set P : Finset (orbitRel.Quotient Γ S) := Finset.univ.filter (fun ω => Nat.card ω.orbit < d)
    with hP_def
  have hmem_P : ∀ ω, ω ∈ P ↔ Nat.card ω.orbit < d := by intro ω; rw [hP_def]; simp
  -- defects vanish off `P`; the defect sum restricts to `P`.
  have hdefect_P : ∑ ω ∈ P, (d - Nat.card ω.orbit) = d - 1 := by
    rw [← hdefect]
    apply Finset.sum_subset (Finset.subset_univ P)
    intro ω _ hω
    have hnlt : ¬ Nat.card ω.orbit < d := by rwa [hmem_P] at hω
    have : Nat.card ω.orbit = d := le_antisymm (hs_le ω) (by omega)
    omega
  -- each proper orbit contributes a defect with `2 * defect ≥ d`.
  have hbig : ∀ ω ∈ P, d ≤ 2 * (d - Nat.card ω.orbit) := by
    intro ω hω
    have hlt : Nat.card ω.orbit < d := (hmem_P ω).mp hω
    have := two_mul_le_of_dvd_of_lt (hs_dvd ω) (hs_pos ω) hlt
    omega
  -- `#P * d ≤ 2 * (d - 1) < 2 * d`, forcing `#P ≤ 1`.
  have hPcard : P.card ≤ 1 := by
    by_contra h
    have h2 : 2 ≤ P.card := by omega
    have hsum_big : P.card * d ≤ 2 * (d - 1) := by
      calc P.card * d = ∑ _ω ∈ P, d := by rw [Finset.sum_const, smul_eq_mul]
        _ ≤ ∑ ω ∈ P, 2 * (d - Nat.card ω.orbit) := Finset.sum_le_sum hbig
        _ = 2 * ∑ ω ∈ P, (d - Nat.card ω.orbit) := by rw [Finset.mul_sum]
        _ = 2 * (d - 1) := by rw [hdefect_P]
    have hge : 2 * d ≤ P.card * d := Nat.mul_le_mul_right d h2
    omega
  -- `#P ≥ 1`: the defect sum `d - 1 ≥ 1` is nonzero, so some orbit is proper.
  have hP_pos : 1 ≤ P.card := by
    rcases Nat.eq_zero_or_pos P.card with h0 | h
    · rw [Finset.card_eq_zero] at h0
      rw [h0, Finset.sum_empty] at hdefect_P
      omega
    · exact h
  have hPcard1 : P.card = 1 := le_antisymm hPcard hP_pos
  obtain ⟨ω₀, hω₀⟩ := Finset.card_eq_one.mp hPcard1
  -- the unique proper orbit `ω₀` has size `1`.
  have hω₀_one : Nat.card ω₀.orbit = 1 := by
    rw [hω₀, Finset.sum_singleton] at hdefect_P
    have := hs_pos ω₀; have := hs_le ω₀; omega
  -- a proper orbit must be `ω₀`.
  have hproper : ∀ ω : orbitRel.Quotient Γ S, Nat.card ω.orbit < d → ω = ω₀ := by
    intro ω hlt
    have : ω ∈ P := (hmem_P ω).mpr hlt
    rw [hω₀] at this
    exact Finset.mem_singleton.mp this
  -- bridge: the orbit of `x` is the quotient-orbit of `⟦x⟧`.
  have horbeq : ∀ x : S, Nat.card (orbit Γ x)
      = Nat.card (orbitRel.Quotient.orbit (Quotient.mk'' x : orbitRel.Quotient Γ S)) :=
    fun x => by rw [orbitRel.Quotient.orbit_mk]
  -- (A): every orbit has size `1` or `d`.
  have hA : ∀ x : S, Nat.card (orbit Γ x) = 1 ∨ Nat.card (orbit Γ x) = d := by
    intro x
    rcases lt_or_ge (Nat.card (orbit Γ x)) d with hlt | hge
    · have hmkω₀ : (Quotient.mk'' x : orbitRel.Quotient Γ S) = ω₀ := hproper _ (horbeq x ▸ hlt)
      left; rw [horbeq x, hmkω₀]; exact hω₀_one
    · exact Or.inr (le_antisymm (by rw [horbeq x]; exact hs_le _) hge)
  refine ⟨hA, ?_⟩
  -- (B): at most one fixed point (two fixed points lie in the unique size-`1` orbit `ω₀`).
  intro x y hx hy
  have hfix1 : ∀ z : S, z ∈ fixedPoints Γ S → (Quotient.mk'' z : orbitRel.Quotient Γ S) = ω₀ := by
    intro z hz
    apply hproper
    rw [← horbeq z, orbit_eq_singleton_of_mem_fixedPoints hz, Nat.card_coe_set_eq,
      Set.ncard_singleton]
    omega
  have hxy : (Quotient.mk'' x : orbitRel.Quotient Γ S) = Quotient.mk'' y := by
    rw [hfix1 x hx, hfix1 y hy]
  have hmem : x ∈ orbit Γ y := Quotient.eq''.mp hxy
  rw [orbit_eq_singleton_of_mem_fixedPoints hy] at hmem
  exact Set.mem_singleton_iff.mp hmem

/-- **Forward orbit count** (converse of `orbit_trivial_or_free_of_card_orbits`).  If a finite group
`Γ` acts on a finite type `S` with a *unique* fixed point `x₀` and acts *freely* off it (every
non-fixed orbit has size `|Γ|`), then the number of orbits is `1 + (|S| − 1) / |Γ|`.  (For
Peterfalvi (9.1): the class side — `⟨E⟩` free on the nontrivial classes, trivial class fixed — has
this orbit count, which the Brauer equality then carries to the simples.) -/
theorem card_orbits_eq_of_free_off_unique_fixed
    (x₀ : S) (hx₀ : x₀ ∈ fixedPoints Γ S)
    (huniq : ∀ x : S, x ∈ fixedPoints Γ S → x = x₀)
    (hfree : ∀ x : S, x ∉ fixedPoints Γ S → Nat.card (orbit Γ x) = Nat.card Γ) :
    Nat.card (orbitRel.Quotient Γ S) = 1 + (Nat.card S - 1) / Nat.card Γ := by
  classical
  set d := Nat.card Γ with hd_def
  have : Fintype (orbitRel.Quotient Γ S) := Fintype.ofFinite _
  have : Nonempty (orbitRel.Quotient Γ S) := ⟨Quotient.mk'' x₀⟩
  have hd_pos : 0 < d := Nat.card_pos
  -- the fixed orbit `⟦x₀⟧` has size `1`; every other orbit has size `d`.
  have h1 : Nat.card (orbitRel.Quotient.orbit (Quotient.mk'' x₀ : orbitRel.Quotient Γ S)) = 1 := by
    rw [orbitRel.Quotient.orbit_mk, orbit_eq_singleton_of_mem_fixedPoints hx₀, Nat.card_coe_set_eq,
      Set.ncard_singleton]
  have hd_orbit : ∀ ω : orbitRel.Quotient Γ S, ω ≠ Quotient.mk'' x₀ → Nat.card ω.orbit = d := by
    intro ω hne
    obtain ⟨a, rfl⟩ := Quotient.mk''_surjective ω
    rw [orbitRel.Quotient.orbit_mk]
    exact hfree a fun hmem => hne (by rw [huniq a hmem])
  -- the orbits partition `S`, and the defect sum collapses to the single fixed orbit.
  have hsum : ∑ ω : orbitRel.Quotient Γ S, Nat.card ω.orbit = Nat.card S := by
    have : ∀ ω : orbitRel.Quotient Γ S, Finite ω.orbit :=
      fun ω => Set.finite_coe_iff.mpr (Set.toFinite _)
    rw [← Nat.card_sigma]
    exact Nat.card_congr (selfEquivSigmaOrbits' Γ S).symm
  have hsize_le : ∀ ω : orbitRel.Quotient Γ S, Nat.card ω.orbit ≤ d := by
    intro ω
    obtain ⟨a, rfl⟩ := Quotient.mk''_surjective ω
    rw [orbitRel.Quotient.orbit_mk]
    exact Nat.le_of_dvd hd_pos (card_orbit_dvd_card_group a)
  have hdefect : ∑ ω : orbitRel.Quotient Γ S, (d - Nat.card ω.orbit) = d - 1 := by
    rw [Finset.sum_eq_single (Quotient.mk'' x₀ : orbitRel.Quotient Γ S)]
    · rw [h1]
    · intro ω _ hne; rw [hd_orbit ω hne, Nat.sub_self]
    · intro h; exact absurd (Finset.mem_univ _) h
  -- `d * #orbits = n + (d - 1)`.
  have hdm : d * Nat.card (orbitRel.Quotient Γ S) = Nat.card S + (d - 1) := by
    have hcancel : ∑ ω : orbitRel.Quotient Γ S, ((d - Nat.card ω.orbit) + Nat.card ω.orbit)
        = ∑ _ω : orbitRel.Quotient Γ S, d :=
      Finset.sum_congr rfl fun ω _ => Nat.sub_add_cancel (hsize_le ω)
    rw [Finset.sum_add_distrib, hsum, hdefect, Finset.sum_const, Finset.card_univ, smul_eq_mul,
      ← Nat.card_eq_fintype_card, mul_comm] at hcancel
    omega
  -- divide out by `d`.
  obtain ⟨m', hm'⟩ : ∃ m', Nat.card (orbitRel.Quotient Γ S) = m' + 1 := by
    have := Nat.card_pos (α := orbitRel.Quotient Γ S)
    exact ⟨Nat.card (orbitRel.Quotient Γ S) - 1, by omega⟩
  rw [hm'] at hdm ⊢
  have hdm' : d * m' = Nat.card S - 1 := by
    have hexp : d * (m' + 1) = d * m' + d := Nat.mul_succ d m'
    omega
  rw [show Nat.card S - 1 = d * m' from hdm'.symm, Nat.mul_div_cancel_left _ hd_pos]
  omega

omit [Finite Γ] in
/-- **Divisibility from a free-off-unique-fixed action.**  If a finite group `Γ` acts on a finite
`S` with a unique fixed point `x₀` and acts freely off it, then `|Γ|` divides `|S| − 1`: the
non-fixed points split into free orbits, each of size `|Γ|`.  (For Peterfalvi (9.1): the
divisibility hypothesis `d ∣ |S| − 1` that `orbit_trivial_or_free_of_card_orbits` needs on simples,
obtained from the free structure on the class side and carried over by `|simples| = |classes|`.) -/
theorem dvd_card_sub_one_of_free_off_unique_fixed
    (x₀ : S) (hx₀ : x₀ ∈ fixedPoints Γ S)
    (huniq : ∀ x : S, x ∈ fixedPoints Γ S → x = x₀)
    (hfree : ∀ x : S, x ∉ fixedPoints Γ S → Nat.card (orbit Γ x) = Nat.card Γ) :
    Nat.card Γ ∣ Nat.card S - 1 := by
  classical
  have : Fintype (orbitRel.Quotient Γ S) := Fintype.ofFinite _
  set d := Nat.card Γ with hd_def
  -- orbit sizes sum to `|S|`; the fixed orbit `⟦x₀⟧` has size `1`, every other orbit size `d`.
  have hsum : ∑ ω : orbitRel.Quotient Γ S, Nat.card ω.orbit = Nat.card S := by
    have : ∀ ω : orbitRel.Quotient Γ S, Finite ω.orbit :=
      fun ω => Set.finite_coe_iff.mpr (Set.toFinite _)
    rw [← Nat.card_sigma]
    exact Nat.card_congr (selfEquivSigmaOrbits' Γ S).symm
  have h1 : Nat.card (orbitRel.Quotient.orbit (Quotient.mk'' x₀ : orbitRel.Quotient Γ S)) = 1 := by
    rw [orbitRel.Quotient.orbit_mk, orbit_eq_singleton_of_mem_fixedPoints hx₀, Nat.card_coe_set_eq,
      Set.ncard_singleton]
  have hd_orbit : ∀ ω : orbitRel.Quotient Γ S, ω ≠ Quotient.mk'' x₀ → Nat.card ω.orbit = d := by
    intro ω hne
    obtain ⟨a, rfl⟩ := Quotient.mk''_surjective ω
    rw [orbitRel.Quotient.orbit_mk]
    exact hfree a fun hmem => hne (by rw [huniq a hmem])
  -- splitting off `⟦x₀⟧`: `|S| = 1 + (#orbits − 1)·d`.
  have hsplit : Nat.card S = 1 + (Nat.card (orbitRel.Quotient Γ S) - 1) * d := by
    have hx₀mem := Finset.mem_univ (Quotient.mk'' x₀ : orbitRel.Quotient Γ S)
    rw [← hsum, ← Finset.add_sum_erase _ _ hx₀mem, h1]
    congr 1
    rw [Finset.sum_congr rfl (fun ω hω => hd_orbit ω (Finset.ne_of_mem_erase hω)),
      Finset.sum_const, smul_eq_mul, Finset.card_erase_of_mem (Finset.mem_univ _),
      Finset.card_univ, Nat.card_eq_fintype_card]
  rw [hsplit, Nat.add_sub_cancel_left]
  exact dvd_mul_left d _

end OddOrder.GroupTheory.FreeActionOrbitCount

namespace OddOrder.RepresentationTheory

/-- **A free action of a finite group divides the cardinality of the set acted on.** If a finite
group `Γ` acts on a finite type `β` *freely* — every point has trivial stabilizer — then
`|Γ| ∣ |β|`.  Equivalently (the contrapositive direction used below): if every orbit has the full
size `|Γ|`, the set decomposes as a disjoint union of `|Γ|`-element orbits.

This is the orbit-counting primitive behind Peterfalvi (6.7.1): a `p`-group `P` acting
fixed-point-freely (here `freely`) on a finite set `Ω` forces `|P| ∣ |Ω|`.  The proof is the
free-action decomposition `β ≃ (β / Γ) × Γ` (`MulAction.selfEquivOrbitsQuotientProd`), which makes
`|β| = |β / Γ| · |Γ|`. -/
theorem card_dvd_of_stabilizer_eq_bot {Γ : Type*} [Group Γ] [Finite Γ] {β : Type*} [Finite β]
    [MulAction Γ β] (h : ∀ b : β, MulAction.stabilizer Γ b = ⊥) :
    Nat.card Γ ∣ Nat.card β := by
  -- 名前付き implicit (`α := Γ`) は mathlib 側の変数名リネームで壊れるので、`h` から推論させる。
  have e := MulAction.selfEquivOrbitsQuotientProd h
  rw [Nat.card_congr e, Nat.card_prod]
  exact Dvd.intro_left _ rfl

/-- **A finite group acting with no non-trivial fixed pairs divides the cardinality.** Variant of
`card_dvd_of_stabilizer_eq_bot` whose hypothesis is the form actually checked in Peterfalvi (6.7.1):
no element `x ≠ 1` fixes any point.  (Trivial stabilizers and "no non-identity element fixes a
point" are equivalent for a group action.) -/
theorem card_dvd_of_no_nontrivial_fixed {Γ : Type*} [Group Γ] [Finite Γ] {β : Type*} [Finite β]
    [MulAction Γ β] (h : ∀ (x : Γ), x ≠ 1 → ∀ b : β, x • b ≠ b) :
    Nat.card Γ ∣ Nat.card β := by
  refine card_dvd_of_stabilizer_eq_bot fun b => ?_
  rw [eq_bot_iff]
  intro x hx
  rw [MulAction.mem_stabilizer_iff] at hx
  by_contra hx1
  exact h x (by simpa using hx1) b hx

end OddOrder.RepresentationTheory
Source
Yawara Ishida, Lean 4 formalization of the Feit–Thompson (odd order) theorem, github.com/yawara/odd-order @ 20a6fccbb63c (Apache-2.0), https://github.com/yawara/odd-order/blob/20a6fccbb63c0b138acda9f7fafd798c42f9441b/OddOrder/GroupTheory/FreeActionOrbitCount.lean

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me