I have been learning about Roth's theorem, trying to understand how Fourier series and dynamical systems (or even graph theory and binary sequences)are involved in counting arithmetic sequences in sets.

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} $$

These is a dichotomy between structure and randomness

- Bohr sets $A = \{ n \in \mathbb{Z} : ||\alpha n - \theta|| < \delta/2 \}$. (Also, nil-Bohr sets).
- "Coin" flip sets
- Flip a coin heads with probability $\delta$, get $\omega \in \{ 0,1\}^\mathbb{Z}$.
- $A = \{ n\in \mathbb{Z}: \omega(n) = head\}$ is Fourier random almost surely

In both cases, the density can be found exactly $\bar{\delta}(A) = \delta$.

After some logical simplifications, the problem boils down to computing correlations between 3 copies of the set $A$

$$ \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) $$

These count arithmetic sequences of all possible lengths and starting points. For Bohr sets and coin-flip sets these terms can be computed exactly.

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?

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.

lengthsand starting points" (my emph) is this just a typo for difference? Also do I understand correctly you insist on a fixed difference. And what do you mean by an explicit proof? – user9072 Nov 23 '12 at 21:36