University of Georgia REU- Additive Combinatorics- Summer 2010 Szemerédi’s Proof of Roth’s Theorem Catherine Ha

| A | = δN necessarily contains a non-trivial 3-term arithmetic progression. The purpose of this paper is to provide the Szemerédi’s proof of Roth’s theorem on the existence of 3-term arithmetic progressions in large sets. We will rely on much of the method used in the Fourier analytic proof to show that if a set A ⊆ [1,N] with |A | = δN does not contain any 3-term arithmetic progressions, then there exists a ”long ” arithmetic progression on which the (relative) density of A increases, to say δ + δ2 20. Provided N is sufficiently large, the density of A will eventually exceed 1 on some progression after a number of iterations, and this is the contradiction that we are seeking for in our argument. Before we begin the proof, it is important to note that the convenient notation log N will replace log2 N. One of the most important tools in this proof of Roth’s theorem is the Cube Lemma, which will be employed later in the paper. Lemma 2. (Cube Lemma) Define a k-dimensional cube to be a set of the form Q(a,d1,...,dk) = {a + ε1d1 +... + εkdk: εi = 0 or 1 for all 1 ≤ i ≤ k} where a,d1,...,dk ∈ N For δ> 0 and k ∈ N, if N ≥ (3/δ) 2k and A ⊆ [1,N] with |A | = δN then A must contain a k-dimensional cube. δN Fix A ⊆ [1,N] with |A | = δN. Within A, we will have