The following problem can become a bit of an obsession. I'm curious if there are any serious strategies for attacking it. The problem is a certain Erdos-Turan conjecture.

Let $ B \subseteq {\mathbb N} $. If, for any natural number $k$, we denote by $ r_B(k)$ the number of pairs $(i,j)$ in $B\times B$ such that $i+j=k$.

We call $ B $ an additive basis of order two if $ r_B $ is never $ 0 $.

Erdos-Turan Conjecture for order two bases: If $ B $ is an additive basis of order 2, then $ r_B $ is unbounded.

Are there any serious strategies for attacking this conjecture? If so, what are they?

Application of Szemeredi's theorem quickly handles sets $B$ of positive upper density. The interesting case is the zero upper density case.

The most recent thing I've seen on this is the paper

Sandor, Csaba A note on a conjecture of Erdos-Turan, INTEGERS: Electronic Journal of Combinatorial Number Theory 8 no. 1 (2008).

(This question may be better for mathstackexchange, but I'm curious if there are any developed lines of attack for research questions like this. Harebrained subquestion: Can Green-Tao type techniques be leveraged for this problem?)

  • 1
    $\begingroup$ Huh. I was about to say that the correct spelling is "harebrained," but... worldwidewords.org/qa/qa-hai1.htm $\endgroup$ – Qiaochu Yuan Oct 28 '10 at 18:40
  • 1
    $\begingroup$ Sounds like a great problem! thanks for asking. $\endgroup$ – Gil Kalai Oct 28 '10 at 18:50
  • $\begingroup$ You're welcome, Gil. This drove me crazy for a while many years ago, and is really fun to think about! $\endgroup$ – Jon Bannon Oct 29 '10 at 16:14
  • 1
    $\begingroup$ I suspect that Green-Tao techniques could prove this for some zero density bases, but not all of them; you'd need to show your basis was dense inside some pseudorandom set, which itself is fairly dense, so there is a limit on how sparse your set can be to apply these techniques; this is fine for applications to the primes, which are still pretty dense, but you can have bases which are really sparse so beyond the reach of this method. $\endgroup$ – Thomas Bloom Feb 14 '11 at 6:16
  • $\begingroup$ Anything new on this? I don't see any published work since 2006. $\endgroup$ – user49237 Apr 6 '14 at 18:03

It is fair to say that no one has a clue. There are two current ideas for "attack":

1) Erdős-Fuchs theorem which asserts that it is not the case that $r$ is nearly constant

2) The argument of Erdős that if $r(n)\leq 1$ for all $n$ (such a $B$ is called Sidon set), then $\liminf |B\cap \{1,\dotsc,n\}|/\sqrt{n/\log n}<100$

The proofs of both results can be found in the lovely book by Halberstam and Roth. Sandor's result is similar to Erdős-Fuchs, but puts a clever twist on it, which permits him to prove a result as strong as his. The argument of Erdős has been successfully extended to Sidon set of even order (that means that all sums of $2m$ terms are distinct). It might sound trivial since if $B$ is a Sidon set of order $2m$, then $m$-fold sumset of $B$ with itself is almost a Sidon set, but does need to do work to get around this ``almost''. It is an open problem whether there is an extension to Sidon sets of odd order.


Another approach not yet mentioned is to attempt to extract a 'thin' basis from a given basis. This is along the lines of the stronger form of the Erdos-Turan conjecture, due to Erdos:

If $A \subset \mathbb{N}$ is an additive basis (of order 2), then $\displaystyle \limsup_{n \rightarrow \infty} r_A(n)/\log(n) > 0$. In essence, that a 'thin' basis that Erdos gave using probabilistic arguments is as thin as possible (in a 1956 paper, Erdos proved the existence of bases $A$ with the property that $r_A(n) = \Theta(\log(n))$, thus answering an old question of Sidon). Thus a natural question to ask is whether for a given basis $B$ does there exist a sub-basis $A$ such that $r_A(n) = O(\log(n))$. This question has been answered positively for Waring bases by Van Vu, see http://www.math.rutgers.edu/~vanvu/papers/numbertheory/thinwaring.pdf

On the other hand, his methods rely heavily on the number theoretic properties of the Waring bases and the probabilistic method. It would take a major advance in machinery to prove a similar theorem for arbitrary additive bases. Nonetheless, it is an idea.

Edit: One may also check out Trevor Wooley's 2003 paper "On Vu's thin basis theorem in Waring's problem" for an improvement of Vu's result.


Hi Jon,

I was recently thinking that non-standard numbers might be helpful.


  • 1
    $\begingroup$ Hi, Adam! I was thinking of you when I posted this. $\endgroup$ – Jon Bannon Nov 23 '10 at 19:49
  • 1
    $\begingroup$ Hey Jon, let's get together - I have a couple of theorems - not sure how important they are but they are as good as anything else out there. $\endgroup$ – Adam Meikle Nov 23 '10 at 20:12

Another approach is the polynomial approach in a 2006 paper by Borwein, Choi, and Chu, found at http://www.cecm.sfu.ca/personal/pborwein/PAPERS/P194.pdf

Essentially, the idea is to show that for each $k$, a set of polynomials $E(k)$ (defined in the paper) is finite. This would imply that the Erdos-Turan conjecture is true.

However, there seems to be no general way to do this; the paper proved that $E(7)$ is finite through computer search and hence showed that $r_{B,2}(n)$ cannot be bounded above by 7.


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.