INTRODUCTION A celebrated theorem of Szemeredi ([SZ]) states that if a set S C Z has positive upper density d(S) = limsup J t ' fl 0, then S contains arbitrarily long arithmetic progressions. Soon after Szemeredi's theorem appeared, H. Furstenberg gave in [Fl] a new, ergodic theoretical proof of Szemeredi's theorem by deducing it from a far-reaching extension of the classical Poincare recurrence theorem. A short time later, in [FK1], Furstenberg and Katznelson proved the following multiple recurrence theorem: Theorem 0.1 Suppose that (X, 23, /i) is a probability space and that T\, • • •, T& are commuting measure-preserving transformations of X. For every A G B with fJi(A) 0 we have 1 N _ 1 liminf — V fi(TrnA n • • • (1 T~n A) 0. As a corollary of this result they obtained a multi-dimensional generalization of Szemeredi's theorem for which there is as yet no non-ergodic proof. We will now formulate this result. The Banach upper density of a set S C Zk is defined to be d*(S)= sup limsup— n , { n n } n € N rwoo | n n | where the supremum goes over all sequences of parallelepipeds n „ = [a£\bM] x ••• x [ a « , 6 « ] C Zk,n e N, W i t h bn — CLn —• 0 0 , 1 Z fc. Corollary 0.2 ([FK1], Theorem B) Suppose that S C Zk with d*(S) 0 and that F C Zfc is a finite configuration. There exists a positive integer n and a vector uGZ f c such that u + n F = {u-\-nx : x e F} C S. The derivation of combinatorial results such as Corollary 0.2 from recurrence results hinges on a general correspondence principle due Furstenberg. Furstenberg's Correspondence Principle Given E C Zh with d*(E) 0 there is a probability space (X, B, /x) and k commuting invertible measure preserving transformations I\ , T2, • • •, X^ of X such that for any ni, n2, • • •, n^ G Zfc one has d* (E H (E - ni) H (F - n2) H • • • H (F - nz)) //(A H Tni n • • • H Tnz A), Received by the editor February 5, 1998. The authors acknowledge the support of the NSF under grant DMS-9706057 and a postodoctoral fellowship administered by the University of Maryland, respectively. 1

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2000 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.