Marcelo Campos, Matthew Jenssen, Marcus Michelen and, and Julian Sahasrabudhe: Striking new Lower Bounds for Sphere Packing in High Dimensions

Combinatorics and more 2023-12-20

A few days ago, a new striking paper appeared on the arXiv

A new lower bound for sphere packing

by Marcelo Campos, Matthew Jenssen, Marcus Michelen, and Julian Sahasrabudhe

Here is the abstract:

We show there exists a packing of identical spheres in $\mathbb R^d$ with density at least $\displaystyle (1-o(1))\frac{d \log d}{2^{d+1}}\,$ as $d\to\infty$ This improves upon previous bounds for general $d$ by a factor of order $\log d$ and is the first asymptotically growing improvement to Rogers’ bound from 1947.

Let me tell you a little about this amazing result. Congratulations, Marcelo, Matthew, Marcus, and Julian!

In an unrelated news: Congratulations to József Balogh, Robert Morris, Wojciech Samotij, David Saxton and Andrew Thomason for being awarded the Steele Prize for seminar contribution to research.

I am thankful to Zachary Chase for telling me about this development.

A brief history

Earlier lower bounds: Every saturated sphere packing (namely when you cannot squeeze in an additional sphere) have density $2^{-d}$ . (This is because when you double all spheres you will get a covering of space.) In 1905, this was improved by a factor of $2 + o(1)$ by Minkowski. The first asymptotic improvement was by Rogers in 1947 and he gave a lower bound of $\displaystyle 2^d d c(1+o(1))$ . Roger’s value for the constant $c$ was $c=2/e$ , and this value was improved to $1.68$ , $2$ , $6/e$ (when $d$ is divisible by 4), and then by Venkatesh to $c=65963$ (when $d$ is large; I wonder, how large?). Venkatesh also proved a lower bound of the form $2^d d \log \log d$ along a sparse sequence of dimensions. Here is the link to Venkatesh’s striking paper from a decade ago. The best upper bound going back to Kabatjanskii and Levenstein is of the form $2^{-(.599+o(1))d}$ .

A theorem about graphs

One interesting aspect of the new paper is the use of combinatorial methods and of graph-theory. The following theorem is closely related to results of Ajtai-Komlos-Szemeredi and of Shearer. For a graph $G$ , $\Delta (G)$ denote the maximum degree of a vertex in $G$ and $\Delta_2 (G)$ denote the maximum codegree, namely, the maximum number of common neighbours a pair of distinct vertices in G can have. ( $\alpha(G)$ is the independence number of $G$ .)

Theorem: Let $G$ be a graph on $n$ vertices, such that $\Delta(G)\le \Delta$ and $\Delta_2(G)\le C \Delta (\log \Delta)^{-c}$ . Then

$\displaystyle \alpha (G) \le (1-o(1))\frac {n \log \Delta}{\Delta},$

where $o(1)$ tends to 0 as $\Delta \to \infty$ and we can take $C=2^{-7}$ and $c=7$ .

This theorem (of much independent interest) is closely related to a theorem of Shearer for triangle free graphs, and an earlier theorem of Ajtai-Komlos-Szemeredi on Ramsey numbers $r(3,n)$ . The technique of proof is known as the Rodl nibble (or the semi-random method). Moving from Shearer-type theorems to results about sphere packing was pioneered twenty years ago by Krivelevich, Litsyn, and Vardy. (Their paper reproved a $\displaystyle 2^d d c(1+o(1))$ lower bound using Shearer’s theorem.)

The graph G(X,r)

If $X$ is a subset of $\mathbb R^d$ the graph $G(X,r)$ has the set $X$ as its set of vertices and two vertices are adjacent if their distance is at mosr $2r$ . The proof of the new sphere packing bound is based on discretization step, where you start with a huge ball $\Omega$ and find a finite set of point $X \subset \Omega$ such that $G(X,r)$ has appropriate degrees and codegrees. The discretization step allows applying the graph theoretic theorem directly and to achieve a sphere packing based on the large independent set, guaranteed by the theorem, that $G(X,r)$ contains.

Connection to physics and the replica method

The paper mentions the notion of amorphous sphere packings in physics and a prediction of Parisi and Zamponi based on the “replica method” that the largest density of “amorphous sphere packings” is $(1+o(1)d \log d2^{-d}$ . This is twice the value achieved in the paper, and the authors even predict that their graph theoretic theorem (and hence their sphere packing bound) can be improved by a factor 2. Roughly speaking, amorphous sphere packings have no long-term correlations.

Spherical codes and kissing numbers.

The paper contains similar constructions for spherical codes, and, in particular, for kissing numbers.

KLS