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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .