r"""Structure theory of small finite groups: generated subgroups, element
orders, normal subgroups and quotients, the derived series and
solvability, Sylow subgroups, and composition series.
No numpy/scipy equivalent -- every routine is hand-rolled from its
textbook definition and is exact but exponential in the worst case, so
feasible only for small groups. See Dummit & Foote, *Abstract Algebra*,
3rd ed., Sec. 2.4 (generated subgroups), 3.1-3.4 (normal subgroups,
quotients, composition series), 4.5 (Sylow), and 6.1 (solvable groups).
"""
from __future__ import annotations
from mathematicskit.abstract_algebra.core.base import CompositionSeriesResult, FiniteGroup, SylowResult
from mathematicskit.abstract_algebra.systems.subgroups import all_subgroups
__all__ = [
"Subgroup",
"generated_subgroup",
"elements_of_order",
"is_normal_subgroup",
"QuotientGroup",
"quotient_group",
"commutator_subgroup",
"derived_series",
"is_solvable",
"sylow_subgroups",
"composition_series",
]
[docs]
class Subgroup(FiniteGroup):
r"""A subgroup :math:`H \le G`, viewed as a finite group in its own right.
Uses the parent group's operation, restricted to the given elements,
so every :class:`~mathematicskit.abstract_algebra.core.base.FiniteGroup`
routine (subgroups, cosets, Cayley tables) applies to :math:`H`
directly.
Parameters
----------
parent : FiniteGroup
elements : list
The subgroup's elements; they must be closed under ``parent``'s operation.
Examples
--------
>>> from mathematicskit.abstract_algebra.systems.groups import CyclicGroup
>>> h = Subgroup(CyclicGroup(6), [0, 2, 4])
>>> h.order, h.operate(4, 4)
(3, 2)
"""
def __init__(self, parent: FiniteGroup, elements: list):
self.parent = parent
self._elements = list(elements)
@property
def elements(self) -> list:
return self._elements
[docs]
def identity(self):
return self.parent.identity()
[docs]
def operate(self, a, b):
return self.parent.operate(a, b)
[docs]
def inverse(self, a):
return self.parent.inverse(a)
[docs]
def generated_subgroup(group: FiniteGroup, generators) -> list:
r"""The subgroup :math:`\langle S \rangle` generated by a set of elements.
Closes ``generators`` under the group operation (a breadth-first
search from the identity). In a finite group this also closes the
set under inverses, since :math:`g^{-1} = g^{\operatorname{ord}(g)-1}`.
See Dummit & Foote, *Abstract Algebra*, 3rd ed., Sec. 2.4.
Parameters
----------
group : FiniteGroup
generators : iterable
Returns
-------
list
The subgroup's elements, in the parent group's element order.
Examples
--------
>>> from mathematicskit.abstract_algebra.systems.groups import CyclicGroup
>>> generated_subgroup(CyclicGroup(12), [8, 6]) # gcd(8, 6, 12) = 2
[0, 2, 4, 6, 8, 10]
"""
generators = list(generators)
found = {group.identity()}
frontier = [group.identity()]
while frontier:
next_frontier = []
for a in frontier:
for g in generators:
product = group.operate(a, g)
if product not in found:
found.add(product)
next_frontier.append(product)
frontier = next_frontier
order = {e: i for i, e in enumerate(group.elements)}
return sorted(found, key=order.__getitem__)
[docs]
def elements_of_order(group: FiniteGroup, k: int) -> list:
r"""Every element of `group` whose order is exactly ``k``.
Cauchy's 1845 theorem guarantees that this list is non-empty
whenever ``k`` is a prime dividing :math:`|G|`. James McKay's 1959
proof shows more: the number of elements of prime order ``p`` is
congruent to :math:`-1 \pmod p`. See Dummit & Foote, *Abstract
Algebra*, 3rd ed., Sec. 3.2 (Cauchy's theorem).
Parameters
----------
group : FiniteGroup
k : int
Returns
-------
list
Examples
--------
>>> from mathematicskit.abstract_algebra.systems.groups import PermutationGroup
>>> s3 = PermutationGroup(3)
>>> len(elements_of_order(s3, 2)), len(elements_of_order(s3, 3)) # 3 transpositions, 2 three-cycles
(3, 2)
"""
return [a for a in group.elements if group.element_order(a) == k]
[docs]
def is_normal_subgroup(group: FiniteGroup, subgroup: list) -> bool:
r"""Whether :math:`H \trianglelefteq G`: :math:`gHg^{-1} = H` for every :math:`g \in G`.
Normal subgroups, introduced by Évariste Galois, are exactly the
subgroups whose cosets form a group (see :func:`quotient_group`).
See Dummit & Foote, *Abstract Algebra*, 3rd ed., Sec. 3.1.
Parameters
----------
group : FiniteGroup
subgroup : list
Returns
-------
bool
Examples
--------
>>> from mathematicskit.abstract_algebra.systems.groups import PermutationGroup
>>> s3 = PermutationGroup(3)
>>> is_normal_subgroup(s3, [(0, 1, 2), (1, 2, 0), (2, 0, 1)]) # A_3
True
>>> is_normal_subgroup(s3, [(0, 1, 2), (1, 0, 2)]) # a transposition subgroup
False
"""
h = set(subgroup)
return all(group.operate(group.operate(g, x), group.inverse(g)) in h for g in group.elements for x in subgroup)
[docs]
class QuotientGroup(FiniteGroup):
r"""The quotient group :math:`G/N` of a group by a normal subgroup.
Elements are the cosets :math:`gN`, stored as ``frozenset`` objects,
multiplied by representatives: :math:`(aN)(bN) = (ab)N`. This is
well defined exactly because :math:`N` is normal. Otto Hölder's 1889
paper made the construction explicit. See Dummit & Foote, *Abstract
Algebra*, 3rd ed., Sec. 3.1.
Parameters
----------
group : FiniteGroup
normal_subgroup : list
Examples
--------
>>> from mathematicskit.abstract_algebra.systems.groups import CyclicGroup
>>> q = QuotientGroup(CyclicGroup(12), [0, 4, 8]) # Z_12 / <4> has order 4
>>> q.order
4
"""
def __init__(self, group: FiniteGroup, normal_subgroup: list):
if not is_normal_subgroup(group, normal_subgroup):
raise ValueError("the quotient G/N requires N to be a normal subgroup of G")
self.group = group
self.normal_subgroup = list(normal_subgroup)
self._coset_of = {}
self._elements = []
for g in group.elements:
if g in self._coset_of:
continue
coset = frozenset(group.operate(g, n) for n in self.normal_subgroup)
self._elements.append(coset)
for x in coset:
self._coset_of[x] = coset
@property
def elements(self) -> list:
return self._elements
[docs]
def coset_of(self, g) -> frozenset:
"""The coset :math:`gN` containing the element ``g`` of the parent group."""
return self._coset_of[g]
[docs]
def identity(self) -> frozenset:
return self._coset_of[self.group.identity()]
def _representative(self, coset: frozenset):
return next(iter(coset))
[docs]
def operate(self, a: frozenset, b: frozenset) -> frozenset:
return self._coset_of[self.group.operate(self._representative(a), self._representative(b))]
[docs]
def inverse(self, a: frozenset) -> frozenset:
return self._coset_of[self.group.inverse(self._representative(a))]
[docs]
def quotient_group(group: FiniteGroup, normal_subgroup: list) -> QuotientGroup:
r"""Build the quotient group :math:`G/N`; see :class:`QuotientGroup`.
Parameters
----------
group : FiniteGroup
normal_subgroup : list
Returns
-------
QuotientGroup
Examples
--------
>>> from mathematicskit.abstract_algebra.systems.groups import PermutationGroup
>>> s3 = PermutationGroup(3)
>>> quotient_group(s3, [(0, 1, 2), (1, 2, 0), (2, 0, 1)]).order # S_3 / A_3 has order 2
2
"""
return QuotientGroup(group, normal_subgroup)
[docs]
def commutator_subgroup(group: FiniteGroup) -> list:
r"""The commutator (derived) subgroup :math:`[G, G]`.
It is generated by every commutator :math:`aba^{-1}b^{-1}`, and is
the smallest normal subgroup with an abelian quotient. See Dummit &
Foote, *Abstract Algebra*, 3rd ed., Sec. 5.4.
Parameters
----------
group : FiniteGroup
Returns
-------
list
Examples
--------
>>> from mathematicskit.abstract_algebra.systems.groups import PermutationGroup
>>> len(commutator_subgroup(PermutationGroup(3))) # [S_3, S_3] = A_3
3
"""
op, inv = group.operate, group.inverse
commutators = {op(op(a, b), op(inv(a), inv(b))) for a in group.elements for b in group.elements}
return generated_subgroup(group, commutators)
[docs]
def derived_series(group: FiniteGroup) -> list:
r"""The derived series :math:`G \ge G' \ge G'' \ge \cdots`, until it stabilizes.
Each term is the commutator subgroup of the previous one. The series
reaches the trivial group exactly when :math:`G` is solvable. See
Dummit & Foote, *Abstract Algebra*, 3rd ed., Sec. 6.1.
Parameters
----------
group : FiniteGroup
Returns
-------
list of list
The distinct terms, starting with the whole group.
Examples
--------
>>> from mathematicskit.abstract_algebra.systems.groups import PermutationGroup
>>> [len(h) for h in derived_series(PermutationGroup(4))] # S_4 > A_4 > V_4 > 1
[24, 12, 4, 1]
"""
series = [list(group.elements)]
while True:
current = Subgroup(group, series[-1])
derived = commutator_subgroup(current)
if len(derived) == len(series[-1]):
return series
series.append(derived)
[docs]
def is_solvable(group: FiniteGroup) -> bool:
r"""Whether `group` is solvable: its derived series ends at :math:`\{e\}`.
Galois's criterion says a polynomial is solvable by radicals exactly
when its Galois group is solvable. The symmetric group :math:`S_5`
is not solvable, which is the group-theoretic reason the general
quintic has no formula in radicals (the Abel-Ruffini theorem). See
Dummit & Foote, *Abstract Algebra*, 3rd ed., Sec. 14.7.
Parameters
----------
group : FiniteGroup
Returns
-------
bool
Examples
--------
>>> from mathematicskit.abstract_algebra.systems.groups import PermutationGroup
>>> is_solvable(PermutationGroup(4)), is_solvable(PermutationGroup(5))
(True, False)
"""
return len(derived_series(group)[-1]) == 1
def _prime_power_part(n: int, p: int) -> int:
part = 1
while n % p == 0:
n //= p
part *= p
return part
[docs]
def sylow_subgroups(group: FiniteGroup, p: int) -> SylowResult:
r"""Every Sylow :math:`p`-subgroup of `group`: the subgroups of order :math:`p^k`, where :math:`p^k \,\|\, |G|`.
Ludwig Sylow's 1872 theorems guarantee that they exist, that they
are all conjugate, and that their number :math:`n_p` satisfies
:math:`n_p \equiv 1 \pmod p` and :math:`n_p \mid |G|/p^k`. See
Dummit & Foote, *Abstract Algebra*, 3rd ed., Sec. 4.5.
Parameters
----------
group : FiniteGroup
p : int
A prime.
Returns
-------
SylowResult
Examples
--------
>>> from mathematicskit.abstract_algebra.systems.groups import PermutationGroup
>>> result = sylow_subgroups(PermutationGroup(4), 3)
>>> result.sylow_order, result.count # n_3 = 4 = 1 (mod 3), and 4 divides 24/3 = 8
(3, 4)
"""
target = _prime_power_part(group.order, p)
subgroups = [h for h in all_subgroups(group) if len(h) == target]
return SylowResult(p=p, sylow_order=target, subgroups=subgroups)
[docs]
def composition_series(group: FiniteGroup) -> CompositionSeriesResult:
r"""A composition series :math:`G = G_0 > G_1 > \cdots > G_m = \{e\}`.
Each :math:`G_{i+1}` is a largest proper normal subgroup of
:math:`G_i`, so every factor :math:`G_i/G_{i+1}` is simple. Camille
Jordan (1869) and Otto Hölder (1889) proved that the factors are the
same, up to order and isomorphism, for every composition series of
:math:`G`. See Dummit & Foote, *Abstract Algebra*, 3rd ed., Sec. 3.4.
Parameters
----------
group : FiniteGroup
Returns
-------
CompositionSeriesResult
Examples
--------
>>> from mathematicskit.abstract_algebra.systems.groups import PermutationGroup
>>> composition_series(PermutationGroup(4)).factor_orders # S_4 > A_4 > V_4 > Z_2 > 1
[2, 3, 2, 2]
"""
series = [list(group.elements)]
while len(series[-1]) > 1:
current = Subgroup(group, series[-1])
candidates = [h for h in all_subgroups(current) if len(h) < current.order and is_normal_subgroup(current, h)]
series.append(max(candidates, key=len))
factor_orders = [len(series[i]) // len(series[i + 1]) for i in range(len(series) - 1)]
return CompositionSeriesResult(series=series, factor_orders=factor_orders)
