3
$\begingroup$

Let $A\subset \mathbb{R^2}$ be a finite set such that $|A|=k^2$. Let $x_i\in \mathbb{R^2}$, $i=1,2,3,4$, be four points in the plane in general position (no three lie on any line).

Let us form the multiset of cardinality $4k^2$ out of the four translates $A+x_i$ and call it $M$.

Question: Can we partition $M$ into four sets (not multisets) $A_i$, $i=1,2,3,4$ with cardinalities $(k+1)^2$, $(k-1)(k+3)$, $(k-1)^2$, $(k-1)^2$, respectively?

Question: Are there any good references for problems of this kind?

$\endgroup$
4
  • 1
    $\begingroup$ I guess the first question is, can we guarantee that the set underlying $M$ has at least $(k+1)^2$ elements? $\endgroup$ Commented Mar 14, 2018 at 22:15
  • $\begingroup$ It is. Somehow I feel that cubes should provide the worst case scenario here - that is where the numbers come from. $\endgroup$
    – TOM
    Commented Mar 15, 2018 at 10:41
  • $\begingroup$ I would search for discrete isoperimetric or discrete Brunn-Minkowski inequalities. $\endgroup$ Commented Mar 17, 2018 at 7:20
  • $\begingroup$ @TOM what does this expected "worst case scenario" look like? The hint "cubes" is not enough for me. $\endgroup$ Commented Mar 18, 2018 at 1:11

1 Answer 1

4
+50
$\begingroup$

Writing $B:=\{x_1,x_2,x_3,x_4\}$ and denoting by $S_i(A,B)$ the set of all those $c\in\mathbb R^2$ with at least $i$ representations as $c=a+b$ with $a\in A$ and $b\in B$, your question can be equivalently restated as follows: Is it true that \begin{align*} |S_1(A,B)| &\ge (k+1)^2, \\ |S_1(A,B)|+|S_2(A,B)| &\ge (k+1)^2+(k-1)(k+3) = 2k^2+4k-2, \\ |S_1(A,B)|+|S_2(A,B)|+|S_3(A,B)| &\ge (k+1)^2+(k-1)(k+3)+(k-1)^2 = 3k^2+2k-1? \end{align*} We know that the first of these three estimates holds true, following from a result of Gardner-Gronchi.

For the second estimate, I cannot presently think of anything better than \begin{align*} |S_1(A,B)|+|S_2(A,B)| &\ge \frac23\big( |S_1(A,B)|+|S_2(A,B)|+|S_3(A,B)| \big) \\ &\ge \frac23\, (3k^2+2k-1) \\ &= 2k^2+\frac43k-\frac23, \end{align*} a little off from the requested.

The last estimate is also true; it follows by observing that $S_4(A,B)=\cap_{i=1}^4(A+x_i)$; this implies $|S_4(A,B)|\le(k-1)^2$ and, as a result, \begin{align*} |S_1(A,B)|+|S_2(A,B)|+|S_3(A,B)| &= |A||B|-|S_4(A,B)| \\ &\ge 4k^2-(k-1)^2 \\ &= 3k^2+2k-1. \end{align*}


Generally, sums of the form $$ \sum_{i=1}^m |S_i(A,B)| = \sum_{c\in A+B} \min\{r_{A,B}(c),m\} $$ (where $r_{A,B}(c)$ is the number of representations $c=a+b$) were considered by Pollard in the case where $A$ and $B$ are subsets of a prime-order group. As an immediate and well-known corollary of Pollard's result, one has $$ \sum_{i=1}^m |S_i(A,B)| \ge m(|A|+|B|-m) $$ whenever $A$ and $B$ are finite sets of real numbers and $1\le m\le\{|A|,|B|\}$.

I am quite sure that sums of this sort have never been studied in the case where $A$ and $B$ are sets in $\mathbb R^n$ with $n\ge 2$. Merging the results of Gardner-Gronchi and Pollard in this situation would certainly be interesting in its own right.


One last remark. Whatever your ultimate goal is, have a look at this paper. Among the rest, it establishes an extremal property of discrete cubes in $\mathbb R^n$ in a sense very close to what you seem to be interested in.

$\endgroup$
2
  • $\begingroup$ Thank you so much for a very thorough answer. Even if it does not give me all that I want, it is way more than I truly expected to get. Thanks again! $\endgroup$
    – TOM
    Commented Mar 20, 2018 at 20:18
  • $\begingroup$ You are welcome, I am glad it helps. $\endgroup$
    – Seva
    Commented Mar 20, 2018 at 20:46

You must log in to answer this question.

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