## Double van der Waerden

— 1. Introduction —

In a previous post I presented a proof of van der Waerden’s theorem on arithmetic progressions:

Theorem 1 (van der Waerden, 1927) Consider a partition of the set of the natural numbers into finitely many pieces ${{\mathbb N}=C_1\cup...\cup C_r}$. Then one of the pieces ${C_i}$ contains arbitrarily long arithmetic progressions.

It follows easily from van der Waerden’s theorem that, for any finite partition of ${{\mathbb N}}$, one of the pieces in the partition contains arbitrarily long geometric progressions. To see this consider the partition of the set ${\{2^n:n\in{\mathbb N}\}}$. In fact, we can take the same piece to contain arbitrarily long arithmetic progressions and arbitrarily long geometric progressions. More precisely:

Theorem 2 Let ${{\mathbb N}=C_1\cup...\cup C_r}$ be a partition of ${{\mathbb N}}$ into finitely many pieces. Then there exists ${i\in\{1,...,r\}}$ such that for all ${k\in{\mathbb N}}$ there are ${a,b,s,t\in{\mathbb N}}$ such that ${a+js\in C_i}$ and ${bt^j\in C_i}$, for each ${j=0,...,k}$.

In this post I will present a proof of this fact due to Bergelson and Hindman.

This proof uses the technology of ultrafilters on ${{\mathbb N}}$, and the only other proof I know of this fact uses the much stronger Szemeredi’s theorem.

— 2. Preliminaries on ultrafilters —

In this section I will list some facts about ultrafilters on ${{\mathbb N}}$ that I will need later in the post. For a more complete treatment, including the proof of all facts claimed here, see, for instance, my previous post on the subject, or these two surveys by Bergelson.

In this post, ${G}$ will denote a countable abelian semigroup and ${S}$ will denote a general semigroup. Also ${e}$ will always denote the identity of the semigroups (it will be clear in the context which semigroup ${e}$ belongs to). We will only use ${G=({\mathbb N},+)}$ and ${G=({\mathbb N},\times)}$, but the theorems and definitions are easier to state in this general form.

An ultrafilter over ${G}$ is a collection ${p}$ of subsets of ${G}$ such that, for every finite partition of ${G}$, exactly one of the pieces is in ${p}$. It follows easily from the definition that the empty set is not in ${p}$; that if ${A,B\in p}$ then ${A\cap B\in p}$, and that if ${A\in p}$ and ${A\subset B}$, then also ${B\in p}$.

The only explicit examples of ultrafilters are the principal ultrafilters and are defined as follows: let ${g\in G}$ and let ${\hat g:=\{A\subset G:g\in A\}}$. The existence of any other ultrafilter requires the axiom of choice (or at least some weak form of it).

The set of all ultrafilters over ${G}$ is denoted by ${\beta G}$. Given a set ${A\subset G}$ we denote by ${\bar A\subset\beta G}$ the set of all ultrafilters that contain ${A}$. We will use the topology on ${\beta G}$ generated by the clopen sets ${\bar A}$ with ${A\subset G}$. With this topology ${\beta G}$ is compact.

Given ${p,q\in\beta G}$ we define the operation ${pq}$ by

$\displaystyle A\in pq\iff\{g\in G:Ag^{-1}\in p\}\in q$

where ${Ag^{-1}:=\{h\in G:hg\in A\}}$. It follows that, with this operation, ${\beta G}$ becomes a left topological semigroup. Moreover if ${p\in\beta G}$ and ${g\in G}$, then ${\hat gp=p\hat g}$. All the facts stated so far are proved is my previous post mentioned above.

We will need the following theorem of Ellis:

Theorem 3 (Ellis) Let ${S}$ be a left topological compact semigroup. Then there exists an element ${s\in S}$ such that ${ss=s}$.

An element ${s\in S}$ which satisfies ${ss=s}$ is called an idempotent.

A left ideal of a non-abelian semigroup ${S}$ is a compact set ${E\subset S}$ such that ${SE:=\{sx:s\in S,x\in E\}\subset E}$. Analogously one define right ideal as a compact set ${E\subset S}$ such that ${ES\subset E}$. We will also say that ${E}$ is a two-sided ideal if ${E}$ is both a left and a right ideal.

Definition 4 An ultrafilter ${p\in\beta G}$ is a minimal idempotent if ${pp=p}$ and there exists a right ideal ${R\subset\beta G}$ which is minimal with respect to inclusion and such that ${p\in R}$. A set ${A\subset G}$ is called central if there exists a minimal idempotent ${p\in\beta G}$ such that ${A\in p}$.

It is true that for any semigroup ${S}$ there exists a minimal idempotent ultrafilter ${p\in\beta G}$, but we will not need this fact for this post.

Finally we will use the following technical definition. This is not standard terminology.

Definition 5 We say that a semigroup ${G}$ is without inverses if for every ${g\in G}$, ${g\neq e}$ there is no ${h\in G}$ such that ${gh=e}$.

It’s easy to verify that both ${({\mathbb N},+)}$ and ${({\mathbb N},\times)}$ are semigroups without inverses.

— 3. Proof of Theorem 2

The following theorem is a generalization of van der Waerden theorem for any abelian semigroup without inverses.

Theorem 6 Let ${G}$ be an abelian semigroup without inverses and let ${A\subset G}$ be central. Then for each ${k\in{\mathbb N}}$ there exist ${a,r\in G}$ such that ${\{ar^j:j=0,...,k\}\subset A}$.

Proof: Let ${e}$ be the identity of ${G}$, if it exists. Otherwise, we can always create an identity, and we will denote it also by ${e}$ (keep in mind that we will apply this theorem to both semigroups ${({\mathbb N},+)}$ and ${({\mathbb N},\times)}$, the second has an identity but the first doesn’t. In any case, this is just a technical detail).

Fix ${k\in{\mathbb N}}$. Let ${X=(\beta G)^{k+1}}$ and let it have the product topology. Note that ${X}$ is a semigroup for pointwise operation. Let ${E}$ be the closure in ${X}$ of the set ${\big\{(a,ar,ar^2,...,ar^k):a\in G, r\in G\cup\{e\}\big\}}$ and let ${I}$ be the closure in ${X}$ of the set ${\{(a,ar,ar^2,...,ar^k):a,r\in G;r\neq e\}}$. Note that

$\displaystyle \begin{array}{rcl} \displaystyle x=(x_0,...,x_k)\in E&\iff&\displaystyle \forall\text{ open }U\ni x, U\cap E\neq\emptyset\\&\iff&\displaystyle \forall\big(U_0\ni x_0,...,U_k\ni x_k\big), U_0\times...\times U_k\cap E\neq\emptyset\\&\iff&\displaystyle \forall\big(A_0\in x_0,...,A_k\in x_k\big), \overline{A_0}\times...\times\overline{A_k}\cap E\neq\emptyset\\&\iff&\displaystyle \forall\big(A_0\in x_0,...,A_k\in x_k\big), \exists a\in G, r\in G\cup\{e\}\\&&\displaystyle \text{ such that } ar^j\in A_j\text{ for }j=0,...,k \end{array}$

Similarly for ${I}$ we get

$\displaystyle \begin{array}{rcl} \displaystyle x=(x_0,...,x_k)\in I&\iff&\displaystyle \forall\big(A_0\in x_0,...,A_k\in x_k\big), \exists a\in G, r\in G\setminus\{e\}\\&&\displaystyle \text{ such that } ar^j\in A_j\text{ for }j=0,...,k \end{array}$

In particular, for any ${p\in\beta G}$, we have ${(p,p,...,p)\in E}$. Indeed, for any ${A_0,...,A_k\in p}$, the intersection ${\bigcap A_j}$ is also in ${p}$ and in particular it is non-empty. Choosing ${a}$ in the intersection and ${r=e}$ we conclude that ${ar^j\in A_j}$ for all ${j}$.

We claim that ${E}$ is a semigroup and ${I\subset E}$ is a two-sided ideal. Indeed, let ${x,y\in E}$. For each ${j=0,...,k}$ let ${A_j\in x_jy_j}$. This implies that ${B_j:=\{g\in G:A_j/g\in x_j\}\in y_j}$. Let ${a\in G}$ and ${r\in G\cup\{e\}}$ be such that ${ar^j\in B_j}$ for each ${j=0,...,k}$. Let ${C_j:=A_j/(ar^j)\in x_j}$. Let ${b\in G}$ and ${s\in G\cup\{e\}}$ be such that ${bs^j\in C_j}$ for each ${j=0,...,k}$. Then ${(bs^j)(ar^j)=(ab)(rs)^j\in A_j}$ and so ${xy\in E}$. Moreover, if either ${x}$ or ${y}$ is in ${I}$, then not both of ${r,s}$ is equal to ${e}$, and since ${G}$ is without inverses, we conclude that ${rs\neq e}$, which implies that ${xy\in I}$. This proves the claim.

Now let ${p\in\beta G}$ be a minimal ultrafilter such that ${A\in p}$. We will show that ${\textbf{p}:=(p,p,...,p)\in I}$. Let ${I_0=\textbf{p}E}$. This is a right ideal of ${E}$. Therefore there exists a minimal right ideal ${R}$ of ${E}$ contained in ${\textbf{p}E}$. We will show that ${\textbf{p}\in R}$.

Since ${p}$ is minimal it is in some minimal right ideal ${R'}$ of ${\beta G}$. Let ${q\in R}$ be an idempotent, it exists by Ellis theorem. Then ${q=\textbf{p}s}$ for some ${s\in E}$. This means that for each ${j=0,...,k}$ we have ${q_j=ps_j}$, and thus ${q_j\in p(\beta G)=R'}$. We conclude that ${q_j(\beta G)=R'}$, and in particular ${p=q_jt_j}$ for some ${t_j\in(\beta G)}$. Therefore ${q_jp=q_jq_jt_j=q_jt_j=p}$, and since this happens for every ${j=0,...,k}$ we obtain that ${q\textbf{p}=\textbf{p}}$. Finally this gives ${\textbf{p}\in qE=R}$ as claimed.

Now we note that ${R\cap I}$ is a non-empty right ideal of ${E}$. Indeed, it is non-empty because if ${x\in R}$ and ${y\in I}$ then ${xy\in R\cap I}$. But since ${R}$ is a minimal right ideal, this implies that ${R\cap I=R}$, and since ${\textbf{p}\in R}$, we conclude that ${\textbf{p}\in I}$.

Since ${A\in p}$ we have that there exists ${a,r\in G}$ with ${r\neq e}$ such that ${\{ar^j:j=0,...,k\}\subset A}$, as desired. $\Box$

Now to finish the proof of Theorem 2 it suffices to show that, for every finite partition of ${{\mathbb N}}$, one of the pieces is both additively central and multiplicatively central. This in turn is a direct consequence of the following theorem:

Theorem 7 There exists an ultrafilter ${p\in\beta{\mathbb N}}$ such that each set ${A\in p}$ is both additively central and multiplicatively central.

Proof: Let ${\Gamma}$ be the set of all additive minimal idempotents. To see that ${\Gamma}$ is non-empty, let ${I\subset\beta{\mathbb N}}$ be a minimal right ideal (in ${(\beta{\mathbb N},+)}$), which exists by Zorn lemma. Then ${I}$ is a compact semigroup in itself. Applying Ellis theorem (Theorem 3) we obtain a minimal idempotent for ${(\beta{\mathbb N},+)}$.

Note that if ${p\in\bar\Gamma}$, then for every ${A\in p}$ there exists ${q\in\Gamma}$ such that ${A\in q}$, and so ${A}$ is central. Conversely, if every ${A\in p}$ is central, then every neighborhood of ${p}$ intersects ${\Gamma}$ and so ${p\in\bar\Gamma}$. We claim that ${\bar\Gamma}$ is a right ideal in ${(\beta{\mathbb N},\times)}$.

Indeed, let ${p\in\bar\Gamma}$ and let ${q\in\beta{\mathbb N}}$. We need to show that ${pq\in\bar\Gamma}$. Let ${A\in pq}$, we need to show that ${A}$ is central. By definition of ${pq}$ we have that ${\{n\in{\mathbb N}:A/n\in p\}\in q}$, and in particular this set is non-empty.

Let ${n\in{\mathbb N}}$ be such that ${A/n\in p}$. Since ${p\in\bar\Gamma}$ we conclude that ${A/n}$ is central. Let ${r\in\Gamma}$ be such that ${A/n\in r}$. This means that ${A\in \hat nr}$, where ${\hat n}$ is the principal ultrafilter at ${n}$. We need to show that ${r\hat n\in\Gamma}$. Let ${R}$ be a minimal right ideal in ${(\beta{\mathbb N},+)}$ such that ${r\in R}$. Then also ${\hat nr=r\hat n\in R}$ and so ${\hat nr}$ is a minimal ultrafilter. It remains to show that ${\hat nr}$ is an idempotent:

$\displaystyle \begin{array}{rcl} \displaystyle B\in\hat nr+\hat nr&\iff&\displaystyle \{m:B-m\in\hat nr\}\in\hat nr\iff\left\{m:\frac{B-m}n\in r\right\}/n\in r\\&\iff&\displaystyle \left\{m:\frac{B-mn}n\in r\right\}\in r\iff\left\{m:\frac Bn-m\in r\right\}\in r\\&\iff&\displaystyle B/n\in r+r=r\iff B\in\hat nr\end{array}$

We have that ${\bar\Gamma}$ is a right ideal in the semigroup ${(\beta{\mathbb N},\times)}$. By Zorn’s lemma we can find a minimal multiplicative ideal inside ${\bar\gamma}$. This is a sub-semigroup of ${(\beta{\mathbb N},\times)}$, so by Ellis theorem we obtain a multiplicative minimal idempotent ${p\in\bar\Gamma}$. In particular every set ${A\in p}$ is both additively and multiplicatively central, as desired. $\Box$

This entry was posted in Combinatorics, Ramsey Theory and tagged , , , . Bookmark the permalink.