MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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. – Yoav Kallus May 14 '12 at 19:25
up vote 6 down vote accepted

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.

share|cite|improve this answer
But what about the Ehrhart polynomial? Doesn't it sort of generalize Pick's formula? – Felix Goldberg May 15 '12 at 8:39
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". – Igor Rivin May 15 '12 at 13:53

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.

share|cite|improve this answer
@Yoav now has undeleted his answer. – Igor Rivin May 15 '12 at 0:00
Thanks for the comment. Together with Ilya's example, my question is now answered completely. – Li Li May 15 '12 at 2:02

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. $$

share|cite|improve this answer
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. – Yoav Kallus May 15 '12 at 0:32

Your Answer


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.