22
$\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} \}$.
Improve this question
$\endgroup$
0

2 Answers 2

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ I apologize but what do you mean by “quadratic density”? $\endgroup$
    – RFZ
    Dec 13 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$
    – Emil Jeřábek
    Dec 13 at 9:06
32
$\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.

Improve this answer
$\endgroup$
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$
    – Emil Jeřábek
    Dec 6 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.