What exactly is the relationship between codes over finite fields and Euclidean sphere-packings?

Question

So I know that error-correcting codes are sphere packings in the Hamming metric, and that intuition and technical tools from the Euclidean case can often be applied to the finite-field case and vice versa. But I've occasionally heard it implied that there's a more direct relationship, and you can actually use bounds on error-correcting codes over finite fields to obtain bounds for Euclidean sphere-packings.

Unfortunately, none of the books on coding theory I have access to tell me how exactly this works, and Google's not being very cooperative either. Does anyone have (a pointer to) an explanation of how exactly you can transfer results between the two settings? Or am I misremembering or misunderstanding what I've read?

Answer 1

Conway and Sloane, Sphere Packings, Lattices, and Groups (SPLAG), is one of the best survey-style mathematics books ever written. It certainly does extend the discussion to error-correcting codes, even though the main theme is Euclidean sphere packings.

The most important relationship between sphere packings and codes, but not the only relationship, is as an extended analogy that leads to uniformly argued bounds and constructions. The Hamming metric and the Euclidean metric are both metrics, and in both cases you are interested in minimum distance sets which you then call codes. But the analogy is more than just that. The Hamming cube is a normed abelian group, and Euclidean space is a normed abelian group. In both cases, there is a special interest in codes that are subgroups. If a code is a subgroup, you only have to check the minimum distance from the 0 vector. Also, recall Pontryagin-Fourier duality: If $A$ is a locally compact abelian group, it has a dual group $\hat{A}$ which is its group of characters. The Hamming cube and Euclidean space are both canonically self-dual in the sense that $A = \widehat{A}$. If $C \subset A$ is a subgroup, it has a dual code $C^\perp$ which is by defining the subgroup $\widehat{A/C} \subset \widehat{A} = A$. (In other words, it is the group of characters which are trivial on $C$.) $C$ has a weight enumerator, which in the Euclidean case is called a theta series, and the weight enumerators of $C$ and $C^\perp$ are related by a transform. The transform is called the MacWilliams identity in the Hamming case and the Jacobi identity in the Euclidean case. The transform is possible because of another fundamental common feature: The Hamming cube and Euclidean space are both 2-point transitive metric spaces.

When a metric space is 2-point transitive, there is a construction due to Delsarte for finding upper bounds on the sizes of codes. The construction is a certain relaxation of the distance distribution of a code that reduces the bound to linear programming. The linear constraints come from harmonic analysis. It is easier in the compact case, and it is explained in SPLAG in the Hamming case and the spherical geometry case, where you get bounds on kissing numbers and other spherical sphere packings. The Euclidean case of the linear programming bounds were later developed by Henry Cohn and Noam Elkies in

• New upper bounds on sphere packings I, Annals of Mathematics 157 (2003), 689-714, doi:10.4007/annals.2003.157.689 arXiv:math/0110009.

On the construction side, the analogy is sometimes more direct. A sphere packing in $\mathbb{R}^n$ could be both a subset of $\mathbb{Z}^n$ and union of cosets of $(2\mathbb{Z})^n$. When it is of this form, it comes from a binary code in $(\mathbb{Z}/2)^n$. Sometimes this leads to the best known sphere packing. In fact one of these cases uses the Best code with $n=10$ (found by Marc Roelant Best). A simpler case is the $D_n$ lattice, which is the best packing when $n=3$, the best lattice packing when $n=4,5$, and thought to be the best packing in these two cases. It comes from the parity code.

This transfer of codes extends to another important case, codes over $\mathbb{Z}/k$ in the Lee metric. The Lee metric on $\mathbb{Z}/k$ is just the graph metric of a $k$-gon, i.e., $d(a,b) = |a-b|$ if you choose residues so that the answer is at most $k/2$. The standard Lee metric on $\mathbb{Z}/k$ is the $\ell^1$ sum of the Lee distances on the factors, but you can view this as an approximation to $\ell^2$ and again lift to the Euclidean case. You can obtain the $E_8$ lattice with way with $k=4$. $k=4$ is also separately because $\mathbb{Z}/4$ is isometric to $(\mathbb{Z}/2)^2$, and this isometry leads to what are called $\mathbb{Z}/4$-linear binary codes. (The Best code mentioned in the previous paragraph is one of these codes.)

Answer 2

Here is some more info:

1. It is useful to think about the problem of "spherical codes" (a set of points in S^n with minimum distance $\alpha$). Understanding densest Euclidean packing amounts to understanding spherical codes when $\alpha$ tends to zero. You can ask about codes in other symmetric spaces. An example worth mentioning is binary codes with prescribed numbers of '1's and '0's.

2. Random (or greedy) constructions give the best known asymptotic constructions for spherical codes (and sphere packing) and for binary codes. (For sphere packings these are the Minkowski-Hlawka lower bounds for error correcting codes these are the Gilbert-Varshamov lower bounds.) It is a fundamental open problem if these random constructions give the best rate of error correcting binary codes and of spherical codes.

3. A major difference between codes and sphere packings is that for codes over a large alphabet there are better constructions than the Gilbert-Varshamov codes based on algebraic geometry (Goppa codes). For these constructions, no analogs for spherical codes are known. (Sometimes people raise doubts if the Hamming distance is appropriate for large alphabet codes.)

4. Several basic techniques for proving upper bounds are common to all these types of codes. Those include the volume bound, the Elias bound, Delsates' LP method and a recent extension by Schrijver based on semidefinite programming.

5. The class of lattice packing is analogous to the class of linear codes.

6. There are various differences (in addition to item 3). For example, the best known kissing number (or [expected] occurrence of minimal distance from a codeword) for binary codes can be exponential in the dimension while for sphere packing only quasi-polynomial kissing numbers are known. The question if there is a sphere packing with exponential kissing number is very interesting. See this answer from the MO question a-round-lattice-with-low-kissing-number.

Answer 3

A nice expository account of some of these issues is:

Thomas M. Thomson, From Error-Correcting Codes Through Sphere Packings to Simple Groups, published by MAA, 1983.

There is also the book by Sloane and Conway:

http://neilsloane.com/doc/splag.html

entitled: Sphere Packings, Lattices, and Groups.

Answer 4

the main connection as concerned to decoding and constructions are the A and B constructions of conway and sloane in SPLAG as mentioned by Malkevitch above. construction B is similar to A accept for an additional restriction, so for brevity i will only cover construction B.

(from SPLAG : conway & sloane)
Construction B:
let C be an (n,M,d) even binary code.

construction B: 1. x = (x_1,...x_n) is a lattice center iff x is congruent (mod 2) to a codeword of C  
                2. sum{x_i,n,i=0} = 0 (mod 4)  (this is the additional restriction from construction A)

the way in which the cluster centers are defined is through a coordinate array representations of points

coordinate array of a point x = (x_1,...x_n) with integer coordinates is obtained by writing the binary expansion of coordinates in x_i columnwise, beginning with the least significant digit.

ex
               * * * - these are in complement form
1's[ 0 1 0 1 0 1 0 1 ]
2's[ 0 1 1 0 0 1 1 0 ] = {4,3,2,1,0,-1,-2,-3}
4's[ 1 0 0 0 0 1 1 1 ]
8's[ 0 0 0 0 0 1 1 1 ]

construction B: a point x is a sphere center if the 1's row of the coordinate array is a codeword c in C and the 2's row has either even weight if the weight of c is divisible by 4 or odd weight if the weight is divisible by 2 but not 4.