Sphere packings of dimension 4

Introduction

Four-dimensional (4d) sphere packings have a natural application in optical communications, where the electromagnetic field has four degrees of freedom: two orthogonal polarizations and two orthogonal quadratures in each polarization [Betti90], [Betti91], [Agrell09]. However, 4d sphere packings were studied even before their applications in optical communications arose. In the context of modulation, the early works constructed a 4d signal space by encoding data simultaneously over a pair of frequencies or a pair of time slots [Welti74], [Zetterberg77], [Saha89].

In a pure mathematical context, 4d geometry is special due to the existence of the so-called D₄ lattice. If a single parity check is applied to the 4d cubic lattice, thus removing half the points, the D₄ lattice is obtained. Applying another parity check to D₄ gives the cubic lattice back, but rescaled and rotated compared with the original. This so-called set partitioning (SP) process is often applied recursively [Ungerboeck82], [Forney88].

Conversely, the D₄ lattice can be constructed by interlacing two 4d cubic lattices with each other. To see how this is possible, we first consider the two-dimensional pattern obtained by placing circles centered on a square grid. If the circles barely touch each other, there will be diamond-shaped “holes” between the circles. These size of these holes are large enough so that a circle with radius √2−1 can be fitted inside each of them, if the original circles have radius 1. The holes are also located on a square grid. If we repeat the same exercise in three dimensions, it can be shown that if unit-radius spheres are placed on a cubic grid, the holes between allows spheres of radius √3−1 to be fitted inside. And finally, generalizing the pattern to four dimensions, the holes between the unit-radius (hyper)spheres centered on a cubic lattice allows another set of spheres of radius √4−1 = 1, i.e., the same size as the original spheres. Therefore, two cubic lattices can coexist in 4d space, without reducing the minimum distance compared with a single cubic lattice. This construction yields the D₄ lattice, which has twice the density, measured as the number of spheres per unit volume, of the cubic lattice.

If the number of points is large, the best 4d sphere packings are thus subsets of the D₄ lattice. Good packings of selected sizes were designed in [Welti74] by selecting D₄ lattice points inside suitably chosen hyperspheres. These packings are included, rotated and rescaled into integer coordinates, under the name w4_*.txt.

Optimal lattice subsets (which are not necessarily the optimal packings) are included under the name l4_*.txt. These sphere packings are spherical subsets of the D₄ lattice. Optimality is guaranteed by enumerating and testing a finite number of possible centroids inside the fundamental simplex [Conway82] of the lattice. The applied algorithm [Agrell14] is a straightforward generalization of the algorithm in [Chow95] for optimizing 2-dimensional lattice subsets.

Conjectured optimal sphere packings of sizes up to M ≤ 32 are collected online in Sloane's unpublished tables [Sloane-web]. These packings are included here, sometimes after rescaling and rotation, under the name c4_*.txt.

The most power-efficient 4d packing, in the sense of maximizing γ, is the biorthogonal packing with size M = 8, whose power efficiency is γ = 3/2 = 1.761 dB. Its coordinates are all 0 except one, which is ±1.

The 24 nearest neighbors of the D₄ lattice form the 24-cell. Coxeter remarked that a “peculiarity of four-dimensional space is the occurrence of the 24-cell, having no analogue above or below” [Coxeter73, p. 289].

Database

References

[Agrell14]

E. Agrell, unpublished, 2014–2023.

[Sloane-web]

http://neilsloane.com/cluster (previously http://www2.research.att.com/~njas/cluster/), accessed April 2010.