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!

  • $\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 Nov 17 '15 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 Nov 17 '15 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 Nov 17 '15 at 16:25

Your Answer

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

Browse other questions tagged or ask your own question.