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?



Separating points of shifts of a finite set in the plane
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](https://mathoverflow.net/a/295422/9924) that the first of these three estimates holds true, following from a result of [Gardner-Gronchi](http://www.ams.org/journals/tran/2001-353-10/S0002-9947-01-02763-5/S0002-9947-01-02763-5.pdf). 


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](https://mathoverflow.net/a/295422/9924) $|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](https://academic.oup.com/jlms/article-abstract/s2-8/3/460/851896?redirectedFrom=PDF) 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](http://math.haifa.ac.il/seva/Papers/ShellOrder.pdf). 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.


