Fourier analysis and Szemerédi's theorem

  • W.T. Gowers

Abstract

The famous theorem of Szemerédi asserts that for every positive integer kk and every positive real number δ>0\delta>0 there is a positive integer NN such that every subset of {1,2,,N}\{1,2,\cdots,N\} of cardinality at least δN\delta N contains an arithmetic progression of length kk. A second proof of the theorem was given by Furstenberg using ergodic theory, but neither this proof nor Szemerédi's gave anything other than extremely weak information about the dependence of NN on kk and δ\delta. In this article we describe a new, more quantitative approach to Szemerédi's theorem which greatly improves the best known bound when k=4k=4, and which will probably do the same for general kk. See also Geom. Funct. Anal. 8, 529-551 (1998; Zbl 0907.11005), A new proof of Szemerédi's theorem, ibid. 11, 465-588 (2001; Zbl 1028.11005).