An intriguing inverse sumset problem

Question

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) 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...

Answer 1

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