1
$\begingroup$

A sequence of natural numbers $(a_n)$ with the property that all pairwise sums of elements are distinct is called a Sidon sequence and it is proved there are at most $s(n)\sim\sqrt n$ elements of such a sequence below $n$.

My question is:
Is there an (infinite) Sidon sequence with the property:
There is an $M>0$ such that for every natural $n\geq M$ there exist $i,j$ with $n=a_i+a_j$.
(We include the case where $i=j$ )

I call this kind of sequence "complete" since it covers all positive integers from some point on.

I guess that such a sequence does not exist and surely we must have $M>1$ (this easy to prove)
I was not able to find a proof or reference.
Any help would be appreciated!

Improve this question
$\endgroup$
3
  • $\begingroup$ I think you're asking for an asymptotic basis for the integers of order 2, such that no number has more than one representation. Erdos conjectured that on the contrary in any such basis the number of representations is unbounded. I don't have Guy, Unsolved Problems In Number Theory handy, but if I did, that's the first place I'd look. In the meantime, you'll want to look at en.wikipedia.org/wiki/Erdős–Turán_conjecture_on_additive_bases $\endgroup$
    – Gerry Myerson
    Commented Nov 17, 2015 at 12:33
  • 3
    $\begingroup$ No, there is a well-known result of Erdos (mentioned on the Wikipedia page for Sidon Sequences) saying that an infinite Sidon sequence must have liminf a_n/n^2 = 0, whereas a sequence with the property you mention cannot have this property. I believe you can find the proof in Halberstam and Richert's sequences book, though I do not currently have it to hand. $\endgroup$
    – Ben Green
    Commented Nov 17, 2015 at 14:00
  • 2
    $\begingroup$ A precise formulation of the result Ben references is as follows: if the representation function of a set $A$ satisfies $r(n) \leq 1$ for all $n$ then $|A \cap [1,...,n]| \leq C \sqrt{n/ \log n}$ holds infinitely often. It is open if $r(n) \leq 2$ implies $|A \cap [1,...,n]| \leq o( \sqrt{n} ) $. The problem of showing $r(n) \leq k$ implies $|A \cap [1,...,n]| \leq o( \sqrt{n} ) $ for all $k$ implies a famous longstanding problem of Erdos and Turan. See: mathoverflow.net/questions/43995/… $\endgroup$
    – Mark Lewko
    Commented Nov 17, 2015 at 16:25

0

Reset to default

You must log in to answer this question.