3
$\begingroup$

$\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!

$\endgroup$
8
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Seva Sep 25 '16 at 7:12
  • $\begingroup$ 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... $\endgroup$ – Johnny T. Sep 26 '16 at 17:10
  • $\begingroup$ 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. $\endgroup$ – David Conlon Sep 29 '16 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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