r"""Subgroup and coset enumeration for small finite groups.
No numpy/scipy equivalent. See Dummit & Foote, *Abstract Algebra*, 3rd
ed., Sec. 2.1 (subgroups), 3.1 (cosets), and Lagrange's theorem (Sec. 3.2).
"""
from __future__ import annotations
from mathematicskit.abstract_algebra.core.base import FiniteGroup
__all__ = ["cyclic_subgroup", "all_subgroups", "left_cosets"]
[docs]
def cyclic_subgroup(group: FiniteGroup, generator) -> list:
r"""The cyclic subgroup :math:`\langle g \rangle = \{e, g, g^2, \dots\}` generated by a single element.
Its size equals :meth:`~mathematicskit.abstract_algebra.core.base.FiniteGroup.element_order`\
(`generator`) -- by Lagrange's theorem, this always divides
:math:`|G|`. See Dummit & Foote, *Abstract Algebra*, 3rd ed.,
Sec. 2.3.
Parameters
----------
group : FiniteGroup
generator
Returns
-------
list
Examples
--------
>>> from mathematicskit.abstract_algebra.systems.groups import CyclicGroup
>>> cyclic_subgroup(CyclicGroup(6), 2)
[0, 2, 4]
"""
e = group.identity()
elements = [e]
x = generator
while x != e:
elements.append(x)
x = group.operate(x, generator)
return elements
[docs]
def all_subgroups(group: FiniteGroup) -> list:
r"""Every subgroup of a small finite group.
Starts from the trivial subgroup and repeatedly extends each subgroup
already found by one more element, closing the result under the group
operation and inverses, until a full pass adds nothing new. Since every
subgroup :math:`H` has a generating set that can be built up one
element at a time (each partial product generating a proper subgroup of
:math:`H`), this fixed-point search reaches *every* subgroup -- including
those needing three or more generators, such as the elementary abelian
:math:`(\mathbb{Z}/2)^3`, which a search over single elements and pairs
alone would miss. Exponential in the worst case, so feasible only for
small groups, but exact. See Dummit & Foote, *Abstract Algebra*, 3rd
ed., Sec. 2.1.
Parameters
----------
group : FiniteGroup
Returns
-------
list of list
Every distinct subgroup, each as a list of its elements, ordered by
increasing size; includes both the trivial subgroup ``{e}`` and the
whole group.
Examples
--------
>>> from mathematicskit.abstract_algebra.systems.groups import CyclicGroup
>>> subgroups = all_subgroups(CyclicGroup(6))
>>> sorted(len(s) for s in subgroups) # divisors of 6: 1, 2, 3, 6
[1, 2, 3, 6]
>>> # (Z/2)^3 as permutations: needs three generators, so pairwise
>>> # closure alone would never reach the whole group.
>>> from mathematicskit.abstract_algebra.systems.groups import PermutationGroup
>>> klein3 = PermutationGroup(6, generators=[(1, 0, 2, 3, 4, 5), (0, 1, 3, 2, 4, 5), (0, 1, 2, 3, 5, 4)])
>>> sorted(len(s) for s in all_subgroups(klein3))
[1, 2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 8]
"""
e = group.identity()
elements = group.elements
def _closure(seed: frozenset, new_element) -> frozenset:
"""Close ``seed | {new_element}`` under the operation and inverses."""
found = set(seed)
found.add(new_element)
found.add(group.inverse(new_element))
frontier = list(found)
while frontier:
next_frontier = []
for a in frontier:
for b in list(found):
for product in (group.operate(a, b), group.operate(b, a)):
if product not in found:
found.add(product)
next_frontier.append(product)
frontier = next_frontier
return frozenset(found)
trivial = frozenset([e])
subgroups = {trivial}
frontier = [trivial]
while frontier:
next_frontier = []
for h in frontier:
for g in elements:
if g in h:
continue
extended = _closure(h, g)
if extended not in subgroups:
subgroups.add(extended)
next_frontier.append(extended)
frontier = next_frontier
return [sorted(h, key=elements.index) for h in sorted(subgroups, key=len)]
[docs]
def left_cosets(group: FiniteGroup, subgroup: list) -> list:
r"""The left cosets :math:`gH` of `subgroup` in `group`.
Partitions :attr:`group.elements
<mathematicskit.abstract_algebra.core.base.FiniteGroup.elements>` into
``|G|/|H|`` disjoint cosets (Lagrange's theorem). See Dummit &
Foote, *Abstract Algebra*, 3rd ed., Sec. 3.1-3.2.
Parameters
----------
group : FiniteGroup
subgroup : list
A subgroup of `group` (e.g. from :func:`cyclic_subgroup` or
:func:`all_subgroups`).
Returns
-------
list of list
Examples
--------
>>> from mathematicskit.abstract_algebra.systems.groups import CyclicGroup
>>> g = CyclicGroup(6)
>>> h = cyclic_subgroup(g, 3) # H = {0, 3}
>>> left_cosets(g, h)
[[0, 3], [1, 4], [2, 5]]
"""
remaining = set(group.elements)
cosets = []
for g in group.elements:
if g not in remaining:
continue
coset = [group.operate(g, h) for h in subgroup]
cosets.append(coset)
remaining -= set(coset)
return cosets
