mathematicskit.abstract_algebra#

mathematicskit.abstract_algebra hub · History · Examples · API reference

Cyclic and permutation groups with Cayley table generation; group-property checks (order, identity, inverses, abelian, cyclicity); subgroup and coset enumeration for small groups; finite field arithmetic (GF(p) and GF(p^n) via irreducible polynomials over GF(p)); and polynomial ring arithmetic (addition, multiplication, division with remainder, gcd) over \(\mathbb{Z}\), \(\mathbb{Q}\), and finite fields. Every algorithm is hand-rolled – finite group/ring/field theory has no numpy/scipy equivalent.

mathematicskit.abstract_algebra: group, ring, and field theory made computational.

Every algorithm here is hand-rolled from its textbook definition – finite group/ring/field theory has no numpy/scipy equivalent. Cyclic, permutation, dihedral, and quaternion group implementations with Cayley table generation; group-property checks (order, identity, inverses, abelian, cyclicity); subgroup and coset enumeration for small groups; structure theory (normal subgroups and quotients, derived series and solvability, Sylow subgroups, composition series); group actions and Burnside orbit counting; homomorphisms and their kernels and images; Reed-Solomon codes over GF(p); finite field arithmetic (GF(p) and GF(p^n) via irreducible polynomials over GF(p)); and polynomial ring arithmetic (addition, multiplication, division with remainder, gcd) over \(\mathbb{Z}\), \(\mathbb{Q}\), and finite fields.

class mathematicskit.abstract_algebra.CompositionSeriesResult(series, factor_orders)[source]#

Bases: object

Container for a composition series \(G = G_0 > G_1 > \dots > G_m = \{e\}\).

Parameters:
factor_orders: list#

The orders \(|G_i / G_{i+1}|\) of the composition factors.

Type:

list of int

series: list#

The subgroups \(G_0, \dots, G_m\), largest first.

Type:

list of list

class mathematicskit.abstract_algebra.CyclicGroup(n)[source]#

Bases: FiniteGroup

The cyclic group \(\mathbb{Z}_n = \{0, 1, \dots, n-1\}\) under addition mod n.

Generated by a single element (e.g. 1); every finite cyclic group of order n is isomorphic to this one. See Dummit & Foote, Abstract Algebra, 3rd ed., Sec. 1.3, 2.3.

Parameters:

n (int) – Group order, n >= 1.

Examples

>>> g = CyclicGroup(5)
>>> g.operate(3, 4)
2
>>> g.inverse(3)
2
>>> g.is_abelian()
True
property elements: list#

Every group element, in a fixed (implementation-defined) order.

Type:

list

identity()[source]#

The group’s identity element.

Return type:

int

inverse(a)[source]#

The inverse of a.

Return type:

int

Parameters:

a (int)

operate(a, b)[source]#

The group operation, \(a \cdot b\).

Return type:

int

Parameters:
class mathematicskit.abstract_algebra.DihedralGroup(n)[source]#

Bases: PermutationGroup

The dihedral group \(D_n\) of symmetries of a regular n-gon, of order \(2n\).

Realized as permutations of the polygon’s vertices 0, ..., n-1, generated by the rotation \(r: i \mapsto i+1 \pmod n\) and the reflection \(s: i \mapsto -i \pmod n\). Felix Klein’s 1872 Erlangen program made groups like this – the transformations that preserve a figure – the organizing principle of geometry. See Dummit & Foote, Abstract Algebra, 3rd ed., Sec. 1.2.

Parameters:

n (int) – Number of polygon vertices, n >= 3.

Examples

>>> d4 = DihedralGroup(4)  # symmetries of a square
>>> d4.order
8
>>> d4.is_abelian()
False
property reflection: tuple#

The generating reflection through vertex 0.

Type:

tuple

property rotation: tuple#

The generating rotation by one vertex.

Type:

tuple

class mathematicskit.abstract_algebra.FiniteGroup[source]#

Bases: ABC

Common interface for a finite group \((G, \cdot)\).

Concrete subclasses (CyclicGroup, PermutationGroup) provide the element set and the group operation; this base class derives the Cayley table, abelian check, and element orders purely from those. See Dummit & Foote, Abstract Algebra, 3rd ed., Ch. 1.

Examples

>>> from mathematicskit.abstract_algebra.systems.groups import CyclicGroup
>>> g = CyclicGroup(4)
>>> g.order
4
>>> g.is_abelian()
True
cayley_table()[source]#

The Cayley (multiplication) table, as element indices.

Row i, column j holds the index (into elements) of elements[i] . elements[j]. See Dummit & Foote, Abstract Algebra, 3rd ed., Sec. 1.7.

Return type:

ndarray

Returns:

ndarray, shape (n, n), int

element_order(a)[source]#

The order of element a: the smallest \(k>0\) with \(a^k = e\).

Parameters:

a

Return type:

int

Returns:

int

abstract property elements: list#

Every group element, in a fixed (implementation-defined) order.

Type:

list

abstractmethod identity()[source]#

The group’s identity element.

abstractmethod inverse(a)[source]#

The inverse of a.

is_abelian()[source]#

Whether the group operation is commutative for every pair of elements.

Return type:

bool

Returns:

bool

abstractmethod operate(a, b)[source]#

The group operation, \(a \cdot b\).

property order: int#

\(|G|\), the number of elements.

Type:

int

class mathematicskit.abstract_algebra.GF(p, n=1, irreducible=None)[source]#

Bases: object

The finite field \(\mathrm{GF}(p^n)\).

n=1 (the default) is the prime field \(\mathrm{GF}(p) = \mathbb{Z}/p\mathbb{Z}\), with elements plain integers 0, ..., p-1. n>1 represents elements as polynomials of degree < n over \(\mathrm{GF}(p)\), with multiplication reduced modulo a fixed irreducible polynomial (found via find_irreducible_polynomial() if not supplied) – \(\mathrm{GF}(p)[x]/(f(x))\) is a field exactly when f is irreducible. See Dummit & Foote, Abstract Algebra, 3rd ed., Sec. 13.5.

Parameters:

  • p (int) – Prime.

  • n (int) – Extension degree, n >= 1.

  • irreducible (Polynomial | None) – A degree-n irreducible polynomial over \(\mathrm{GF}(p)\); found automatically if omitted.

Examples

>>> field = GF(2, 3)  # GF(8)
>>> field.order
8
>>> a = Polynomial([1, 1, 0], modulus=2)  # 1 + x
>>> b = Polynomial([0, 1, 1], modulus=2)  # x + x^2
>>> field.multiply(a, b).degree <= 2  # result stays reduced mod the irreducible polynomial
True
add(a, b)[source]#

Field addition.

elements()[source]#

Every field element.

Return type:

list

Returns:

list of int (if n == 1) or list of Polynomial (if n > 1)

inverse(a)[source]#

Multiplicative inverse of a nonzero element.

n == 1: via Fermat’s little theorem, \(a^{-1} \equiv a^{p-2} \pmod p\). n > 1: via the polynomial extended Euclidean algorithm (finding \(u, v\) with \(ua + v \cdot \text{irreducible} = \gcd = 1\)).

multiply(a, b)[source]#

Field multiplication, reduced modulo the extension’s irreducible polynomial when n > 1.

property order: int#

\(|\mathrm{GF}(p^n)| = p^n\).

Type:

int

class mathematicskit.abstract_algebra.GroupPropertiesResult(order, is_abelian, identity, element_orders=<factory>)[source]#

Bases: object

Container for a finite group’s summary properties.

Parameters:
element_orders: dict#

{element: order} for every element.

Type:

dict

identity: object#
is_abelian: bool#
order: int#
class mathematicskit.abstract_algebra.HomomorphismResult(kernel, image, is_homomorphism)[source]#

Bases: object

Container for a group homomorphism’s kernel and image.

Parameters:
image: list#
is_homomorphism: bool#
kernel: list#
class mathematicskit.abstract_algebra.PermutationGroup(degree, generators=None)[source]#

Bases: FiniteGroup

The group generated by a set of permutations, under composition.

Elements are tuples p with p[i] = the image of i under the permutation; the full element set is found by closing the generators under composition (a breadth-first search from the identity). generators=None builds the full symmetric group \(S_n\) (generated by an adjacent transposition and the full n-cycle). See Dummit & Foote, Abstract Algebra, 3rd ed., Sec. 1.3, 1.6.

Parameters:

  • degree (int) – The permutations act on {0, ..., degree - 1}.

  • generators (list of tuple, optional) – Generating permutations; defaults to generators of the full symmetric group \(S_{\text{degree}}\).

Examples

>>> # S_3, the symmetric group on 3 elements: order 6, non-abelian.
>>> g = PermutationGroup(3)
>>> g.order
6
>>> g.is_abelian()
False
>>> # A cyclic subgroup: generated by the 3-cycle (0 1 2).
>>> g3 = PermutationGroup(3, generators=[(1, 2, 0)])
>>> g3.order
3
property elements: list#

Every group element, in a fixed (implementation-defined) order.

Type:

list

identity()[source]#

The group’s identity element.

Return type:

tuple

inverse(a)[source]#

The inverse of a.

Return type:

tuple

Parameters:

a (tuple)

operate(a, b)[source]#

The group operation, \(a \cdot b\).

Return type:

tuple

Parameters:
class mathematicskit.abstract_algebra.Polynomial(coeffs, modulus=None)[source]#

Bases: object

A polynomial with coefficients over \(\mathbb{Q}\) (modulus=None, stored as exact fractions.Fraction) or \(\mathrm{GF}(p)\) (modulus=p, coefficients reduced mod p).

Coefficients are stored lowest-degree first: coeffs[k] is the coefficient of \(x^k\). Integer (Z) and rational (Q) coefficients are both represented exactly as Fraction (Z is simply the sub-case where every coefficient happens to have denominator 1); this is what makes polynomial division with remainder always well-defined (needs the divisor’s leading coefficient to be invertible, which holds automatically in a field but not in \(\mathbb{Z}\) itself). See Dummit & Foote, Abstract Algebra, 3rd ed., Ch. 9.

Parameters:

  • coeffs (sequence) – Coefficients, lowest degree first.

  • modulus (int | None) – A prime p, for coefficients in \(\mathrm{GF}(p)\); None (the default) for \(\mathbb{Q}\) coefficients.

Examples

>>> p = Polynomial([1, 2, 1])  # 1 + 2x + x^2 = (1+x)^2
>>> q = Polynomial([1, 1])  # 1 + x
>>> quotient, remainder = divmod(p, q)
>>> quotient.coeffs, remainder.coeffs
([Fraction(1, 1), Fraction(1, 1)], [Fraction(0, 1)])
property degree: int#

The polynomial’s degree (-1 for the zero polynomial, by convention).

Type:

int

evaluate(x)[source]#

Evaluate the polynomial at x, via Horner’s method.

Parameters:

x

Returns:

The same type as the polynomial’s coefficients.

class mathematicskit.abstract_algebra.QuaternionGroup[source]#

Bases: FiniteGroup

The quaternion group \(Q_8 = \{\pm1, \pm i, \pm j, \pm k\}\) under quaternion multiplication.

Elements are the strings "1", "-1", "i", "-i", "j", "-j", "k", "-k", multiplied by William Rowan Hamilton’s 1843 rules \(i^2 = j^2 = k^2 = ijk = -1\). It is the smallest non-abelian group in which every subgroup is normal. See Dummit & Foote, Abstract Algebra, 3rd ed., Sec. 1.5.

Examples

>>> q = QuaternionGroup()
>>> q.operate("i", "j"), q.operate("j", "i")
('k', '-k')
>>> q.operate(q.operate("i", "j"), "k")  # ijk = -1
'-1'
>>> q.element_order("i")
4
property elements: list#

Every group element, in a fixed (implementation-defined) order.

Type:

list

identity()[source]#

The group’s identity element.

Return type:

str

inverse(a)[source]#

The inverse of a.

Return type:

str

Parameters:

a (str)

operate(a, b)[source]#

The group operation, \(a \cdot b\).

Return type:

str

Parameters:
class mathematicskit.abstract_algebra.QuotientGroup(group, normal_subgroup)[source]#

Bases: FiniteGroup

The quotient group \(G/N\) of a group by a normal subgroup.

Elements are the cosets \(gN\), stored as frozenset objects, multiplied by representatives: \((aN)(bN) = (ab)N\). This is well defined exactly because \(N\) is normal. Otto Hölder’s 1889 paper made the construction explicit. See Dummit & Foote, Abstract Algebra, 3rd ed., Sec. 3.1.

Parameters:

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
coset_of(g)[source]#

The coset \(gN\) containing the element g of the parent group.

Return type:

frozenset

property elements: list#

Every group element, in a fixed (implementation-defined) order.

Type:

list

identity()[source]#

The group’s identity element.

Return type:

frozenset

inverse(a)[source]#

The inverse of a.

Return type:

frozenset

Parameters:

a (frozenset)

operate(a, b)[source]#

The group operation, \(a \cdot b\).

Return type:

frozenset

Parameters:
class mathematicskit.abstract_algebra.Subgroup(parent, elements)[source]#

Bases: FiniteGroup

A subgroup \(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 FiniteGroup routine (subgroups, cosets, Cayley tables) applies to \(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)
property elements: list#

Every group element, in a fixed (implementation-defined) order.

Type:

list

identity()[source]#

The group’s identity element.

inverse(a)[source]#

The inverse of a.

operate(a, b)[source]#

The group operation, \(a \cdot b\).

class mathematicskit.abstract_algebra.SylowResult(p, sylow_order, subgroups)[source]#

Bases: object

Container for the Sylow \(p\)-subgroups of a finite group.

Parameters:
property count: int#

\(n_p\), the number of Sylow \(p\)-subgroups.

Type:

int

p: int#
subgroups: list#

Every Sylow \(p\)-subgroup, each as a list of elements.

Type:

list of list

sylow_order: int#

\(p^k\), the largest power of p dividing \(|G|\).

Type:

int

mathematicskit.abstract_algebra.all_subgroups(group)[source]#

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 \(H\) has a generating set that can be built up one element at a time (each partial product generating a proper subgroup of \(H\)), this fixed-point search reaches every subgroup – including those needing three or more generators, such as the elementary abelian \((\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)

Return type:

list

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]
mathematicskit.abstract_algebra.analyze_homomorphism(source, target, phi)[source]#

Kernel, image, and homomorphism check together.

The first isomorphism theorem, stated in its modern abstract form by Emmy Noether in 1927, gives \(G/\ker\varphi \cong \varphi(G)\), so \(|G| = |\ker\varphi| \cdot |\varphi(G)|\).

Parameters:
Return type:

HomomorphismResult

Returns:

HomomorphismResult

Examples

>>> from mathematicskit.abstract_algebra.systems.groups import CyclicGroup
>>> result = analyze_homomorphism(CyclicGroup(12), CyclicGroup(4), lambda a: a % 4)
>>> len(result.kernel) * len(result.image)  # = |Z_12|
12
mathematicskit.abstract_algebra.commutator_subgroup(group)[source]#

The commutator (derived) subgroup \([G, G]\).

It is generated by every commutator \(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)

Return type:

list

Returns:

list

Examples

>>> from mathematicskit.abstract_algebra.systems.groups import PermutationGroup
>>> len(commutator_subgroup(PermutationGroup(3)))  # [S_3, S_3] = A_3
3
mathematicskit.abstract_algebra.composition_series(group)[source]#

A composition series \(G = G_0 > G_1 > \cdots > G_m = \{e\}\).

Each \(G_{i+1}\) is a largest proper normal subgroup of \(G_i\), so every factor \(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 \(G\). See Dummit & Foote, Abstract Algebra, 3rd ed., Sec. 3.4.

Parameters:

group (FiniteGroup)

Return type:

CompositionSeriesResult

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]
mathematicskit.abstract_algebra.count_orbits(group, points, action)[source]#

The number of orbits, by Burnside’s lemma: the average number of fixed points.

\[|X/G| = \frac{1}{|G|} \sum_{g \in G} |\mathrm{Fix}(g)|\]

The formula was known to Augustin-Louis Cauchy (1845) and Ferdinand Georg Frobenius (1887); William Burnside’s 1897 book made it standard. Counting fixed points is usually far easier than listing orbits. See Dummit & Foote, Abstract Algebra, 3rd ed., Sec. 4.1.

Parameters:

  • group (FiniteGroup)

  • points (iterable)

  • action (Callable) – action(g, x) returns the image of point x under g.

Return type:

int

Returns:

int

Examples

>>> from itertools import product
>>> from mathematicskit.abstract_algebra.systems.groups import CyclicGroup
>>> necklaces = ["".join(w) for w in product("RB", repeat=4)]  # 2-colored 4-bead necklaces
>>> count_orbits(CyclicGroup(4), necklaces, lambda g, w: w[g:] + w[:g])
6
mathematicskit.abstract_algebra.cyclic_subgroup(group, generator)[source]#

The cyclic subgroup \(\langle g \rangle = \{e, g, g^2, \dots\}\) generated by a single element.

Its size equals element_order()(generator) – by Lagrange’s theorem, this always divides \(|G|\). See Dummit & Foote, Abstract Algebra, 3rd ed., Sec. 2.3.

Parameters:
Return type:

list

Returns:

list

Examples

>>> from mathematicskit.abstract_algebra.systems.groups import CyclicGroup
>>> cyclic_subgroup(CyclicGroup(6), 2)
[0, 2, 4]
mathematicskit.abstract_algebra.derived_series(group)[source]#

The derived series \(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 \(G\) is solvable. See Dummit & Foote, Abstract Algebra, 3rd ed., Sec. 6.1.

Parameters:

group (FiniteGroup)

Return type:

list

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]
mathematicskit.abstract_algebra.elements_of_order(group, k)[source]#

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 \(|G|\). James McKay’s 1959 proof shows more: the number of elements of prime order p is congruent to \(-1 \pmod p\). See Dummit & Foote, Abstract Algebra, 3rd ed., Sec. 3.2 (Cauchy’s theorem).

Parameters:
Return type:

list

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)
mathematicskit.abstract_algebra.find_irreducible_polynomial(p, n)[source]#

Find a monic irreducible polynomial of degree n over \(\mathrm{GF}(p)\), by brute-force search.

An irreducible polynomial of every degree exists over every finite field (Dummit & Foote, Abstract Algebra, 3rd ed., Corollary 13.24 – via counting arguments), so this search always terminates. See Lidl & Niederreiter, Introduction to Finite Fields, Sec. 3.1-3.3.

Parameters:

  • p (int) – Prime.

  • n (int) – Degree, n >= 1.

Return type:

Polynomial

Returns:

Polynomial

Examples

>>> poly = find_irreducible_polynomial(2, 3)
>>> poly.degree
3
>>> is_irreducible(poly)
True
mathematicskit.abstract_algebra.generated_subgroup(group, generators)[source]#

The subgroup \(\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 \(g^{-1} = g^{\operatorname{ord}(g)-1}\). See Dummit & Foote, Abstract Algebra, 3rd ed., Sec. 2.4.

Parameters:
Return type:

list

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]
mathematicskit.abstract_algebra.group_properties(group)[source]#

Summarize a finite group’s order, abelian-ness, and every element’s order.

Parameters:

group (FiniteGroup)

Return type:

GroupPropertiesResult

Returns:

GroupPropertiesResult

Examples

>>> result = group_properties(CyclicGroup(4))
>>> result.order
4
>>> result.is_abelian
True
>>> result.element_orders
{0: 1, 1: 4, 2: 2, 3: 4}
mathematicskit.abstract_algebra.homomorphism_image(source, target, phi)[source]#

The image \(\varphi(G) \le H\), in the target group’s element order.

Parameters:
Return type:

list

Returns:

list

Examples

>>> from mathematicskit.abstract_algebra.systems.groups import CyclicGroup
>>> homomorphism_image(CyclicGroup(6), CyclicGroup(6), lambda a: (2 * a) % 6)
[0, 2, 4]
mathematicskit.abstract_algebra.homomorphism_kernel(source, target, phi)[source]#

The kernel \(\ker\varphi = \{g \in G : \varphi(g) = e_H\}\), always a normal subgroup.

Parameters:
Return type:

list

Returns:

list

Examples

>>> from mathematicskit.abstract_algebra.systems.groups import CyclicGroup
>>> homomorphism_kernel(CyclicGroup(12), CyclicGroup(4), lambda a: a % 4)
[0, 4, 8]
mathematicskit.abstract_algebra.is_cyclic(group)[source]#

Whether group is cyclic: some element generates the entire group.

Checked by testing whether any single element has order \(|G|\) (via element_order()). See Dummit & Foote, Abstract Algebra, 3rd ed., Sec. 2.3.

Parameters:

group (FiniteGroup)

Return type:

bool

Returns:

bool

Examples

>>> from mathematicskit.abstract_algebra.systems.groups import CyclicGroup, PermutationGroup
>>> is_cyclic(CyclicGroup(6))
True
>>> is_cyclic(PermutationGroup(3))  # S_3 is not cyclic (it's non-abelian)
False
mathematicskit.abstract_algebra.is_homomorphism(source, target, phi)[source]#

Whether \(\varphi(ab) = \varphi(a)\varphi(b)\) for every pair \(a, b \in G\).

Parameters:
Return type:

bool

Returns:

bool

Examples

>>> from mathematicskit.abstract_algebra.systems.groups import CyclicGroup
>>> is_homomorphism(CyclicGroup(12), CyclicGroup(4), lambda a: a % 4)
True
>>> is_homomorphism(CyclicGroup(12), CyclicGroup(5), lambda a: a % 5)
False
mathematicskit.abstract_algebra.is_irreducible(poly)[source]#

Whether poly is irreducible over \(\mathrm{GF}(p)\): has no polynomial factor of degree \(1 \leq d \leq \deg(\text{poly})/2\).

Checked by trial division against every monic polynomial of degree 1 through deg(poly) // 2 (degree-1 divisors are equivalent to checking for a root in \(\mathrm{GF}(p)\)). Feasible for the small p, small degree cases this domain’s examples use. See Lidl & Niederreiter, Introduction to Finite Fields, Sec. 3.1.

Parameters:

poly (Polynomial) – With modulus set (coefficients in \(\mathrm{GF}(p)\)).

Return type:

bool

Returns:

bool

Examples

>>> is_irreducible(Polynomial([1, 1, 1], modulus=2))  # x^2+x+1 over GF(2)
True
>>> is_irreducible(Polynomial([0, 1, 1], modulus=2))  # x^2+x = x(x+1): reducible
False
>>> is_irreducible(Polynomial([1], modulus=2))  # the constant 1 is a unit, not irreducible
False
>>> is_irreducible(Polynomial([0], modulus=2))  # nor is the zero polynomial
False
mathematicskit.abstract_algebra.is_normal_subgroup(group, subgroup)[source]#

Whether \(H \trianglelefteq G\): \(gHg^{-1} = H\) for every \(g \in G\).

Normal subgroups, introduced by Évariste Galois, are exactly the subgroups whose cosets form a group (see quotient_group()). See Dummit & Foote, Abstract Algebra, 3rd ed., Sec. 3.1.

Parameters:
Return type:

bool

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
mathematicskit.abstract_algebra.is_solvable(group)[source]#

Whether group is solvable: its derived series ends at \(\{e\}\).

Galois’s criterion says a polynomial is solvable by radicals exactly when its Galois group is solvable. The symmetric group \(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)

Return type:

bool

Returns:

bool

Examples

>>> from mathematicskit.abstract_algebra.systems.groups import PermutationGroup
>>> is_solvable(PermutationGroup(4)), is_solvable(PermutationGroup(5))
(True, False)
mathematicskit.abstract_algebra.left_cosets(group, subgroup)[source]#

The left cosets \(gH\) of subgroup in group.

Partitions group.elements into |G|/|H| disjoint cosets (Lagrange’s theorem). See Dummit & Foote, Abstract Algebra, 3rd ed., Sec. 3.1-3.2.

Parameters:
Return type:

list

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]]
mathematicskit.abstract_algebra.orbits(group, points, action)[source]#

The orbits of group acting on points, found by direct search.

Parameters:

  • group (FiniteGroup)

  • points (iterable) – A finite set closed under the action.

  • action (Callable) – action(g, x) returns the image of point x under group element g.

Return type:

list

Returns:

list of list – Each orbit as a list of points.

Examples

>>> from mathematicskit.abstract_algebra.systems.groups import CyclicGroup
>>> rotate = lambda g, word: word[g:] + word[:g]  # Z_3 rotating 3-letter words
>>> len(orbits(CyclicGroup(3), ["aab", "aba", "baa", "aaa"], rotate))
2
mathematicskit.abstract_algebra.poly_add(p, q)[source]#

Polynomial addition.

Parameters:
Return type:

Polynomial

Returns:

Polynomial

Examples

>>> poly_add(Polynomial([1, 2]), Polynomial([3, 4, 5])).coeffs
[Fraction(4, 1), Fraction(6, 1), Fraction(5, 1)]
mathematicskit.abstract_algebra.poly_divmod(p, q)[source]#

Polynomial division with remainder: p = quotient * q + remainder, deg(remainder) < deg(q).

Standard polynomial long division, requiring q’s leading coefficient to be invertible (automatic over \(\mathbb{Q}\) or \(\mathrm{GF}(p)\), both fields). See Dummit & Foote, Abstract Algebra, 3rd ed., Sec. 9.2, “Division Algorithm”.

Parameters:
Returns:

(Polynomial, Polynomial) – (quotient, remainder).

Examples

>>> quotient, remainder = poly_divmod(Polynomial([-1, 0, 1]), Polynomial([-1, 1]))  # (x^2-1)/(x-1)
>>> quotient.coeffs, remainder.coeffs  # x + 1, remainder 0
([Fraction(1, 1), Fraction(1, 1)], [Fraction(0, 1)])
mathematicskit.abstract_algebra.poly_gcd(p, q)[source]#

Greatest common divisor of two polynomials, via the Euclidean algorithm.

\(\gcd(p, q) = \gcd(q, p \bmod q)\), terminating when the remainder is the zero polynomial – exactly the integer Euclidean algorithm with polynomial division in place of integer division. See Dummit & Foote, Abstract Algebra, 3rd ed., Sec. 9.2.

Parameters:

  • p (Polynomial) – Must share the same coefficient field (modulus).

  • q (Polynomial) – Must share the same coefficient field (modulus).

Return type:

Polynomial

Returns:

Polynomial

Examples

>>> # gcd(x^2 - 1, x - 1) = x - 1 (up to a scalar).
>>> g = poly_gcd(Polynomial([-1, 0, 1]), Polynomial([-1, 1]))
>>> g.degree
1
mathematicskit.abstract_algebra.poly_mul(p, q)[source]#

Polynomial multiplication: convolution of coefficients.

Parameters:
Return type:

Polynomial

Returns:

Polynomial

Examples

>>> poly_mul(Polynomial([1, 1]), Polynomial([1, -1])).coeffs  # (1+x)(1-x) = 1 - x^2
[Fraction(1, 1), Fraction(0, 1), Fraction(-1, 1)]
mathematicskit.abstract_algebra.poly_sub(p, q)[source]#

Polynomial subtraction.

Parameters:
Return type:

Polynomial

Returns:

Polynomial

mathematicskit.abstract_algebra.quotient_group(group, normal_subgroup)[source]#

Build the quotient group \(G/N\); see QuotientGroup.

Parameters:
Return type:

QuotientGroup

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
mathematicskit.abstract_algebra.rs_decode_erasures(received, k, p)[source]#

Recover a \(k\)-symbol message from a codeword with erased symbols.

Lagrange-interpolates the unique polynomial of degree below \(k\) through any \(k\) surviving positions, working exactly in \(\mathrm{GF}(p)\).

Parameters:

  • received (sequence) – The codeword, with None at each erased position.

  • k (int) – Message length.

  • p (int) – The prime field size used to encode.

Return type:

list

Returns:

list of int – The message symbols (polynomial coefficients, lowest degree first).

Examples

>>> codeword = rs_encode([2, 5, 1], n=6, p=11)
>>> damaged = [None, codeword[1], None, codeword[3], codeword[4], None]
>>> rs_decode_erasures(damaged, k=3, p=11)
[2, 5, 1]
mathematicskit.abstract_algebra.rs_encode(message, n, p)[source]#

Encode message as the values \(m(0), m(1), \dots, m(n-1)\) of its polynomial over \(\mathrm{GF}(p)\).

Parameters:

  • message (sequence of int) – The \(k\) message symbols, each in range(p); message[i] is the coefficient of \(x^i\).

  • n (int) – Codeword length, \(k \le n \le p\).

  • p (int) – A prime field size.

Return type:

list

Returns:

list of int

Examples

>>> rs_encode([3, 1], n=5, p=7)  # m(x) = 3 + x at x = 0..4
[3, 4, 5, 6, 0]
mathematicskit.abstract_algebra.sylow_subgroups(group, p)[source]#

Every Sylow \(p\)-subgroup of group: the subgroups of order \(p^k\), where \(p^k \,\|\, |G|\).

Ludwig Sylow’s 1872 theorems guarantee that they exist, that they are all conjugate, and that their number \(n_p\) satisfies \(n_p \equiv 1 \pmod p\) and \(n_p \mid |G|/p^k\). See Dummit & Foote, Abstract Algebra, 3rd ed., Sec. 4.5.

Parameters:
Return type:

SylowResult

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)
On this page
Show Source