2
$\begingroup$

Let $\alpha > 0$. Prove that there is a constant $b>0$ such that any subset $A$ of $\{1,\ldots, N\}$ of size at least $\alpha N$ contains at least $bN^2$ three-term arithmetic progressions (each with non-zero common difference, of course). (Of course, we also implicitly assume that N is large enough in terms of $\alpha$.)

The only related result I know (and we can use it without proof) is Roth's theorem - that any set of size at least $\dfrac{CN}{\log\log N}$ for some constant $C>0$ contains a three-term arithmetic progression.

Is there a way to perhaps apply this theorem repeatedly or do I have to think of something completely different?

Any help appreciated.

$\endgroup$
2
  • 1
    $\begingroup$ The dichotomy used for the density increment argument used to prove Roth's theorem in these notes (Proposition 1) looks very reminiscent of the statement you are trying to prove. Unfortunately, I don't see how to extend this particular dichotomy to your statement... $\endgroup$ Commented Feb 22, 2020 at 13:20
  • 1
    $\begingroup$ @geraldoaltier Unfortunately, I'm not sure modifying this proof of Roth's theorem would work - when you use the dichotomy to pass to a sub-progression, you get rid of many of the 3APs you are looking for (i.e. the sub-progression no longer contains $\gg N^2$ 3APs). $\endgroup$
    – John Don
    Commented Feb 29, 2020 at 14:17

1 Answer 1

4
$\begingroup$

This can be proven using just Roth's theorem as you suggest:

Let $A \subset \{1,\ldots, N\}$ with density $\alpha > 0$. We assume throughout that $N$ is sufficiently large. (Also, throughout, "3AP" means a non-trivial 3-term arithmetic progression.)

Let $M = M(\alpha)$ be large enough such that, for any $M' \geqslant M$, any subset of $\{1, \ldots, M'\}$ with density at least $\frac\alpha 2$ contains a 3AP (such an $M$ exists by Roth's theorem$^\dagger$).

Now, for each $d \leqslant \frac{N}{10M}$, partition $\{1,\ldots, N\}$ into progressions with common difference $d$ and of length between $M$ and $2M$ $^\ddagger$, and let $P(d)$ denote the number of these progressions in which $A$ has density $\geqslant \frac \alpha 2$. Then

\begin{align} |A| &= \alpha N \\ & \leqslant 2M P(d) + \frac{\alpha N}{2} \end{align}

so that $P(d) \geqslant \frac{\alpha N}{4M}$.

By construction, the intersection of $A$ with each of these $P(d)$ progressions contains at least one 3AP. Summing over all $d \leqslant \frac{N}{10M}$, we get

$$ \sum_d P(d) \geqslant \frac{\alpha N^2}{40 M^2} $$

3APs in $A$. However, in summing over all $d$, we have over-counted - a given 3AP could be contained in multiple progressions of length $\Theta(M)$ with distinct common differences, $d$. But each 3AP in $A$ is contained in fewer than $M^2$ progressions of length $M$. (So each distinct 3AP in $A$ has been counted no more than $(2M)^2$ times.)

Hence, the number of distinct 3APs contained in $A$ is $\geqslant \frac{\alpha N^2}{160 M^4}$. Thus, since $M$ only depended on $\alpha$, we have that

$$ \# \{ 3 \text{-APs in } A \} \, \gg_{\alpha} \, N^2 $$


$\dagger$: Specifically, we need $M$ s.t. $\frac \alpha 2 > \frac{C}{\log\log M}$

$\ddagger$: We first partition $\{1,\ldots, N\}$ into $\sim \frac N d \geqslant 10M$ progressions with common difference $d$. We then split each of these progressions into blocks of length $M$ - there may be a small block of length $< M$ left over, which we just merge with the previous block, giving a progression of length $< 2M$.

$\endgroup$

You must log in to answer this question.

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