, , ,

1 Introduction and main results

In his seminal paper [?] , Furstenberg gave an ergodic theoretic proof of the famous theorem of Szemerédi claiming that every integer subset with positive density contains arbitrarily long arithmetic progressions. Furstenberg proved this by showing the following multiple recurrence property for measure preserving systems:

Theorem 1.1 (Furstenberg). Let

(X, X, μ, T)

be a finite measure preserving system and

A \in X

be a set with

μ (A) > 0

. Then for every

k \in N

, there exists

n \in N

such that

μ (A \cap T^{- n} A \cap \dots \cap T^{- n k} A) > 0 .

This motivated the following definition:

Definition 1.2. Let

(X, X, μ, T)

be a probability preserving system. We say that

S \subset N

is a set of

k

-recurrence for the transformation

T

if for every

A \in X

with

μ (A) > 0

, there exists

n \in S

such that

μ (A \cap T^{- n} A \cap \dots \cap T^{- k n} A) > 0 .

We say that

S \subset N

is a set of

k

-recurrence if it is a set of

k

-recurrence for every probability preserving transformation.

S

is infinite then the difference set

S - S = {s_{1} - s_{2} : s_{1}, s_{2} \in S}

is easily shown to be a set of

1

-recurrence. By appropriately choosing

S

, Furstenberg constructed, in [?,pages177-178] , a set of

1

-recurrence that is not a set of

2

-recurrence. Constructing sets of

2

-recurrence is much harder, in fact all the examples known turned out to be sets of

k

-recurrence for every

k

. This raised the question, first stated explicitly by Bergelson in [?] :

Question. Let

k \geq 2

be an integer. Does there exist a set of

(k - 1)

-recurrence that is not a set of

k

-recurrence?

The main objective of this article is to show that the answer is affirmative. The examples that we construct are very explicit:

Theorem A. Let

k \geq 2

be an integer and

α \in R

be irrational. We define

S_{k} = {n \in N : {n^{k} α} \in [1 / 4, 3 / 4]},

where

{a}

denotes the fractional part of

a

. Then

S_{k}

is a set of

(k - 1)

-recurrence but not a set of

k

-recurrence.

It will appear in the proof that not only the set

S_{k}

is a set of

(k - 1)

-recurrence for powers of a single transformation, but that it is a set of

(k - 1)

-recurrence for families of commuting transformations (see definition in Section 3 ).

We also answer the corresponding question for sets of

k

-convergence:

Definition 1.3. A set

S = {a_{1} < a_{2} < \dots} \subset N

is called a set of

k

-convergence if for for every probability preserving system

(X, X, μ, T)

and functions

f_{1}, \dots, f_{k} \in L^{\infty} (μ)

, the averages

\frac{1}{N} \sum_{n = 1}^{N} T^{a_{n}} f_{1} \cdot \dots \cdot T^{k a_{n}} f_{k}

converge in

L^{2} (μ)

N \to \infty

Host and Kra in [?] (see also Ziegler's work in [?] for an alternative proof ) showed that

S = N

is a set of

k

-convergence for every

k

. We show:

Theorem B. Let

k \geq 2

be an integer and

α \in R

be irrational. Let

I_{j} = {\begin{matrix} n \in [2^{j}, 2^{j + 1}] : {n^{k} a} \in [1 / 10, 2 / 10] & if j is even \\ n \in [2^{j}, 2^{j + 1}] : {n^{k} a} \in [5 / 10, 6 / 10] & if j is odd \end{matrix}

and define

S_{k}^{'} =^{\infty} ⋃_{j = 1} I_{j} .

Then

S_{k}^{'}

is a set of

(k - 1)

-convergence but not a set of

k

-convergence.

It will be clear from the proof that

S_{k}^{'}

is also a set of

(k - 1)

-recurrence but not a set of

k

-recurrence.

The strategy of the proof of the theorems is as follows: In Section 2 we use some elementary considerations in order to show that

S_{k}

is not a set of

k

-recurrence and

S_{k}^{'}

is not a set of

k

-convergence. The basic observation is that if

S

is a set of

k

-recurrence/convergence then the set consisting of the

k

-th powers of elements of

S

has good

1

-recurrence/convergence properties. In Section 3 we prove a multiple ergodic theorem (Proposition 3.2 ) that enables us to show that

S_{k}

is a set of

(k - 1)

-recurrence and

S_{k}^{'}

is a set of

(k - 1)

-convergence.

Finally, in Section 4 we derive a combinatorial consequence.

2 Bad sets for $k$ -recurrence and $k$ -convergence

We will use the following elementary fact:

Lemma 2.1. Let

k \in N

. Then there exists a nonzero integer

m

and integers

l_{1}, \dots, l_{k}

such that

\begin{matrix} l_{1} + 2 l_{2} + \dots + k l_{k} = 0 \end{matrix}

\begin{matrix} ⋮ \end{matrix}

\begin{matrix} l_{1} + 2^{k - 1} l_{2} + \dots + k^{k - 1} l_{k} = 0 \end{matrix}

\begin{matrix} l_{1} + 2^{k} l_{2} + \dots + k^{k} l_{k} = m . \end{matrix}

\begin{matrix}  \end{matrix}

Proof. The corresponding (Vandermonde) determinant is nonzero, so for $m = 1$ we can find a rational solution for the system. After multiplying by an appropriate nonzero integer we get an integer solution for the advertised system. □

The following result will enable us to show that the set

S_{k}

is bad for

k

-recurrence and

S_{k}^{'}

is bad for

k

-convergence. To better illustrate the idea, after proving the proposition, we explain how the argument works for

k = 2

Proposition 2.2. If

S = {a_{1} < a_{2} < \dots} \subset N

is a set of

k

-recurrence then

S^{k} = {a_{1}^{k} < a_{2}^{k} < \dots}

is a set of

1

-recurrence for all circle rotations, and if

S

is a set of

k

-convergence then

S^{k}

is a set of

1

-convergence.

Remarks. Note that in the above proposition we only claim that

S^{k}

is a set of

1

-recurrence for rotations of the circle. It is clear that the argument we give in the proof below can be extended to show that if

S

is a set of

k

-recurrence, then

S^{k}

is a set of recurrence for all translations of multidimensional tori. In fact, it is an unsolved problem whether a set

S

being of

k

-recurrence implies that

S^{k}

is a set of

1

-recurrence.

Here is a related unsolved problem of Katznelson from [?] : is it true that a set of recurrence for all translations of multidimensional tori is, in fact, a set of topological recurrence?

Proof of Proposition 2.2 . (i) Let

S

be a set of

k

-recurrence. It suffices to show that for every

α \in [0, 1)

and

ɛ > 0

there exists

n \in N

such that

‖ a_{n}^{k} α ‖ \leq ɛ

, where

∥ a ∥

is the distance of

a

to the closest integer. To do this we use the

k

-recurrence property for some appropriately chosen system. We define the measure preserving transformation

R

acting on

T^{k}

with the Haar measure

λ

as follows: the

i

-th coordinate of

R (t_{1}, \dots, t_{k})

t_{i} + (\binom{i}{1}) t_{i - 1} + (\binom{i}{2}) t_{i - 2} + \dots + (\binom{i}{i - 1}) t_{1} + α .

The last coordinate of

R^{j n} (t_{1}, \dots, t_{k})

\begin{matrix} c_{j, n} = t_{k} + (\binom{k}{1}) (j n) t_{k - 1} + (\binom{k}{2}) (j n)^{2} t_{k - 2} + \dots + (\binom{k}{k - 1}) (j n)^{k - 1} t_{1} + (j n)^{k} α . \end{matrix}

(2.1)

By Lemma 2.1 there exist

l_{1}, \dots, l_{k} \in Z

such that

\begin{matrix} l_{1} c_{1, n} + \dots + l_{k} c_{k, n} = m n^{k} α + (l_{1} + \dots + l_{k}) t_{k} \end{matrix}

(2.2)

holds for some nonzero integer

m

, and for all

n \in N

α \in [0, 1)

. Let

U_{ɛ} = B (0, ɛ / (2 M))

where

M = | l_{1} | + \dots + | l_{k} |

. If

S

is a set of

k

-recurrence then there exists an

n_{0} \in S

such that

U_{ɛ} \cap R^{- n_{0}} U_{ɛ} \cap \dots \cap R^{- k n_{0}} U_{ɛ} \neq \emptyset .

Let

(t_{1}, \dots, t_{k})

be an element of the intersection and

c_{j, n}

j = 1, \dots, k

, be given by 2.1 . We have

∥ c_{j, n_{0}} ∥ \leq ɛ / 2 M

j = 1, \dots, k

, and

∥ t_{k} ∥ \leq ɛ / (2 M)

. Using 2.2 we get that

‖ n_{0}^{k} (m α) ‖ \leq ɛ

. Since

m

does not depend on the choice of

α

, and for every nonzero integer

m

the map

α \to m α

is onto, the result follows.

(ii) Suppose that

S = {a_{1} < a_{2} < \dots}

is a set of

k

-convergence. Let

l_{1}, \dots, l_{k}, m

be as in the proof part (i), and let

R

be the transformation defined there. If

f_{j} (t_{1}, \dots, t_{k}) = e (l_{j} t_{k})

j = 1, \dots, k

, then the averages

\frac{1}{N} \sum_{n = 1}^{N} R^{a_{n}} f_{1} \cdot \dots \cdot R^{k a_{n}} f_{k} = e ((l_{1} + \dots + l_{k}) t_{k}) \cdot \frac{1}{N} \sum_{n = 1}^{N} e (a_{n}^{k} m α)

converge in

L^{2} (λ)

N \to \infty

. Hence, for every

α \in [0, 1)

the averages

\frac{1}{N} \sum_{n = 1}^{N} e (a_{n}^{k} α)

converge as

N \to \infty

. The spectral theorem gives that for every measure preserving system

(X, X, μ, T)

and

f \in L^{2} (μ)

the averages

\frac{1}{N} \sum_{n = 1}^{N} T^{a_{n}^{k}} f

converge in

L^{2} (μ)

N \to \infty

, completing the proof. □

We now give an example illustrating how the argument of Proposition 2.2 works for

k = 2

Example. (i) Suppose that

S

is a set of

2

-recurrence. Let

α \in [0, 1)

and

ɛ > 0

. The transformation

R : T^{2} \to T^{2}

is defined by

R (t_{1}, t_{2}) = (t_{1} + α, t_{2} + 2 t_{1} + α) .

Then

R^{n} (t_{1}, t_{2}) = (t_{1} + n α, t_{2} + 2 n t_{1} + n^{2} α) .

Since

S

is a set of

2

-recurrence there exists an

n_{0} \in S

such that

U_{ɛ} \cap R^{- n_{0}} U_{ɛ} \cap R^{- 2 n_{0}} U_{ɛ} \neq \emptyset,

where

U_{ɛ} = B (0, ɛ / 4)

. If

(t_{1}, t_{2})

is an element of the intersection then

\begin{matrix} ∥ t_{2} ∥ \leq ɛ / 4, ∥ c_{1} ∥ \leq ɛ / 4, ∥ c_{2} ∥ \leq ɛ / 4, \end{matrix}

(2.3)

where

c_{1} = t_{2} + 2 n_{0} t_{1} + n_{0}^{2} α, c_{2} = t_{2} + 4 n_{0} t_{1} + 4 n_{0}^{2} α .

Since

c_{2} - 2 c_{1} = 2 n_{0}^{2} α + t_{2}

we get from 2.3 that

‖ n_{0}^{2} (2 α) ‖ \leq ɛ

. This implies that

S^{2}

is a set of recurrence for circle rotations.

(ii) Suppose that

S = {a_{1} < a_{2} < \dots}

is a set of

2

-convergence. We define the transformation

R : T^{2} \to T^{2}

as in part

(i)

and the functions

f (t_{1}, t_{2}) = e (- 2 t_{2}), f_{2} (t_{1}, t_{2}) = e (t_{2}) .

Then

\frac{1}{N} \sum_{n = 1}^{N} R^{a_{n}} f_{1} \cdot R^{2 a_{n}} f_{2} = e (- t_{2}) \cdot \frac{1}{N} \sum_{n = 1}^{N} e (a_{n}^{2} α) .

Since

S

is a set of

2

-convergence it follows that the averages

\frac{1}{N} \sum_{n = 1}^{N} e (a_{n}^{2} α)

converge as

N \to \infty

for every

α \in [0, 1)

. The spectral theorem gives that

S^{2}

is a set of

2

-convergence.

Corollary 2.3. The set

S_{k}

of Theorem A is not a set of

k

-recurrence and the set

S_{k}^{'}

of Theorem B is not a set of

k

-convergence.

Proof. By definition, $S_{k}^{k}$ is not a set of recurrence for the rotation by $α$ , so by Proposition 2.2 we have that $S_{k}$ is not a set of $k$ -recurrence.
Let $S_{k}^{'} = {a_{1} < a_{2} < \dots}$ and $A_{N} = \frac{1}{N} \sum_{n = 1}^{N} e (a_{n}^{k} α), B_{N} = \frac{1}{N} \sum_{n = N + 1}^{2 N} e (a_{n}^{k} α) .$ By the definition of $S_{k}^{'}$ we have that for $j$ even the real part of $B_{2^{j}}$ is positive and bounded away from zero, and for $j$ odd the real part of $B_{2^{j}}$ is negative. Hence, the sequence $B_{N}$ does not converge as $N \to \infty$ . Since $B_{N} = 2 A_{2 N} - A_{N}$ it follows that the sequence $A_{N}$ does not converge as $N \to \infty$ . By Proposition 2.2 , $S_{k}^{'}$ is not a set of $k$ -convergence. □

3 Good sets for $k$ -recurrence and $k$ -convergence

We will use the following elementary lemma ([?] ):

Lemma 3.1 (Van der Corput). Let

{a_{n}}_{n \in N}

be a bounded sequence of vectors in a Hilbert space. For each

m

we set

b_{m} = {limsup}_{N - M \to \infty} | \frac{1}{N - M} \sum_{n = M + 1}^{N} < a_{n + m}, a_{n} > | .

{limsup}_{N - M \to \infty} \frac{1}{N - M} \sum_{m = M + 1}^{N} b_{m} = 0

then

{lim}_{N - M \to \infty} \frac{1}{N - M} \sum_{n = M + 1}^{N} a_{n} = 0

in norm.

Proposition 3.2. Let

k \in N

T_{1}, \dots, T_{k - 1}

be commuting measure preserving transformations acting on the probability space

(X, X, μ)

, and

p \in R [t]

be a polynomial of degree

\geq k

with irrational leading coefficient.

g : T \to C

is Riemann integrable and

f_{1}, \dots, f_{k - 1} \in L^{\infty} (μ)

, then the difference

\frac{1}{N - M} \sum_{n = M + 1}^{N} T_{1}^{n} f_{1} \cdot \dots \cdot T_{k - 1}^{n} f_{k - 1} \cdot g (p (n)) - \frac{1}{N - M} \sum_{n = M + 1}^{N} T_{1}^{n} f_{1} \cdot \dots \cdot T_{k - 1}^{n} f_{k - 1} \cdot \int_{T} g d λ

converges to

0

L^{2} (μ)

N - M \to \infty

Proof. Using the standard estimation by continuous functions from above and below, it suffices to check the result when $g$ is a continuous function. By Weierstrass approximation theorem of continuous functions by trigonometric polynomials, and using linearity, it suffices to check the result when $g (t) = e^{2 π i l t}$ for some $l \in Z$ . The case $l = 0$ is trivial. If $l \neq 0$ the polynomial $q (n) = l p (n)$ satisfies the assumptions of our theorem, so it suffices to verify the result when $g (t) = e (t)$ , where $e (t) = e^{2 π i t}$ .
We proceed by induction on the number of functions $k$ . If $k = 1$ (empty product is $1$ ) then ${lim}_{N - M \to \infty} \frac{1}{N - M} \sum_{n = M + 1}^{N} e (p (n)) = 0$ follows from Weyl's uniform distribution theorem. Assume that the result is true for $k - 1$ functions. We will verify the result for $k$ functions. We can assume that ${∥ f_{k} ∥}_{\infty} \leq 1$ . We apply Van der Corput's Lemma on the Hilbert space $L^{2} (μ)$ for the sequence of functions $a_{n} (x) = f_{1} (T_{1}^{n} x) \cdot \dots \cdot f_{k} (T_{k}^{n} x) \cdot e (p (n)) .$ It suffices to verify that for every $m \in N$ the averages
$\frac{1}{N - M} \sum_{n = M + 1}^{N} \int a_{n + m} (x) \cdot \bar{a_{n} (x)} d μ = \frac{1}{N - M} \sum_{n = M + 1}^{N} \int T_{1}^{n} (T_{1}^{m} f_{1} \cdot {\bar{f}}_{1}) \cdot \dots \cdot T_{k}^{n} (T_{k}^{m} f_{k} \cdot {\bar{f}}_{k}) \cdot e (p (n + m) - p (n)) d μ$
go to 0 as $N - M \to \infty$ . Introducing the notation $S_{i} = T_{i} T_{k}^{- 1}$ , $i = 1, \dots, k - 1$ , and using Cauchy's inequality, it suffices to prove that $\frac{1}{N - M} \sum_{n = M + 1}^{N} S_{1}^{n} (T_{1}^{m} f_{1} \cdot {\bar{f}}_{1}) \cdot \dots \cdot S_{k - 1}^{n} (T_{k - 1}^{m} f_{k - 1} \cdot {\bar{f}}_{k - 1}) \cdot e (p (n + m) - p (n))$ converge to zero in $L^{2} (μ)$ as $N - M \to \infty$ . But this follows from the induction hypothesis since the transformations $S_{i}$ commute, and for $m \in N$ the polynomial $q (n) = p (n + m) - p (n)$ has degree $\geq k - 1$ and irrational leading coefficient. □

We remark that the non-uniform version (

M = 0

) of the previous result suffices for the proof of the next corollary¹ The uniform version is only used to simplify the proof.

Definition 3.3. We say that

S \subset N

is a set of

k

-recurrence for commuting transformations if whenever

T_{1}, \dots, T_{k}

are commuting measure preserving transformations acting on the probability space

(X, X, μ)

and

A \in X

with

μ (A) > 0

, there exists

n \in S

such that

μ (A \cap T_{1}^{- n} A \cap \dots \cap T_{k}^{- n} A) > 0 .

Corollary 3.4. The set

S_{k}

of Theorem A is a set of

(k - 1)

-recurrence for commuting transformations and the set

S_{k}^{'}

of Theorem B is a set of

(k - 1)

-convergence.

Proof. To show that

S_{k}

is a set of

(k - 1)

-recurrence for commuting transformations we apply Proposition 3.2 for

g (t) = 1_{[1 / 4, 3 / 4]} (t)

and

p (n) = n^{k} α

. We get that if

T_{1}, \dots, T_{k - 1}

are commuting measure preserving transformations acting on the probability space

(X, X, μ)

, and

A \in ℬ

with

μ (A) > 0

, then

\begin{matrix} {limsup}_{N \to \infty} \frac{1}{N} \sum_{n = 1}^{N} 1_{S_{k}} (n) \cdot μ (A \cap T_{1}^{- n} A \cap \dots \cap T_{k - 1}^{- n} A) = \end{matrix}

\begin{matrix} \frac{1}{2} \cdot & {limsup}_{N \to \infty} \frac{1}{N} \sum_{n = 1}^{N} μ (A \cap T_{1}^{- n} A \cap \dots \cap T_{k - 1}^{- n} A) > 0, \end{matrix}

\begin{matrix}  \end{matrix}

where positiveness follows from the multiple recurrence theorem of Furstenberg and Katznelson [?] . Hence,

S_{k}

is a set of

(k - 1)

-recurrence. To show that

S_{k}^{'}

is a set of

(k - 1)

-convergence we apply Proposition 3.2 for

T_{i} = T^{i}

i = 1, \dots, k - 1

p (n) = n^{k} α

, and

g = 1_{[1 / 10, 2 / 10]}

on intervals of the form

[2^{j}, 2^{j} + N)

, for large

N < 2^{j}

,when

j

is even, and

g = 1_{[5 / 10, 6 / 10]}

on intervals of the form

[2^{j}, 2^{j} + N)

, for large

N < 2^{j}

, when

j

is odd. We get that for every

f_{1}, \dots, f_{k - 1} \in L^{\infty} (μ)

the difference

\frac{1}{N} \sum_{n = 1}^{N} 1_{S_{k}^{'}} (n) \cdot T^{n} f_{1} \cdot \dots \cdot T^{(k - 1) n} f_{k - 1} - \frac{1}{10} \cdot \frac{1}{N} \sum_{n = 1}^{N} T^{n} f_{1} \cdot \dots \cdot T^{(k - 1) n} f_{k - 1}

converges to zero in

L^{2} (μ)

N \to \infty

. We know from [?] that the averages

\frac{1}{N} \sum_{n = 1}^{N} T^{n} f_{1} \cdot \dots \cdot T^{(k - 1) n} f_{k - 1}

converge in

L^{2} (μ)

N \to \infty

, so the set

S_{k}^{'}

is a set of

(k - 1)

-convergence. This completes the proof. □

The reason we cannot prove that

S_{k}^{'}

is a set of

(k - 1)

-convergence for commuting transformations is that we do not yet know the analogous convergence result for the averages

\frac{1}{N} \sum_{n = 1}^{N} T_{1}^{n} f_{1} \cdot \dots \cdot T_{k}^{n} f_{k} .

¹ See our note at http://www.csi.hu/mw/general_dyadic_construction_short.pdf .

4 Combinatorial consequence

A set

S \subset N

is called intersective if for every integer subset

Λ

with positive density we have

Λ \cap (Λ + n) \neq \emptyset

for some

n \in S

. More generally we define:

Definition 4.1. A set

S \subset N

k

-intersective if every integer subset with positive density contains at least one arithmetic progression of length

k + 1

and common difference in

S

In [?,pages528-529] it is shown that:

Proposition 4.2. A set

S \subset N

k

-intersective if and only if it is a set of

k

-recurrence.

We conclude from Theorem A that:

Corollary 4.3. Let

k \geq 2

. There exists a set that is

(k - 1)

-intersective but not

k

-intersective.

(Nikos Frantzikinakis) Department of Mathematics, McAllister Building, Pennsylvania State University, University Park, PA, 16802, USA E-mail address : nikos@math.psu.edu (Emmanuel Lesigne) Universite Franc ois Rabelais de Tours, Laboratoire de Mathematiques et Physique Theorique (UMR CNRS 6083), Faculte des Sciences et Techniques, Parc de Grandmont, 37200 Tours, France E-mail address : lesigne@univ-tours.fr (Máté Wierdl) Department of Mathematical Sciences, University of Memphis, Memphis, TN, 38152, USA E-mail address : mw@csi.hu

Nikos Frantzikinakis, Emmanuel Lesigne,

Máté Wierdl