Ramsey and Ultrafilters 1 – Ramsey DocCourse Prague 2016 – Mike Pawliuk

The following notes are from the Ramsey DocCourse in Prague 2016. The notes are taken by me and I have edited them. In the process I may have introduced some errors; email me or comment below and I will happily fix them.

Special thanks to Ivan Khatchatourian for clarifying some typos and adding some elaborations.

Title: Ramsey and Ultrafilter 1 (of 2)

Lecturer: Slawomir Solecki

Date: Wednesday October 19, 2016.

Main Topics: Gowers’ Theorem, Lupini’s Theorem, Furstenberg-Katznelson Theorem, Monoids, Semigroups.

Definitions: [many]

Lecture 1 – Lecture 2

These two lectures are based on the following 2016 paper of Solecki: “Monoid actions and ultrafilter methods in Ramsey theory“.

Introduction

We will look at three related Ramsey results: Gowers’ Theorem, Lupini’s generalization and Furstenberg-Katznelson. These theorems all use the technology of (partial) semigroups and idempotent ultrafilters. We will introduce the relevant technology and then work towards a general statement that captures all three theorems. To do this we introduce language and notions from Monoid theory.

The second lecture will look at the proofs of these theorems.

The following references are useful in understanding the ideas that go into these proofs:

- “Partition theorems for spaces of variable words” Bergelson-Blass-Furstenberg, 1994. PDF.
- “Introduction to Ramsey Spaces” Todorcevic, 2010. Google Book

The three big theorems

Definition. Let $\mathcal{A}$ be an alphabet (usually taken to be $n := \{0, \ldots, n-1\}$ ). A located word is a finite partial function from $\mathbb{N}$ to $\mathcal{A}$ . Given two located words $v,w$ we say that $v \prec w$ iff $\max(\text{dom}(v)) < \min(\text{dom}(w))$ .

When $v \prec w$ we write the concatenation $vw$ for $v \cup w$ .

Denote by $W(\mathcal{A})$ the words in $\mathcal{A}$ . In the (common) case that $\mathcal{A} = \{0, \ldots, n-1\} = n$ we denote $W(n):= W(\mathcal{A})$ .

The Tetris operator $T: n \longrightarrow n$ where $T(i) = i-1$ if $i>0$ and $T(0)=0$ . We may extend this to act on words by taking $T(n_0 n_1 \ldots n_k) = T(n_0) T(n_1) \ldots T(n_k)$ .

We denote $k$ repeated applications of $T$ on a word by $T^k(w)$ .

Gowers’ theorem

We are now in a position to state Gowers’ theorem. In short it is a Ramsey result about the structure of repeated applications of $T$ to different sections of a word.

Gowers’ Theorem. Colour $W(n)$ using finitely many colours. There are words $w_0 \prec w_1 \prec \ldots$ (with $\max w_i = n-1, \forall i$ ) such that the colour of $T^{i_0}(w_{n_0}) \ldots T^{i_k}(w_{n_k})$ depends only on $\min(i_0, \ldots, i_k)$ for all $n_0 < \ldots < n_k$ and all $i$ .

Note that if the minimum is $0$ , then there are no applications of the Tetris operator, so all these words have the same colour.

There is also a hereditary version of Gowers’ Theorem that guarantees the existence of monochromatic block subspaces.

Definition. Fix words $v_0 \prec v_1 \prec \ldots$ such that $\max(v_i) = n-1$ .

Let $\langle (v_i)\rangle = \{T^{i_0}(v_{n_0}) \ldots T^{i_k}(v_{n_k}) : n_0 < \ldots < n_k \text{ and }i_0 < \ldots < i_k\}$ .

Hereditary Gowers’ Theorem. Colour $\langle (v_i)\rangle$ using finitely many colours. There are words $w_0 \prec w_1 \prec \ldots \in \langle (v_i)\rangle$ such that the colour of $T^{i_0}(w_{n_0}) \ldots T^{i_k}(w_{n_k})$ depends only on $\min(i_0, \ldots, i_k)$ for all $n_0 < \ldots < n_k$ and all $i$ .

Lupini’s theorem

We now prepare to state Lupini’s generalization of this. The generalization focuses on generalizing the Tetris operator to any 1-Lipschitz maps.

Definition. Fix $n$ . Let $I_n = \{f: n \longrightarrow n : f(0)=0, f(i-1) \leq f(i) \leq f(i-1)+1, \forall 1 \leq i \leq n\}$ .

Equivalently, $I_n$ is the collection of non-decreasing surjections onto $k$ for some $0 < k \leq n$ . Equivalently, it is the collection of non-decreasing $1$ -Lipschitz functions from $n$ to $n$ .

Note that the Tetris operator is in $I_n$ .

Theorem (Lupini 2016). Colour $W(n)$ using finitely many colours. There are words $w_0 \prec w_1 \prec \ldots$ (with $\max w_i = n-1, \forall i$ ) such that the colour of $f_0(w_{n_0}) \ldots f_k(w_{n_k})$ depends only on $\max_{i\leq k}(\max f_i)$ for all $f_0, \ldots, f_k \in I_n$ and all $n_0 < \ldots < n_k$ .

Exercise. We really did mean “ $\max$ ” here. Show that this is consistent with Gowers’ theorem and the Tetris operation.

Lupini noticed that his proof did not extend to the hereditary version, and asked the following question:

Question (Lupini). Fix $v_0 \prec v_1 \prec \ldots$ (with $\max v_i = n-1, \forall i$ ). Let $\langle (v_i)\rangle = \{f_0(v_{n_0}) \ldots f_k(v_{n_k}) : n_0 < \ldots < n_k \text{ and }f_0, \ldots, f_k \in I_n\}$ . Does the conclusion of Lupini’s Theorem hold for this subspace?

Proposition (Solecki). No! (for $n \geq4$ )

We’ll discuss this example later, but it is the function that sends $i$ to $i\text{mod} n$ (and each “tooth” is a $v_i$ ). There is a 2-colouring of $\langle (v_i)\rangle$ such that no $w_0 \prec w_1 \prec \ldots$ (with $\max w_i = n-1, \forall i$ ), is the set $\{f_0(w_{n_0}) \ldots f_k(w_{n_k}) : n_0 < \ldots < n_k \text{ and }f_0, \ldots, f_k \in I_n, \exists i \leq k, f_i = Id_n\}$ is monochromatic.

Notice that the max is stabilized.

Furstenberg-Katznelson

“This theorem doesn’t get so much press.”

Definition. Let $A,B$ be disjoint finite sets. Let $c_0, c_1, \ldots, c_k \in A \cup B$ .

The word $\overline{c_0c_1\ldots c_k}$ is the word achieved by first removing all letters in $B$ , then replacing each string of a repeated letter $a \in A$ with a single instance of $a$ .

We will now set the alphabet $\mathcal{A} = A\cup B \cup \{\star\}$ where $\star$ is a placeholder not it $A,B$ . For $c \in A \cup B, w \in W(\mathcal{A})$ let $w(c)$ be the word in $W(A \cup B)$ obtained by substituting the letter $c$ for every occurrence of $\star$ .

This is meant to capture the notion of “type” that the colouring will depend on. In the earlier theorems it was captured by $\min$ or $\max$ .

Theorem (Furstenberg-Katznelson). Fix a finite set of words $F \subset W(A)$ . Colour $W(\mathcal{A})$ using finitely many colours. There are words $w_0 \prec w_1 \prec \ldots \in W(B \cup \{\star\})$ (with $\star$ occuring at least once in each word) such that if $w_{n_0}(c_0) \ldots w_{n_k}(c_k) \in F$ , then its colour depends only on $\overline{c_0c_1\ldots c_k}$ for all $c_0, \ldots, c_k \in A \cup B$ and all $n_0 < \ldots < n_k$ .

If you only draw your substitutions from $B$ , then $\overline{c_0c_1\ldots c_k}$ is always the empty word. This yields the infinite Hales-Jewett theorem (taking $F=\{\emptyset\}$ .)

There is an example where the theorem is false if the set $F$ is infinite.

Monoids and semigroups

Now the goal is to find an abstract setting for all three of these theorems. We draw language from semigroups and monoids.

Definition. A partial semigroup $(S, \star)$ is a set $S$ with a partially defined, associative binary operation $\star$ . We will assume our partial semigroups are directed, that is $\forall s_1, \ldots, s_n, \exists t \in S$ such that $s_i t$ is defined for all $i \leq n$ .

A (finite) monoid $M$ is a set with an associative (fully defined) binary operation and identity element denoted $1_M$ .

A monoid $M$ acts on a partial semigroup $S$ if

$1_M \cdot s = s$ for all $s \in S$ ,
$m \cdot (n \cdot s) = (mn) \cdot s$ , for all $m,n \in M$ and $s \in S$ .
$\forall s,t \in S, \forall m \in M$ if $st$ is defined, then $m(s)m(t)$ is defined equal to $m(st)$ .
$\forall s,t \in S, \forall m \in M$ if $st$ is defined, then $sm(t)$ is defined.

The first two conditions are the usual “action” conditions, and the third and fourth are required because we only have a partial semigroup.

Our monoids will usually resemble the Tetris operator.

Examples

Gowers’. Here $T$ and $T^i$ are the elements of the desired monoid. $M = \{T^i : 0 \leq i < n\}$ .

Lupini. $I_n$ with composition, and it acts letter by letter. (Exercise. Show that this is a monoid.)

Furstenberg-Katznelson. This one is slightly more complicated, but completely illustrates the correct abstraction.

$M = A \cup B \cup \{1\}$ , where $1$ is just a helpful placeholder. Define the operation as follows:

$cb=b$ for all $c \in A \cup B, b \in B$
$ca=c$ for all $c \in A \cup B, a \in A$
$1c=c1=c$ for all $c \in A \cup B$ .

Notice that elements of $A$ and $B$ behave differently. $M$ acts on words in $W(A\cup B \cup \{\star\})$ by substitution for $\star$ and left multiplication on other letters.

Ramsey appears

This helps us describe some Ramsey behaviour.

Definition. Let $M$ be a finite monoid. We say that $M$ is Ramsey if for all colourings of $W(M)$ , there are words $w_0 \prec w_1 \prec \ldots$ (with $1_M$ occuring at least once in each word) such that the collection of all words $m_0(w_{n_0}) \ldots m_k(w_{n_k})$ , where $m_0, \ldots, m_k \in M$ and all $n_0 < \ldots < n_k$ , is monochromatic.

It turns out that Lupini’s example is not Ramsey, but behaves like Ramsey. (We’ll explain more below.)

Some definitions from monoid theory

Fix a finite monoid $M$ .

Definition. Define the collection of ideals $X(M) = \{mM : m \in M\}$ , and give it the partial order $\subseteq$ . (This object isn’t that complicated, usually it’s $M$ or with an added point.)

$M$ acts on $X(M)$ by $m(nM) = (mn)M$ , and is order preserving.

For a fixed $m \in M$ , the R-class of $m$ is the set $\{m^\prime \in M: m^\prime M = m M\}$ . (This is an equivalence class.)

$M$ is R-trivial if each R-class has only one element.

$M$ is almost R-trivial if for each $n \in M$ whose R-class has more than one element we have $mn=n$ for all $m\in M$ .

The idea for almost R-trivial is that “you can have more than one element in each R-class, but they must be of a specific type.”

Exercise. For the three monoids we looked at above, the first two are R-trivial and Furstenberg-Katznelson is almost R-trivial.

The structure of $X(M)$

In the case of almost R-trivial, Ramsey is equivalent to the geometric structure of $X(M)$ .

Theorem (Solecki). Let $M$ be almost R-trivial. Then $M$ is Ramsey iff $X(M)$ is linear.

Even in the case where $X(M)$ we can still get “traces of Ramsey”.

Gowers’. This $X(M)$ is linear with $0 > 1 > \ldots > n-1$ .

Furstenberg-Katznelson. This is not linear. $1_M$ is on top, it is above all elements of $A$ (which form an antichain) and there is a single point for all of $B$ below everything. (Exercise Prove this.)

solecki_2_fk — $X(M)$ for Furestenberg-Katznelson

“You extract the type from this poset.”

Lupini. Here $\vert X(I_n) \vert = 2^{n-1}$ , for $n \geq 1$ . $n=1,2,3$ are all lines. For $n=4$ we get a cycle as follows:

Ultrafilters

Bergelson-Blass-Hindman realized we could use ultrafilter methods on partial semigroups. Here we introduce some basic topological notions and the key lemma.

Definition. Let $S$ be a partial directed semigroup.

$\gamma S$ is the collection of all ultrafilters $\mathcal{U}$ on $S$ such that $\forall s \in S \{t : st \text{ is defined }\} \in \mathcal{U}$ . (This is exactly where we need that the partial semigroup is directed.)

$C \in \mathcal{U} \star \mathcal{V}$ iff $\{s \in S : \{t : st \in C\} \in \mathcal{V}\} \in \mathcal{U}$ iff $\mathcal{U}s\mathcal{V}t st \in C$ . In the third part we are using ultrafilter quantification: $\mathcal{U}x \phi(x)$ means $\exists A \in \mathcal{U}$ such that $\forall x \in A, \phi(x)$ . This is reminiscent of measure theory where we say “for all $x$ in a measure 1 set”.

The topology on $\gamma S$ is generated by sets of the form $\{\mathcal{U} \in \gamma S : A \in \mathcal{U}\}$ , where $A \subseteq S$ . Here $\gamma S$ is a compact left topological semigroup (i.e. multiplication on the left is left continuous).

This gives us the following fundamental theorem.

Ellis’ Lemma. If $S$ is a left topological compact semigroup, there is an $s \in S$ such that $aa=a$ .

Definition. Call $a \in S$ an idempotent element of $S$ if $aa=a$ .

Let $E(S)$ be the collection of all idempotent elements of $S$ .

If $M$ acts on $S$ by endomorphisms, then $M$ acts on $\gamma S$ by continuous automorphisms where $C \in m(\mathcal{U})$ iff $m^{-1}(C) = \{s \in S : m(s)\in C\} \in \mathcal{U}$ .

Note that $m(\mathcal{U}\star\mathcal{V}) = m(\mathcal{U})\star m(\mathcal{V})$ for all $m \in M$ .

3 thoughts on “Ramsey and Ultrafilters 1 – Ramsey DocCourse Prague 2016”

Michael K says:

October 21, 2016 at 10:26 am

Hi Mike, I think that in the three big theorems the sequences of words w_1 < w_2 < … should be infinite

LikeLike

1. Micheal Pawliuk says:
  
  October 21, 2016 at 3:47 pm
  
  Indeed! Fixed now.
  
  LikeLike
  
Pingback: Ramsey and Ultrafilters 2 – Ramsey DocCourse Prague 2016