Are any good strategies known for Erdos-Turan conjecture on additive bases of order two? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T10:21:37Z http://mathoverflow.net/feeds/question/43995 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/43995/are-any-good-strategies-known-for-erdos-turan-conjecture-on-additive-bases-of-ord Are any good strategies known for Erdos-Turan conjecture on additive bases of order two? Jon Bannon 2010-10-28T16:40:04Z 2012-04-20T01:13:00Z <p>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. </p> <p>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$. </p> <p>We call $B$ an additive basis of order two if $r_B$ is never $0$.</p> <p>Erdos-Turan Conjecture for order two bases: If $B$ is an additive basis of order 2, then $r_B$ is unbounded. </p> <blockquote> <p>Are there any serious strategies for attacking this conjecture? If so, what are they?</p> </blockquote> <p>Application of Szemeredi's theorem quickly handles sets $B$ of positive upper density. The interesting case is the zero upper density case. </p> <p>The most recent thing I've seen on this is the paper </p> <p>Sandor, Csaba <em>A note on a conjecture of Erdos-Turan</em>, INTEGERS: Electronic Journal of Combinatorial Number Theory 8 no. 1 (2008).</p> <p>(This question may be better for mathstackexchange, but I'm curious if there are any developed lines of attack for research questions like this. <em>Harebrained subquestion:</em> Can Green-Tao type techniques be leveraged for this problem?)</p> http://mathoverflow.net/questions/43995/are-any-good-strategies-known-for-erdos-turan-conjecture-on-additive-bases-of-ord/44004#44004 Answer by Boris Bukh for Are any good strategies known for Erdos-Turan conjecture on additive bases of order two? Boris Bukh 2010-10-28T19:20:43Z 2010-10-28T19:20:43Z <p>It is fair to say that no one has a clue. There are two current ideas for "attack":</p> <p>1) Erdős-Fuchs theorem which asserts that it is not the case that $r$ is nearly constant</p> <p>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}&lt;100$</p> <p>The proofs of both results can be found in the <a href="http://www.ams.org/mathscinet-getitem?mr=687978" rel="nofollow">lovely book by Halberstam and Roth</a>. 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 <a href="http://www.ams.org/mathscinet-getitem?mr=1234964" rel="nofollow">has been successfully extended</a> 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.</p> http://mathoverflow.net/questions/43995/are-any-good-strategies-known-for-erdos-turan-conjecture-on-additive-bases-of-ord/47128#47128 Answer by Adam Meikle for Are any good strategies known for Erdos-Turan conjecture on additive bases of order two? Adam Meikle 2010-11-23T18:17:01Z 2010-11-23T18:17:01Z <p>Hi Jon,</p> <p>I was recently thinking that non-standard numbers might be helpful.</p> <p>Adam</p> http://mathoverflow.net/questions/43995/are-any-good-strategies-known-for-erdos-turan-conjecture-on-additive-bases-of-ord/55362#55362 Answer by Stanley Yao Xiao for Are any good strategies known for Erdos-Turan conjecture on additive bases of order two? Stanley Yao Xiao 2011-02-13T23:59:07Z 2011-02-17T18:50:39Z <p>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:</p> <p>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 <a href="http://www.math.rutgers.edu/~vanvu/papers/numbertheory/thinwaring.pdf" rel="nofollow">http://www.math.rutgers.edu/~vanvu/papers/numbertheory/thinwaring.pdf</a></p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/43995/are-any-good-strategies-known-for-erdos-turan-conjecture-on-additive-bases-of-ord/56877#56877 Answer by Stanley Yao Xiao for Are any good strategies known for Erdos-Turan conjecture on additive bases of order two? Stanley Yao Xiao 2011-02-28T05:50:37Z 2011-02-28T05:50:37Z <p>Another approach is the polynomial approach in a 2006 paper by Borwein, Choi, and Chu, found at <a href="http://www.cecm.sfu.ca/personal/pborwein/PAPERS/P194.pdf" rel="nofollow">http://www.cecm.sfu.ca/personal/pborwein/PAPERS/P194.pdf</a></p> <p>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.</p> <p>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.</p>