## Single and multiple recurrence along non-polynomial sequences

Vitaly Bergelson, Florian Richter and I have recently uploaded to the arXiv our new paper “Single and multiple recurrence along non-polynomial sequences”. In this paper we address the question of what combinatorial structure is present in the set of return times of a non-polynomial sequence, i.e., sets of the form

$\displaystyle R=\big\{n\in{\mathbb N}:\mu(A\cap T^{-f(n)}A)>\mu^2(A)-\epsilon\big\} \ \ \ \ \ (1)$

where ${(X,\mu,T)}$ is a measure preserving system, ${A\subset X}$, ${\epsilon>0}$ and ${f:{\mathbb N}\rightarrow{\mathbb N}}$ is some non-polynomial function.

The departure point for this paper was the observation that when ${f(n)}$ is a polynomial with integer coefficients and ${f(0)=0}$, set ${R}$ in (1) is syndetic, i.e. has bounded gaps (for the special case ${f(n)=n}$ this is the content of Khintchine’s theorem, and the general case was obtained by Furstenberg, see a proof in my earlier post), but the same is no longer true in general for non-polynomial sequences ${f(n)}$.

For instance when ${f(n)=\lfloor n^a\rfloor}$ for some positive ${a\in{\mathbb R}\setminus{\mathbb Z}}$ (where ${\lfloor \cdot\rfloor}$ denotes the floor function) it is known that the set ${R}$ from (1) is nonempty, and in fact has positive density but is not (in general) syndetic.

Our first theorem shows that nevertheless, the set ${R}$ has an interesting (and a-priori surprising) combinatorial property, it is thick, i.e., contains arbitrarily long intervals of integers. One reason why this is surprising is that the notions of thick and syndetic sets are dual in the sense that a set is thick if and only if its complement is not syndetic and vice-versa. See my previous post for some discussion of the basic properties of thick and syndetic sets.

Theorem 1 Let ${(X,\mu,T)}$ be a measure preserving system, let ${A\subset X}$, and ${a,\epsilon>0}$, ${a\notin{\mathbb N}}$. Then the set ${R}$ defined in (1) for ${f(n)=\lfloor n^a\rfloor}$ is thick.

Theorem 1 implies in particular that for every ${k\in{\mathbb N}}$ there exists some ${n\in{\mathbb N}}$ such that each of the sets ${T^{-f(n)}A}$, ${T^{-f(n+1)}A}$, … , ${T^{-f(n+k)}A}$ have a large intersection with ${A}$. Our second theorem proves that in fact all of these sets intersect together.

Theorem 2 Let ${(X,\mu,T)}$ be a measure preserving system, let ${A\subset X}$, and ${a,\epsilon>0}$, ${a\notin{\mathbb N}}$. Then for every ${k\in{\mathbb N}}$ there exist (many) ${n\in{\mathbb N}}$ such that

$\displaystyle \mu\Big(A\cap T^{-f(n)}A\cap T^{-f(n+1)}A\cap\cdots\cap T^{-f(n+k)}A\Big)>0$

where ${f(n)=\lfloor n^a\rfloor}$.

Note that both Theorems 1 and 2 fail when ${f(n)}$ is a polynomial.

In the paper we deal with a considerably more general class of non-polynomial functions (see Definition 4 below) but for now I will restrict attention to the example ${f(n)=\lfloor n^a\rfloor}$.

— 1. Well distributed and thickly dense sequences —

It is well known that, in view of the spectral theorem or Bochner-Herglotz’ theorem, properties of the set

$\displaystyle R=\big\{n\in{\mathbb N}:\mu(A\cap T^{-f(n)}A)>\mu^2(A)-\epsilon\big\}$

can be studied using the theory of uniform distribution of sequences modulo ${1}$. For instance, the fact that ${R}$ has positive density when ${f(n)}$ is a polynomial is a corollary of Weyl’s theorem that the sequence ${f(n)\alpha\bmod1}$ is uniformly distributed in ${[0,1)}$ for every irrational ${\alpha}$.

In fact, in this situation, the sequence ${f(n)\alpha\bmod1}$ is well distributed, i.e., for every non-empty interval ${(x,y)\subset[0,1)}$ and for every sequence of intervals of integers ${(I_N)_{N\in{\mathbb N}}}$ with lengths ${|I_N|\rightarrow\infty}$ we have

$\displaystyle \lim_{N\rightarrow\infty}\frac1{|I_N|}\sum_{n\in I_N}1_{(x,y)}\big(f(n)\alpha\bmod1\big)=y-x.$

This fact, together with the spectral theorem implies that the set

$\displaystyle R=\big\{n\in{\mathbb N}:\mu(A\cap T^{-f(n)}A)>\mu^2(A)-\epsilon\big\}$

is syndetic when ${f\in{\mathbb Z}[x]}$ satisfies ${f(0)=0}$.

It is not hard to see the relation between well distribution and syndeticity: if a sequence is well distributed modulo ${1}$ then it is syndetically dense, i.e., it visits every interval in a syndetic set of times. More precisely, a sequence ${x_n}$ in a topological space is syndetically dense if for every non-empty open set ${U}$, the set ${\{n:x_n\in U\}}$ is syndetic.

On the other hand, when ${f(n)=\lfloor n^a\rfloor}$ for ${a>0}$, ${a\notin{\mathbb Z}}$, the fact that the set ${R}$ has positive density was derived by Bergelson and Håland from the fact that (any multiple of) the sequence ${n^a\bmod1}$ is uniformly distributed on ${[0,1]}$. However, the sequence ${n^a\bmod1}$ is not well distributed on ${[0,1]}$. This is easy to see for ${a<1}$. Indeed in this case, ${n^a}$ grows to infinity but slower and slower, so that there are arbitrarily long intervals of integers where ${n^a}$ barely moves at all. For instance, for ${n}$ in the interval ${[2^k,2^k+k]}$, the function ${n^a}$ only changes by ${\frac k{2^{k(1-a)}}}$ which clearly prevents it from becoming well distributed modulo ${1}$.

What we observed is that in fact ${n^a\bmod1}$ exhibits the opposite phenomenon of well distribution: it is thickly dense, i.e. it visits every interval in a thick set of times. More precisely, a sequence ${x_n}$ in a topological space is thickly dense if for every non-empty open set ${U}$, the set ${\{n:x_n\in U\}}$ is thick.

It turns out that for every non-integer positive ${a}$, the sequence ${n^a\bmod1}$ is thickly dense in ${[0,1]}$!

Theorem 3 Let ${a\in{\mathbb R}\setminus{\mathbb Z}}$ be positive and let ${U\subset[0,1]}$ be a non-empty open set. Then the set ${\{n:n^a\bmod1\in U\}}$ is thick.

This stands in stark contrast with the syndetic denseness of polynomials. Indeed observe that if for any two disjoint subintervals ${U}$ and ${V}$ of ${[0,1]}$, if for a sequence ${x_n}$ the set ${R_U=\{n:x_n\in U\}}$ is thick, then the set ${R_V=\{n:x_n\in V\}}$, which is contained in the complement of ${R_U}$ can not be syndetic. Similarly, if ${R_U}$ is syndetic then ${R_V}$ can not be thick. Therefore, for any nonempty open set ${U\subset[0,1]}$ and irrational ${\alpha\in{\mathbb R}}$, we obtain the following bizarre behaviour for the set ${\{n:\alpha n^a\mod1\in U\}}$: it is syndetic when ${a>0}$ is an integer but thick when ${a}$ is not.

We don’t actually prove Theorem 3 in the paper, but here is a sketch of the proof.

Proof of Theorem 3: To prove that the set ${\{n:n^a\bmod1\in U\}}$ is thick it suffices to show that for every ${k}$ there exists ${n}$ such that ${\{n^a,(n+1)^a,\dots,(n+k)^a\}\subset U}$. We can rewrite this condition in terms of the carthesian product of ${U}$ as

$\displaystyle \big(n^a,(n+1)^a,\dots,(n+k)^a\big)\in U^{k+1}$

Therefore it will suffice to show that for every ${k\in{\mathbb N}}$, the closure

$\displaystyle \overline{\Big\{\big(n^a,(n+1)^a,\dots,(n+k)^a\big):n\in{\mathbb N}\Big\}}$

contains the diagonal of ${{\mathbb T}^{k+1}}$. This will be achieved by showing that the sequence

$\displaystyle x:n\mapsto\big(n^a,(n+1)^a,\dots,(n+k)^a\big)$

is in fact uniformly distributed in some sub-torus ${H}$ of ${{\mathbb T}^{k+1}}$ which contains the diagonal. When ${k we can in fact take ${H}$ to be all of ${{\mathbb T}^{k+1}}$.

Let ${\Lambda:=\Big\{\tau\in{\mathbb Z}^{k+1}:\big\langle\tau,x(n)\big\rangle= o_{n\rightarrow\infty}(1)\Big\}}$ and observe that ${\Lambda}$ is a subgroup of ${{\mathbb T}^{k+1}}$. Now using standard tools from the theory of uniform distribution (namely the Weyl’s criterion, Fejér theorem on uniform distribution and the van der Corput trick) one can easily show that the sequence ${x(n)}$ is uniformly distributed in the closed subgroup ${H:=\big\{x\in{\mathbb T}^{k+1}:\langle \tau,x\rangle\in{\mathbb Z}\text{ for all }\tau\in\Lambda\big\}}$.

Finally, it suffices to show that the diagonal of ${{\mathbb T}^{k+1}}$ is contained in ${H}$. Using the generalized binomial theorem, it is easy to see that for every ${\tau=(\tau_0,\dots,\tau_k)\in{\mathbb Z}^{k+1}}$ we have

$\displaystyle \langle \tau,x(n)\rangle=\big(\tau_0+\cdots+\tau_k+o(1)\big)n^a,$

and hence if ${\tau\in\Lambda}$ then ${\tau_0+\dots+\tau_k=0}$. This implies that any point ${x}$ in the diagonal of ${{\mathbb T}^d}$ satisfies ${\langle x,\tau\rangle=0}$ and hence ${x\in H}$. $\Box$

Unfortunately this is not quite enough to establish Theorem 1. One of the difficulties is that, as the more astute reader will have noticed, we conveniently started talking about the sequence ${n^a}$ instead of ${\lfloor n^a\rfloor}$ or even ${n^a\alpha}$ for some ${\alpha\in{\mathbb R}}$.

— 2. Well distribution with respect to Riesz means —

As mentioned earlier, in the paper we deal with a more general class of functions than ${f(n)=\lfloor n^a\rfloor}$. To describe this class we will make use of the discrete derivative operator ${\Delta}$ on functions ${f:{\mathbb N}\rightarrow{\mathbb R}}$ defined as ${\Delta f(n)=f(n+1)-f(n)}$.

Definition 4 Denote by ${{\mathcal F}_0}$ the collection of all sequences ${f:{\mathbb N}\rightarrow{\mathbb R}}$ which are eventually monotone, satisfy ${\displaystyle\lim_{n\rightarrow\infty}f(n)=0}$ and ${\displaystyle\sum_{n=1}^\infty f(n)=\infty}$.

For each ${\ell\in{\mathbb N}}$ let ${{\mathcal F}_\ell:=\big\{f:{\mathbb N}\rightarrow{\mathbb R}:\Delta f\in{\mathcal F}_{\ell-1}\big\}}$ and let ${{\mathcal F}=\bigcup_{\ell=1}^\infty{\mathcal F}_\ell}$.

Example 1

• For each ${a>0}$ non integer, the function ${f(n)=n^a}$ is in ${{\mathcal F}_\ell}$ where ${\ell=\lceil a\rceil}$.
• The functions ${f(n)=\log n}$, ${f(n)=\log\log n}$ or ${f(n)=\log^2n}$ are all in ${{\mathcal F}_1}$.

Theorem 1 holds for any function arising from ${{\mathcal F}}$.

Theorem 5 Let ${(X,\mu,T)}$ be a measure preserving system, let ${A\subset X}$, and ${\epsilon>0}$. Then for every ${f\in{\mathcal F}}$, the set

$\displaystyle R=\big\{n\in{\mathbb N}:\mu(A\cap T^{-\lfloor f(n)\rfloor}A)>\mu^2(A)-\epsilon\big\}$

is thick.

In view of the discussion in the previous section (or just by considering a rotation on the torus) there is a close connection between Theorem 5 and the fact that for any ${f\in{\mathcal F}}$ the sequence ${f(n)\bmod1}$ is thickly dense in ${[0,1)}$. However, the proof we used to establish thick denseness of the sequence ${n^a}$ in the previous section will not work for functions such as ${f(n)=n^2\log n}$, because the triple ${\big(f(n),f(n+1),f(n+2)\big)}$ is not uniformly distributed in any subgroup of ${{\mathbb T}^3}$.

It is true that the sequence ${\big(f(n),f(n+1),f(n+2)\big)}$ is dense in ${{\mathbb T}^3}$ whenever ${f\in{\mathcal F}_2}$, but one can not prove this using the usual theory of uniform distribution. Instead we resort to the concept of Riesz means (or weighted means, as discussed in this previous post), and indeed of uniform Riesz means:

Definition 6 Let ${W\in{\mathcal F}_1}$ be a weight. A sequence ${f:{\mathbb N}\rightarrow{\mathbb C}}$ converges with respect to the Riesz mean ${W}$ if

$\displaystyle \underset{n\rightarrow\infty}{{W}\text{-}\lim}~f(n):= \lim_{N\rightarrow\infty}\frac1{W(N)}\sum_{n=1}^N\Delta W(n)f(n)$

exists. We say that the uniform limit with respect to ${W}$ exists if

$\displaystyle \underset{n\rightarrow\infty}{{UW}\text{-}\lim}~f(n):= \lim_{W(N)-W(M)\rightarrow\infty}\frac1{W(N)-W(M)}\sum_{n=M}^N\Delta W(n)f(n)$

exists.

Note that for ${W(n)=n}$ the ${{W}\text{-}\lim}$ coincides with the Cesàro limit. However, for different weights ${W}$ we get more general modes of convergence. For instance, if ${W(n)=\log n}$, the ${W}$${\lim}$ is what is usually called the logarithmic averages.

It makes sense to define uniform distribution with respect to Riesz means. We say that a sequence ${x(n)}$ taking values in a compact group ${G}$ is uniformly distributed with respect to a weight ${W\in{\mathcal F}_1}$ if for every continuous function ${\phi\in C(G)}$ the limit ${W}$${\lim\phi(x(n))}$ exists and equals ${\int_G\phi d\mu}$, where ${\mu}$ is the Haar measure on ${G}$. If moreover the uniform limit ${UW}$${\lim\phi(x(n))}$ exists and equals ${\int_G\phi d\mu}$, then we say that ${x(n)}$ is well distributed with respect to ${W}$.

It turns out that every function ${f\in{\mathcal F}}$ is well distributed ${\bmod1}$ with respect to some Riesz mean, and moreover, the sequence ${\big(f(n),f(n+1),\dots,f(n+k)\big)}$ is well distributed with respect to some Riesz mean in some subgroup ${H}$ of ${{\mathbb T}^{k+1}}$.

One can also extend the notion of syndetic sets to that of ${W}$-syndetic sets. Recall that a set ${S}$ is syndetic if it has non-empty intersection with every large enough interval. In other terms, if there exists a length ${L}$ such that for every interval ${I\subset{\mathbb N}}$ with ${|I|\geq L}$ we have ${|I\cap L|\geq1}$. For Riesz means ${W}$, we replace the cardinality of a finite set ${I}$ with the quantity ${\sum_{i\in I}\Delta W(i)}$. Observe that letting ${W(n)=n}$ we recover the cardinality of ${I}$ in this way.

Definition 7 (${W}$-syndetic set) Let ${W\in{\mathcal F}}$. A set ${S\subset{\mathbb N}}$ is ${W}$-syndetic if there exists ${L>0}$ such that for every interval ${I=[a,b]\subset{\mathbb N}}$ with ${W(b)-W(a)\geq L}$ we have

$\displaystyle \sum_{n\in I\cap S}\Delta W(n)\geq1.$

It turns out that the set ${R}$ in Theorem 5 is not only thick (in the usual sense) but also ${W}$-syndetic for some ${W\in{\mathcal F}}$. This follows easily from the facts mentioned about and the observation that if a sequence ${x(n)}$ is well distributed with respect to ${W}$ on some compact group ${G}$, then for every non-empty open set ${U}$ of ${W}$, the set ${\{n:x(n)\in U\}}$ is ${W}$-syndetic. This in turn follows directly from the next proposition.

Proposition 8 Let ${S\subset{\mathbb N}}$ and let ${W\in{\mathcal F}_1}$. Then ${S}$ is ${W}$-syndetic if and only if for every sequence of intervals ${[a_N,b_N]}$ in ${{\mathbb N}}$ with ${W(b_N)-W(a_N)\rightarrow\infty}$

$\displaystyle \limsup_{N\rightarrow\infty}\frac1{W(b_N)-W(a_N)}\sum_{n=a_N}^{b_N} \Delta W(n)1_S(n)>0.$

The statement is still true if one replaces ${\limsup}$ with ${\liminf}$.

Proof: Assume first that ${S}$ is not ${W}$-syndetic and let ${I_N=[a_N,b_N]}$ be an interval of length ${N}$ such that ${W(b_N)-W(a_N)\geq N}$ but ${\sum_{n=a_N}^{b_N}\Delta W(n)1_S(n)<1}$. Then it is clear that

$\displaystyle \limsup_{N\rightarrow\infty}\frac1{W(b_N)-W(a_N)}\sum_{n=a_N}^{b_N} \Delta W(n)1_S(n)=0.$

Next assume that ${S}$ is ${W}$-syndetic and let ${L}$ be given by Definition 7. Then every interval ${I=[a,b]}$ with ${W(b)-W(a)>2rL}$ can be partitioned into ${r}$ disjoint intervals ${I_i=[a_i,b_i]}$, ${i=1,\dots,r}$ with ${W(a_i)-W(b_i)>L}$ and so we have

$\displaystyle \sum_{n=a}^{b}\Delta W(n)1_S(n) \geq\sum_{i=1}^r\sum_{n=a_i}^{b_i}\Delta W(n)1_S(n) \geq r$

which implies that

$\displaystyle \begin{array}{rcl} &&\displaystyle\limsup_{N\rightarrow\infty}\frac1{W(b_N)-W(a_N)}\sum_{n=a_N}^{b_N} \Delta W(n)1_S(n) \\&\geq& \displaystyle\limsup_{N\rightarrow\infty} \frac{\lfloor(W(b_N)-W(a_N))/2L\rfloor}{W(b_N)-W(a_N)} \\&=& \displaystyle\frac1{2L}>0 \end{array}$

$\Box$