Start with a natural number $k$, and choose natural numbers $K={n_1,ldots,n_k}$ which are pairwise distinct. For each $1leq jleq k$, choose another integer $i_j$ such that $0leq i_jleq n_j$.

Question :What is the minimum size of the set $A={i_1,n_1-i_1, i_2,n_2-i_2,ldots, i_k,n_k-i_k}$ ?

I did some googling and found the term “sumset” kept floating around in my search results. As I am entirely new to the additive combinatorics and additive number theory, I was totally lost and couldn’t make out how to solve my problem.

I did find a neat geometric (graph theoretic) interpretation to my problem.

**Graph Theoretic Interpretation**

Suppose that we have $2k$ points arranged in a $k times 2$ array. It is easier to think of this as a $ktimes 2$ matrix $A=(a_{(j,epsilon)})$ where $epsilonin{1,2}$ and $1leq jleq k$. The points are arranged in such a way that $a_{(j,1)} = i_j$ and $a_{(j,2)} = n_j-i_j$. Now we draw lines between two points if and only if they are equal. Now, without loss of generality, after re-indexing the $n_j$‘s and substituting $i_jmapsto n_j-i_j$ if necessary, we can assume that the lines are either horizontal or vertical. Furthermore, since the $n_j$‘s are pariwise distinct, we cannot have the following different types of structures,

- Any type of rectangle which has at least three sides (that is in any orientation)
- Two vertical lines, that is amounting to $a_{(j,1)} = a_{(j+1,1)}$ and $a_{(j,2)} = a_{(j+1,2)}$

What you get after joining is a disjoint union of lines and points. The size of the set in question is now the number of disjoint components in the resulting diagram. I did some examples by hand and I am getting the minimum size of the set to be of the order of $k/4$. But,

**Here is an interesting example**

Fix a large $Xgg 0$, and choose $n_j$‘s to be precisely all those integers less than $X$ which can be written as sum of two squares, and choose $i_j$ such that both $i_j$ and $n_j-i_j$ are perfect squares. Clearly in this case, $|K| sim X/sqrt{log(X)}$ from a classical result of Landau (which I am currently unable to find the reference for) and $|A| sim sqrt{X}$

Any help is appreciated.

Thank you…