Ferkans — Interactive Telecom Tutor

How Dense Can Packings Get? The Two-Sided Question

Having seen the best lattices available in each dimension, the natural question is: how dense could a lattice packing be, if we were free to pick any lattice? This question has two sides:

Lower bound (existence). How dense can we prove some lattice to be? This is the Minkowski–Hlawka theorem: a random-lattice argument shows that some lattice achieves density $\ge \zeta(n) / 2^{n-1}$ , a bound that was essentially tight for 70 years.
Upper bound (impossibility). How dense can any lattice (or any packing) possibly be? This is the Kabatiansky–Levenshtein bound and its successors, culminating in the Cohn–Elkies linear-programming bound used by Viazovska.

The two bounds sandwich the optimum $\Delta_n$ between roughly $2^{-n}$ (Minkowski–Hlawka) and $2^{-0.5990 n}$ (Kabatiansky– Levenshtein). The exponential gap is a separate $70$ -year-open problem; in dimensions $8$ and $24$ the gap was closed by Viazovska's exact constructions.

This section states both bounds, sketches the Minkowski–Hlawka argument in the style of Shannon's random coding, and explains why these bounds shape the theory of coded modulation in Part IV.

Definition:
Hermite Constant

The Hermite constant in dimension $n$ is $\gamma_n \;=\; \sup_{\Lambda} \, \frac{d_{\min}^2(\Lambda)}{V(\Lambda)^{2/n}},$ taken over all $n$ -dimensional lattices. Equivalently, $\gamma_n$ is the supremum of $d_{\min}^2(\Lambda)$ over lattices with $V(\Lambda) = 1$ , or equivalently the supremum of $4 \rho^2 / V^{2/n}$ .

$\gamma_n$ is related to the best lattice packing density $\Delta_n$ by $\Delta_n \;=\; V_n \cdot \gamma_n^{n/2} / 2^n, \qquad \delta_n = \Delta_n / V_n = \gamma_n^{n/2} / 2^n.$ The Hermite constant is known exactly for $n \le 8$ and $n = 24$ :

$n$	$\gamma_n$	Extremal lattice
$1$	$1$	$\mathbb{Z}$
$2$	$2/\sqrt{3}$	$A_2$
$3$	$\sqrt[3]{2}$	$A_3 = D_3$
$4$	$\sqrt{2}$	$D_4$
$5$	$\sqrt[5]{8}$	$D_5$
$6$	$\sqrt[3]{64/3}$	$E_6$
$7$	$\sqrt[7]{64}$	$E_7$
$8$	$2$	$E_8$
$24$	$4$	$\Lambda_{24}$

For other dimensions the Hermite constant is unknown — only upper and lower bounds are available.

Note that $\gamma_8 = 2$ exactly, with extremiser $E_8$ — a particularly clean value. $\gamma_{24} = 4$ is also exact, with extremiser $\Lambda_{24}$ . Both of these exact values were known (from Conway–Sloane Ch. $1$ ) for decades before Viazovska's $2017$ proof of global sphere-packing optimality.

,

Theorem: Minkowski–Hlawka Lower Bound on Densest Lattice Packing

For every $n \ge 2$ , there exists an $n$ -dimensional lattice $\Lambda$ with packing density $\Delta(\Lambda) \;\ge\; \frac{\zeta(n)}{2^{n-1}}, \qquad \zeta(n) = \sum_{k=1}^\infty k^{-n}.$ In particular, $\Delta_n \ge 2^{-n+1}$ (the zeta factor is close to $1$ for large $n$ ).

The proof is an averaging argument, in the same spirit as Shannon's random-coding theorem: we construct a random lattice, compute the expected number of short vectors, and apply Markov's inequality to pull out a lattice with few short vectors and hence large packing radius. The randomisation is over a specific parameterised family of lattices (due to Siegel) whose density is easy to compute on average.

Show Hint

Consider the family of lattices obtained from $\mathbb{Z}^n$ by a uniformly random unimodular transformation with determinant $\rho^{-n/2}$ .

Compute the expected number of nonzero lattice points inside a ball of radius $r < 1$ .

Apply Markov's inequality to extract a lattice with no points in the ball.

Proof

The random lattice family

Consider the family of lattices $\Lambda_\mathbf{M} = \mathbf{M} \mathbb{Z}^n$ where $\mathbf{M}$ is drawn from a suitable probability distribution on $\mathrm{SL}_n(\mathbb{R})$ (Siegel's invariant measure). Normalise to $|\det \mathbf{M}| = 1$ so $V(\Lambda_\mathbf{M}) = 1$ . The density $\Delta(\Lambda_\mathbf{M}) = \rho_\mathbf{M}^n V_n$ depends on the packing radius, which is half the minimum distance.

Expected count of short vectors

For any radius $r$ with $r < 1$ (so $r^n V_n < V_n$ ), Siegel's mean-value theorem gives $\mathbb{E}[|\{\mathbf{x} \in \Lambda_\mathbf{M} \setminus \{0\} : \|\mathbf{x}\| < r\}|] \;=\; \frac{r^n V_n}{V(\Lambda)} \cdot \frac{1}{\zeta(n)} \cdot (\text{minor const}) \;=\; \frac{r^n V_n}{\zeta(n)}.$ (The $1/\zeta(n)$ factor comes from restricting to primitive lattice vectors — lattice points whose coordinates have no common factor.)

Markov's inequality

If the expected count is $< 1$ , then with positive probability the count is zero. Setting the bound $r^n V_n / \zeta(n) < 1$ gives $r^n < \zeta(n) / V_n$ , so a lattice with packing radius $\rho \ge r = (\zeta(n) / V_n)^{1/n}$ exists. Therefore $\Delta_n \;\ge\; \rho^n V_n \;\ge\; \zeta(n).$ This gives the single-factor bound; the additional factor of $2$ is lost when we convert "primitive-vector density" to "all-vector density", giving the stated $\zeta(n) / 2^{n-1}$ . $\blacksquare$

, ,

The Minkowski–Hlawka Argument is Shannon's Random Coding

The Minkowski–Hlawka proof proceeds by average, not by construction. Shannon's channel-coding theorem proceeds by averaging error probability over a uniformly random codebook, then picking a realisation at least as good as average. Minkowski–Hlawka averages packing density over a randomly chosen lattice, then picks a realisation at least as good as average.

This parallel is not accidental. Loeliger ( $1997$ ) showed that the random-coding arguments for the AWGN channel and the random-lattice arguments for sphere packing are two faces of the same measure- theoretic identity. It explains why Erez–Zamir's capacity-achieving lattice code (Ch. $16$ ) works the way it does: a random lattice achieves the AWGN capacity in expectation, and so a deterministic lattice exists that achieves it.

Theorem: Kabatiansky–Levenshtein Upper Bound (Informational)

For every $n$ , the density of any sphere packing in $\mathbb{R}^n$ satisfies $\log_2 \Delta_n \;\le\; -0.5990 n + o(n).$ Combined with the Minkowski–Hlawka lower bound $\log_2 \Delta_n \ge -n + o(n)$ , we have $-n \;\lesssim\; \log_2 \Delta_n \;\lesssim\; -0.5990 n$ for large $n$ . The gap is approximately $0.4 n$ bits, or roughly $1$ dB per dimension in coding-gain language.

Kabatiansky–Levenshtein's bound comes from a linear-programming formulation of sphere packing: pack spheres of radius $1$ in the unit sphere at the origin (kissing configurations), and use orthogonal polynomial LP bounds to constrain the number of kissing neighbours. Cohn–Elkies ( $2003$ ) improved the bound in specific dimensions using a Fourier-analytic LP, which Viazovska then sharpened to equality for $n = 8, 24$ .

Show Hint

The proof uses Gegenbauer polynomials and the Delsarte method — beyond our scope.

We state the bound and illustrate its gap to Minkowski–Hlawka.

Proof

Statement only

The Kabatiansky–Levenshtein bound is the sharpest known upper bound that is independent of dimension (at $0.5990 n$ ). Dimension- specific bounds — Cohn–Elkies ( $2003$ ) and its descendants — can sharpen it to tight in $n = 8, 24$ as Viazovska and collaborators showed. In most other dimensions, the gap between the best known lattice and Kabatiansky–Levenshtein remains of order $2^{0.4 n}$ .

Practical interpretation

For the coded-modulation designer: no code can beat the Kabatiansky–Levenshtein density in any dimension. The gap between the best known lattice and this upper bound is the "reserve capacity" that might be unlocked by better lattice constructions — or, per Viazovska, is sometimes zero (no reserve; the best lattice is already optimal). $\blacksquare$

,

Packing Density vs Dimension: Bounds and Best-Known Lattices

Log-scale plot of $\log_2 \Delta_n$ (or equivalently center density $\delta_n$ ) vs dimension $n$ , showing four curves: (i) the cube $\mathbb{Z}^n$ (baseline), (ii) the best known lattice in each dimension (from Conway–Sloane Table 1.2), (iii) the Minkowski– Hlawka lower bound on $\Delta_n$ , and (iv) the Kabatiansky– Levenshtein upper bound. The gap between the two bounds grows linearly with $n$ . The $n = 8$ and $n = 24$ points sit on the upper bound (Viazovska). A toggle lets you add or remove the Minkowski–Hlawka bound.

Parameters

Show Minkowski-Hlawka lower bound on best density

Theorem: Viazovska's Theorems: $E_8$ and $\Lambda_{24}$ Close the Gap

In dimensions $n = 8$ and $n = 24$ , $\Delta_8 = \Delta(E_8) = \frac{\pi^4}{384}, \qquad \Delta_{24} = \Delta(\Lambda_{24}) = \frac{\pi^{12}}{12!}.$ These are the first — and, as of $2024$ , only — dimensions $n > 3$ in which the densest packing is known exactly and proved. The Kabatiansky–Levenshtein upper bound is tight for $n = 8, 24$ (after Cohn–Elkies refinement), and the lattices $E_8$ and $\Lambda_{24}$ achieve it.

What makes $8$ and $24$ exceptional is that the Cohn–Elkies LP has a "magic" Schwartz function whose zero structure exactly matches the minimum norms of $E_8$ (resp. $\Lambda_{24}$ ). Viazovska constructed the magic function using Eisenstein series and theta functions of half-integer weight — a tour de force of modular-form theory. In every other dimension the LP does not close, and a genuine gap between lower and upper bounds persists.

Show Hint

We state the result and connect it to the Hermite constants $\gamma_8 = 2, \gamma_{24} = 4$ .

The proof uses Poisson summation plus a modular magic function; see Viazovska 2017 and the Cohn–Kumar–Miller–Radchenko–Viazovska companion paper.

Proof

Proof technique sketch

The Cohn–Elkies linear-programming method starts from Poisson summation: for a Schwartz function $f : \mathbb{R}^n \to \mathbb{R}$ with nonnegative Fourier transform, applied to a sphere packing with balls of radius $r$ , one obtains $\Delta \;\le\; \frac{\widehat{f}(0)}{f(0)} \, \frac{1}{(2 r)^n} \, V_n$ provided $f(\mathbf{x}) \le 0$ for $\|\mathbf{x}\| \ge 2 r$ . Finding the best such $f$ is a linear programme. Viazovska's $2017$ breakthrough was to construct this optimal $f$ explicitly for $n = 8$ (and with her collaborators for $n = 24$ ) using modular forms.

Consequence for the Hermite constant

For $E_8$ : $d_{\min}^2 = 2$ , $V(E_8) = 1$ , so $\gamma_8 = d_{\min}^2 / V^{2/n} = 2$ . For $\Lambda_{24}$ : $d_{\min}^2 = 4$ (in standard normalisation), $V = 1$ , so $\gamma_{24} = 4$ . Viazovska et al. proved these are the global suprema over all lattices in those dimensions. The result also applies to non-lattice packings, making these the globally optimal sphere packings. $\blacksquare$

, ,

Why This Matters: Forward to Ch. 16: Lattice Codes Achieving AWGN Capacity

The Minkowski–Hlawka bound tells us that random lattices, with high probability, have density close to the asymptotic bound. This is the key existence result used by Erez–Zamir ( $2004$ ) to prove that lattice encoding and decoding achieves the AWGN capacity $\tfrac12 \log_2(1 + \text{SNR})$ — the first non-Gaussian construction to do so. Chapter 16 unfolds this argument in detail, showing how a sequence of random lattices plus MMSE scaling plus dithering converges to capacity-achieving performance. The ingredients are exactly the ones we've introduced in this chapter: Voronoi regions, second moments, theta series, and the Minkowski–Hlawka existence theorem.

Why This Matters: Forward to Ch. 17: LAST Codes and DMT Optimality

El Gamal, Caire, and Damen ( $2004$ ) took the nested-lattice construction one step further: a MIMO channel version where one lattice is used for coding and a sublattice for shaping, and the whole construction achieves the diversity–multiplexing trade-off (DMT) optimally on MIMO fading channels. These are the LAST codes (Lattice space–time codes), one of the CommIT group's major contributions. Chapter 17 builds LAST on top of the lattice vocabulary of this chapter; you cannot state the LAST result without first having Minkowski–Hlawka and a concrete lattice family in hand.

🔧Engineering Note

Asymptotic Bounds vs Practical Coding Gain

The gap between Minkowski–Hlawka and Kabatiansky–Levenshtein is about $\approx 0.4 n$ bits of density, or $\approx 1$ dB of coding gain per added dimension. In practice, using $E_8$ in an $8$ -D lattice code gives a $3.01$ -dB coding gain over $\mathbb{Z}^8$ ; using $\Lambda_{24}$ in $24$ -D gives $6.02$ dB. Both are well below the asymptotic bounds but are already more than practical decoding complexity can support: a 4-QAM + LDPC code in a CMOS modem delivers comparable gain at a tiny fraction of the complexity.

The message for the practitioner: lattice theory is the upper bound on what coded modulation can achieve in a given dimension. Practical codes usually stop well short of this upper bound and make up the gap with shaping (Ch. 4) and iterative decoding (Parts II and V). The asymptotic bounds of this section are benchmarks, not design targets.

Practical Constraints

•
Minkowski–Hlawka: guarantees $\Delta \ge \zeta(n)/2^{n-1}$ asymptotically, but does not construct an explicit lattice.
•
Kabatiansky–Levenshtein: upper bound $\Delta \le 2^{-0.599 n}$ , sharp only at $n = 8, 24$ (Viazovska).
•
Practical codes: $3$ – $6$ dB of coding gain in $n = 8, 24$ ; shaping (Ch. 4) adds up to $1.53$ dB independently.

Common Mistake: Large Kissing Number is Not the Same as High Density

Mistake:

Assuming that a lattice with many short vectors ("large kissing number") automatically has a high packing density. For example, the densest $8$ -D lattice $E_8$ has kissing number $240$ , but the Laminated lattice $\Lambda_8^*$ (often confused with $E_8$ in textbooks) also has kissing number $240$ and the same packing density: they are dual and isomorphic. However, a different lattice with kissing number $400$ in $8$ -D does not exist (Odlyzko–Sloane kissing bound), and if it did, its density could still be lower than $E_8$ 's because it might have a much larger fundamental volume.

Correction:

Density and kissing number are independent invariants. Density is $\Delta = \rho^n V_n / V$ ; kissing number is the count of minimum vectors. Conway–Sloane list both separately. To compare lattices, look at $\Delta$ (or equivalently center density $\delta$ ); to predict error-rate multiplicity, look at $K$ . These are different numbers.

Most Dimensions Are Still Open

As of $2024$ , the densest sphere packing is known and proved in dimensions $n = 1, 2, 3, 4, 5, 8, 24$ (Hales in $2014$ for $n=3$ , Viazovska in $2017$ for $n=8, 24$ ). For all other dimensions the optimal packing is conjectured but not proven. In particular:

$n = 4, 5$ : known via $D_4, D_5$ , but the proof (Korkine–Zolotarev, $1877$ ) is less celebrated than Viazovska's.
$n = 6, 7$ : conjecturally $E_6, E_7$ , but unproven.
$n = 9, 10, 11$ : the "Laminated lattices" $\Lambda_9, \Lambda_{10}, \Lambda_{11}$ are believed best but unproven.
$n = 12, 16, 32$ : $K_{12}, \Lambda_{16}, \Lambda_{32}$ are best known but unproven.
$n = 48, 56, 60, 72$ : extremal constructions via algebraic number fields.

For coded modulation, the takeaway is: use the best known lattice (Nebe–Sloane database), know that better lattices may or may not exist but haven't been found, and build your code assuming the best-known density is what you can deliver. In practice, this is more than enough.

Minkowski–Hlawka bound

A lower bound on the densest lattice packing in $n$ dimensions: $\Delta_n \ge \zeta(n) / 2^{n-1}$ . Proved by a random-lattice averaging argument in the spirit of Shannon's random coding.

Kabatiansky–Levenshtein bound

An upper bound on the density of any sphere packing in $\mathbb{R}^n$ : $\log_2 \Delta_n \le -0.5990 n + o(n)$ . Refined and sharpened to tight in $n = 8, 24$ by Cohn–Elkies and Viazovska.

Quick Check

Which of the following best describes the "gap" between Minkowski–Hlawka and Kabatiansky–Levenshtein?

Zero in every dimension.

Exponentially small: $O(2^{-n})$ .

Exponential: roughly $2^{0.4 n}$ in density.

Proved zero by Viazovska in all dimensions.

Correction:

Exponential: roughly

2^{0.4 n}

in density.

The lower bound is $\Delta \ge 2^{-n+1}$ (ignoring log factors) and the upper bound is $\Delta \le 2^{-0.599 n}$ . The ratio is $2^{(1 - 0.599) n} = 2^{0.401 n}$ , or about $1.2$ dB per dimension. Closing this gap is the central open problem of sphere-packing theory.

Quick Check

In how many dimensions $n \ge 4$ is the globally densest sphere packing currently known and proved?

One ( $n = 8$ only).

Two ( $n = 8$ and $n = 24$ ).

Four ( $n = 4, 5, 8, 24$ ).

All of them.

Correction:

Four (

n = 4, 5, 8, 24

).

$n = 4$ : $D_4$ is densest (Korkine–Zolotarev $1877$ ); $n = 5$ : $D_5$ (same authors); $n = 8$ : $E_8$ (Viazovska $2017$ ); $n = 24$ : $\Lambda_{24}$ (Cohn–Kumar–Miller–Radchenko–Viazovska $2017$ ). The case $n = 3$ is also known (Hales's Kepler-conjecture proof $1998/2014$ ), but we asked for $n \ge 4$ .

Key Takeaway

Packing density is bounded above by Kabatiansky–Levenshtein at $2^{-0.599 n}$ and below by Minkowski–Hlawka at $2^{-n+1}$ — an exponential-in- $n$ gap that is the central open problem of sphere- packing theory. In dimensions $n = 8$ and $n = 24$ , Viazovska and collaborators closed the gap and proved that $E_8$ and $\Lambda_{24}$ are globally optimal. The Minkowski–Hlawka existence argument (random-lattice averaging) is the direct analogue of Shannon's random-coding argument; Ch. 16 will use it to build a capacity- achieving lattice code for the AWGN channel, and Ch. 17 will use a nested-lattice variation to achieve the DMT-optimal LAST code on MIMO fading channels. The lattice-theoretic bounds we have proved are the absolute upper envelope for Part IV's constructions.

Packing Bounds and Viazovska's Theorems

How Dense Can Packings Get? The Two-Sided Question

Definition: Hermite Constant

Theorem: Minkowski–Hlawka Lower Bound on Densest Lattice Packing

The random lattice family

Expected count of short vectors

Markov's inequality

The Minkowski–Hlawka Argument is Shannon's Random Coding

Theorem: Kabatiansky–Levenshtein Upper Bound (Informational)

Statement only

Practical interpretation

Packing Density vs Dimension: Bounds and Best-Known Lattices

Parameters

Theorem: Viazovska's Theorems: E8E_8E8​ and Λ24\Lambda_{24}Λ24​ Close the Gap

Proof technique sketch

Consequence for the Hermite constant

Why This Matters: Forward to Ch. 16: Lattice Codes Achieving AWGN Capacity

Why This Matters: Forward to Ch. 17: LAST Codes and DMT Optimality

Asymptotic Bounds vs Practical Coding Gain

Common Mistake: Large Kissing Number is Not the Same as High Density

Most Dimensions Are Still Open

Minkowski–Hlawka bound

Kabatiansky–Levenshtein bound

Quick Check

Quick Check

Key Takeaway

Definition:
Hermite Constant

Theorem: Viazovska's Theorems: $E_8$ and $\Lambda_{24}$ Close the Gap