most recent 30 from http://mathoverflow.net 2013-05-23T21:24:52Z http://mathoverflow.net/feeds/question/114290 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/114290/bohr-sets-coin-flip-sets-and-roths-theorem John Mangual 2012-11-23T21:11:58Z 2012-11-25T20:17:53Z

<p>I have been learning about <a href="http://terrytao.wordpress.com/2010/04/08/254b-notes-2-roths-theorem/" rel="nofollow">Roth's theorem</a>, trying to understand how Fourier series and <a href="http://math.nyu.edu/~venkatesh/lec3.pdf" rel="nofollow">dynamical systems</a> (or even <a href="https://matheuscmss.wordpress.com/2012/01/07/applications-of-szemeredis-regularity-lemma-triangle-removal-lemma-roths-theorem-corners-theorem-and-graph-removal-lemma/" rel="nofollow">graph theory</a> and <a href="http://www.cs.cmu.edu/~odonnell/boolean-analysis/" rel="nofollow">binary sequences</a>)are involved in counting arithmetic sequences in sets.</p> <blockquote> <p>Any integer set of positive upper density has infinitely many arithmetic arithmetic sequences of length 3. $$ \bar{\delta}(A) = \limsup_{N \to \infty} \frac{|A \cap [-N,N]|}{2N+1} $$</p> </blockquote> <p>These is a dichotomy between structure and randomness </p> <ul> <li>Bohr sets $A = \{ n \in \mathbb{Z} : ||\alpha n - \theta|| &lt; \delta/2 \}$. (Also, <a href="http://arxiv.org/abs/0903.1642" rel="nofollow">nil-Bohr sets</a>).</li> <li>"Coin" flip sets <ul> <li>Flip a coin heads with probability $\delta$, get $\omega \in \{ 0,1\}^\mathbb{Z}$.</li> <li>$A = { n\in \mathbb{Z}: \omega(n) = head}$ is Fourier random almost surely</li> </ul></li> </ul> <p>In both cases, the density can be found exactly $\bar{\delta}(A) = \delta$.</p> <p>After some logical simplifications, the problem boils down to computing correlations between 3 copies of the set $A$</p> <p>$$ \mathbb{E}[1_A 1_A 1_A] = \sum_{n,r \in \mathbb{Z}} 1_A(n)1_A(n+r)1_A(n+2r) $$</p> <p>These count arithmetic sequences of all possible lengths and starting points. For Bohr sets and coin-flip sets these terms can be computed exactly.<br> <hr> What are the known asymptotics (if any) for the number of arithmetic sequences of a given difference $r(\bar{\delta})$ as a function of the upper density? </p> <p>I am just trying to understand what is happening in the proof of Roth's theorem. Maybe it is possible to get an "explicit" proof of Roth theorem at least in some cases. </p>

http://mathoverflow.net/questions/114290/bohr-sets-coin-flip-sets-and-roths-theorem/114445#114445 Ben Barber 2012-11-25T20:17:53Z 2012-11-25T20:17:53Z

<p>You can achieve density $2/3$ with no APs of common difference $r$ by knocking out every third element of each of the $r$ infinite APs of common difference $r$. And as Anthony Quas points out in the comments, for general $\delta$ we can achieve a density $\delta$ of all APs of common difference $r$ by taking our set to be a union of long intervals. So we can't ask for too much about the common differences of the APs we obtain from Roth's theorem.</p>