Start with a natural number $k$, and choose natural numbers $K=\{n\_1,\ldots,n\_k\}$ which are pairwise distinct. For each $1\leq j\leq k$, choose another integer $i\_j$ such that $0\leq i\_j\leq 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.


**Here is an interesting example**


Fix a large $X\gg 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 (see [here](https://en.wikipedia.org/wiki/Landau%E2%80%93Ramanujan_constant)) and $|A| \sim \sqrt{X}$


I kind of feel that $\sqrt{k}$ is the worst possible size of $A$.


Any help is appreciated.


Thank you...



An intriguing inverse sumset problem
Your question is basically asking for sets where the sum set has maximal size, which is attainable by e.g. a geometric progression. More precisely, in your set-up:


Given $k$ the minimum possible size of $A$ is the smallest $n$ such that $\binom{n+1}{2}\geq k$ (so asymptotically $n\sim (2k)^{1/2}$).


This is an upper bound since we can first choose $A=\{1,2,4,\ldots,2^{n-1}\}$ and then $K$ to be an appropriately sized subset of $A+A$.


This is a lower bound since your setup implies in particular that $K\subseteq A+A$, and if $\lvert A\rvert=n$ then the trivial upper bound for the size of $A+A$ is $\binom{n+1}{2}$.


