Child pages
  • Szemeredis Theorem
Skip to end of metadata
Go to start of metadata

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.


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.


Advanced studies


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.

  • No labels