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 has in arithmetic progressions. For this we recall the definition of the quantity for a set . For and we define to be the number of terms of the set contained in the arithmetic progression
We then define . That is, is the maximum number of terms of contained in arithmetic progressions of length .
For the set of squares Erdös conjectured that we must have . This is was first proved by Szemerédi:
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 and positive integer , there exists such that if is a set of integers contained in some interval such that and , then contains an arithmetic progression of length .
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 as follows. For integers and let us define the set:
If we don’t have that then there is a , a sequence and integer sequences and such that . By Szemerédi’s theorem we conclude that for large enough there is a four term arithmetic progression in and thus in . However this contradicts the four squares theorem.
2. A -set does not contain arbitrarily long arithmetic progressions
Recall that if a set is a -set for any since then we have the strong bound . What can we say if a set is a -set for some . The only bound that I’m aware of is due to Rudin:
Theorem 4 (Rudin) Suppose that is a -set. Then does not contain arbitrarily long arithmetic progressions. In particular we have that if is large enough.
is an -polynmial. However is essentially the Dirichlet kernel
We conlcude that and for any . Since is a -set we conclude that , which means that there are boundedly many consecutive terms of an arithmetic progression in . We conclude that if is large enough then any term arithmetic progression cannot lie entirely in . Unfortunately this only gives the weak statement for large enough.
Corollary 5 Suppose that is a -set for some . Then satisfies . In particular has density .
Proof: Since the set is a -set, we conclude that it does not contain arbitrarily long arithmetic progressions. The proof then is identical to that of Theorem 1.