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$
1
  • $\begingroup$ What do you know for small $k$? $\endgroup$ Commented Mar 17, 2018 at 1:32

1 Answer 1

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .