Starring Golay codes, the sporadic symmetry group Mathieu 24 (M24), and the Leech lattice, which is the "one lattice of power" that rules all other lattices from its 24 dimensional throne.

With a guest role for Klein's Quartic.

(home)

Note: Part of this work made it to
the American Mathematical Society weblog 'Visual Insight':

http://blogs.ams.org/visualinsight/2015/12/01/golay-code/

http://blogs.ams.org/visualinsight/2015/12/01/golay-code/

I started this page after brooding on the intriguing fact that apparently, a devilishly smart way of doing error tolerant digital signal transmission, called the Golay code, is related to the magical symmetry group M24.

My curiosity for M24 was sparked by remarks like this one in the Atlas of Finite groups (A famous big red book that I bought, in the hope to understand it one day ): "The group M24 is one of the most remarkable of all finite groups. Many properties of the larger sporadic groups reduce on examination to properties of M24. This centenarian group can still startle us with its youthful acrobatics." The 3D print on top of the book is a great dodecahedron, which we will encounter in a minute.

There are many maddeningly
fascinating references to M24, and
the Leech
lattice, but to understand this, you have to pass through some daunting
mountains of difficult mathematics. Until I found the secret passage
that I describe on this page. Read on...

The error detecting trick I already knew was the "parity
bit". This occurs in the old RS232 code, where you have to type config
parameters things like 7,1,e. That means 7 data bits, 1 parity bit,
even parity. Sometimes, if the connection does not work, you have to
change this, although usually this is taken care of by higher level
software.

The idea of parity
check
is simple, you count the number of 1's, and then add a parity bit, to
ensure the total amount of 1's is even (or odd, if you want odd
parity). This allows you to detect errors. If one bit gets
flipped, then the parity will no longer be correct. In practice,
you would do some kind of RESEND request to the other side. But if the
other side is a spacecraft 4 light hours away on a Pluto mission it
will be helpful if you can correct the data yourself.

The trick to correct errors as well as detect them, is related
to
geometry. Below is a picture of a polyhedron, in this case a cube.
Imagine the data bits are placed on the vertices, and on each of the
faces is 1
parity check bit. They are the parity bit on the 4 bits on the
vertices contained in the face. So this code would have 8 data
bits and 6 parity bits.

Data bits on the vertices, and parity check bits on the faces, which detect and locate an error for correction.

With the cubical code, we can almost detect and correct 2 errors, but it turns out you can figure out an unlucky combination that it cannot distinguish from another.

Note1: We alway assume there is some maximum number of errors per block. Given unlimited errors, you can screw up anything.

A natural question to ask is, how much better can we do than the cubical code? I don't know if Golay was on the same line of thought, but in 1949 he set out to find the ultimate code. Golay's original article is very short, only half a page:

http://www.maths.manchester.ac.uk/~ybazlov/code/golay_paper.pdf

Because of its conciseness I was hoping to understand it quickly. He writes that he found his code by looking for a row of Pascal's triangle whose first few entries add up to an exact power of 2. It was at first not clear to me how Pascal's triangle comes in. Golay perhaps overdid the conciseness somewhat by not explaining this.

But I get it now:

Suppose you have N parity check bits in a block of M bits. You can maximally encode 2

The number of possible error positions of 0 errors is 1

The number of possible error positions of 1 errors is M

The number of possible error positions of 2 errors is M(M-1)/2

The number of possible error positions of 3 errors is M(M-1)(M-2)/2/3

These combinatorial numbers are just the (M+1)th row of Pascal's triangle. (Aha, Golay said M, so he is human too).

Row 24 gives: 1, 23, 23*22/2=253, 23*22*21/2/3=1771, which adds up to 2048, which is 2

.

So if you can find a scheme with 12 data bits and 11 parity bits that describes up to 3 errors, then you know for sure this is optimal, because 11 bits cannot possible encode more data than that which is needed to describe the errors.

Golay then goes on to supply a scheme for identifying up to 3 errors, using the so-called "generator matrix". This is just a n M*(M-N) matrix, with which you multiply modulo 2 with the data bits, to get the M (data+checksum) bits. Matrix multiplying modulo 2 is actually equivalent to just doing a parity count of the rows of the left matrix, masked by the columns of the second matrix. Once you try it, you will see it is easy.

To help get used to generator matrices, here are the generator matrix for the "cube code" in our animation, and for a simple parity check. They are written in such a way that you need to put your data bits as a row vector, multiplied on the right side by the generator matrix, which then gives the new (data+parity) as a row vector.

Generator matrix for the "cube code", and for a simple parity check.

Golay figured out the optimal code for 23 bits, called the "Perfect Binary Golay code", but often, one extra bit is added, to get the 24 bit "Extended Binary Golay Code". This one is in fact a little more wasteful, but its relation to symmetry is more clear. We will use the Extended Binary Golay Code, whose generator matrix is given on Wikipedia:

(Wikipedia image), Generator matrix for the extended binary Golay code.

Now this matrix corresponds to a polyhedral code on the [suspense music building up...] great dodecahedron!

The great dodecahedron is perhaps not the most famous polyhedron, but is actually special in a couple of ways. It has 12 vertices and 12 faces (12 pentagons that intersect each other). So its number of faces is equal to its number of vertices. It also has 5 vertices per face, and 5 faces per vertex, so it has this additional face/vertex symmetry. These 2 feats are pulled off by only 1other uniform polyhedron: the small stellated dodecahedron. But that one is more or less the same polyhedron, with the vertices reconnected differently. Indeed, as Refurio Anachro pointed out, they are each other's dual.

Great dodecahedron

If we worked the same way as with the cube, doing a parity sum for each face, we get all the ones and zeros exactly opposite to the Golay code. So what we have to do is for each face, parity sum all vertices except those contained by it. This means each of the 12 faces does a parity sum over 7 vertices. Count the ones in each row of the Golay generator matrix, they are all 8. Below is an animation of a failed bit (green blinking disk on the pentagonal face), and the 7 awakened parity checks (red blinking). I put the data bits on the faces this time, and the parity bits on the vertices, for greater clarity. One of the symmetries if the Golay code is that you can interchange the faces and the vertices and parity/data.

Animations of the data bits on the great dodecahedral faces, with an error (green flash), and the parity check alarms (red flash) on the vertices.

So we've done it! We have an easy to visualize interpretation of the Golay code.

The Leech lattice

Let us now define the Leech lattice in a way we can understand. In 24 dimensional space, you can consider all points with integer coordinates. These form a 24 dimensional hypercubical lattice, which does not seem so special.

But what if you keep only points whose coordinates are related to the Golay code? That is basically the idea that Leech had back in 1964. This new lattice would after rescaling by the distance between 2 neighbours, be much denser. Leech knew his lattice would be highly symmetrical, but he did not know enough group theory to figure out the symmetry group. He tried to interest group theorists and eventually Conway ended up solving it, resulting in the discovery of 3 sporadic groups Co1, Co2, and Co3.

One feature of Golay codes is that the minimum squared distance between 2 valid words is 8. Leech wanted to retain this property in his lattice. So he could not just take all integers modulo 2, and check if that is a legal Golay word. Because then you could for example replace any '0'by '2', to get another lattice point, which would be at squared distance 4.

At this point, we will multiply all numbers by 2, for later convenience. So Golay words are now doubled eg(0,2,0,0,2...) and the minimum squared distance between two words is 32.

Then, changing by 8 is OK (squared distance 64). In fact the Leech lattice is periodic by translations of 8 integers in each direction. In the matrix below, the first row vector is an example of such a translation.

Another translation that would be allowed is 2 translations by 4, in 2 different directions. Examples of these can also be seen in the matrix below. This would lead to words that are strings of '0','2','4' and '6'. These even points are just half the points of the Leech lattice. Interestingly, Leech first left it at that. But about a year later he doubled the density by adding also odd points (See now why we multiplied the points by 2). If you take an even Golay word and make all even numbers odd , then the new word will be at a squared distance of 24. So shift one coordinate by 3 instead of 1: Squared distance 23+9=32! This is implemented by the bottom row of the matrix below.You can of course choose any coordinate to shift by 3 instead of the first one, but these vectors can be formed by linear combinations of the others.

Another way to see it is to represent the coordinates modulo 8 as 3 bits, (000,001,010,011,100,101,110,111). So for each point, you have 24 numbers of 3 bits. Then, the middle bits have to form Golay words. The least significant bit must either be all 24 ones (odd points) or 24 all zeros (even points). The highest of the 3 bits can be anything, except the even points need to have an even number of ones, while the odd points require an odd number of ones. ( I got that from an article by Austin Roberts)

24 row vectors that generate the Leech lattice. The vectors are arranged so the upper right triangle of the matrix is zero. This ensures that each new row is linearly independent of the previous ones, since it is the first to use a new column. The first (blue) row is a translation by 8. All translations by multiples of 8 are allowed, others can be made by linear combinations. The red rows are 11 legal Golay words multiplied by 2, which together with row 1 (the zero word mod 8) generate all Golay words multiplied by 2. The black vectors are translations by 4 in 2 different directions. Finally, the bottom green vector jumps from the even points to the odd points, while changing one coordinate by by an extra 4.

I could now go on to find and write amazing facts about the Leech lattice, but I run out of time. Conway and Sloane wrote a book on sphere packings, and in the introduction they mention that they considered making a special abbreviation for "It is a truly remarkable fact that", because they were so often amazed by the properties of packings.

Note2: This might be a good place to introduce the buzzword "Hamming weight". This is just the minimum number of different bits between 2 valid words. So for plain code, the Hamming weight is1. But with a parity check, it becomes 2, because if you change one bit, you must also change the parity. For the cube code shown above, it is 4. For the (extended) Golay code it is 8. If you look N-dimensional space whose coordinates are the N bits of a code block, then you can draw an N-dimensional sphere around the valid word, with a radius related to the Hamming weight. All words inside that sphere, except the center, will be illegal words, ie one with a bad parity check. The Golay code has the property that all possible bit combinations, plotted out in the N dimensional space, fall inside a spheres centered around a legal words. This can be interpreted as "correcting" the surrounding words to the word in the sphere center. You can see that this will work especially well with dense packings, and the densest known packings in any dimension <=24 is the Leech lattice!

M24

The group M24 was discovered by Mathieu somewhere around 1870. All finite simple (ie not built from combining other groups) groups have now been classified, a work of decades. They come in families, but there are 26 "sporadic groups", which do not fit in. The Mathieu groups are the oldest of these. More and more, people are discovering strange things about sporadic groups, such as monstrous moonshine.

M24 is the "automorphism group" of the Golay code: the set of all ways to manipulate the order of the bits without destroying the structure of the code. Since we now can visualize the Golay code, maybe we can start to understand M24. I think I will put this page on the web first, and then start thinking about M24. A bit of low hanging fruit:

-You can switch the data bits and the parity bits: If you ask which data bits correspond to a pattern of parity bits, this is just the parity pattern you get by entering the parity pattern as data!

- The word with 24 zero's, or with 24 ones, are both legal words. All other words have 8, 12 or 16 ones.

Klein's Quartic

Klein's quartic is a cherished object in discussions around the Internet, I spent quite a bit of time making models of it and trying to understand it. It is a highly symmetrical figure with 24 heptagons. To see the connection with Golay codes, note that in Golay codes, each data bit has 7 parity bits "connected" to it, and vice versa, just like the heptagonal structure in Klein quartic. The total number of bits is 24, just like the number of vertices of the Klein Quartic. However, the connectivity is different to the usual Klein Quartic, which is tiled by {7,3}, each vertex has 3 heptagons. The Golay code has four heptagons meeting at each point. This allows a partitioning of the heptagons into 2 groups of 12, colored blue and green: If the data bits are imagined on the green heptagons, than the blue heptagons contain the parity sums of the surrounding data bits.

Klein Quartic tiled with {7,4}. If the data bits are imagined on the green heptagons, then the blue heptagons contain the parity sums of the surrounding data bits.

Note the outer heptagons are cut up into 7 wedges each, each wedge attached to a neighbour on the 'fundamental polygon'

Stellating the Klein Quartic You get a figure with 24 heptagrams, and at each vertex now 7 heptagrams meet, and the genus goes from 3 to 19!

(Not all heptagrams are drawn)

links

Part of this work made it to the American Mathematical Society weblog 'Visual Insight':

http://blogs.ams.org/visualinsight/2015/12/01/golay-code/

Joe fields has a nice web page in which the Golay code is explained with dodecahedra. Masks are used rather than relating vertices to faces:

http://giam.southernct.edu/DecodingGolay/introduction.html

David Richter has a nice page on M24 and Klein's Quartic:

http://homepages.wmich.edu/~drichter/mathieu.htm

There is a page (In Dutch) about Golay. Apparently, he was for a time a professor in Eindhoven, where he was a legend. Also, I read he worked on electric network analogies, so I should definitely like him!

A short bibliography on John leech. It is interesting to read how he discovered the leech lattice, but that finding its properties, like they are known today, was not at all easy, even for Leech himself. the definitive form of the lattice took several years (1964-1967), and to find its symmetry group he tried to lure others until finally Conway took the bait:

http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Leech.html

http://www.math.ups.edu/~bryans/Current/Journal_Spring_2006/ARoberts_LeechLattice.pdf

http://www.ams.org/notices/201309/rnoti-p1168.pdf