On a Problem of Sidon in Additive Number Theory, and on some Related Problems

To the memory of S. Sidon. Let 0 < a, < a,. .. be an infinite sequence of positive integers. Denote by f(n) the number of solutions of n=a i +a;. About twenty years ago, SIDON 1) raised the question wether there exists a sequence a; satisfying f(n) > 0 for all n > 1 and lim f(n)'nE = 0 for all t > 0. In the present note, I will construct such a sequence. In fact, my sequence will satisfy (1) 0 < f(n) < c l log n for all n > l. (The c's will denote suitable positive absolute constants .) It seems probable that (1) can not be strengthened very much. TURAN and I conjectured 2) that if f(n) > 0 for all n > n0 then lim sup f(n)=-; this conjecture seems very hard to prove. A still stronger conjecture would be the following : Let a,< a.,<. .. be an infinite sequence of integers satisfying 0). < ck2. Then lim sup f(n) _ c,~. We will not be able to construct our sequences explicitely, but we will be able to show that in some sense almost all sequences satisfy (1). The idea of our construction is the following. Define A k as the least integer greater than c2 k"i 2'2', 2. Pick in all possible ways A,, integers from the interval , (2k 2'~+') One can do this in (A~) ways. One thus obtains the integers J < b2kl <. .. < b.4. I will show that if for each k one neglects o(Ak) " bad" choices of the b('''' and forms a sequence a, < a 2 <. .. from any of the "good" choices of the b;'') (k-1,2,. .. ; 1-i :5A,,) the sequence a,< a .,<. .. will satisfy (1). Thus roughly speaking (1) will be satisfied for almost all choices of the b(k'. We have to make one more remark. For small values of k it may happen that c2 2 k,12 k' 2 > 2k. In this case the b(k) are simply all the integers of the interval (2 k, 2k} 1). Also, it is clearly enough to show that f(n) > 0 for all 1) Oral communication .