Computer Science/Discrete Mathematics Seminar II
A simple proof of a reverse Minkowski inequality
We consider the following question: how many points with bounded norm can a "non-degenerate" lattice have. Here, by a "non-degenerate" lattice, we mean an n-dimensional lattice with no surprisingly dense lower-dimensional sublattices.
Dadush and Regev conjectured an upper bound on this quantity (which they called a "reverse Minkowski-type inequality") and showed a number of applications---from cryptography to Brownian motion on flat tori. In joint work with Regev in 2016, we proved this conjecture via a rather tedious proof using two heavy hammers from convex geometry.
Recently, Eldan showed how to remove the tedium from the proof, and even more recently, Dadush showed how to remove the heavy hammers (to prove a slightly different result). The resulting (still unpublished) streamlined proof is quite nice, and we present it more-or-less in full.