Group theory

Multiplication tables and Latin squares

Posted on by John

The multiplication table of a finite group forms a Latin square.

You form the multiplication table of a finite group just as you would the multiplication tables from your childhood: list the elements along the top and side of a grid and fill in each square with the products. In the context of group theory the multiplication table is called a Cayley table.

There are two differences between Cayley tables and the multiplication tables of elementary school. First, Cayley tables are complete because you can include all the elements of the group in the table. Elementary school multiplication tables are the upper left corner of an infinite Cayley table for the positive integers.

(The positive integers do not form a group under multiplication because only 1 has a multiplicative inverse. The positive integers form a magma, not a group, but we can still talk of the Cayley table of a magma.)

The other difference is that the elements of a finite group typically do not have a natural order, unlike integers. It’s conventional to start with the group identity, but other than that the order of the elements along the top and sides could be arbitrary. Two people may create different Cayley tables for the same group by listing the elements in a different order.

A Cayley table is necessarily a Latin square. That is, each element appears exactly once in each row and column. Here’s a quick proof. The row corresponding to the element a consists of a multiplied by each of the elements of the group. If two elements were the same, i.e. ab = ac for some b and c, then b = c because you can multiply on the left by the inverse of a. Each row is a permutation of the group elements. The analogous argument holds for columns, multiplying on the right.

Not all Latin squares correspond to the Cayley table of a group. Also, the Cayley table of an algebraic structure without inverses may not form a Latin square. The Cayley table for the positive integers, for example, is not a Latin square.

Here’s an example, the Cayley table for Q8, the group of unit quaternions. The elements are ±1, ±i, ±j, and ±k and the multiplication is the usual multiplication for quaternions:

i² = j² = k² = ijk = −1.

as William Rowan Hamilton famously carved into the stone of Brougham Bridge. I colored the cells of the table to make it easier to scan to verify that table is a Latin square.

Latin square posts

Quaternion posts

Up to isomorphism

Posted on by John

The previous post showed that there are 10 Abelian groups that have 2025 elements. Implicitly that means there are 10 Abelian groups up to isomorphism, i.e. groups that are not in some sense “the same” even if they look different.

Sometimes it is clear what we mean by “the same” and there’s no need to explicitly say “up to isomorphism” and doing so would be pedantic. Other times it helps to be more explicit.

In some context you want to distinguish isomorphic as different objects. This is fine, but it means that you have some notion of “different” that is more strict than “not isomorphic.” For example, the x-axis and the y-axis are different subsets of the plane, but they’re isomorphic as 1-dimensional vector spaces.

Abelian groups

There is a theorem that says ℤmn, the group of integers mod mn, is isomorphic to the direct sum ℤm ⊕ ℤn if and only if m and n are relatively prime. This means, for example, that ℤ15 and ℤ3 ⊕ ℤ5 are isomorphic, but ℤ9 and ℤ3 ⊕ ℤ3 are not.

Because of this theorem it’s possible to come up with a list of Abelian groups of order 2025 that looks different from the list in the previous post but it actually the same, where “same” means isomorphic.

In the previous post we listed direct sums of groups where each group was a cyclic group of some prime power order:

  • ℤ81 ⊕ ℤ25
  • ℤ81 ⊕ ℤ5 ⊕ ℤ5
  • ℤ27 ⊕ ℤ3 ⊕ ℤ25
  • ℤ27 ⊕ ℤ3 ⊕ ℤ5 ⊕ ℤ5
  • ℤ9 ⊕ ℤ9 ⊕ ℤ25
  • ℤ9 ⊕ ℤ9 ⊕ ℤ5 ⊕ ℤ5
  • ℤ9 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ25
  • ℤ9 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ5 ⊕ ℤ5
  • ℤ3 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ25
  • ℤ3 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ5 ⊕ ℤ5

We could rewrite this list as follows by combining group factors of relatively prime orders:

  • ℤ2025
  • ℤ5 ⊕ ℤ405
  • ℤ3 ⊕ ℤ675
  • ℤ15 ⊕ ℤ135
  • ℤ9 ⊕ ℤ225
  • ℤ45 ⊕ ℤ45
  • ℤ3 ⊕ ℤ3 ⊕ ℤ295
  • ℤ3 ⊕ ℤ15 ⊕ ℤ45
  • ℤ3 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ75
  • ℤ3 ⊕ ℤ3 ⊕ ℤ15 ⊕ ℤ15

This listing follows a different convention, namely that the order of each group is a factor of the order of the next.

Related posts

Abelian groups of order 2025

Posted on by John

Every finite Abelian group can be written as the direct sum of cyclic groups of prime power order.

To find the number of Abelian groups of order 2025 we have to find the number of ways to partition the factors of 2025 into prime powers.

Now 2025 = 34 × 52.

We can partition 34 into prime powers 5 ways:

  • 34
  • 33 × 3
  • 32 × 32
  • 32 × 3 × 3
  • 3 × 3 × 3 × 3

And we can partition 52 two ways:

  • 52
  • 5 × 5

A couple of notes here. First, we only consider positive powers. Second, two partitions are considered the same if they consist of the same factors in a different order. For example, 3 × 3 × 32 and 32 × 3 × 3 are considered to be the same partition.

It follows that we can partition 2025 into prime powers 10 ways: we choose one of the five ways to partition 34 and one of the two ways to partition 52. Here are all the Abelian groups of order 2025:

  • ℤ81 ⊕ ℤ25
  • ℤ81 ⊕ ℤ5 ⊕ ℤ5
  • ℤ27 ⊕ ℤ3 ⊕ ℤ25
  • ℤ27 ⊕ ℤ3 ⊕ ℤ5 ⊕ ℤ5
  • ℤ9 ⊕ ℤ9 ⊕ ℤ25
  • ℤ9 ⊕ ℤ9 ⊕ ℤ5 ⊕ ℤ5
  • ℤ9 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ25
  • ℤ9 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ5 ⊕ ℤ5
  • ℤ3 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ25
  • ℤ3 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ3 ⊕ ℤ5 ⊕ ℤ5

Given a prime number q, there are as many ways to partition qk as the product of positive prime powers as there are ways to partition k into the sum of positive integers, denoted p(k). What we have shown above is that the number of Abelian groups of order 34 52 equals p(4) p(2).

In general, to find the number of Abelian groups of order n, factor n into prime powers, then multiply the partition numbers of the exponents in the factorization.

Related posts

Normal subgroups are subtle

Posted on by John

The definition of a subgroup is obvious, but the definition of a normal subgroup is subtle.

Widgets and subwidgets

The general pattern of widgets and subwidgets is that a widget is a set with some kind of structure, and a subwidget is a subset that has the same structure. This applies to vector spaces and subspaces, manifolds and submanifolds, lattices and sublattices, etc. Once you know the definition of a group, you can guess the definition of a subgroup.

But the definition of a normal subgroup is not something anyone would guess immediately after learning the definition of a group. The definition is not difficult, but its motivation isn’t obvious.

Standard definition

A subgroup H of a group G is a normal subgroup if for every g ∈ G,

g−1Hg = H.

That is, if h is an element of H, g−1hg is also an element of H. All subgroups of an Abelian group are normal because not only is g−1hg also an element of H, it’s the same element of H, i.e. g−1hg = h.

Alternative definition

There’s an equivalent definition of normal subgroup that I only ran across recently in a paper by Francis Masat [1]. A subgroup H of a group G is normal if for every pair of elements a and b such that ab is in H, ba is also in H. With this definition it’s obvious that every subgroup of an Abelian group is normal because ab = ba for any a and b.

It’s an easy exercise to show that Masat’s definition is equivalent to the usual definition. Masat’s definition seems a little more motivated. It’s requiring some vestige of commutativity. It says that a subgroup H of a non-Abelian group G has some structure in common with subgroups of normal groups if this weak replacement for commutativity holds.

Categories

Category theory has a way of defining subobjects in general that basically formalizes the notion of widgets and subwidgets above. It also has a way of formalizing normal subobjects, but this is more recent and more complicated.

The nLab page on normal subobjects says “The notion was found relatively late.” The page was last edited in 2016 and says it is “to be finished later.” Given how exhaustively thorough nLab is on common and even not-so-common topics, this implies that the idea of normal subobjects is not mainstream.

I found a recent paper that discusses normal subobjects [2] and suffice it to say it’s complicated. This suggests that although analogs of subgroups are common across mathematics, the idea of a normal subgroup is more or less unique to group theory.

Related posts

[1] Francis E. Masat. A Useful Characterization of a Normal Subgroup. Mathematics Magazine, May, 1979, Vol. 52, No. 3, pp. 171–173

[2] Dominique Bourn and Giuseppe Metere. A note on the categorical notions of normal subobject and of equivalence class. Theory and Applications of Categories, Vol 36, No. 3, 2021, pp. 65–101.

Groups of order 2024

Posted on by John

This time last year I wrote about groups of order 2023 and now I’d like to do the same for 2024.

There are three Abelian groups of order 2024, and they’re not hard to find.

We can factor

2024 = 8 × 11 × 23

and so the Abelian groups of order 2024 are of the form

G ⊕ ℤ11 ⊕ ℤ23

where G is a group of order 8, and there are three possibilities for G:

  • ℤ8,
  • ℤ4 ⊕ ℤ2, and
  • ℤ2 ⊕ ℤ2 ⊕ ℤ2.

How many non-Abelian groups of order 2024 are there? Conway’s estimate would be a total of 52 groups, Abelian and non-Abelian, but that turns out to be a bit high.

There is a formula for the number of groups of order n, but it only applies to square-free numbers. The number 2024 is divisible by 4, so it’s not square-free.

There are 46 groups of order 2024, so 43 of these are non-Abelian. When n is divisible by a square, finding the number of groups of order n is hard, but the results have been tabulated for small n. I’ve seen a table going up to 2048 and no doubt there are tables that go further.

Number of groups of squarefree order

Posted on by John

This post is a sort of footnote to the previous post, Estimating the number of groups of a given order.

The following is taken from an answer to a question on Stack Exchange.

In general there is no formula f(n) for the number of groups of order up to isomorphism. However, if n is squarefree (no prime to the power 2 divides n), then Otto Hölder in 1893 proved the following amazing formula

f(n) = \sum_{m \mid n} \prod_p \frac{p^{c(p)} - 1}{p-1}

where p is a prime divisor of n/m and c(p) is the number of prime divisors q of m that satisfy q = 1 (mod p).

In a sense that can be made precise, about 60% of integers are square free [1]. So Hölder’s formula is often useful, but there are a lot of values it can’t compute.

In this post I develop Python code to implement Hölder’s formula. I’ve tested the code below by comparing it to a table of f(n) for n = 1, 2, 3, …, 100.

from sympy import mobius, divisors, factorint

def squarefree(n):
    return n > 1 and mobius(n) != 0

def prime_divisors(n):
    return list(factorint(n).keys())

def c(p, m):
    return len( [q for q in prime_divisors(m) if q % p == 1] )

def holder(n):
    if not squarefree(n):
        print("Sorry. I can't help you.")
        return None

    s = 0
    for m in divisors(n):
        prod = 1
        for p in prime_divisors(n // m):
            prod *= (p**c(p, m) - 1) // (p - 1)
        s += prod
        
    return s

[1] The number of square-free integers between 1 and x is asymptotically equal to 6x/π² as x → ∞.

Estimating number of groups of a given order

Posted on by John

John Conway et al [1] give the name gnu(n) to the number of groups of order n, where “gnu” stands for group number. This function has been studied since the 19th century, but I don’t know whether there has ever been a standard notation for it. Mathematica calls it FiniteGroupCount. It’s also the first sequence in OEIS.

When n is square-free, there is a formula due to Hölder that computes gnu(n). This formula is given in the next post. But in general computing gnu(n) is hard. However, [1] gives a surprisingly good heuristic for estimating gnu(n).

Let Ω(n) be the number of prime factors of n, counted with multiplicity. So, for example, Ω(75) = 3 because 3 is a factor with multiplicity 1 and 5 is a factor with multiplicity 2.

Let B(n) be the nth Bell number, the number is the number of ways to partition a set of n labeled items.

The heuristic estimate for gnu(n) is

gnu(n) ≈ B( Ω(n) ).

This can be implemented in Python as follows.

    from sympy import bell, primeomega
    def estimate(n): return bell(primeomega(n))

The following plot shows the exact and approximate values of gnu(n) for n = 1, 2, 3, …, 100.

The exact value was plotted first in blue, then the estimate was plotted in orange. The orange line matches the blue so well as to hide it, except at the two spikes where gnu(n) is largest.

Here’s a plot of the errors.

Aside from the two outliers, the error is between −5 and 1.

[1] John H. Conway, Heiko Dietrich and E.A. O’Brien. Counting groups: gnus, moas and other exotica

Enriched categories

Posted on by John

We begin with a couple examples.

First, the set of linear transformations from one vector space to another is itself a vector space.

Second, the set of continuous linear operators from one Banach space to another is itself a Banach space. Or maybe better, this set can be made into a Banach space.

In the first example, it’s pretty obvious how to add linear transformations and how to multiply a linear transformation by a scalar.

The second is a little more involved. Banach spaces are vector spaces, but with more structure. They have a norm, and the space is complete with respect to the topology defined by that norm. So while it’s obvious that the set of continuous linear operators between two Banach spaces is a vector space, it’s not quite obvious that it is in fact a Banach space. The latter requires that we define a norm on this space of continuous operators, and that we prove that this new space is complete. That’s why I said the set “can be made into” a Banach space because some construction is required.

The fancy way to describe these examples is to say that they are both examples of a category enriched over itself. A category is “enriched” if the set of morphisms [1] between two objects can be given the structure of a category itself, a category with more structure than the category of sets. This new category need not be the same as the one you started out with, but it can be.

If the morphisms between objects in a category C have the structure of category D, then we say C is enriched over D. If C = D, then we say the category is enriched over itself. The category of vector spaces with linear transformations is enriched over itself, as is the category of Banach spaces with continuous linear operators.

This post was motivated by a recent comment that said

Another categorical difference between working with groups and working with abelian groups is that “the category of abelian groups is enriched over itself” — in plainer language, between two groups G and H there’s a *set* of homomorphisms from G to H, but if G and H are abelian then this set of homomorphisms has the structure of an *abelian group* as well!

The proof that the homomorphisms between two Abelian groups forms an Abelian group is very simple. We show that if we define the addition of homomorphisms f and g element-wise, the result is a homomorphism.

\begin{align*} (f + g)(x + y) &\equiv f(x + y) + g(x + y) \\ &= f(x) + f(y) + g(x) + g(y) \\ &= f(x) + g(x) + f(y) + g(y) \\ &\equiv (f + g)(x) + (f + g)(y) \end{align*}

The critical step is the third line where we swap the order of f(y) and g(x). That’s where we use the fact that we’re working with Abelian groups.

Denoting the group operation + implies by convention that we’re working with Abelian groups; it goes against convention to use + to denote anything that isn’t commutative. But if our group operation were not commutative, the proof above would be invalid. And not only would the proof be invalid, the theorem would be false. There’s no way to salvage the theorem with a different proof. The set of homomorphisms between two general groups may not be a group.

[1] Think of morphisms as structure-preserving functions. Linear transformations preserve the structure of vector spaces. When our objects have more structure, the morphisms are more restrictive. We wouldn’t want to just consider linear maps between Banach spaces because arbitrary linear maps don’t preserve the topology of the spaces. Instead we look at continuous linear maps. In general morphisms don’t have to be functions, they just have to behave like them, i.e. satisfy the axioms that were motivated by structure-preserving functions.

When there is only one group of a given size

Posted on by John

Today’s date, US style, is 9/26/2023, and there is only one group, up to isomorphism, of size 9262023. You could verify this in Mathematica with the command

    FiniteGroupCount[9262023]

which returns 1.

For a given n, when is there only one group of size n?

There are two requirements. First, n has to be the product of distinct primes, i.e. no prime appears in the factorization with a power greater than 1. Second, no prime divides one less than another prime.

Now

9262023 = 3 × 41 × 257 ×293

and you can check that 3 does not divide 40, 256, or 292, nor does 41 divide 2, 252, or 292, etc.

A more compact way to state the criteria above is to say

gcd(n, φ(n)) = 1

where φ(n) is Euler’s totient function, the number of positive numbers less than n and relatively prime to n.

Why are these criteria equivalent? If

n = pqr…

then

φ(n) = (p − 1)(q − 1)(r − 1)…

If n and φ(n) have a nontrivial common factor, it has to be one of the prime factors of n, and none of these divide any term of φ(n).

Source: Dieter Jungnickel. On the Uniqueness of the Cyclic Group of Order n. The American Mathematical Monthly, Vol. 99, No. 6. (Jun. – Jul., 1992), pp. 545–547.