Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
4  
The $d=2$ case does work out by ad hoc methods. The closure of a locally maximal lattice-avoiding symmetric convex region is a polytope with a lattice point in the interior of each facet, and in the plane these belong generically (up to lattice automophism) to one of two combinatorial classes, one with two degrees of freedom and one with three. The function which measures the maximum non-surjecting dilation of the polar has a unique maximum (on the boundary of the two classes) when the polar is the 2-octahedron. –  Tracy Hall Aug 6 '10 at 4:49
add comment

3 Answers 3

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.

share|improve this answer
    
Thanks Greg! I had a version of this argument (based on Poisson summation and a generic smooth bump function used in place of J) but it gave bounds that were exponentially poor in d. I didn't realise that Fourier analysis can be used in convex geometry to give bounds polynomial in the dimension, which seems like a useful fact to know even if it still falls short of the sharpest answer. –  Terry Tao Aug 9 '10 at 9:22
1  
Of course we both use the Poisson summation formula. It is worth investigating where the $O(\sqrt{n})$ factor is lost. I don't know whether it is in the John ellipsoid step, or in the Poisson summation step, or in the original conjecture. So, a question is what is your polarity constant just for ellipsoids. If you have seen the work of Cohn-Elkies, and earlier Levenshtein, the message is that (for the sphere packing problem) Fourier analysis is not only asymptotically competitive, but also probably exactly optimal in 2, 8, and 24 dimensions. –  Greg Kuperberg Aug 9 '10 at 14:18
add comment

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.

share|improve this answer
    
Well, that's better than my answer! –  Greg Kuperberg Jun 21 '12 at 22:53
add comment

This is not really an answer, but a comment on a natural variation of the original problem: assume a convex body in $\mathbb{R}^n$ that is not necessarily centrally symmetric contains only one lattice point as an interior point. What can be said about the dual of $K$ defined with respect to the unique lattice point in its interior?

In general, you can say that the volume of the dual body cannot be too small. In this paper Balacheff, Tzanev, and I conjecture that the volume of the dual cannot be less than $(n+1)/n!$. We can prove this in dimension two under the following equivalent guise:

Theorem. The area of a convex body in the plane that intersects every integer line $mx + ny = 1$ is at least $3/2$. Moreover, equality holds only for the triangle with vertices $(1, 0)$, $(0, 1)$, $(−1,−1)$ and its images under (integer) unimodular transformations.

In higher dimensions, we rely (heavily!) on Greg Kuperberg's lower bound for the volume produc to prove.

Theorem. The volume of a convex body in $\mathbb{R}^n$ that intersects every integer hyperplane $m_1x_1 + · · · + m_nx_n = 1$ is at least $(\pi/8)^n(n + 1)/n!$.

But the fun part of the paper is that is also shows that these inequalities are (in the case of the first theorem) or should be extended to inequalities about Finsler metrics or even contact manifolds.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.