Szemeredis Theorem

Short course: Szemeredi's Theorem

Aimo Hinkkanen (Professor, University of Illinois at Urbana-Champaign)
 30.5.-14.6. 2012, University of Helsinki

Time and place

The lectures will be held in Exactum (Kumpula, University of Helsinki) as follows:

Wednesday 30. May 10 - 12 o'clock in lecture room D123
 Friday 1. June 10 - 12 o'clock in lecture room D123
 Tuesday 5. June 10 - 12 o'clock in lecture room D123
 Thursday 7. June 10 - 12 o'clock in lecture room D123
 Tuesday 12. June 10 - 12 o'clock in lecture room D123
 Thursday 14. June 10 - 12 o'clock in lecture room D123

The course folder in room C326 contains hand-written lecture notes for the course.

Scope

Credit points: 3. The course can be passed for by solving assigned exercise problems. Here are the exercises. In order to get credit points please give/send your solutions to Hans-Olav Tylli (Department of Mathematics and Statistics) before 31. July, 2012.

Level

Advanced studies

Abstract

In 1928, van der Waerden proved that given positive integers r and k, there is a positive integer M(r,k) such that if the set of integers from 1 to M(r,k) is partitioned into r subsets, then at least one subset contains an arithmetic progression of length k.

In 1936, Erdös and Turán conjectured a stronger result that implies that if k is a positive integer and 0 < b < 1, then there exists an integer N=N(k,b) such that every subset of the integers from 1 to N whose number of elements is at least bN contains an arithmetic progression of length k. This was proved by Roth in 1953 for k=3, by Szemerédi in 1969 for k=4, and in full generality by Szemerédi in 1975. Thus the result is known as Szemerédi's theorem.

Szemerédi's proof is combinatorial. A proof based on ergodic theory was found by Furstenberg in 1977. Yet another proof was discovered by Gowers in 2001. In this course we discuss Gowers's proof only.
 The proof by Gowers is based on showing that if we start with a sufficiently large set, we can find a subset that is still large in a suitable sense and that has certain extra properties. This idea is used repeatedly, with a bound on the number of iterations required. One ends up with a subset that can be proved to contain an arithmetic progression of length k.

A constant feature in the proof when dealing with different types of properties is the use of the finite Fourier transformation. It might not be unfair to say that the many proofs of subresults are based on elementary but complicated counting arguments together with the Fourier transformation. A number of new concepts are formulated. Of crucial importance is the concept of an alpha-uniform set of degree d, which generalizes an idea used by Roth for the case k=3. Gowers also obtains the best known upper bound for van der Waerden's number M(r,k). In Gowers's proof all steps are explicitly and effectively quantitative, leading to an explicit bound for N(k,b), and, unlike Szemerédi's proof, the proof is independent of van der Waerden's theorem.

It would not be possible to cover all of the 124-page paper of Gowers in the time available. We will present the basic logic of the proof, give an exposition of the new concepts used, and go through in detail the proofs of some of the most important auxiliary results. Similar themes are used in the proofs of many of the other steps, so this should give an idea of the proof overall.