No Sidon sequence which is an asymptotic basis of order $2$

$\omega \subseteq \mathbb{R}^+$ is called a Sidon sequence, if all the sums $a + a' \ (a, a' \in \omega, a \leq a')$ are distinct, and it is an asymototic basis of order $2$, if any positive integer $n$ sufficiently large can be expressed as a sum of $2$ elements of $\omega$.

According to the article I am reading, apparently it is not too difficult to show that there does not exist $\omega$ such that it is a Sidon sequence and also an asymototic basis of order $2$, but I am not quite seeing how to prove this at the moment.

I was wondering if someone could possibly give me an explanation on how to show this? Thank you very much!

Sidon set $A$ has at most $\sqrt{n}(1+o(1))$ elements not exceeding $n$ (*). So, $A+A$ contains at most $|A|(|A|+1)/2=n(1/2+o(1))$ elements not exceeding $n$, unlike an asymptotic basis of order 2.

(*) may be proved as follows: fix $M$, denote your elements $x_1<x_2<\dots<x_m\leqslant n$ and consider all differences $x_j-x_i$ for $i<j\leqslant i+M$. They are all distinct, there areat least, say, $M(m-M)$ such differences and the sum of them does not exceed $\frac{M(M+1)}2 n$, thus $\frac{M(M+1)}2 n\geqslant (M(m-M))^2/2$, optimizing by $M$ or just by taking very large $M$ we get what we need: $m\leqslant \sqrt{n}(1+o(1))$.

An answer to your question can be found in this old paper by Erdős and Turán:

https://www.renyi.hu/~p_erdos/1941-01.pdf

In this paper, they also state their beautiful conjecture on additive bases: if $B$ is a subset of the natural numbers and $f(n)$ represents the number of ways of writing $n$ as a sum of two elements in $B$, then $f(n) > 0$ for $n \geq n_0$ implies that $\limsup_{n \rightarrow \infty} f(n) = \infty$. This conjecture is still wide open.

• For the non-asymptotic version, Borwein, Choi, and Chu ams.org/journals/mcom/2006-75-253/S0025-5718-05-01777-1/… has shown that if $B$ is a basis of order $2$, then there are integers with at least eight (ordered) representations as a sum of two elements of $B$. – Seva Sep 25 '16 at 7:12
• Thank you very much for this reference! By the way, where exactly in the paper does it answer my question? I haven't been able to spot it... – Johnny T. Sep 26 '16 at 17:10
• Under header III, using a little complex analysis, they show that the number of representations as a sum of two elements in $B$ cannot be fixed after a given point. This is more general than what Fedor proves in his comment, but his proof has the advantage of being completely elementary. – David Conlon Sep 29 '16 at 20:20