Let be a dynamical system (i.e., a measure preserving probability system, with invertible). The Khintchine recurrence theorem states:
If with , then for every , is syndetic.
A multiple recurrence theorem due to Furstenberg states:
Let be a dynamical system, let with and let . Then
(This was subsequently shown by the latter two authors [Ann. Math. (2) 161, No. 1, 397–488 (2005; Zbl 1077.37002)] to be a limit.)
Both of these theorems can be regarded a generalizations of the Poincaré recurrence theorem, and the original aim of the authors was to give a simultaneous generalization of both theorems, to show that for such a dynamical system and for , and , the set of such that is syndetic. However, surprisingly, the authors are able to show that if is ergodic, then this is true for and , but false for (and also false in the non-ergodic cases of and ). The case of uses a combinatorial result due to Ruzsa, which appears as an appendix.