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

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

2010-10-28T16:40:04Z

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 by Boris Bukh for Are any good strategies known for Erdos-Turan conjecture on additive bases of order two?

2010-10-28T19:20:43Z

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 by Adam Meikle for Are any good strategies known for Erdos-Turan conjecture on additive bases of order two?

2010-11-23T18:17:01Z

Hi Jon,

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

Adam

Answer by Stanley Yao Xiao for Are any good strategies known for Erdos-Turan conjecture on additive bases of order two?

2011-02-13T23:59:07Z

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 by Stanley Yao Xiao for Are any good strategies known for Erdos-Turan conjecture on additive bases of order two?

2011-02-28T05:50:37Z

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.