Ramsey and Ultrafilters 1 – Ramsey DocCourse Prague 2016

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

You might also be interested in Solecki’s independent lecture about projective Fraisse limits [link soon].

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(\dom(v)) < \min(\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. 1_M \cdot s = s for all s \in S ,
  2. m \cdot (n \cdot s) = (mn) \cdot s , for all m,n \in M and s \in S .
  3. \forall s,t \in S, \forall m \in M if st is defined, then m(s)m(t) is defined equal to m(st) .
  4. \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.)

$latex  X(M) $ for Furestenberg-Katznelson
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:

$latex  I_1 $ through $latex  I_4 $
I_1 through I_4

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”

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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