Group Theory Speedrun

(Any %)

Group theory studies algebraic structures of sets and binary operations over their elements.

Note that group theory does not concern itself with what the elements of the set are, or what their binary operator does more generally, it only cares about specific relations between the elements and the operator. We will primarily use a small set of integers, as an example, but this can relate to type algebra, linear algebra, elliptic curves, and more.

Single Operator

Magma

A magma is the simplest construct, it is just a set equipped with a binary operator that can operate on elements of that set. This is represented with the following notation.

\(a, b \in S : a \star b = c \in S\)

Note that the operator is a star. While this is commonly an addition operator, group theory also abstracts the operator, so it could be any binary operator.

set_S = { 0, 1, 2, 3, 4 }

add = lambda x, y : (x + y) % 5

def is_magma(op):
    for i in set_S:
        for j in set_S:
            if op(i, j) not in set_S return False
    return True

is_magma(add)

# True

We use a set of numbers, zero to four, and an addition operator where the value wraps around on overflow.

Semigroup

A semigroup is a magma, in that it is a set equipped with a binary operator, but the operator is also associative.

\(\forall a, b, c \in S : (a \star b) \star c = a \star (b \star c)\)

def is_semigroup(op):
    for a in set_S:
        for b in set_S:
            for c in set_S:
                if op(op(a, b), c) != op(a, op(b, c)):
                    return False
    return True

is_semigroup(add)

# True

Monoid

A monoid is a semigroup that contains an element called the "unit" or "identity" element. The unit element is an element such that applying the binary operator to it and any other element returns the other element.

\(\forall a \in S, \exists e \in S : a \star e = e \star a = a\)

add_unit = 0

def is_monoid(op):
    for a in set_S:
        if op(a, add_unit) != a:
            return False
    return True

is_monoid(add)

# True

For addition of integers, the unit element is zero.

Group

A group is a monoid where all elements have a unique inverse such that the operator applied to any element and its inverse returns the unit element.

\(\forall a \in S, \exists a^{-1} : a \star a^{-1} = a^{-1} \star a = e\)

For addition of integers, the unit element of a positive integer is its corresponding negative integer and vice versa.

def has_inverse(op, a):
    for i in set_S:
        if add(a, i) == unit:
            return True
    return False

def is_group(op):
    for a in set_S:
        if not has_inverse(op, a):
            return False
    return True

is_group(add)

# True

Abelian Group

An Abelian group is a group where the operator is commutative.

\(\forall a, b \in S : a \star b = b \star a\)

Multiple Operators

Ring

A ring is a set with two binary operations. This is generally referred to as addition and multiplication, though the names can also be abstracted. Conceptually the "multiplication" operator can be considered the iterative application of an element to itself with the "addition" operator.

The ring constraints are the addition operator must form an abelian group with the set and the multiplication operator must both form a monoid over the set and be distributive over addition.

\(\begin{gather} \forall a, b, c \in S : (a + b) + c = a + (b + c) \\ \forall a \in S, \exists e \in S : a + e = e + a = a \\ \forall a \in S, \exists a^{-1} \in S : a + a^{-1} = a^{-1} + a = e \\ \forall a, b \in S : a + b = b + a \\ \\ \forall a, b, c \in S : (a * b) * c = a * (b * c) \\ \forall a \in S, \exists e \in S : a * e = e * a = a \\ \forall a, b, c \in S : a * (b + c) = a * b + a * c \end{gather}\)

mul = lambda x, y : (x * y) % 5

def is_ring():
    is_add_abelian_group = is_semigroup(add) and is_monoid(add)
        and is_group(add) and is_abelian_group(add)

    is_mul_monoid = is_semigroup(mul) and is_monoid(add)

    return is_add_abelian_group and is_mul_monoid

is_ring()

# True

Field

A field is a ring with a multiplicative inverse, sometimes referred to as division, as well as the constraint that the addition unit element and the multiplication unit element, sometimes referred to as zero and one, are not the same element.

An example of a field is the set of real numbers with addition, multiplication, the additive inverse which is subtraction, and the multiplicative inverse which is division.

\(\begin{gather} \forall a \in S, \exists a^{-1} : a * a^{-1} = a^{-1} * a = e \\ 0, 1 \in S : 0 \neq 1 \end{gather}\)

Field Extension

A field is a field extension if it contains a subfield within it. More generally, if a function from a field F to a field G maps every element of F to G, then F is a subfield of G and G is a field extension of F.

An example of a field extension is the set of complex numbers in relation to its subfield, the set of real numbers.

\(F \subset G\)

Galois Field

A Galois field is a field with a finite number of elements. A common example of a Galois field is a set of integers modulo a prime number.

Note that the set_S in the code examples throughout this article actually form a Galois field because it is a set of integers modulo the number 5, addition is associative, has a unit element, has an inverse, and is commutative, and multiplication is associative, has a unit element, is distributive over addition, has an inverse, and zero does not equal one.

An interesting note about Galois fields is when the elements are integers, the modulus must be a prime number. This is because if the set contains two elements where, when multiplied, it produces the modulus, the result is zero. If the result of non-zero multiplication is zero, it begins to breaks axioms, meaning it would no longer be a field.

Conclusion

While this does not cover nearly all of group theory, this is meant to give an overview of important concepts for groups and abstract algebra.

Monoids are an important part of category theory, especially the infamous monad, being a "monoid in the category of endofunctors".

The notion of addition, multiplication, and their relationship are representable in type theory. Additionally, ad hoc polymorphism, aka operator overloading, creates syntax sugar over group theory concepts. It does not matter whether the elements are integers on a Galois field, vectors of a vector space, or complex numbers, if the expected axioms of addition and multiplication are met for a given type, we can override the behavior of these operators and blackbox the underlying functionality.

This also has important implications for elliptic curve cryptography. Elliptic curve pairings rely on bilinear maps which deal with cartesian products and field extensions. When writing in domain specific languages for zero knowledge proofs, it's common to perform computation with "field elements", or element of the prime Galois field.

Until next time.