Proof of Roth's theorem due to Heath -Brown and Szemeredi

Question

The following question (statement) is from Tao and Vu's Additive combinatorics, at which I am stuck and would appreciate some help.

I wish to prove Theorem 10.27 (page 390) using Proposition 10.28 and Lemma 10.29.

Proposition 10.28: Let $A \subset [1,N]$ be such that $|A| = \delta N$ for some $0<\delta\le 1$ and such that $A$ has no proper arithmetic progressions of length $3$. Suppose also that $N \ge 100/(\delta)^2$. Let $p$ be a prime between $N$ and $2N$, and identify $[1,N]$ with a subset of $\mathbb{Z}_p$. Let $f_U:=1_A - \delta 1_{[1,N]}$. Then there exists a set $S \subset\mathbb{Z}_N$ such that $|S| = O(\delta^{-5})$ and $$\sum_{\xi \in S}|\hat{f}_{U}(\xi)|^2 = \Omega(\delta^2 |S|^{1/5}).$$

Lemma 10.29: Let $N$ and $p$ be as in the above lemma. Let $f:\mathbb{Z}_p \to \mathbb{R}$ be a function supported on $[1,N]$ such that $|f(n)|\le 1$ for all $n$, and such that $$\mathbb{E}_{n \in [1,N]}|f(n)| \le \delta$$ and $$\sum_{\xi \in S} |\hat{f}(\xi)|^2 \ge \sigma$$ for some set $S \subset \mathbb{Z}_p$ and some $\sigma >0$. Then there exists a proper arithmetic progression $P' \subset [1,N]$ with $|P'|=\Omega(N^{1/(|S|+1)})$ and $$\mathbb{E}_{n \in P'}f(n) =\Omega(\sigma /\delta).$$

Here is my work to prove Theorem 10.27:

Now we want to use the above two proposition / lemma to prove the following:

Corollary: Let $A \subset [1,N]$ be such that $|A| = \delta N$ for some $0<\delta\le 1$ and such that $A$ has no proper arithmetic progressions of length $3$. Suppose also that $N \ge 100/(\delta)^2$. Then there exists a set $S \subset\mathbb{Z}_N$ such that $|S| = O(\delta^{-5})$ and there exists a proper arithmetic progression $P' \subset [1,N]$ with $|P'|=\Omega(N^{1/(|S|+1)})$ such that we have a density increment $$P_{P'}(A) \ge P_P(A) +\Omega(\delta |S|^{1/5}).$$

Clearly the corollary follows from Proposition 10.28 and Lemma 10.29 if we choose the function $f$ (in Lemma 10.29) to be $f:=1_A - \delta_{[1,N]}$ as it satisfies all the hypothesis in Lemma 10.29 and so it turns out that $\sigma$ in Lemma 10.29 is same as $\delta^2 |S|^{1/5}$

Now we wish to iterate the corollary to prove Theorem 10.27. So, let the new density is $\delta_{i+1}$ and original density if $\delta_i$, then from corollary it follows that if $N_i$ is large enough ( $N_i \ge 100/(\delta_i)^2$ ) then we can find a subset $S_i$ of $N_i$ such that the new sub-progression has length atleast $\Omega(N_i^{1/(|S_i| +1)}$) and $$\delta_{i+1} \ge \delta_i + \Omega(\delta_i |S_i|^{1/5})$$

Suppose we wish to keep doubling the density , then we can do this atmost $log_2(1/\delta)+1$ as density is always bounded by 1, so the total number of times we can double the density is bounded. Note that the process stops only if $N_i <100/(\delta_i)^2$ . So, if the process terminates at step $i$ then we have : $$N_i < 100/(\delta)_i)^2 \leq 100/(\delta)^2$$ and moreover each time we iterate the corollary we move down to a sub-AP whose length is reduced by a power of $1/(|S_i|+1)$.

Also, the total number of steps $(i)$ that we can keep doubling the density is $O(1/\delta)$. Then we have the following: ($\delta$ is the density of 3-AP free set in $[1,N]$) $$N \le N_i^{{(|S_i|+1)}^i} \le (100/\delta^2)^{{(|S_i|+1)}^{O(1/\delta)}}, \;\;\;\; say (*)$$

But I am unable to conclude from here to show (Theorem 10.27) that $\delta = O(1/\log^c N) \implies |A| = (N/ \log^c N)$. Can someone please tell me where do i go wrong or how to conclude the last step , which shows the density of 3-AP free set. I have explained the steps that I used to reach the conclusion (*) . Please help me to prove this bound. Thanks.

Answer 1

As Sean Eberhard says, there are clearer writeups of the Heath-Brown--Szemerédi argument, such as the notes of Ben Green that he links to, but here are the details of how to deduce the final density bound of $\delta \ll (\log N)^{-c}$ for some $c>0$ from the kind of density increment lemma you mention, just treating it as a black box.

The density change at each step is like

$$ \delta_{i+1} \geq \delta_i(1+\Omega(\lvert S_i\rvert^{1/5})).$$

The change in the size of the progression at each step is $$ N_{i+1} \geq cN_i^{1/2\lvert S_i\rvert}$$

for some constant $c>0$. (Actually a little better than this of course, but this makes the calculations a little cleaner.)

(Note that there's a trade-off in that as $\lvert S_i\rvert$ gets larger the density increase gets better, but there's a loss in the length of the new progression, so these two parameters need to be carefully balanced. It might be easier to first run through what happens if we could always guarantee that $\lvert S_i\rvert\in [1,10]$, say, and see how the bound follows then, and then return to the general case below.)

Suppose we have managed to run this density increment procedure for $K$ steps. Then we certainly have

$$\delta_K \gg (\lvert S_1\rvert\cdots \lvert S_K\rvert)^{1/5}\delta$$

(again, we have more than this, but this is enough for now) and

$$N_K \geq c^KN^{2^{-K}1/\lvert S_1\rvert\cdots \lvert S_K\rvert}.$$

Since the density $\delta_K$ is trivially $\leq 1$ we have $\lvert S_1\rvert\cdots \lvert S_K\rvert\ll \delta^{-5}$, and so $N_K \geq c_1^K N^{\Omega(2^{-K}\delta^5)}$.

Now we note that this procedure cannot continue indefinitely -- indeed, since $\delta_{i+1}\geq C\delta$ for some absolute constant $C>1$ (this is just using the trivial fact that $\lvert S_i\rvert\geq 1$ at each step), we have $1\geq \delta_K\geq C^K\delta$ and so $K \ll \log(1/\delta)$. Therefore

$$N_K \gg c_1^{O(\log(1/\delta))}N^{\Omega(\delta^{O(1)})}.$$

But the only reason we have stopped the density increment at $N_K$ must be because the bound $N_K\geq 100/\delta_K^2$ fails (certainly no non-trivial 3APs can appear at any point). Therefore $N_K \ll \delta_K^{-2}\ll \delta^{-2}$. Using the above lower bound on $N_K$, this implies that

$$\delta^{-O(1)}\gg N^{\Omega(\delta^{O(1)})}.$$

It's now straightforward to deduce $\delta \ll (\log N)^{-c}$ for some $c>0$ from this - but it can be a little mysterious the first time you see it, so here's a little more detail. It's easier if we first assume that $\delta \leq 1/2$, say. This means that, at the cost of possibly choosing some horribly large exponent $C$, the above bound implies that there must exist some $C$ such that

$$ \delta^{-C} \geq N^{\delta^C}.$$

Taking logs of both sides, we have

$$ C\log(1/\delta) \geq \delta^C\log N.$$

If $\log(1/\delta) \geq (\log N)^{1/2}$, say, then we have $\delta \leq \exp(-\sqrt{\log N})$, so certainly $\delta \ll 1/\log N$ (say), which is much better than we were aiming for. So we can instead assume that $\log(1/\delta)< (\log N)^{1/2}$, and hence

$$ C\delta^{-C} \geq (\log N)^{1/2},$$

whence $\delta \ll (\log N)^{-1/2C}$, as required.

Answer 2

To be frank the details in that part of the book are exceptionally hard to follow. Do yourself a major favor and look for a different source, say http://people.maths.ox.ac.uk/greenbj/papers/szemeredi-roth.pdf.