Are any good strategies known for Erdos-Turan conjecture on additive bases of order two?

Question

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?)

Answer 1

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.

Answer 2

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.

Answer 3

Hi Jon,

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

Adam

Answer 4

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.