# Subset of $[N]$ with given density $\alpha$ contains at least $\Theta(N^2)$ 3-term arithmetic progressions

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.

• 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... Commented Feb 22, 2020 at 13:20
• @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). Commented Feb 29, 2020 at 14:17

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