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

Improve this question
$\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$
    – Fedor Petrov
    Feb 15, 2019 at 10:59
  • $\begingroup$ oeis.org/A066063 $\endgroup$
    – LeechLattice
    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$
    – Greg Martin
    Feb 15, 2019 at 15:56
  • $\begingroup$ Surely, the sequence works as an upper bound. $\endgroup$
    – LeechLattice
    Feb 15, 2019 at 16:18

1 Answer 1

Reset to default
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$.

Improve this answer
$\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.