A few days ago, a new striking paper appeared on the arXiv
by Marcelo Campos, Matthew Jenssen, Marcus Michelen, and Julian Sahasrabudhe
Here is the abstract:
We show there exists a packing of identical spheres in 
with density at least 
as 
This improves upon previous bounds for general 
by a factor of order 
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 unrelated news: Congratulations to József Balogh, Robert Morris, Wojciech Samotij, David Saxton and Andrew Thomason for being awarded the Steele Prize for seminal 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 
. (This is because when you double all spheres you will get a covering of space.) In 1905, this was improved by a factor of 
by Minkowski. The first asymptotic improvement was by Rogers in 1947 and he gave a lower bound of 
. Roger’s value for the constant 
was 
, and this value was improved to 
, 
, 
(when is divisible by 4), and then by Venkatesh to 
(when is large; I wonder, how large?). Venkatesh also proved a lower bound of the form 
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 
.
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 
, 
denote the maximum degree of a vertex in and 
denote the maximum codegree, namely, the maximum number of common neighbours a pair of distinct vertices in G can have. (
is the independence number of .)
Theorem: Let be a graph on 
vertices, such that 
and 
. Then
where 
tends to 0 as 
and we can take 
and 
.
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 
. 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 lower bound using Shearer’s theorem.)
The graph G(X,r)
If 
is a subset of the graph 
has the set as its set of vertices and two vertices are adjacent if their distance is at mosr 
. The proof of the new sphere packing bound is based on discretization step, where you start with a huge ball 
and find a finite set of point 
such that 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 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 
. 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, and it added to recent improvements on these questions. A spherical code is a collection of points on the unit sphere 
of pairwise angle at least 
. Denote by 
the maximal cardinality of such a spherical code. Let 
be the surface area of a spherical cup of radius normalized by the surface area of the entire sphere . (We assume that 
.) Only recently, Jenssen, Joos, and Perkins improved the easy bound of 
(just look at a saturated family of spherical caps of radius 
) by a linear factor in the dimension. The new paper adds an additional factor.
Update: Interesting comments over Facebook.
Combinatorics and more 
A small (especially by comparison to the amazing work that the post is about) typo but I mention it as it is slightly confusing: presumably the Steele prize was for a “seminal” contribution to research rather than a “seminar” one.
GK: Thanks; corrected. (Perhaps the words seminal and seminar has similar roots.)
Also, 2^{-d} changes to 2^d at some point.
GK: Thanks, corrected (I hope).
Pingback: Fun with Algorithms (FUN 2024) | Combinatorics and more
Matthew Jenssen told me some further interesting things related to the new breakthrough. A natural question is if the new method leads also to improvements for the Gilbert Varshamov (GV) bound for error correcting codes. Matthew mentioned Jiang and Vardy’s lower bound for error-correcting codes which gave a linear improvement over GV (using graph theoretic ideas) https://arxiv.org/abs/math/0404325 and said that he does not expect more than a constant improvement (as long as you stay with the standard metric of![[q]^n](https://s0.wp.com/latex.php?latex=%5Bq%5D%5En&bg=ffffff&fg=333333&s=0&c=20201002)
which seems to be forced.) Jiang and Vardy used Ajtai-Komlos-Szemeredi theorem. Matthew also mentioned a large amount of literature on statistical physics approaches (both rigorous and non-rigorous) to error-correcting codes, starting (perhaps) with the work of Sourlas https://www.nature.com/articles/339693a0.
Pingback: On the Limit of the Linear Programming Bound for Codes and Packing | Combinatorics and more