Let $[n]$ denote the set $\{0,1,...,n\}$. A subset $S\subseteq [n]$ is said to have complete double if $S+S=[2n]$. Let $m(n)$ be the smallest size of a subset of $[n]$ with complete double. My questions are:



> 
> Question 1: has this function been studied before? Any reference? It looks related to [Sidon sets](https://en.wikipedia.org/wiki/Sidon_sequence), but not quite the same.
> 
> 
> Question 2: It is easy to see that $m(n)\geq 2\sqrt{n}-1$. Can we show that $m(n)\approx 2\sqrt{n}$ asymptotically? (see the comments on how to get to $2\sqrt{2n}$).
> 
> 
> 


I found one similar question (for $\mathbb F\_2^n$ instead of integers) [here](https://mathoverflow.net/questions/188767/minimal-sumset-basis-in-the-discrete-linear-space-mathbb-f-2n) but could not find further useful references.



Size of sets with complete double
Let $S\subset [1,N]$ with $S+S=2N$. I will show that $S$ must have at least $(2.033 +o(1))\sqrt{N}$ elements for large $N$. The argument can certainly be improved, but I don't know what the right answer should be. 


Assume that $N$ is large and that $|S| =O(\sqrt{N})$ (else we are done of course). Let $r(n)$ denote the number of ways of writing $n$ as $a+b$ 
with $a$ and $b$ in $S$. Apart from the cases $a=b$ which occur for at $O(\sqrt{N})$ values, we have $r(n)\ge 2$ for $n\le 2N$ (since $a+b$ and $b+a$ 
will be counted as two different solutions). As noted in the problem, we then 
have 
$$ 
4N +O(\sqrt{N}) \le \sum\_{n\le 2N} r(n) = |S|^2, 
$$ 
which gave the asymptotic bound $|S| \ge 2\sqrt{N}+O(1)$ that we now wish to improve. 


Decompose $S$ into three sets $A$, $B$, $C$, where $A=S\cap[1,N/3)$, $B=S\cap[N/3,2N/3)$, and $C= S\cap[2N/3,N]$. Say $|A|=\alpha\sqrt{N}$, $|B|=\beta\sqrt{N}$ and $|C| =\gamma\sqrt{N}$, so that we know already that $\alpha+\beta+\gamma\ge 2+o(1)$. 


Consider $A+A$. This must cover all numbers in $[1,N/3]$ and therefore we must have 
$$ 
|A|^2 \ge \sum\_{n\le N/3} r(n) \ge 2N/3+ O(\sqrt{N}).
$$ 
Therefore we must have 
$$ 
\alpha \ge \sqrt{2/3} +o(1). \tag{1} 
$$ 


Similarly $C+C$ must cover all elements in $[5N/3,2N]$ which leads to 
$$ 
\gamma \ge \sqrt{2/3}+ o(1). \tag{2}
$$ 


Now consider $B+B$ and $A+C$. These sums are all in $[2N/3,4N/3]$ and therefore we obtain 
$$ 
\sum\_{2N/3 \le n \le 4N/3} r(n) \ge |B|^2 + 2|A| |C| +O(\sqrt{N}) = (\beta^2+2\alpha\gamma+o(1)) N. 
$$ 
Therefore 
$$ 
|S|^2 =\sum\_{n\le 2N} r(n) \ge \Big(\sum\_{n< 2N/3} +\sum\_{2N/3\le n\le 4N/3} +\sum\_{4N/3<n \le 2N} \Big) r(n) 
$$
must be at least
$$
\Big(\frac{8}{3} + \beta^2 + 2\alpha \gamma +o(1)\Big) N. \tag{3}
$$


Put $\alpha+\gamma =2\sqrt{2/3}+\delta$, with $\delta>0$. Since both $\alpha$ and $\gamma$ must be $\ge \sqrt{2/3}+o(1)$ we must have 
$$
\alpha\gamma \ge \sqrt{2/3}(\sqrt{2/3}+\delta)+o(1) = \frac 23 +\sqrt{\frac 23}\delta +o(1).
$$
If $\delta\ge 2-2\sqrt{2/3}$, then using this in (3) we would get 
$$
|S|^2 \ge \Big( 4 +2 \sqrt{2/3} \delta+o(1)\Big) N \ge 4.599N, 
$$ 
which is more than we claimed. 


Suppose then that $\delta \le 2-2\sqrt{2/3}$, so that $\beta \ge 2-(\alpha+\gamma)=2-2\sqrt{2/3}-\delta (>0)$. Using this in (3) we find 
$$ 
|S|^2 \ge \Big( 4+ 2\sqrt{2/3} \delta + (2-2\sqrt{2/3}-\delta)^2 +o(1) \Big) N.
$$
The right side is smallest for $\delta=0$, yielding 
$$
|S|^2 \ge (4+(2-2\sqrt{2/3})^2+o(1))N,
$$
which gives $|S| \ge (2.0333\ldots +o(1))\sqrt{N}$. 


