Recognition of generalized quaternion groups
DefinitionOddOrder_GroupTheory_QuaternionRecognitionfeit-thompsonfinite-groupsgroup-theoryishida-odd-order
A finite group with a cyclic subgroup of index and an element that inverts with (the unique involution of ) is isomorphic to the generalized quaternion group QuaternionGroup M (quaternionIsoOfInverting). The statement was lifted from a private Chapter 6 lemma to a shared leaf because Isaacs Problem 3F.1 (Ch. 3) needs the same recognition theorem and Ch. 3 cannot import Ch. 6.
The bundle consists of the single declaration quaternionIsoOfInverting (used in the inverting case of Lemma 6.13).
The bundle also proves 1 supporting lemma 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/QuaternionRecognition.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.SpecificGroups.Quaternion
import Mathlib.GroupTheory.Index
import Mathlib.GroupTheory.OrderOfElement
import Mathlib.Tactic.Group
import Mathlib.Tactic.Linarith
import Mathlib.Tactic.Positivity
import Mathlib.Tactic.Ring
namespace OddOrder.GroupTheory
/-- **Quaternion recognition helper** (used in Lem 6.13 inverting case): given a finite group `P`
with `c, a ∈ P` such that `⟨c⟩` has index `2`, `a ∉ ⟨c⟩`, `orderOf c = 2 * M` with `M > 0`,
`a² = c ^ M` (the unique involution in `⟨c⟩`), and `a c a⁻¹ = c⁻¹`, then
`P ≃* QuaternionGroup M`. -/
noncomputable def quaternionIsoOfInverting
{P : Type*} [Group P] [Finite P]
(c a : P) (M : ℕ) (hM_pos : 0 < M) (h_order : orderOf c = 2 * M)
(h_idx : (Subgroup.zpowers c).index = 2)
(h_a_notmem : a ∉ Subgroup.zpowers c)
(h_a_sq : a ^ 2 = c ^ M) (h_conj : a * c * a⁻¹ = c⁻¹) :
P ≃* QuaternionGroup M := by
classical
haveI : Fintype P := Fintype.ofFinite P
set N := 2 * M with hN_def
haveI : NeZero M := ⟨hM_pos.ne'⟩
haveI : NeZero N := ⟨by positivity⟩
have hN_pos : 0 < N := Nat.pos_of_ne_zero (NeZero.ne N)
have h_orderOf : orderOf c = N := h_order
-- Conjugation by `a` inverts every power of `c`.
have h_conj_zpow : ∀ k : ℤ, a * c ^ k * a⁻¹ = c ^ (-k) := fun k => by
have step1 : a * c ^ k * a⁻¹ = (a * c * a⁻¹) ^ k := by
have : Function.Bijective ((MulAut.conj a : P ≃* P) : P → P) :=
(MulAut.conj a : P ≃* P).bijective
simp
rw [step1, h_conj, inv_zpow, ← zpow_neg]
-- Cardinality computation: |P| = 2 * N = 4 * M.
have hcard_P : Nat.card P = 4 * M := by
have h := (Subgroup.zpowers c).index_mul_card
rw [h_idx, Nat.card_zpowers, h_orderOf] at h
omega
-- Forward map `QuaternionGroup M → P`.
let fwd : QuaternionGroup M → P
| QuaternionGroup.a i => c ^ i.val
| QuaternionGroup.xa i => a * c ^ i.val
-- Helpers (mirror dihedral case, with `N = 2 * M`).
have hc_addval : ∀ i j : ZMod N, c ^ ((i + j).val) = c ^ i.val * c ^ j.val := by
intro i j
rw [← pow_add, pow_eq_pow_iff_modEq, Nat.ModEq, h_orderOf, ZMod.val_add, Nat.mod_mod]
have hc_subval : ∀ i j : ZMod N, c ^ ((j - i).val) = c ^ j.val * (c ^ i.val)⁻¹ := by
intro i j
have h := hc_addval (j - i) i
rw [sub_add_cancel] at h
exact eq_mul_inv_iff_mul_eq.mpr h.symm
-- Commutation: `c ^ k * a = a * c ^ (-k)` for `k : ℤ` (uses no `a²` assumption).
have h_zpow_a : ∀ k : ℤ, c ^ k * a = a * c ^ (-k) := fun k => by
have h := h_conj_zpow (-k)
rw [neg_neg] at h
rw [show (c ^ k : P) = a * c ^ (-k) * a⁻¹ from h.symm,
mul_assoc (a * c ^ (-k)), inv_mul_cancel, mul_one]
-- Cross-relation: `c^i.val * a * c^j.val = a * c^(j-i).val`.
have h_sr_r : ∀ i j : ZMod N, c ^ i.val * a * c ^ j.val = a * c ^ (j - i).val := by
intro i j
have step1 : c ^ i.val * a = a * c ^ (-(i.val : ℤ)) := by
have := h_zpow_a (i.val : ℤ); rw [zpow_natCast] at this; exact this
rw [step1, mul_assoc, ← zpow_natCast c j.val, ← zpow_add]
congr 1
rw [show (c ^ (j - i).val : P) = c ^ ((j - i).val : ℤ) from (zpow_natCast c _).symm,
zpow_eq_zpow_iff_modEq, h_orderOf]
rw [← ZMod.intCast_eq_intCast_iff]
push_cast
rw [ZMod.natCast_zmod_val, ZMod.natCast_zmod_val, ZMod.natCast_zmod_val]
ring
-- Injectivity.
have hfwd_inj : Function.Injective fwd := by
rintro (i | i) (j | j) h <;> simp only [fwd] at h
· congr 1
have hmod : i.val ≡ j.val [MOD N] := by
rw [← h_orderOf]; exact (pow_eq_pow_iff_modEq).mp h
unfold Nat.ModEq at hmod
rw [Nat.mod_eq_of_lt (ZMod.val_lt i), Nat.mod_eq_of_lt (ZMod.val_lt j)] at hmod
exact ZMod.val_injective N hmod
· exfalso; apply h_a_notmem
have : a = c ^ i.val * (c ^ j.val)⁻¹ := by rw [h]; group
rw [this]
exact Subgroup.mul_mem _
(Subgroup.pow_mem _ (Subgroup.mem_zpowers c) _)
(Subgroup.inv_mem _ (Subgroup.pow_mem _ (Subgroup.mem_zpowers c) _))
· exfalso; apply h_a_notmem
have : a = c ^ j.val * (c ^ i.val)⁻¹ := by rw [← h]; group
rw [this]
exact Subgroup.mul_mem _
(Subgroup.pow_mem _ (Subgroup.mem_zpowers c) _)
(Subgroup.inv_mem _ (Subgroup.pow_mem _ (Subgroup.mem_zpowers c) _))
· congr 1
have heq : c ^ i.val = c ^ j.val := mul_left_cancel h
have hmod : i.val ≡ j.val [MOD N] := by
rw [← h_orderOf]; exact (pow_eq_pow_iff_modEq).mp heq
unfold Nat.ModEq at hmod
rw [Nat.mod_eq_of_lt (ZMod.val_lt i), Nat.mod_eq_of_lt (ZMod.val_lt j)] at hmod
exact ZMod.val_injective N hmod
-- Bijectivity from cardinality + injectivity.
have hbij : Function.Bijective fwd := by
rw [Fintype.bijective_iff_injective_and_card]
refine ⟨hfwd_inj, ?_⟩
rw [QuaternionGroup.card, ← Nat.card_eq_fintype_card, hcard_P]
-- map_mul (4 cases: a/a, a/xa, xa/a, xa/xa). Note xa/xa uses `a² = c^M`.
have hfwd_mul : ∀ x y : QuaternionGroup M, fwd (x * y) = fwd x * fwd y := by
rintro (i | i) (j | j) <;> simp only [fwd]
· -- a i * a j = a (i+j)
change c ^ (i + j).val = c ^ i.val * c ^ j.val
exact hc_addval i j
· -- a i * xa j = xa (j - i)
change a * c ^ (j - i).val = c ^ i.val * (a * c ^ j.val)
rw [← mul_assoc]; exact (h_sr_r i j).symm
· -- xa i * a j = xa (i + j)
change a * c ^ (i + j).val = a * c ^ i.val * c ^ j.val
rw [mul_assoc, ← hc_addval]
· -- xa i * xa j = a (↑M + j - i). Uses a² = c^M.
change c ^ ((↑M + j - i : ZMod N)).val = a * c ^ i.val * (a * c ^ j.val)
-- Compute RHS: a * c^i.val * a * c^j.val = a² * c^(j-i).val = c^M * c^(j-i).val
-- = c^(M + j - i).val
rw [mul_assoc, ← mul_assoc (c ^ i.val), h_sr_r, ← mul_assoc, ← sq, h_a_sq]
-- Goal: c ^ (↑M + j - i).val = c ^ M * c ^ (j - i).val
have : c ^ M * c ^ (j - i).val = c ^ ((↑M + (j - i) : ZMod N)).val := by
rw [hc_addval]
congr 1
-- Need: c^M = c^((↑M : ZMod N).val). i.e., `(M : ZMod N).val = M` since M < N.
rw [show ((↑M : ZMod N).val : ℕ) = M from by
rw [ZMod.val_natCast]
exact Nat.mod_eq_of_lt (by rw [hN_def]; omega)]
rw [this]
congr 1
ring_nf
let setEquiv : QuaternionGroup M ≃ P := Equiv.ofBijective fwd hbij
exact (MulEquiv.mk' setEquiv hfwd_mul).symm
lemma eq_pow_half_orderOf_of_mem_zpowers_sq_eq_one
{P : Type*} [Group P] [Finite P] (c y : P)
(hy_mem : y ∈ Subgroup.zpowers c) (hy_sq : y ^ 2 = 1) (hy_ne : y ≠ 1) :
y = c ^ (orderOf c / 2) ∧ orderOf c = 2 * (orderOf c / 2) ∧ 0 < orderOf c / 2 := by
classical
have hc_fin : IsOfFinOrder c := isOfFinOrder_of_finite c
have hN_pos : 0 < orderOf c := hc_fin.orderOf_pos
have hy_range : y ∈ (Finset.range (orderOf c)).image (fun n : ℕ => c ^ n) :=
(mem_zpowers_iff_mem_range_orderOf (x := c) (y := y)).mp hy_mem
rcases Finset.mem_image.mp hy_range with ⟨m, hm_range, hm_eq⟩
have hm_lt : m < orderOf c := Finset.mem_range.mp hm_range
have hpow2 : c ^ (2 * m) = 1 := by
have := hy_sq
rw [← hm_eq, pow_two, ← pow_add] at this
simpa [two_mul] using this
have h_dvd : orderOf c ∣ 2 * m := orderOf_dvd_of_pow_eq_one hpow2
have h_not_dvd : ¬ orderOf c ∣ m := by
intro hdm
apply hy_ne
rw [← hm_eq]
exact orderOf_dvd_iff_pow_eq_one.mp hdm
have hm_pos : 0 < m := by
by_contra hm_nonpos
have hm0 : m = 0 := Nat.eq_zero_of_not_pos hm_nonpos
exact h_not_dvd (by rw [hm0]; exact dvd_zero _)
rcases h_dvd with ⟨q, hq⟩
have hq_pos : 0 < q := by
by_contra hq_nonpos
have hq0 : q = 0 := Nat.eq_zero_of_not_pos hq_nonpos
nlinarith
have hq_lt_two : q < 2 := by
have hlt : orderOf c * q < orderOf c * 2 := by nlinarith
exact (Nat.mul_lt_mul_left hN_pos).mp hlt
have hq_eq : q = 1 := by omega
have htwo_m : 2 * m = orderOf c := by
rw [hq_eq, mul_one] at hq
exact hq
have hm_half : m = orderOf c / 2 := by omega
refine ⟨?_, ?_, ?_⟩
· rw [← hm_half]
exact hm_eq.symm
· omega
· omega
end OddOrder.GroupTheory
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/QuaternionRecognition.lean