# What is the minimal density of a set A such that A+A = N?

Thinking about the four square theorem and related questions, I found myself wondering: What is the minimal density of a set $$A \subset \{0, 1, 2, ... \}$$ such that $$A + A = \mathbb{N}$$?

What I know:

1. If A has less than quadratic density, then $$A + A$$ is not $$\mathbb{N}$$ by a simple counting argument.
2. There are quadratic density sets $$A$$ such that $$A + A + A$$ is $$\mathbb{N}$$, such as the triangular numbers.
3. For any positive constant $$\varepsilon > 0$$ there is a set of density $$\varepsilon$$ satisfying $$A + A = \mathbb{N}$$: Let $$k = \lceil 1/\varepsilon \rceil$$, and set $$A = [k-1] \cup \{ kn : n \in \mathbb{N} \}$$.

Let $$A_{\mathrm{even}}$$ ($$A_{\mathrm{odd}}$$) be the set of integers whose binary expansion has $$0$$ at every even (odd, respectively) position, and $$A=A_{\mathrm{even}}\cup A_{\mathrm{odd}}$$. Then all three sets have quadratic density, and $$A+A=A_{\mathrm{even}}+A_{\mathrm{odd}}=\mathbb N$$.

• I apologize but what do you mean by “quadratic density”?
– RFZ
Commented Dec 13, 2023 at 5:57
• I took the term from the question, so you should have asked the OP instead. I assume it means $|A\cap[0,n)|=\Theta(\sqrt n)$. Commented Dec 13, 2023 at 9:06

It is easy to see that quadratic density is both required and sufficient. The question is then of the leading coefficient.

Let $$A$$ be such that $$A+A = \mathbb{N}$$, and let $$A(n) = \lvert A \cap [0,n] \rvert$$ the number of its elements not exceeding $$n$$. We are interested in the limiting behavior of $$A(n) / \sqrt{n}$$.

Emil Jeřábek's construction here has $$A(n)/\sqrt{n} \approx 2$$ when $$n$$ is large.

Gerd Hofmeister has constructed a set $$A$$ with $$\underline{\lim} \frac{A(n)}{\sqrt{n}} = \sqrt{7/2} < 1.870829.$$ The idea is to take an infinite union of finite bases $$A_i$$, with each $$A_i+A_i$$ covering a suitable initial segment of the nonnegative integers and $$A_i$$ having a suitable cardinality.

Using a more recent construction of finite additive bases (by me), a similar infinite-union construction should give $$\sqrt{294/85} < 1.859792$$.

Those were upper bounds on what is needed. For the other direction we can also borrow results from finite additive bases. Let $$A_n = A \cap [0,n]$$, then we must have $$A_n + A_n \supseteq [0,n]$$, so $$\lvert A_n+A_n \rvert > n$$, and by a straightforward counting argument, $$\lvert A_n \rvert > \sqrt{2n} \pm o(\sqrt{n})$$. So we get a lower bound $$\lim \frac{A(n)}{\sqrt{n}} > \sqrt{2}.$$ This can also be improved by taking tighter results from the finite additive bases.

Hofmeister, Gerd, Thin bases of order two, J. Number Theory 86, No. 1, 118-132 (2001). ZBL0998.11011.

Kohonen, Jukka, An improved lower bound for finite additive 2-bases, J. Number Theory 174, 518-524 (2017). ZBL1359.11013.

• Another nitpick: the set in my answer does not have $A(n)/\sqrt n\sim2$ for $n\to\infty$. The ratio oscilates between $2$ (for $n$ of the form $4^k$) and $\frac32\sqrt3$ (for $n=\lfloor4^k/3\rfloor$). Commented Dec 6, 2023 at 17:50