Group theory

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.

Normal and non-normal subgroups

Posted on by John

The word “normal” in mathematical nomenclature does not always means “usual” or “customary” as it does in colloquial English. Instead, it might that something has a convenient property. That is the case for normal subgroups.

We can do things with normal subgroups that we cannot do with other subgroups, such as take quotients, and so once normal subgroups are introduced in an algebra class, non-normal subgroups disappear from the discussion. A student might be left with the impression that non-normal subgroups don’t exist.

This post will give a very simple example of a group with a non-normal subgroup, and show how we can’t do operations with this group that we can with normal subgroups.

Definition of normal subgroup

A normal subgroup of a group G is a subgroup N such gN = Ng for any element g in G. That is, if I multiply everything in N by g on the left or I multiply everything in N by g on the right, I get the same set of elements.

This does not mean that gn = ng for every n in N. It means that for every n in N, there is some element m in N such that gn = mg. The elements n and m might be the same, but they might not.

In an Abelian (commutative) group, gn always equals ng, and so all subgroups are normal. But most groups are not Abelian.

Structure-preserving functions

Along with every algebraic structure there are functions that preserve aspects of that structure. In the category of groups, these structure-preserving functions are called homomorphisms, coming from the Greek words for “same” and “shape.”

A homomorphism between groups gives you a sort of picture of the first group inside the second group in a way that is consistent with the structure of groups. Specifically, if f is a homomorphism from a groups G to a group H, then

f(xy) = f(x) f(y).

Here we denote the group operation by writing two things next to each other. So “xy” means the group operation in G applied to x and y. This operation may or may not be multiplication. The same is true on the right-hand side: f(x) f(y) means the group operation in H applied to f(x) and f(y).

For example, if we let G be the real numbers with the group operation being addition, and we let H be the positive real numbers with the group operation being multiplication, then the exponential function is a homomorphism between these groups:

exp(x + y) = exp(x) exp(y).

Kernels

The kernel of a homomorphism between G and H is the subset of things in G that get sent to the identity element in H. In the example above, the identity element in H is 1, and the only element in G that gets mapped to 1 is the number 0. It’s not a coincidence that 0 is the identity element in G: homomorphisms always send the identify element of one group to the identity element of the other group. The kernel of a homomorphism always includes the identity, but it may also include more.

Normal subgroups are subgroups that can be kernels. A subgroup of G is normal if and only if there is some homomorphism from G to another group that has that subgroup as its kernel.

A non-normal subgroup

Let G be the group of permutations on three elements. The group operation is composition, i.e. do one permutation then do the other.

The identity element is the permutation that leaves everything alone. Denote this by 1. Another element of G is the permutation that swaps the first two elements. We’ll denote this by (12).

So if our three elements are a, b, and c, then the permutation 1 takes (a, b, c) to (a, b, c). And the permutation (12) takes (a, b, c) to (b, a, c).

The two elements 1 and (12) form a subgroup of G. But we will show that a homomorphism from G to a group H cannot take these two elements, and only these two elements, to the identity on H. It won’t matter what group H is, but we’ll need a name for the identity element in H. Let’s call it e.

Let f be a homomorphism from G to H. () By definition

f(xy) = f(x) f(y)

and by applying this to (xy)z we have

f(xyz) = f(x) f(y) f(z)

If we let z be the inverse of x and y is in the kernel of f, we have

f(xyx-1) = f(x) f(y) f(x-1) = f(x) e f(x)-1 = e.

This says that if y is in the kernel of f, xyx-1 must also be in the kernel of f for every x.

The permutation that swaps the second and third elements, (23), is its own inverse: swap the second and third elements twice and you’re back where you started. So if (12) is in the kernel of f then so is (23)(12)(23). You can work out that (23)(12)(23) reverses three elements. This shows that if the subgroup consisting of 1 and (12) is in the kernel of f, so is the reverse permutation, which is not part of our subgroup. So our subgroup alone cannot be a kernel of a homomorphism.

Related posts

Elliptic curve Diffie-Hellman key exchange

Posted on by John

I concluded the previous post by saying elliptic curve Diffie-Hellman key exchange (ECDHE) requires smaller keys than finite field Diffie-Hellman (FFDHE) to obtain the same level of security.

How much smaller are we talking about? According to NIST recommendations, a 256-bit elliptic curve provides about the same security as working over a 3072-bit finite field. Not only are elliptic curves smaller, they scale better. A 512-bit elliptic curve is believed to be about as secure as a 15360-bit finite field: a factor of 2x for elliptic curves and a factor of 5x for finite fields.

The core idea of Diffie-Hellman is to pick a group G, an element g, and a large number of x. If y is the result of starting with x and applying the group operation x times, it is difficult to recover x from knowing y. This is called the discrete logarithm problem, taking its name from the case of the group operation being multiplication. But the inverse problem is still called the discrete logarithm problem when the group is additive.

In FFDHE the group G is the multiplicative group of a generator g modulo a large prime p. Applying the group operation (i.e. multiplication) to g a number of times x is computing

y = gx

and x is rightly called a discrete logarithm; the process is directly analogous to taking the logarithm of a real number.

In ECDHE the group is given by addition on an elliptic curve. Applying the group operation x times to g, adding g to itself x times, is written xg. The problem of recovering x from xg is still called the discrete logarithm problem, though you could call it the discrete “division” problem.

Some groups are unsuited for Diffie-Hellman cryptography because the discrete logarithm problem is easy. If we let G be the additive group modulo a prime (not the multiplicative group) then it is easy to recover x from xg.

Note that when we talk about applying the group operation a large number of times, we mean a really large number of times, in theory, though not in practice. If you’re working over an elliptic curve with on the order of 2256 elements, and x is on the order of 2256, then xg is the result of adding x to itself on the order of 2256 times. But in practice you’d double g on the order of 256 times. See fast exponentiation.

In the post on FFDHE we said that you have to be careful that your choice of prime and generator doesn’t give the group structure that a cryptanalysist could exploit. This is also true for the elliptic curves used in ECDHE, and even more so because elliptic curves are more subtle than finite fields.

If large-scale quantum computing ever becomes practical, Diffie-Hellman encryption will be broken because a quantum computer can solve discrete logarithm problems efficiently via Schor’s algorithm. This applies equally to finite fields and elliptic curves.

Related posts