# Summarizing homotopy groups of spheres

I don’t understand homotopy groups of spheres, and it’s OK if you don’t either. Nobody fully understands them. This post is really more about information compression than homotopy. That is, I’ll be looking at ways to summarize what is known without being overly concerned about what the results mean.

## The task: map two integers to a list of integers

For each positive integer k, and non-negative integer n, the kth homotopy group of the sphere Sn is a finitely generated Abelian group, something that can be described by a finite list of numbers. So we’re looking at simply writing a function that takes two integers as input and returns a list of integers. This function is implemented in an online calculator that lets you lookup homotopy groups.

Computing homotopy groups of spheres is far from easy. The first Fields medal given to a topologist was for partial work along these lines. There are still groups that haven’t been computed, and potentially more Fields medals to win. But our task is much more modest: simply to summarize what has been discovered.

This is not going to be too easy, as suggested by the sample of results in the table below. This table was taken from the Homotopy Type Theory book, and was in turn based on the Wikipedia article on homotopy groups of spheres.

## Output data representation

To give an example of what we’re after, the table says that π13(S²), the 13th homotopy group of the 2-sphere, is Z12 × Z2. All we need to know is the subscripts on the Z‘s, the orders of the cyclic factors, and so our function would take as input (13, 2) and return (12, 2).

The table tells us that π8(S4) = Z22. This is another way of writing Z2 × Z2, and so our function would take (8, 4) as input and return (2, 2).

When I said above that our function would return a list of integers I glossed over one thing: some of the Z‘s don’t have a subscript. That is some of the factors are the group of integers, not the group of integers mod some finite number. So we need to add an extra symbol to indicate a factor with no subscript. I’ll use ∞ because the integers as the infinite cyclic group. For example, our function would take (7, 4) and return (∞, 12). I will also use 1 to denote the trivial group, the group with 1 element.

Some results are unknown, and so we’ll return an empty list for these.

The order of the numbers in the output doesn’t matter, but we will list the numbers in descending order because that appears to be conventional.

## Theorems

Some of the values of our function can be filled in by a general theorem, and some will simply be data.

If we call our function f, then there is a theorem that says f(kn) = (1) if kn.  This accounts for the zeros in the upper right corner of the chart above.

There’s another theorem that says f(n+mn) is independent of n if n > m + 1. These are the so-called stable homotopy groups.

The rest of the groups are erratic; we can’t do much better than just listing them as data.

(By the way, the corresponding results for homology rather than homotopy are ridiculously simple by comparison. For k > 0, the kth homology group of Sn is isomorphic to the integers if k = n and is trivial otherwise.)

# Weakening the requirements of a group

A group is a set with a binary operation that

1. closed
2. associative,
3. has an identity, and
4. has inverses.

This post will look at each of these properties and what happens if you modify or remove it.

## Magmas

Closed means that applying the binary operation to any two elements of the set yields another elements of the set. (I saw a book one time that had at the top of some chapter a quote something like “The product of two real numbers is a real number; we should be surprised if it were a head of cabbage.”) For example, the positive integers are closed under multiplication but not under division.

A set with a closed binary operation is called a magma.

## Semigroups

Associative means that you can parenthesize an expression any way you want and always get the same result. It may be practically important how you parenthesize an expression. For example, matrix multiplication can far fewer operations if you carry out the multiplications in the right order. In programming, left folds and right folds (such as foldl and foldr in Haskell) may have very different efficiency, but they’re supposed to return the same result if you’re folding an associative operation.

A magma with an associative operation is called a semigroup.

Differential equation theory is concerned with analytic semigroups. If you advance the solution of an evolution equation by a positive time increment t and then by an increment s, you end up at the same place as if you’d advanced the solution by ts.

Notice that the time increment is required to be positive. That’s because the initial conditions for an evolution equation might reside in a different function space than the solutions at any future time. That’s the case, for example, with the heat equation, where initial conditions can be rough but the solution smooths out immediately as you move forward in time.

## Monoids

If you add the requirement that a semigroup has an identity, you get a monoid. Partial differential equation theory is more concerned with analytic semigroups than analytic monoids for the reason explored above: you might not have an identity.

Positive integers with multiplication form a monoid but not a group because they have an identity, 1, but positive integers other than 1 do not have a multiplicative inverse that is an integer.

A monoid in which every element has an inverse is a group. ## Quasigroups

So far we’ve built up a progression of stronger and stronger requirements leading up to groups, starting with requiring that our operation is associative. What if we don’t have associativity, but we do have other properties?

Non-associative operations are less common. Perhaps the best known operation that is not associative is octonion multiplication.

There are four division algebras over the reals: the reals themselves, complex numbers, quaternions, and octonions. Real and complex numbers are both fields. Quaternions are not a field because multiplication is not commutative. Octonions are even further from being a field because multiplication is not even associative.

But division is possible for octonions, except for 0, and so non-zero octonions form a quasigroup, a magma with division.

## Loops

A quasigroup that has an identity element is called a loop. Note that for quasigroups we said “division is possible,” not that elements have inverses. If elements do have inverses, then you can divide by an element by multiplying by its inverse. But you can define division by the ability to solve equations. We say you can divide b by a if axb and yab have unique solutions.

A loop with associativity is a group.

## Alternative loops

Loops are not required to have an associative property, but they may satisfy a weak form of associativity.

An alternative loop satisfies x(xy) = (xx)y and x(yy) = (xy)y. Non-zero octonions form an alternative loop with respect to multiplication.

## Moufang loops

A Moufang loop is a loop that satisfies these requirements:

1. z(x(zy)) = ((zx)z)y
2. x(z(yz)) = ((xz)y)z
3. (zx)(yz) = (z(xy))z
4. (zx)(yz) = z((xy)z)

These conditions imply the alternative loop conditions, so Moufang loops are alternative loops.

Moufang loop are still not required to be associative, but they’re getting closer. And as you might have anticipated, non-zero octonions with respect to multiplication form a Moufang loop. # Defining the Fourier transform on LCA groups

My previous post said that all the familiar variations on Fourier transforms—Fourier series analysis and synthesis, Fourier transforms on the real line, discrete Fourier transforms, etc.—can be unified into a single theory. They’re all instances of a Fourier transform on a locally compact Abelian (LCA) group. The difference between them is the underlying group.

Given an LCA group G, the Fourier transform takes a function on G and returns a function on the dual group of G. We said this much last time, but we didn’t define the dual group; we just stated examples. We also didn’t say just how you define a Fourier transform in this general setting.

## Characters and dual groups

Before we can define a dual group, we have to define group homomorphisms. A homomorphism between two groups G and H is a function h between the groups that preserves the group structure. Suppose the group operation is denoted by addition on G and by multiplication on H (as it will be in our application), saying h preserves the group structure means

h(x + y) = h(x) h(y)

for all x and y in G.

Next, let T be the unit circle, i.e. complex numbers with absolute value 1. T is a group with respect to multiplication. (Why T for circle? This is a common notation, anticipating generalization to toruses in all dimensions. A circle is a one-dimensional torus.)

Now a character on G is a continuous homomorphism from G to T. The set of all characters on G is the dual group of G. Call this group Γ. If G is an LCA group, then so is Γ.

## Integration

The classical Fourier transform is defined by an integral. To define the Fourier transform on a group we have to have a way to do integration on that group. And there’s a theorem that says we can always do that. For every LCA group, there exists a Haar measure μ, and this measure is nice enough to develop our theory. This measure is essentially unique: Any two Haar measures on the same LCA group must be proportional to each other. In other words, the measure is unique up to multiplying by a constant.

On a discrete group—for our purposes, think of the integers and the integers mod m—Haar measure is just counting; the measure of a set is the number of things in the set. And integration with respect to this measure is summation.

## Fourier transform defined

Let f be a function in L¹(G), i.e. an absolutely integrable function on G. Then the Fourier transform of f is a function on Γ defined by What does this have to do with the classical Fourier transform? The classical Fourier transform takes a function of time and returns a function of frequency. The correspondence between the classical Fourier transform and the abstract Fourier transform is to associate the frequency ω with the character that takes x to the value exp(iωx).

There are multiple slightly different conventions for the classical Fourier transform cataloged here. These correspond to different constant multiples in the choice of measure on G and Γ, i.e. whether to divide by or multiply by √(2π), and in the correspondence between frequencies and characters, whether ω corresponds to exp(±iωx) or exp(±2πiωx).

# Safe primes, Sylow theorems, and Cryptography

A logarithm is the inverse of an exponential, and so we can generalize the idea of a logarithm wherever we can generalize the idea of an exponential. In particular, we can raise elements to exponents in a discrete group, and that leads to the definition of a discrete logarithm.

Diffie-Hellman public key cryptography is based on the assumption that discrete logarithms are hard to compute. There are algorithms to compute discrete logarithms that are much faster than brute force. For example, baby-step giant-step is a fairly simple algorithm. There are more efficient algorithms as well, but the best known algorithms are still much slower than raising numbers to powers. Whenever you find something that is much harder to undo than to do, it might be useful in cryptography, and that is the case with discrete logs.

Diffie-Hellman encryption requires users to compute exponentials and presumably requires attackers to compute discrete logs. I say “presumably” because it’s a fatal error in cryptography to assume an attacker has to solve the problem you think he’d have to solve. For example, you can create a simple encryption scheme by permuting the alphabet and encrypting each letter to its counterpart in the permutation. Someone might naively think “No one can break this because they’d have to try 26! permutations of the alphabet, over 400 million million million million possibilities!” Except that’s not how anyone approaches a substitution cipher. If it were, you wouldn’t see cryptograms in puzzle books.

As far as we know, discrete logarithms are hard to compute when working over integers mod p where p is a large prime, except for primes that have certain properties. We’ll look at what those properties are below and how to avoid them.

For a prime p, the integers mod p form a finite field. They are a group under addition, and the non-zero elements form a group under multiplication. It’s the multiplicative group we care about here. This group has order p-1, i.e. it has p-1 elements.

A group of prime order has no proper subgroups. But a group of composite order does. And our multiplicative group has order p-1, which is composite. (Except for p = 3, and cryptography depends on primes far, far bigger than 3.)

Sylow’s theorems tell us something about what kinds of subgroups a group must have. If s is prime and sk is a factor of the order of our group, then the group has a subgroup of order sk. We don’t want our multiplicative group to have any small-order subgroups because these would make it easier to compute discrete logarithms.

A safe prime p has the form 2q + 1 where q is also prime . Diffie-Hellman chooses safe primes for moduli because this means the multiplicative group of order p-1 = 2q has no small subgroups. (It has two small subgroups, {1} and {1, -1}, but these can easily be avoided. The algorithm requires picking a generator g, and as long as you don’t pick g to be 1 or -1 mod p, then g generates a group of order q, and if p is gigantic, so is q.) Because q is prime, the subgroup of order q does not have any further subgroups.

Related post: Probability that a number is prime

  If q and p = 2q + 1 are both prime, q is called a Sophie Germain prime and p is a safe prime.

# Visualizing Galois groups of quadratics

Yesterday Jack Kennedy told me about a graph he’d made as part of a project he’s working on and I asked if I could post it here.

The Galois group of a quadratic polynomial x2 + bx + c is either A2 or S2. If b2 – 4c is a perfect square, the polynomial has rational roots and the Galois group is the trivial group A2. Otherwise there are distinct irrational roots and the Galois group is the two-element group S2.

As b and c range over integers, color a pixel yellow if the group is A2 and black otherwise. This produces the image below. Note that what appear to be the crossed lines y = ±x intersecting at 0 are actually the lines y = ±(x+1) intersecting at (-1,0).

You can find a larger image here. View the page source to see the JavaScript that produced the image. The page is calculating and setting the value of one million pixels, and yet the time to render the page isn’t even noticeable.

* * *

For daily tweets on algebra and other math, follow @AlgebraFact on Twitter. # Normal subgroups are not transitive

The property “is a normal subgroup of” is not transitive.

If A is a subgroup of B, and B is a subgroup of C, then A is a subgroup of C. But the corresponding statement about normal subgroups is false. And there’s a simple example that shows it is false.

We need to find a group C with subgroups A and B such that A is normal in B, B is normal in C, but A is not normal in C.

The subgroup A must have at least two elements, otherwise A would just be the group identity and would then be a normal subgroup of C. The order of a subgroup divides the order of the group, so B must have at least twice as many elements as A, and C must have twice as many elements as B. So the smallest possible example would be a group with 8 elements and subgroups of order 2 and 4.

We’re in luck, because there’s a group of order 8 that will work, D8. This is the group of symmetries of a square under flips and rotations. Let A be the subgroup of flips about the vertical axis of symmetry. Let B the symmetries you can find by combinations of such flips and 180 degree rotations. You can show that A is normal in B, and B is normal in C.

Now let c be a 90 degree clockwise turn and let a be a flip. You can show that cac-1 is not a flip or the identity, so A is not a normal subgroup of C.

Related post: A 3,000 page proof (classification of finite simple groups)

For daily tweets on algebra and other math, follow @AlgebraFact on Twitter. 