Minkowski-Hlawka bound

(Rogers, 1947)

Let \(p\) be an arbitrary prime, \(\mathbb{F}_p\) be the field with \(p\) elements and let \(\pi_p:\mathbb{Z}^{d} \rightarrow \mathbb{F}_p^{d}\) be the natural coordinate-wise projection map.

Let \(\mathcal{L}_p\) be the set of sub-lattices of \(\mathbb{Z}^{d}\) that are pre-images of one-dimensional subspaces in this projection map scaled to become unit covolume, i.e. \[\mathcal{L}_p = \{ C_p \pi_p^{-1}( \mathbb{F}_p v) \ | \ v \in \mathbb{F}_p^d \setminus \{ 0\} \}, C_p = p^{-\left(1-\frac{1}{d}\right)} .\]

Consider a compactly supported continuous function \(f:\mathbb{R}^{d} \rightarrow \mathbb{R}\) and the lattice-sum function \(\Phi_f:X_d \rightarrow \mathbb{R}\). Then the following holds. \[\begin{align} \lim_{ p \rightarrow \infty}\left[ \frac{1}{\# {\mathcal{L}}_p}\sum_{ \Lambda \in {\mathcal{L}}_p} \Phi_{f}\left( \Lambda\right) \right] = \int_{\mathbb{R}^{d}} f(x) dx. \end{align}\]

It is well known that the theorem above can be used to effectively generate lattices that reach Minkowski bound of lattice packing density. That is, this can be used to effectively show that

\[\begin{align} c_{d} \ge 2-\varepsilon, \end{align}\] for any \(\varepsilon>0\). Here \(c_{d}\) is the lattice packing constant in \(d\)-dimensions defined as \[\begin{align} c_{d} = \sup\{ \mathop{\mathrm{vol}}(B_{R}(0)) \ | \ \exists \ g \in SL_d(\mathbb{R})\ | \ B_{R}(0) \cap g \mathbb{Z}^{d} = \{ 0\} \}. \end{align}\]

Indeed, we can substitute \(f\) as the indicator function of \(B_{R}(0)\), a ball of radius \(R\) at \(0\), we know from this theorem that for large enough \(p\) and some \(v \in \mathbb{F}_{p}^{d} \setminus \{ 0\}\), the lattice \(p^{-\left( 1 - \frac{1}{d} \right)} \pi_{p}^{-1} \left( \mathbb{F}_p v \right)\), which is a unit covolume lattice, must intersect trivially with the ball of volume \(2- \varepsilon\) for any \(\varepsilon >0\). This recovers recovers the well-known Minkowski-Hlawka bound on lattice packings.

Since the average is over the number of points in the intersection of a ball with a lattice, we will expect this average to be biased towards the bad lattices, since a short vector will produce lots of lattice points in a ball. A small average (or even the fact that it converges), hints that there should be lots of lattices with large intersections with the ball.

And even then, there are no known methods to generate lattices that achieve these bounds in a sub-exponential running times, or explicitly descriptions of one such sequence of lattices reaching this bound. Avi Widgerson in a talk called this the problem of finding hay in a haystack.

References