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!

Improve this question
$\endgroup$
0

2 Answers 2

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

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.

Improve this answer
$\endgroup$
3
  • 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
    Commented Sep 25, 2016 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.
    Commented Sep 26, 2016 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
    Commented Sep 29, 2016 at 20:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .