24
$\begingroup$

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

2 Answers 2

38
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I apologize but what do you mean by “quadratic density”? $\endgroup$
    – RFZ
    Commented Dec 13, 2023 at 5:57
  • 1
    $\begingroup$ 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)$. $\endgroup$ Commented Dec 13, 2023 at 9:06
33
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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$). $\endgroup$ Commented Dec 6, 2023 at 17:50

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.