You are here

From Error-Correcting Codes Through Sphere Packings to Simple Groups

Thomas M. Thompson and William Watkins
Publisher: 
Mathematical Association of America
Publication Date: 
2004
Number of Pages: 
244
Format: 
Paperback
Series: 
Carus Mathematical Monographs 21
Price: 
33.00
ISBN: 
978-0-88385-037-4
Category: 
Monograph
BLL Rating: 

The Basic Library List Committee considers this book essential for undergraduate mathematics libraries.

[Reviewed by
Francis Fung
, on
11/3/2009
]

The book under review is an expository gem that traces an interconnected set of mathematical developments across multiple fields. This is a fascinating mathematical journey that cuts across several disparate fields of mathematics and forms a key component of one of the greatest achievements of 20th century mathematics, the classification of finite simple groups.

It begins in the 1940s at Bell Labs, at the dawn of information theory, where Claude Shannon’s seminal work “A Mathematical Theory of Communication” [8] established the unity of all information and laid the groundwork for essentially all digital communication. Shannon defined the “capacity” of a noisy channel (the maximum rate at which information can be transmitted across it) and proved that if one wants to send information across the channel at a rate beneath the capacity of the channel, then there exist “error correcting codes” that can transmit the information at that rate with arbitrarily low probability of transmission error.

Meanwhile, Richard Hamming at Bell Labs was frustrated: his computer jobs would often stop because the codes his computer used could detect errors but not correct them. They were using error-detecting protocols such as the following: to transmit a 4-digit binary word like 1101, one can generate a 5-digit binary codeword that always has an even number of 1s in it by adding a fifth “parity check” digit on the end that ensures that the number of 1s is even in the codeword before transmitting it. Since any single transmission error that flips a digit from 1 to 0 (or 0 to 1) will cause the received word to have an odd number of 1s in it, we can see that the received word has an error, but we cannot tell which position it is in. Hamming devised a scheme of overlapping parity checks that would turn a 4-digit word into a 7-digit codeword, such that if a digit is flipped, then the parity checks would fail in such a way as to uniquely identify which digit was flipped. This provides a concrete construction of an “error-correcting code”. Marcel Golay also published a paper on this topic (hailed as the most significant published page in the history of coding theory) and discovered two very exceptional multiple-error-correcting codes that bear his name and play a critical role in this book’s story.

A geometric way of viewing the decoding process is to view binary words of length n as points in an n-dimensional vector space over the finite field of two elements. By defining a metric (the Hamming distance) between two words as the number of places in which they differ, we can try to pack the space with “spheres” of a given radius centered around each codeword. If that packing “covers” the entire space, then we can “decode” a transmitted word by determining which codeword’s sphere contains the transmitted word.

A mathematician named John Leech incorporated these insights into his research into sphere packings of high-dimensional Euclidean spaces. In particular, he discovered a way to use one of Golay’s codes to construct a remarkably dense sphere packing in 24 dimensions. The centers of these spheres form a lattice, which now called the Leech lattice. The lattice has a very remarkable symmetry group, and the famed mathematician John H. Conway constructed the symmetry group and in the process discovered three finite simple groups that now bear his name.

The Golay codes yield five of the 26 so-called “sporadic” finite simple groups (those that do not fit into one of the infinite families), and Conway’s investigation of the Leech lattice yielded several more. Thus the story told in this book is one (crucial) strand in the classification of finite simple groups. A recent book by Ronan entitled Symmetry and the Monster [7] gives a non-technical account of the story, starting with Galois and culminating in the discovery of the Monster (and its still-mysterious connections with modular function theory, vertex operator algebras, and string theory that are referred to as Moonshine. Another recent book, Symmetry by du Sautoy [3], covers similar material. For more details on the Leech lattice, sporadic simple groups, sphere packings, and a wide variety of beautiful mathematics, the reader can consult Conway and Sloane’s monumental Sphere Packings, Lattices, and Groups [2] and the references therein.

In the years since this book was first published, there have been many advances in the fields discussed. Coding theory has experienced revolutionary advances, including the use of algebraic geometry to generate more effective codes and the advent of turbo coding, which uses iterative decoding algorithms that amount to probabilistic inference on graphical models [10, 11]. Hales and Ferguson settled the Kepler conjectures[4, 5], showing with the aid of a computer that the face-centered cubic lattice (and its nonlattice counterpart) are indeed the densest sphere packings in three dimensions. Also, Cohn and Kumar [1] verified that the Leech lattice is the densest lattice packing in 24 dimensions. The classification of finite simple groups has been completed and a project to revise the classification is ongoing [6].

This book requires a solid foundation in linear algebra, group theory (including the Sylow theorems, permutation groups, group actions on sets, and perhaps a little about linear groups), a little number theory (exposure to quadratic reciprocity would be good), and some combinatorics. There are reasonably self-contained introductions to several fundamental mathematical objects such as the Fano projective plane, finite fields, and linear groups, as well as very accessible and concrete introductions to the principal characters in the book such as error-correcting codes, sphere packings and Euclidean lattices. This book is a beautiful mix of linear algebra, combinatorics and group theory, and is highly recommended to all interested readers at the advanced undergraduate level and above.


References:

[1] Cohn, H., and H. Kumar, “The Densest Lattice in Twenty-Four Dimensions”, Electronic Research Announcements of the American Mathematical Society, 2004

[2] Conway, J. H., and N. J. A. S. Sloane. Sphere Packings, Lattices, and Groups, 3nd ed., Springer-Verlag, 1998.

[3] du Sautoy, M. “Symmetry: A Journey into the Patterns of Nature”, Harper, 2008.

[4] Hales , T. “A Proof of the Kepler Conjecture”, Annals of Mathematics, Vol. 16 (2005), No. 3, pp. 1063-118.3 See also http://annals.math.princeton.edu/annals/2005/162-3/annals-v162-n3-p01-s.pdf.

[5] Hales, T. and S. Ferguson, “Sphere Packing I-VII”, Discrete and Computational Geometry, Vol. 36 (2004), No. 1, pp. 1-265. See also http://sites.google.com/site/thalespitt/kepler-conjecture for more information.

[6] Gorenstein, D., R. Lyons, and R. Solomon, The Classification of Finite Simple Groups, Vol. 1, American Mathematical Society, 1994. Available online at: http://www.ams.org/online_bks/surv40-1/surv40-1-master.pdf

[7] Ronan, M. Symmetry and the Monster: One of the Greatest Quests of Mathematics, Oxford University Press, 2006.

[8] Shannon, C. E., "A Mathematical Theory of Communication", Bell System Technical Journal, vol. 27, pp. 379-423, 623-656, July, October, 1948. (See http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf)

[9] Stichtenoth, H. Algebraic Function Fields and Codes, 2nd ed, Springer-Verlag, 2009.

[10] Thompson, T. M. From Error-Correcting Codes Through Sphere Packings To Simple Groups, Mathematical Association of America, 1983.

[11] van Lint, J. H. Introduction to Coding Theory, 2nd ed., Springer-Verlag, 1992.


Francis Fung is a principal software engineer at Pegasystems, developing software for business process management. He can be reached at yahoo dot com with email address starting with “fyc” and followed by his last name.

Dummy View - NOT TO BE DELETED