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

Question

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

Answer 1

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

Answer 2

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.