## The Rudin (Hardy-Littlewood) Conjecture, Notes 3: Omissions.

1. The set of squares does not contain arbitrarily long arithmetic progressions.

As we have mentioned in the beginning of this discussion, Rudin was originally interested (among other things) in the number of terms the set of squares ${S}$ has in arithmetic progressions. For this we recall the definition of the quantity ${\alpha_N(E)}$ for a set ${E\subset \mathbb Z}$. For ${a,b\in\mathbb Z}$ and ${N\in\mathbb N}$ we define ${\alpha_E(N,a,b)}$ to be the number of terms of the set ${E}$ contained in the arithmetic progression

$\displaystyle \begin{array}{rcl} a+b,a+2b,\ldots,a+Nb. \end{array}$

We then define ${\alpha_E(N){\stackrel{\mathrm {def}}{=}} \sup_{a,b\in\mathbb Z} \alpha_E(N,a,b)}$. That is, ${\alpha_E(N)}$ is the maximum number of terms of ${E}$ contained in arithmetic progressions of length ${N}$.

For the set of squares ${S=\{1,2^2,3^2\ldots\}}$ Erdös conjectured that we must have ${\alpha_S(N)=o(N)}$. This is was first proved by Szemerédi:

Theorem 1 (Szemerédi) We have that ${\alpha_S(N)=o(N)}$.

In order to describe the proof of this theorem we need Szemeredi’s theorem in its finitary version:

Theorem 2 (Szemeredi’s theorem) For every ${\delta > 0}$ and positive integer ${k}$, there exists ${N = N(\delta,k)}$ such that if ${A}$ is a set of integers contained in some interval ${[a, b]}$ such that ${b-a> N}$ and ${|A| > \delta(b-a)}$, then ${A}$ contains an arithmetic progression of length ${k}$.

We also need the following theorem (proposed by Fermat and first proved by Euler) which states that the set of squares does not contain arithmetic progressions of length bigger than 3.

Theorem 3 (Four squares theorem) There are no four distinct squares (of integers) in arithmetic progression.

For a very nice exposition and proof of this theorem see for example this note of Alf van den Poorten.

Proof of Theorem 1: Szemerédi gave a proof of the bound ${\alpha_S(N)=o(N)}$ as follows. For integers ${a\geq 0}$ and ${N,b\geq 1}$ let us define the set:

$\displaystyle \mathcal Z(N,a,b)=\{1\leq n \leq N: a+nb\in S\}.$

If we don’t have that ${\alpha_S(N)=o(N)}$ then there is a ${\delta>0}$, a sequence ${N_j\rightarrow +\infty}$ and integer sequences ${a_j\geq 0}$ and ${b_j\geq1}$ such that ${|\mathcal Z(N_j,a_j,b_j)|\geq \delta N_j}$. By Szemerédi’s theorem we conclude that for ${j}$ large enough there is a four term arithmetic progression in ${\mathcal Z(N_j,a_j,b_j)}$ and thus in ${S}$. However this contradicts the four squares theorem. $\Box$

As was mentioned in the first post on Rudin’s problem, the record for ${\alpha_S(N)}$ is due to Bombieri and Zannier and is of the form ${\alpha_S(N)=O(N^\frac{3}{5}+o(1))}$. For more details see [BZ].

2. A ${\Lambda(1)}$-set does not contain arbitrarily long arithmetic progressions

Recall that if a set ${E\subset \mathbb Z}$ is a ${\Lambda(p)}$-set for any ${p>2}$ since then we have the strong bound ${\alpha_S(N)=O(N^\frac{2}{p})}$. What can we say if a set ${E}$ is a ${\Lambda(p)}$-set for some ${p\leq 2}$. The only bound that I’m aware of is due to Rudin:

Theorem 4 (Rudin) Suppose that ${E\subset \mathbb Z}$ is a ${\Lambda(1)}$-set. Then ${E}$ does not contain arbitrarily long arithmetic progressions. In particular we have that ${\alpha_E(N) if ${N}$ is large enough.

Proof: Let us assume that there are ${M}$ consecutive terms of of an arithmetic progression in ${E}$, ${a+b,a+2b,\ldots,a+Mb \in E}$. Then we have that

$\displaystyle \begin{array}{rcl} f(\theta)=\sum_{n=1} ^M e^{in\theta} \end{array}$

is an ${E}$-polynmial. However ${f}$ is essentially the Dirichlet kernel

$\displaystyle \begin{array}{rcl} |f(\theta)|=\bigg| \frac{\sin{(\frac{1}{2}Mb\theta )}}{sin({\frac{1}{2}b\theta})}\bigg|. \end{array}$

We conlcude that ${\|f\|_1\simeq \log M}$ and ${\|f\|_p\lesssim_p 1}$ for any ${p<1}$. Since ${E}$ is a ${\Lambda(1)}$-set we conclude that ${M\lesssim 1}$, which means that there are boundedly many consecutive terms of an arithmetic progression in ${E}$. We conclude that if ${N}$ is large enough then any ${N}$ term arithmetic progression cannot lie entirely in ${E}$. Unfortunately this only gives the weak statement ${\alpha_N(E) for ${N}$ large enough. $\Box$

Corollary 5 Suppose that ${E\subset \mathbb Z}$ is a ${\Lambda(p)}$-set for some ${p\geq 1}$. Then ${E}$ satisfies ${\alpha_E(N)=o(N)}$. In particular ${E}$ has density ${0}$.

Proof: Since the set ${E}$ is a ${\Lambda(1)}$-set, we conclude that it does not contain arbitrarily long arithmetic progressions. The proof then is identical to that of Theorem 1. $\Box$

3. References.