## Convergence along ultrafilters

— 1. Introduction —

On my previous post about recurrent theorems I stated Khintchine’s theorem and Sarkozy’s theorem. There I classified Khintchine’s theorem as a theorem about large intersections and Sarkozy’s theorem as a theorem about large recurrent times.

This will be the first in a series of two posts where I will prove the following result, which I would classify as a theorem about large recurrent times for large intersections. Recall that a measure preserving system (shortened to m.p.s.) is a quadruple ${(X,{\cal B},\mu, T)}$, where ${(X,{\cal B},\mu)}$ is a probability space and ${T:X\rightarrow X}$ preserves the measure, i.e. for each ${A\in {\cal B}}$ we have ${\mu(T^{-1}A)=\mu(A)}$.

Theorem 1 Let ${(X,{\cal B},\mu, T)}$ be a m.p.s. and let ${A\in {\cal B}}$ have positive measure. Let ${q\in {\mathbb Z}[x]}$ be a polynomial such that ${q(0)=0}$. Then for any ${\lambda<1}$, the set

$\displaystyle \{n\in {\mathbb Z}:\mu(T^{-q(n)}A\cap A)>\lambda\mu(A)^2\}$

is syndetic, i.e. has bounded gaps.

It turns out we just need the polynomial ${q}$ to be divisible, i.e., for each ${k\in {\mathbb N}}$ there is some ${n}$ such that ${q(n)}$ is divisible by ${k}$ (If ${q(0)=0}$, or actually if ${q(n)=0}$ for some ${n}$ then ${q}$ is automatically divisible). Also, in order to prove that the set is syndetic we prove the stronger fact that it is indeed IP${^*}$.

The main tool to prove theorem 1 is that of limits along ultrafilters (which I mentioned in the end of my previous post on different ways of taking limits). We denote this as ${p}$-lim, where ${p}$ is an ultrafilter on ${{\mathbb N}}$ (which explains why the polynomial was given the name “${q}$“). The proof follows this survey by Bergelson (it’s Theorem 3.11 there), where there is much more information about this and similar results.

In this post I define and prove (most of) the results about ultrafilters that we will need. I will complete the proof of theorem 1 in my next post.

Definition 2 (Ultrafilter) An ultrafilter on ${{\mathbb N}}$ is a collection ${p}$ of subsets of ${{\mathbb N}}$ satisfying the following ${4}$ conditions.

1. ${\emptyset\notin p}$.
2. If ${A\in p}$ and ${A\subset B}$ then ${B\in p}$.
3. If ${A}$ and ${B}$ are in ${p}$ then also ${A\cap B\in p}$.
4. If ${A\notin p}$ then ${{\mathbb N}\setminus A\in p}$.

Given a natural number ${n}$, it is not hard to check that the collection of all subsets of ${{\mathbb N}}$ that contains ${n}$ form an ultrafilter. Such ultrafilters are called principal. However this are rather uninteresting ultrafilters, so we will only consider non-principal ultrafilters. The existence of a non-principal ultrafilter requires the axiom of choice (under the form of the Zorn’s lemma): one considers some non-principal collection of subsets satisfying the first ${3}$ conditions (such a collection is called a filter, for instance all sets of the form $\{n,n+1,n+2,...\}$) and then consider the family of all filters that contain the first given filter. It’s not hard to check that we are in conditions of the Zorn’s lemma and that the maximal element will be a filter that also satisfies the fourth axiom of ultrafilter. This explains why ultrafilters are sometimes called maximal filters.

Another way to think about ultrafilters is to see them as finitely additive probability measures on ${{\mathbb N}}$ that only give the value ${0}$ and ${1}$. More precisely ${p(A)=1\iff A\in p}$ and ${p(A)=0\iff A\notin p}$. This motivates the following definition:

Definition 3 (Convolution of ultrafilters) Let ${p}$ and ${r}$ be ultrafilters. We define their convolution as

$\displaystyle A\in p*r\qquad\iff\qquad \{n\in{\mathbb N}:A-n\in p\}\in r$

One can check that this corresponds to the usual convolution of measures. One type of ultrafilters that are of special interest are the idempotent ultrafilters:

Definition 4 (Idempotent Ultrafilters) An ultrafilter ${p}$ is called idempotent if ${p*p=p}$.

The fact that idempotent ultrafilters exist is a consequence of a theorem of Ellis and uses topological properties of the set of all ultrafilters, namely that this set with the convolution is a compact left continuous semigroup.

Given an ultrafilter ${p}$, and a sequence ${\{x_n\}_{n\in{\mathbb N}}}$ in a topological space, one can consider the limit of ${\{x_n\}}$ along ${p}$:

Definition 5 (Convergence along an ultrafilter) Let ${p}$ be an ultrafilter and let ${\{x_n\}_{n\in{\mathbb N}}}$ be a sequence in some topological space ${X}$. Let ${x\in X}$. We say that ${x_n}$ converges to ${x}$ along ${p}$ (or that ${ p}$${\displaystyle\lim_{n\rightarrow\infty} x_n=x}$) if for each neighborhood ${U}$ of ${x}$, the set ${\{n\in{\mathbb N}: x_n\in U\}}$ is in ${p}$.

The most fascinating aspect of this method of convergence is that if the topological space ${X}$ is compact, then any sequence has limit along ${p}$:

Proposition 6 Let ${p}$ be an ultrafilter, let ${X}$ be a compact Hausdorff space and let ${\{x_n\}_{n\in{\mathbb N}}}$ be any sequence taking values on ${X}$. Then there exists exactly one point ${x\in X}$ such that ${ p}$${\displaystyle\lim_{n\rightarrow\infty} x_n=x}$.

Proof: First we prove existence, if no such ${x}$ exists, then for each point ${y\in X}$ there is an open neighborhood ${U_y}$ of ${y}$ such that ${\{n\in{\mathbb N}: x_n\in U_y\}\notin p}$. The cover ${U_y}$ will have a finite subcover by compactness, and so we can partition ${{\mathbb N}}$ into finitely many disjoint pieces, according to which atom of the subcover contains ${x_n}$ (if ${x_n}$ belongs to more than one atom of the finite subcover, choose any of those atoms arbitrarily). Also by constructions, no piece in this partition is in ${p}$, and we can easily see that this contradicts the fact that ${p}$ is an ultrafilter.

To prove uniqueness, let ${x\neq y}$ be two distinct points in ${X}$. Choose two disjoint neighborhoods ${U_x}$ of ${x}$ and ${U_y}$ of ${y}$. The sets ${\{n:x_n\in U_x\}}$ and ${\{n:x_n\in U_y\}}$ are also disjoint and so they can’t both be in ${p}$, so ${x}$ and ${y}$ can’t both be a $p$${\lim}$ of ${\{x_n\}}$. $\Box$

We will use this fact on spheres in the ${L^2}$ space (which are compact in the weak topology by the Banach-Alaoglu theorem). Finally we need the following result, relating ${p}$${\lim}$ with the convolution of ultrafilters:

Proposition 7 Let ${p}$ and ${r}$ be ultrafilters, let ${X}$ be a compact Hausdorff space and let ${\{x_n\}_{n\in{\mathbb N}}}$ be a sequence taking values in ${X}$. Then

$\displaystyle (p*r)\text{-}\lim_{n\rightarrow\infty} x_n=r\text{-}\lim_{t\rightarrow\infty} \left(p\text{-}\lim_{m\rightarrow\infty} x_{t+m}\right)$

Proof: Let ${\displaystyle x=(p*r)\text{-}\lim_{n\rightarrow\infty} x_n}$ and let ${\displaystyle y_t=p\text{-}\lim_{m\rightarrow\infty} x_{t+m}}$. Then for each neighborhood ${U}$ of ${x}$, we have

$\displaystyle \begin{array}{rcl} \{n:x_n\in U\}\in p*r&\iff&\displaystyle \{t:\{n:x_n\in U\}-t\in p\}\in r\\&\iff&\displaystyle \{t:\{n-t:x_n\in U\}\in p\}\in r\\&\iff& \displaystyle \{t:\{m:x_{t+m}\in U\}\in p\}\in r\\&\iff&\displaystyle \{t:y_t\in U\}\in r \end{array}$

Since this happens for every neighborhood of ${x}$ we conclude that ${r}$${\displaystyle\lim_{t\rightarrow\infty} y_t=x}$.

$\Box$

We will also need another fact about convergence along ultrafilters, roughly speaking it says that passing to certain “subsequences” doesn’t change the limit. First let’s make a definition

Definition 8 Let ${p}$ be an ultrafilter, and let ${A\subset {\mathbb N}}$. Let ${\{x_n\}}$ be some sequence taking values in a topological space. We denote the ${p}$${\lim}$ over ${A}$ to be ${\displaystyle p\text{-}\lim_{n\rightarrow\infty;n\in A}x_n=x}$ and this means that for each neighborhood ${U}$ of ${x}$, the set ${\{n\in A: x_n\in U\}\in p}$.

Note that if ${A\in p}$ then ${p}$${\lim_{n\rightarrow\infty;n\in A}x_n=p}$${\lim_{n\rightarrow\infty}x_n}$ and if ${A\notin p}$ then the ${p}$${\lim}$ over ${A}$ doesn’t exist.

Corollary 9 Let ${p}$ be an idempotent ultrafilter and let ${a\in{\mathbb N}}$. Also let ${\{x_n\}}$ be a sequence in a compact Hausdorff space. We have:

1. If ${B\in p}$ then ${B\cap(a{\mathbb N})\in p}$.
2. ${p}$${\displaystyle \lim_{n\rightarrow\infty, n\in a{\mathbb N}}x_n=p}$${\displaystyle \lim_{n\rightarrow\infty}x_n}$.

Proof:

1. We can partition ${{\mathbb N}=a{\mathbb N}\cup(a{\mathbb N}+1)\cup...\cup (a{\mathbb N}+(a-1))}$, so by the condition (4) in the definition of ultrafilters and a simple induction we conclude that exactly one of the sets ${a{\mathbb N}+i}$ is in ${p}$, we now will prove that ${i=0}$. Since ${p}$ is idempotent we have that ${\{x\in{\mathbb N}:(a{\mathbb N}+i+x)\in p\}\in p}$. But the set ${(a{\mathbb N}+i+x)}$ is in ${p}$ exactly when ${a|x}$, and so the set ${a{\mathbb N}\in p}$ as desired. Now the intersection ${(a{\mathbb N})\cap B\in p}$ as well.
2. This follows from part (1) and the comment before this corollary.

$\Box$