# Bound of size $X\subset \mathbb{Z}/N\mathbb{Z}$ which satisfies $X+X=\mathbb{Z}/N\mathbb{Z}$

(Sorry for my poor english skill..)

Let $$N$$ be a large integer and the set $$X$$ be the subset of $$\mathbb{Z}/N\mathbb{Z}$$. For two sets $$A$$ and $$B$$, we define $$\begin{equation} A+B:=\{a+b : a\in A, b\in B\}. \end{equation}$$ Is there a bound of size X that satisfies $$X+X=\mathbb{Z}/N\mathbb{Z}$$?

• Obviously $m(m+1)/2\geqslant N$ where $m=|X|$. On the other hand, therу exist such $X$ of size roughly $C\sqrt{N}$ (take $s=[\sqrt{N}]$ and $X=\{0,1,\dots,s-1,s,2s,3s,\dots,s^2,s(s+1)\}$.) – Fedor Petrov Feb 15 at 10:59
• oeis.org/A066063 – Bullet51 Feb 15 at 13:53
• @Bullet51: Note that A066063 is only a related sequence, not the same one, since the OP is concerned with modular arithmetic. – Greg Martin Feb 15 at 15:56
• Surely, the sequence works as an upper bound. – Bullet51 Feb 15 at 16:18

Let $$f(N)$$ denote the size of the smallest $$X \subseteq \mathbb Z / N \mathbb Z$$ such that $$X+X= \mathbb Z / N \mathbb Z$$. As Fedor Petrov pointed out above, $$\sqrt{2} \sqrt{N} \leq f(N) \leq 2 \sqrt{N}.$$
As far as I am aware, the precise value of the multiplicative constant is not known. There is a fairly recent paper of Jia and Shen which improves the upper bound to $$f(N) \leq (\sqrt{3} +o(1)) \sqrt N$$.