3
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I am not sure I understand your terminology: "These count arithmetic sequences of all possible lengths and 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? $\endgroup$
    – user9072
    Commented Nov 23, 2012 at 21:36
  • 2
    $\begingroup$ If you're asking what I think you're asking: Compute $f(r,\delta)$, the maximum possible density of 3-term progressions with difference $r$ in a set of density $\delta$, I think the answer is fairly easy. It's just $\delta$. For example, insert blocks of length $N\gg r$ spaced regularly $N/\delta$ apart. This sequence has density $\delta$ and most elements of the set are initial points of 3-term progressions spaced $r$ apart. You clearly can't do better than this. $\endgroup$
    – Anthony Quas
    Commented Nov 23, 2012 at 22:25
  • 1
    $\begingroup$ @Anthony Quas: from the context a lower bound seems more relevant. But I agree that it is not quite clear what is asked for. And as implict in my comment I somehow doubt that with fixed difference there is much to say (with arbitrary difference this would be quite different); as your example shows, as other sets with same density would have no AP of that difference. $\endgroup$
    – user9072
    Commented Nov 23, 2012 at 23:41

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .