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

Your Answer

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

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