Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: A quantitative ergodic theory proof of Szemer´di’s e theorem. | A quantitative ergodic theory proof of Szemeredi s theorem Terence Tao Department of Mathematics UCLA Los Angeles CA 90095-1555 tao@ http tao Submitted May 14 2004 Accepted Oct 30 2006 Published Nov 6 2006 Mathematics Subject Classihcation 11B25 37A45 Abstract A famous theorem of Szemeredi asserts that given any density 0 Ỗ 1 and any integer k 3 any set of integers with density Ỗ will contain inhnitely many proper arithmetic progressions of length k. For general k there are essentially four known proofs of this fact Szemeredi s original combinatorial proof using the Sze-meredi regularity lemma and van der Waerden s theorem Furstenberg s proof using ergodic theory Gowers proof using Fourier analysis and the inverse theory of additive combinatorics and the more recent proofs of Gowers and Rodl-Skokan using a hypergraph regularity lemma. Of these four the ergodic theory proof is arguably the shortest but also the least elementary requiring passage via the Furstenberg correspondence principle to an inhnitary measure preserving system and then decomposing a general ergodic system relative to a tower of compact extensions. Here we present a quantitative self-contained version of this ergodic theory proof and which is elementary in the sense that it does not require the axiom of choice the use of inhnite sets or measures or the use of the Fourier transform or inverse theorems from additive combinatorics. It also gives explicit but extremely poor quantitative bounds. 1 Introduction A famous theorem of van der Waerden 44 in 1927 states the following. Theorem Van der Waerden s theorem . 44 For any integers k m 1 there exists an integer N NvdW k m 1 such that every colouring c 1 . Ng 1 . mg of 1 . Ng into m colours contains at least one monochromatic arithmetic progression of length k . a progression in 1 . Ng of cardinality k on which c is constant . THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R99 1 See for instance 22 for the .
