3
$\begingroup$

(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}$?

$\endgroup$
  • 9
    $\begingroup$ 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)\}$.) $\endgroup$ – Fedor Petrov Feb 15 at 10:59
  • $\begingroup$ oeis.org/A066063 $\endgroup$ – Bullet51 Feb 15 at 13:53
  • $\begingroup$ @Bullet51: Note that A066063 is only a related sequence, not the same one, since the OP is concerned with modular arithmetic. $\endgroup$ – Greg Martin Feb 15 at 15:56
  • $\begingroup$ Surely, the sequence works as an upper bound. $\endgroup$ – Bullet51 Feb 15 at 16:18
6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.