4
$\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$
4
  • 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$ Commented Feb 15, 2019 at 10:59
  • $\begingroup$ oeis.org/A066063 $\endgroup$ Commented Feb 15, 2019 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$ Commented Feb 15, 2019 at 15:56
  • $\begingroup$ Surely, the sequence works as an upper bound. $\endgroup$ Commented Feb 15, 2019 at 16:18

1 Answer 1

7
$\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 and acknowledge you have read our privacy policy.

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