Or Ordentlich, Oded Regev and Barak Weiss: New bounds for Covering Density!

Update (June 3, 2020): The paper New bounds on the density of lattice coverings is now on the arXiv.

Barak Weiss lectured about his breakthrough results with Or Ordentlich, and Oded Regev, at a Simons Institute workshop: Lattices: Geometry, Algorithms and Hardness.

It is a famous problem what is the densest (or, most efficient) packing of unit balls in Euclidean n-dimensional spaces and, of course, you can ask the same questions for other convex bodies. A sort of a dual problem, also famous, is the question of the most efficient covering the n-dimensional Euclidean space by balls or by translates of other convex bodies.

A very basic insight is that covering is much more efficient than packing. Can you explain the reason for that? The only thing that came up to my mind was that convex sets are roundish from the outside but not from the inside which makes it easier to cover with them.

But how efficiently can we cover the n-dimensional Euclidean space with translates of a convex body $K$?

C.A. Rogers with coauthors had some very fundamental results regarding covering (and packing) in the 50s and 60s. Or Ordentlich, Oded Regev and Barak Weiss have made a terrific improvement for one of the main questions in this area. They showed that for every convex set K, you can find a lattice of determinant 1, and r>0  such that rK+L = \mathbb R^n and

{\rm vol} (rK) \le cn^2.

The best earlier upper bound was n^{\log \log n}.

One surprising aspect of the proof is the use of finite field Kakeya-type questions. Since the breakthrough by Zeev Dvir, many people had hopes for applications from the finite fields results to the Euclidean setting (in particular, to the Euclidean Kakeya problem itself) and it is rare to see such applications. The proof here relies on results by  Dvir, Kopparty, Saraf, Sudan, and Lev. The Ordentlich-Regev-Weiss paper is not yet on the arXiv but the lecture gives a good picture about the results and the proofs.

The definition of the covering density of L with respect to a convex body K

The definition of the covering density of K

Old results for the Euclidean ball

Old results for general convex bodies

The first main result

 

The required finite field Kakeya theorem.

This entry was posted in Combinatorics, Computer Science and Optimization, Geometry and tagged , , . Bookmark the permalink.

3 Responses to Or Ordentlich, Oded Regev and Barak Weiss: New bounds for Covering Density!

  1. N says:

    Is there a conjecture about how small vol(rK) should be? Is there a known lower bound?

    • Gil Kalai says:

      For the Euclidean ball the covering density behave roughly like n. Of course, there are bodies like the cube that tile space so they pack and cover perfectly.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s