3
$\begingroup$

Let $A$ be a finite set in $\mathbb{R}^2$ of $k^2$ elements and consider a set $B=\{x_1,x_2,x_3,x_4\}$ such that the points in $B$ are in general position (no three points on a line).

Question 1: Is it true that $|A+B|\geq (k+1)^2$?

Question 2: Is it true that $|\cap_{i}(A+x_i)|\leq (k-1)^2$?

Question 3: If either of 1-2 are true, is it the case that one of the extremal sets $A$ is a discrete square?

$\endgroup$
  • $\begingroup$ What do you know for small $k$? $\endgroup$ – Joseph O'Rourke Mar 17 '18 at 1:32
3
$\begingroup$

As shown by Gardner and Gronchi ("A Brunn-Minkowski Inequality for the Integer Lattice", equality (8) / Theorem 6.6), if $A,B\subset\mathbb R^n$ are finite sets such that $B$ has full dimension, then $$ |A+B|^{1/n} ≥ |A|^{1/n} + \frac1{(n!)^{1/n}}\, (|B|−n)^{1/n}. $$ (This estimate should be viewed as a real-world analogue of the ideal-world "discrete Brunn-Minkowski inequality".)

In your situation ($n=2,\ |A|=k^2,\ |B|=4$) this yields $$ |A+B|^{1/2} \ge k + 1, $$ answering in the affirmative your first question.

For the second question, observe that letting $I:=\cap_i(A+x_i)$, we have $I-B\subseteq A$. Hence, applying the Gardner-Gronchi inequality once again, $$ k = |A|^{1/2} \ge |I-B|^{1/2} \ge |I|^{1/2} + 1, $$ which gives an affirmative answer to your second question.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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