6
$\begingroup$

Let $K$,$L$,$M$ be convex lattice polytopes (so their vertices are in $\mathbb{Z}^n$) in $\mathbb{R}^n$ satisfying $K+L\subseteq M+M$ (Minkowski sum). Do we always have $$|K\cap\mathbb{Z}^n|\cdot|L\cap\mathbb{Z}^n|\le |M\cap\mathbb{Z}^n|^2 ?$$

I looked at books/papers on Erhart polynomial and Brunn-Minkowski inequality etc., but did not find an satisfying answer. Any comment? Thanks.

$\endgroup$
1
  • $\begingroup$ I deleted my previous answer which is rendered irrelevant by the recent edit. I thought the measure implied by the OP was the Lebesgue measure, not the lattice point counting measure. $\endgroup$ May 14, 2012 at 19:25

3 Answers 3

6
$\begingroup$

This inequality does not necessarily hold, at least for $n\geq 3$. It is somehow connected with the fact that there is no Pick's formula in more than two dimensions since there exists a convex lattice polytope with a large volume but containing a small number of lattice points.

So, for instance, for $n=3$ let $M$ be the convex hull of the points $(0,0,0)$, $(1,1,0)$, $(0,1,2k)$ and $(1,0,2k)$. Then $|M\cap {\mathbb Z}^3|=4$, but $(M+M)\cap {\mathbb Z}^3\supset \{(1,1,t):0\leq t\leq 2k\}$. So $K$ and $L$ can be chosen as vertical segments containing $k$ lattice points each.

$\endgroup$
2
  • $\begingroup$ But what about the Ehrhart polynomial? Doesn't it sort of generalize Pick's formula? $\endgroup$ May 15, 2012 at 8:39
  • $\begingroup$ I believe "sort of" is the key word. This is a good opportunity to plug the book of M. Beck and S. Robins "computing the continuous discretely". $\endgroup$
    – Igor Rivin
    May 15, 2012 at 13:53
3
$\begingroup$

Actually, @Yoav's answer is more relevant than he thinks. In this paper:

MR1837217 (2002g:52011) Gardner, R. J.(1-WWA); Gronchi, P.(I-CNR-GA) A Brunn-Minkowski inequality for the integer lattice. (English summary) Trans. Amer. Math. Soc. 353 (2001), no. 10, 3995–4024 (electronic).

The authors prove just what they say they prove. The form of the inequality is a little different, but for example, using @Yoav's computation (which I am loath to copy and paste, he might want to undelete his answer), you get the following: $|(K+L)/2|^2 \geq |K|(|L| - n)/n!$ in dimension $n$ (assuming $L$ is full-dimensional). They have better inequalities in $2$ dimensions, but you should just read the (very well written) paper.

$\endgroup$
2
  • $\begingroup$ @Yoav now has undeleted his answer. $\endgroup$
    – Igor Rivin
    May 15, 2012 at 0:00
  • $\begingroup$ Thanks for the comment. Together with Ilya's example, my question is now answered completely. $\endgroup$
    – Li Li
    May 15, 2012 at 2:02
1
$\begingroup$

Undeleted for the sake of a full record

Your inequality seems to follow easily from the Brunn-Minkowski inequality. Namely,

$$ |(K+L)/2|^2 \ge \left[|K/2|^{1/n}+|L/2|^{1/n}\right]^{2n} \ge\left[4|K/2|^{1/n}|L/2|^{1/n}\right]^{n} =|K||L|\text. $$

$\endgroup$
1
  • $\begingroup$ This was given as answer to the original revision of the question, where $|K|$ was used (instead of $|K\cap\mathbb Z^n|$), which I took to mean the Lebesgue measure. $\endgroup$ May 15, 2012 at 0:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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