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

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

-
Huh. I was about to say that the correct spelling is "harebrained," but... worldwidewords.org/qa/qa-hai1.htm –  Qiaochu Yuan Oct 28 '10 at 18:40
Thanks, Qiaochu! I never even thought to check!!!! –  Jon Bannon Oct 28 '10 at 18:44
Sounds like a great problem! thanks for asking. –  Gil Kalai Oct 28 '10 at 18:50
You're welcome, Gil. This drove me crazy for a while many years ago, and is really fun to think about! –  Jon Bannon Oct 29 '10 at 16:14
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. –  Thomas Bloom Feb 14 '11 at 6:16

## 4 Answers

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.

Adam

-
Hi, Adam! I was thinking of you when I posted this. –  Jon Bannon Nov 23 '10 at 19:49
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. –  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.

-
Thanks for these answers, Stanley! –  Jon Bannon Feb 28 '11 at 11:59