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.

4 Responses to Double van der Waerden

  1. Pingback: Applications of ultrafilters | Complex Projective 4-Space

  2. Pingback: Pomerance Theorem on colinear points in certain paths in a two dimensional lattice | I Can't Believe It's Not Random!

  3. Pingback: Piecewise syndetic sets, topological dynamics and ultrafilters | I Can't Believe It's Not Random!

  4. Pingback: An arithmetic van der Corput trick and the polynomial van der Waerden theorem | I Can't Believe It's Not Random!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s