Question

Let $K \subset {\bf R}^d$ be a symmetric convex body (an open bounded convex neighbourhood of the origin with $K = -K$) with the property that $K + {\bf Z}^d \neq {\bf R}^d$, i.e. the projection of $K$ to the standard torus ${\bf R}^d/{\bf Z}^d$ is not surjective, or equivalently $K$ is disjoint from some coset $x + {\bf Z}^d$ of the standard lattice. My question is: what does this say about the polar body

$$K^* := \{ \xi \in {\bf R}^d: \xi \cdot x < 1 \hbox{ for all } x \in K \}?$$

Intuitively, the property $K + {\bf Z}^d \neq {\bf R}^d$ is a "smallness" condition on K, and is thus a "largeness" condition on $K^*$.

If $K^*$ contains a non-trivial element $n$ of $2 {\bf Z}^d$, then $K$ is contained in the strip ${ x: |n \cdot x| < 1/2 }$, and will thus avoid the coset $x+{\bf Z}^d$ whenever $x \cdot n = 1/2$. So this is a sufficient condition for $K + {\bf Z}^d \neq {\bf R}^d$, but it is not necessary. Indeed, if one takes $K$ to be the octahedron

$$K := \{ (x_1,\ldots,x_d) \in {\bf R}^d: |x_1|+\ldots+|x_d| < d/2 \}$$

then $K$ avoids $(1/2,\ldots,1/2)+{\bf Z}^d$, but the dual body

$$ K^* = \{ (\xi_1,\ldots,\xi_d) \in {\bf R}^d: |\xi_1|,\ldots,|\xi_d| < 2/d \}$$

is quite far from reaching a non-trivial element of $2 {\bf Z}^d$.

On the other hand, by using the theory of Mahler bases or Fourier analysis one can show that if $K + {\bf Z}^d \neq {\bf R}^d$, then $K^*$ must contain a non-trivial element of $\varepsilon_d {\bf Z}^d$ for some $\varepsilon_d > 0$ depending only on $d$. However the bounds I can get here are exponentially poor in $d$.

Based on the octahedron example (which intuitively seems to be the "biggest" convex set that still avoids a coset of ${\bf Z}^d$), one might tentatively conjecture that if $K + {\bf Z}^d \neq {\bf R}^d$, then the closure of $K^*$ contains a non-trivial element of $\frac{2}{d} {\bf Z}^d$. I do not know how to prove or disprove this conjecture (though I think the $d=2$ case might be worked out by ad hoc methods, and the $d=1$ case is trivial), so I am posing it here as a question.

Answer 1

Hi Terry. Here is a sketch of an argument that should yield the estimate $1/\varepsilon_d = O(d^{3/2})$. That is not your full conjecture, but it is getting there. I haven't checked every detail of the more delicate second half of the argument, but it should work.

First, let me rephrase the question with only polynomial overhead. The contrapositive of your statement is that if the integer lattice is a lattice packing of $K^*$, then it is a lattice covering of $\varepsilon_d K$ (up to a factor of 2). You can replace $K^*$ by the largest inscribed ellipsoid $E$, and then John's theorem says that $\sqrt{d} \cdot K \supseteq E^*$. Then, after a linear transformation, we can say that $E = E^*$ is the round unit ball $B = B_1(0)$, i.e., the $\ell^2$ unit ball. The contrapositive hypothesis is that lattice $\Lambda$ is a lattice packing of $B$, i.e., a unit sphere packing. You want to bound the sphere covering radius of $\Lambda^*$.

By taking a Fourier transform on $L^2(\mathbb{R}^d)$, what you know is that $\Lambda^*$ is a "1-design" in the sense of Delsarte. (This is with a scaled Fourier transform so that none of the geometric lengths have factors of $\pi$.) If $f$ is a sufficiently regular function whose Fourier transform is supported on the unit ball in $\mathbb{R}^d$, then the integral of $f$ on $\mathbb{R}^d$ equals its sum on $\Lambda^*$. I have a paper on $t$-designs [arXiv:math/0405366] which suggests a method that could give you a covering radius, although in my paper it was the analytically easier case of a compact domain. The idea is to find an $f(x) = f(||x||_2)$ whose integral is positive, yet which is non-positive for $||x||_2 > c$, and whose Fourier transform satisfies the support condition. Then $\Lambda^*$ must have a lattice point in the ball $B_c(0)$, and indeed in $B_c(p)$ for any $p$. I call this the "positive island" method.

In one stage of the argument in my paper, I made a positive island function on the manifold $\mathbb{C}P^d$ of the form $P(z)/(a-z)$, where $P$ is a Jacobi polynomial (with indices suppressed) and $a$ is its last zero. This was for $t$-designs on $\mathbb{C}P^n$ (and later the simplex, using the moment map). There is a similar formula for ordinary spherical $t$-designs on $S^d$. To make this expression relevant to your question, you can take the limit as the degree $t \to \infty$ and the positive island shrinks to a point. In this limit, the geometry of the manifold becomes approximately Euclidean and so approximates your question. The island function $P(z)/(a-z)$ limits to the function $$f(x) = \frac{J(||x||_2)^2}{c^2-||x||^2_2}$$ on $\mathbb{R}^d$, where $J(r)$ is a hyperspherical Bessel function and $c$ is its first zero.

So, for roundabout reasons, what should happen is that the integral of this $f(x)$ vanishes and its Fourier transform has the right support property. If you perturb $f$ slightly, you can make its integral positive. I imagine that there is a direct argument for the properties of this $f$, but I did not work at it. However, I did check a few cases numerically with Maple and it seems to work. For instance, the integral on $\mathbb{R}^3$ of $$f(x) = \frac{(\sin x)^2}{x^2(\pi^2-x^2)}$$ vanishes.

Now, the first zero of the first hyperspherical Bessel function in $\mathbb{R}^d$ is the same as the first zero $j_{(d-2)/2,1}$ of an ordinary Bessel function. I believe that this number is $O(d)$. This would yield the estimate $1/\varepsilon_d = O(d^{3/2})$, since you also get a factor of $O(d^{1/2})$ from John's theorem.

Answer 2

If I understand the question correctly, I think the best known bound is still that of Wojciech Banaszczyk: "Inequalities for Convex Bodies and Polar Reciprocal Lattices in $R^n$ II: Application of $K$-Convexity". Discrete & Computational Geometry 16(3): 305-311 (1996) http://dx.doi.org/10.1007/BF02711514

The bound is $1/\epsilon_d = O(d\cdot \log(d))$. Not yet the optimal answer you were seeking, but within a log factor from optimal.