Bo’az Klartag: Striking new Lower Bounds for Sphere Packing in High Dimensions

Combinatorics and more 2025-04-09

Two day ago, a new striking paper appeared on the arXiv

Lattice packing of spheres in high dimensions using a stochastically evolving ellipsoid, by Bo’az Klartag.

Abstract: We prove that in any dimension $latex n$ there exists an origin-symmetric ellipsoid $\mathcal {E} \subset \mathbb R^n$ of volume $c n^2$ that contains no points of $\mathbb Z^n$ other than the origin, where $c>0$ is a universal constant. Equivalently, there exists a lattice sphere packing in $\mathbb R^n$ whose density is at least $c n^2 \cdot 2^{-n}$ . Previously known constructions of sphere packings in $\mathbb R^n$ had densities of the order of magnitude of $n\cdot 2^{-n}$ , up to logarithmic factors. Our proof utilizes a stochastically evolving ellipsoid that accumulates at least $cn^2$ lattice points on its boundary, while containing no lattice points in its interior except for the origin.

This is an amazing breakthrough. Congratulations Bo’az!

Bo’az and I live in (essentially) the same apartment building in “Kohav Hatzafon” (כוכב הצפון – “the star of the north”) neighborhood of Tel Aviv. Yesterday evening, we met at a new coffee place in the neighborhood and I heard about his new proof — and gained a fresh perspective on the history of the problem. I hope to write a more detailed post about the mathematics behind Bo’az proof and its historical context, but for now, let me mention one important ingredient of the proof below.

Before that, here are links to two relevant posts from a year and a half ago. The first is about the improved lower bound $c n \log n \cdot 2^{-n}$ achieved by Marcelo Campos, Matthew Jenssen, Marcus Michelen, and Julian Sahasrabudhe (and with some history and connections), and the second is about the limitation of the linear programming method for upper bounds for packing and codes.

A few words about the mathematics, as I understood from Bo’az. An argument dating back to Minkowski shows that the problem of finding the densest sphere packing is equivalent to finding the ellipsoid of maximum volume that contains no points of $\mathbb Z^n$ other than the origin. (If the ellipsoid contains non-zero lattice points only on its boundary, that’s acceptable as well, since a slight shrinking will eliminate those.)

Bo’az described a stochastic process for constructing an ellipsoid that has no non-zero lattice points in its interior, but many such points on its boundary. Once the process reaches a stage where an integral point lies on the boundary, Bo’az insists on keeping that point on the boundary permanently. This constraint effectively reduces the dimension of the parameter space for the ellipsoids by one each time such a point is fixed.

There are $n(n+1)/2$ parameters defining an ellipsoid, and they can be used to construct an ellipsoid with no non-zero interior lattice points and $n(n+1)$ integral points in the boundary.(The factor of two comes from the central symmetry of the ellipsoid.) What is the expected volume of such an ellipsoid? As I understand it, the computation is rather involved, and the result is that the expected volume is proportional $n^2$ .

What is the largest volume $E(n)$ of an ellipsoid that misses all non zero integral points? (As we already mentioned, $2^{-n}E(n)$ is the maximum density of a sphere packing in $\mathbb R^n$ .) This is somewhere between $cn^2$ and $1.32^n$ . It is a common belief that $E(n) \le (1+\epsilon)^n$ . (I can see some reasons for disbelief as well.) Venkatesh conjectured that $E(n)$ grows at most polynomially in $n$ and Bo’az writes that it is not entirely unlikely that the answer is quadratic in $n$ .