Group theory

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.

Analogy between prime numbers and simple groups

Posted on by John

Simple groups are the building blocks of groups similar to the way prime numbers are the building blocks of integers. This post will unpack this analogy in two ways:

  1. How do simple groups compare to prime numbers?
  2. How does the composition of simple groups compare to the composition of prime numbers?

The former analogy is stronger than the latter.

Primes and simple groups

A simple group has no nontrivial subgroups, just a prime number has no nontrivial factors. Except that’s not quite right. A simple group is defined as having no nontrivial normal subgroups. The previous post compares normal and non-normal subgroups. Normal subgroups have nice properties which are necessary for decomposition and composition. You can’t define quotients for non-normal groups.

Every subgroup of an Abelian group is normal, so in the context of Abelian groups it is true that simple groups have no nontrivial subgroups, i.e. the only subgroups of a simple Abelian group G are the identity and G itself. It follows from Sylow’s theorems that the order of a finite Abelian group with no nontrivial factors must be an integer with no nontrivial factors, i.e. a prime number. Every Abelian finite simple group must be isomoprphic to the integers mod p for some prime p.

Non-Abelian finite simple groups do not have prime order, but they not decomposable in the sense described below.

Composition and decomposition

Prime numbers compose to form other numbers by products. You can also compose groups by taking products, though you need more than that. It is not the case that all finite groups are products of finite simple groups.

Let ℤn denote the cyclic group of order n and let ⊕ denote direct sum. The group ℤ4 is not isomorphic to ℤ2 ⊕ ℤ2. Even in the case of Abelian groups, not all Abelian groups are the direct sum or direct product of simple groups. [1]

Finite groups can be decomposed into smaller finite simple groups, but we can’t easily or uniquely rebuild a group from this decomposition.

The Jordan-Hölder theorem says that a finite group G has a composition series

1 = H0 ⊲ H1 ⊲ … ⊲ Hn = G

where each H is a maximal normal subgroup of the next, the quotients Hi+1 / Hi of consecutive are simple groups. The composition series is not unique, but all such series are equivalent in a sense that the Jordan-Hölder theorem makes precise.

It seems to me that the composition series ought to be called a decomposition series in that you can start with G and find the H‘s, but it’s a difficult problem, known as “the extension problem,” to reconstruct G from the H‘s, and in general there are multiple solutions.

The analogy to prime numbers would be if there was an essentially unique way to factor a number, but not a unique way to multiply the factors back together.

Reductionism

Some people thought that the classification of finite simple groups would be the end group theory. That has not been the case. Some also thought sequencing of the human genome would lead to cures for a huge range of diseases. That has not been the case either. Reductionism often produces disappointing results.

Related posts

[1] In the context of Abelian groups, (direct) products and coproducts (i.e. direct sums) are isomorphic.