Presentazione Tesi Magistrale

Gowers’ Ramsey Theorem

Pietro Porqueddu

University of Pisa

03/02/2017

Pietro Porqueddu (University of Pisa) Gowers’ Ramsey Theorem 03/02/2017 1 / 37

Introduction

In 1992, Timothy Gowers provided a positive answer to the oscillationstability problem in c0.

The very core of the proof is a combinatorial argument which represents avery important result in Ramsey Theory known as Gowers’ RamseyTheorem.

One of the typical problems is Ramsey Theory is to determine whethersome structure is preserved when it is partitioned (coloured).

The distortion problem

Let (E , ‖ · ‖) be a Banach space and λ > 1 a real number. We say that Eis λ-distortable if there exists an equivalent norm | · | on E such that forevery infinite-dimensional vector subspace X of E ,

{|x ||y || x , y ∈ X and ||x || = ||y || = 1

}≥ λ.

We say that E is distortable if it is λ-distortable for some λ > 1, and it isarbitrarily distortable if it is λ-distortable for every λ > 1.

The question of whether a Banach space is distortable or not is called thedistortion problem.

Let (E , ‖ · ‖) be a Banach space and λ > 1 a real number. We say that Eis λ-distortable if there exists an equivalent norm | · | on E such that forevery infinite-dimensional vector subspace X of E ,

{|x ||y || x , y ∈ X and ||x || = ||y || = 1

}≥ λ.

We say that E is distortable if it is λ-distortable for some λ > 1, and it isarbitrarily distortable if it is λ-distortable for every λ > 1.

The question of whether a Banach space is distortable or not is called thedistortion problem.

R.C. James (1964) proved that c0 and `1 are not distortable.

V. Milman (1971) proved that a non-distortable space must containan isomorphic copy of c0 or `p, 1 ≤ p <∞.

The problem in the case of separable Hilbert spaces and for `p, forany 1 < p <∞, was solved affirmatively by E. Odell and T.Schlumprecht (1994).

The oscillation stability problem

In a Banach space (E , ‖ · ‖), the oscillation stability problem is thequestion of whether or not, given ε > 0, for every real-valued Lipschitzfunction f on the unit sphere SE there exists an infinite-dimensionalsubspace X of E on the unit sphere of which f varies by at almost ε, i.e.,whether there is a real number a ∈ R and an infinite-dimensional subspaceX of E such that ||a− f (x)|| < ε for all x ∈ X with ||x || = 1.

In a separable and uniform convex Banach space (such as the `p spaces for1 < p <∞), the distortion problem and the oscillation stability problemare equivalent.

The oscillation stability problem

In a Banach space (E , ‖ · ‖), the oscillation stability problem is thequestion of whether or not, given ε > 0, for every real-valued Lipschitzfunction f on the unit sphere SE there exists an infinite-dimensionalsubspace X of E on the unit sphere of which f varies by at almost ε, i.e.,whether there is a real number a ∈ R and an infinite-dimensional subspaceX of E such that ||a− f (x)|| < ε for all x ∈ X with ||x || = 1.

In a separable and uniform convex Banach space (such as the `p spaces for1 < p <∞), the distortion problem and the oscillation stability problemare equivalent.

Gowers’ Theorem

Theorem

Let ε > 0 and let F be a real-valued Lipschitz function on the unit sphereof c0. Then there is an infinite-dimensional subspace of c0 on the unitsphere of which F varies by at most ε.

The strategy of the proof is to find explicit generators of such a subspacetaken among the maps which belong to a δ-net on Sc0 .

Gowers’ Theorem

Theorem

The strategy of the proof is to find explicit generators of such a subspacetaken among the maps which belong to a δ-net on Sc0 .

What we will see

• In the first part, we will introduce the notions of ultrafilter andsemigroup, and some of their properties.

• In the second part, we will prove Gowers’ Ramsey Theorem.

• Finally, we will see Gowers’ solution of the oscillation stability problem inc0 as a consequence of Gowers’ Ramsey Theorem.

Semigroups

Definition

A semigroup is a nonempty set S with a map

· : S2 7−→ S

defined for all x , y ∈ S , that satisfies the associative law

(x · y) · z = x · (y · z)

Usually we will drop the · and we will write xy instead of x · y .

Ideals and subsemigroups

Definition

A compact left-semigroup is a nonempty semigroup S with a compactHausdorff topology such that, for all x ∈ S , the map

λx : y 7−→ xy

is continuous for all y . A subset T ⊆ S is a (compact) subsemigroup of Sif it is a compact left-semigroup as subspace of S .

Idempotents and Ellis’ Theorem

Definition

An element x ∈ S is idempotent if and only if x2 = x .

Theorem (Ellis’ Theorem)

Every compact left-semigroup S has an idempotent.

Idempotents and Ellis’ Theorem

Definition

An element x ∈ S is idempotent if and only if x2 = x .

Theorem (Ellis’ Theorem)

Every compact left-semigroup S has an idempotent.

Filters and ultrafilters

Definition

Let S be a set. A family F of subsets of S is a filter on S if

1 ∅ /∈ F and S ∈ F ;

2 If A,B ∈ F , then A ∩ B ∈ F ;

3 If A ∈ F and A ⊆ B, then B ∈ F .

Proposition

Let S be a set and F a filter on S. The following are equivalent

1 If A /∈ F , then Ac ∈ F ;

2 If A1 ∪ . . . ∪ An ∈ F , then there exists i such that Ai ∈ F ;

3 F is maximal respect to the inclusion, i.e. if G is a filter on S andF ⊆ G, then F = G.

Definition

A filter F on a set S which satisfies one, and then all, of the properties ofthe above proposition is called ultrafilter.

We will denote by βS the set of all ultrafilters on S .

Proposition

Definition

Proposition

Definition

The space βS

Definition

On βS we define the topology generated by the (cl)open set basis

B = {OA | A ⊆ S}

where OA = {U ultrafilter on S | A ∈ U}

Theorem

The space βS is the Stone-C ech compactification of the discrete space S:

1 βS is a compact Hausdorff space;

2 S is a dense discrete subset of βS;

3 for any compact Hausdorff space K and any f : S → K , there existsan unique continuous extension f : βS → K .

The space βS

Definition

On βS we define the topology generated by the (cl)open set basis

B = {OA | A ⊆ S}

where OA = {U ultrafilter on S | A ∈ U}

Theorem

The space βS is the Stone-C ech compactification of the discrete space S:

1 βS is a compact Hausdorff space;

2 S is a dense discrete subset of βS;

3 for any compact Hausdorff space K and any f : S → K , there existsan unique continuous extension f : βS → K .

The space βS

Theorem

Let (S , ·) be a compact semigroup. There exists a unique associativebinary operation ∗ : βS × βS → βS satisfying the following conditions

1 For every x , y ∈ S, x ∗ y = x · y;

2 For each V ∈ βS, the function pV : βS × βS → βS is continuous,where pV(U) = U ∗ V;

3 For each x ∈ S, the function qx : βS × βS → βS is continuous,where qx(V) = x ∗ V.

Proposition

Let U ,V be ultrafilters in βS. Then

A ∈ U ∗ V ⇔ {x ∈ S | {y ∈ S | x · y ∈ A} ∈ V} ∈ U .

The space βS

Theorem

Let (S , ·) be a compact semigroup. There exists a unique associativebinary operation ∗ : βS × βS → βS satisfying the following conditions

1 For every x , y ∈ S, x ∗ y = x · y;

2 For each V ∈ βS, the function pV : βS × βS → βS is continuous,where pV(U) = U ∗ V;

3 For each x ∈ S, the function qx : βS × βS → βS is continuous,where qx(V) = x ∗ V.

Proposition

Let U ,V be ultrafilters in βS. Then

A ∈ U ∗ V ⇔ {x ∈ S | {y ∈ S | x · y ∈ A} ∈ V} ∈ U .

Algebra in βS

Proposition

The ultrafilter product U ∗ V has the following properties

1 (U ∗ V) ∗W = U ∗ (V ∗W);

2 V → U ∗ V is a continuous map from βS into βS for every U .

Corollary

The space (βS , ∗) is a compact left-semigroup.

Corollary

There exist idempotent ultrafilters in (βS , ∗).

Algebra in βS

Proposition

1 (U ∗ V) ∗W = U ∗ (V ∗W);

Corollary

Algebra in βS

Proposition

1 (U ∗ V) ∗W = U ∗ (V ∗W);

Corollary

The set FIN±k

Let k be a positive integer. We consider the set FIN±k of the maps

p : N→ {0,±1, . . . ,±k}

such that supp(p) = {n ∈ N | p(n) 6= 0} is finite, and p attains at leastone of the values k or −k.

We define on FIN±k a coordinate-wise sum

(p + q)(n) = p(n) + q(n)

whenever supp(p) ∩ supp(q) = ∅.

The set FIN±k

p : N→ {0,±1, . . . ,±k}

(p + q)(n) = p(n) + q(n)

The set FIN±k

p : N→ {0,±1, . . . ,±k}

(p + q)(n) = p(n) + q(n)

Ultrafilters on FIN±k

The set FIN±k is an example of partial semigroup.

The construction of a semigroup of ultrafilters (βS , ∗) works also for alarge class of partial semigroups S . In this case, we need to restrict tocofinite ultrafilters.

Definition

We say that an ultrafilter U on FIN±k is cofinite if

∀p ∈ FIN±k , {q ∈ FIN±k | p + q is defined} ∈ U .

We denote by γFIN±k the set of all cofinite ultrafilters.

Proposition

The set (γFIN±k ,+) is a compact left-semigroup.

The set FIN±k is an example of partial semigroup.

The construction of a semigroup of ultrafilters (βS , ∗) works also for alarge class of partial semigroups S . In this case, we need to restrict tocofinite ultrafilters.

Definition

We say that an ultrafilter U on FIN±k is cofinite if

∀p ∈ FIN±k , {q ∈ FIN±k | p + q is defined} ∈ U .

We denote by γFIN±k the set of all cofinite ultrafilters.

Proposition

The set (γFIN±k ,+) is a compact left-semigroup.

We extend the sum to the partial semigroup

FIN±[1,k] =k⋃

FIN±i ,

If p ∈ FIN±k and q ∈ FIN±h , then p + q ∈ FIN±max{k,h}.

The correspondent space of ultrafilters is

γ(FIN±[1,k]) =k⋃

γFIN±i

We extend the sum to the partial semigroup

FIN±[1,k] =k⋃

FIN±i ,

If p ∈ FIN±k and q ∈ FIN±h , then p + q ∈ FIN±max{k,h}.

The correspondent space of ultrafilters is

γ(FIN±[1,k]) =k⋃

γFIN±i

The tetris operation

Definition

We call tetris operation the map T : FIN±k → FIN±k−1 defined as

T (p)(n) =

p(n)− 1 if p(n) > 0,

0 if p(n) = 0,

p(n) + 1 if p(n) < 0.

Notice that T (p + q) = T (p) + T (q) whenever p, q have disjoint supports.

The tetris operation

Definition

We call tetris operation the map T : FIN±k → FIN±k−1 defined as

T (p)(n) =

p(n)− 1 if p(n) > 0,

0 if p(n) = 0,

p(n) + 1 if p(n) < 0.

Notice that T (p + q) = T (p) + T (q) whenever p, q have disjoint supports.

Block sequences

Definition

A basic block sequence B = {bn}n of elements of FIN±k is any sequencesuch that

supp(bi ) < supp(bj) whenever i < j .

Definition

The partial subsemigroup of FIN±k generated by a basic block sequenceB = {bn}n is the family of functions of the form

ε0T j0(bn0) + ε1T j1(bn1) + . . .+ εlTjl (bnl ),

where εi = ±1, n0 < . . . < nl , j0, . . . , jl ∈ {0, . . . , k − 1} and at least oneof the j0, . . . , jl is equal to zero.

Block sequences

Definition

A basic block sequence B = {bn}n of elements of FIN±k is any sequencesuch that

supp(bi ) < supp(bj) whenever i < j .

Definition

The partial subsemigroup of FIN±k generated by a basic block sequenceB = {bn}n is the family of functions of the form

ε0T j0(bn0) + ε1T j1(bn1) + . . .+ εlTjl (bnl ),

where εi = ±1, n0 < . . . < nl , j0, . . . , jl ∈ {0, . . . , k − 1} and at least oneof the j0, . . . , jl is equal to zero.

Extending the tetris operation

We extend the tetris operation on the space of cofinite ultrafilters asfollows: T : γFIN±k → γFIN±k−1 is the function where

T (U) = {A ⊆ FIN±k−1 | {p ∈ FIN±k |T (p) ∈ A} ∈ U}.

for all U ∈ γFIN±k .

Proposition

T : γFIN±k → γFIN±k−1 is a continuous onto homomorphism.

Extending the tetris operation

We extend the tetris operation on the space of cofinite ultrafilters asfollows: T : γFIN±k → γFIN±k−1 is the function where

T (U) = {A ⊆ FIN±k−1 | {p ∈ FIN±k |T (p) ∈ A} ∈ U}.

for all U ∈ γFIN±k .

Proposition

T : γFIN±k → γFIN±k−1 is a continuous onto homomorphism.

Subsymmetric ultrafilters

For every A ⊆ FIN±k and ε > 0, we define

(A)ε = {q ∈ FIN±k | ∃p ∈ A ‖ p − q ‖∞≤ ε}

Definition

We say that a cofinite ultrafilter U ∈ γFIN±k is subsymmetric if

−(A)1 ∈ U for all A ∈ U .

We denote by S±k the set of all subsymmetric ultrafilters on FIN±k .

For every A ⊆ FIN±k and ε > 0, we define

(A)ε = {q ∈ FIN±k | ∃p ∈ A ‖ p − q ‖∞≤ ε}

Definition

We say that a cofinite ultrafilter U ∈ γFIN±k is subsymmetric if

−(A)1 ∈ U for all A ∈ U .

We denote by S±k the set of all subsymmetric ultrafilters on FIN±k .

The set S±k is a closed subsemigroup of γFIN±k .

T (U) ∈ S±k−1 for all U ∈ S±k .

The set S±k is a closed subsemigroup of γFIN±k .

T (U) ∈ S±k−1 for all U ∈ S±k .

Do subsymmetric ultrafilters exist?

Answer: It is claimed by Todorcevic, but he does not prove it in detail.

The set S±k 6= ∅ for all k ≥ 1.

Todorcevic’s hint.

Let V be a cofinite ultrafilter on FIN±k . Then

U = T k−1(V)− T k−1(V) + T k−2(V)− T k−2(V) + . . .+

+ T (V)− T (V) + V − V + T (V)− T (V) + . . .+

+ T k−2(V)− T k−2(V) + T k−1(V)− T k−1(V)

is a subsymmetric ultrafilter.

U = T k−1(V)− T k−1(V) + T k−2(V)− T k−2(V) + . . .+

+ T (V)− T (V) + V − V + T (V)− T (V) + . . .+

+ T k−2(V)− T k−2(V) + T k−1(V)− T k−1(V)

U = T k−1(V)− T k−1(V) + T k−2(V)− T k−2(V) + . . .+

+ T (V)− T (V) + V − V + T (V)− T (V) + . . .+

+ T k−2(V)− T k−2(V) + T k−1(V)− T k−1(V)

Theorem (Gowers)

For every finite partition of FIN±k there is a piece P of the partition suchthat (P)1 contains a partial subsemigroup of FIN±k generated by an infinitebasic block sequence.

We cannot ask the partial semigroup to be contained entirely in P.Consider the colourings:

1 RED if the first nonzero coordinate is positive, BLUE otherwise. Thenf and −f have always different colours.

2 RED if the first and last nonzero coordinates have the same sign,BLUE otherwise. Then f + g and f − g have always different colours.

Theorem (Gowers)

To prove Gowers’ Theorem we need the following lemma:

There exists a sequence of ultrafilters Uj ∈ S±j (1 ≤ j ≤ k) such that forall 1 ≤ i ≤ j ≤ k:

(i) Ui + Ui = Ui ;(ii) Ui + Uj = Uj + Ui = Uj ;(iii) T j−i (Uj) = Ui .

A sketch of the proof:• Consider the sequence of ultrafilter Uj (1 ≤ j ≤ k) given by the lemma.• Let P be the piece of the partition such that P ∈ Uk .• Since Uk is subsymmetric, (P)1 ∩ −(P)1 ∈ Uk .• We can construct a block sequence {xn}n and a decreasing sequence ofsets {Al

n}n (1 ≤ l ≤ k) such that

1 Ak0 = (P)1 ∩ −(P)1, Al

n = T k−l(Akn);

2 Aln = −Al

n ∈ Ul ;3 ±xn ∈ Ak

n and ±T k−l(xn) ∈ Aln;

4 C l ,jm = {y ∈ FIN±l | ± T k−j(xm)± y ∈ A

max{l ,j}m } ∈ Ul for

1 ≤ j , l ≤ k .

1 Ak0 = (P)1 ∩ −(P)1, Al

n = T k−l(Akn);

2 Aln = −Al

n ∈ Ul ;3 ±xn ∈ Ak

1 ≤ j , l ≤ k .

1 Ak0 = (P)1 ∩ −(P)1, Al

n = T k−l(Akn);

2 Aln = −Al

n ∈ Ul ;3 ±xn ∈ Ak

1 ≤ j , l ≤ k .

1 Ak0 = (P)1 ∩ −(P)1, Al

n = T k−l(Akn);

2 Aln = −Al

n ∈ Ul ;3 ±xn ∈ Ak

1 ≤ j , l ≤ k .

1 Ak0 = (P)1 ∩ −(P)1, Al

n = T k−l(Akn);

2 Aln = −Al

n ∈ Ul ;3 ±xn ∈ Ak

1 ≤ j , l ≤ k .

We can represent the sequence {Aln}n (1 ≤ l ≤ k) with this diagram

Ak0 ⊃ Ak

1 ⊃ . . . ⊃ Akn−2 ⊃ Ak

n ∈ Uk↓T ↓T

Ak−10 ⊃ Ak−1

1 ⊃ . . . ⊃ Ak−1n−2 ⊃ Ak−1

n ∈ Uk−1

↓T ↓T...

...↓T ↓TA1

0 ⊃ A11 ⊃ . . . ⊃ A1

n−2 ⊃ A1n ∈ U1

ε0T j0(xn0) + ε1T j1(xn1) + . . .+ εlTjl (xnl ),

1 Ak0 = (P)1 ∩ −(P)1, Al

n = T k−l(Akn).

2 Aln = −Al

n ∈ Ul .3 ±xn ∈ Ak

n and ±T k−l(xn) ∈ Aln.

ensure that +T i (xni ), −T i (xni ), and their sums belong to thegenerated subspace.

max{l ,j}m } ∈ Ul .

ensures we can recursively pick xn so that the sums are well-defined.

1 Ak0 = (P)1 ∩ −(P)1, Al

n = T k−l(Akn).

2 Aln = −Al

n ∈ Ul .3 ±xn ∈ Ak

1 Ak0 = (P)1 ∩ −(P)1, Al

n = T k−l(Akn).

2 Aln = −Al

n ∈ Ul .3 ±xn ∈ Ak

1 Ak0 = (P)1 ∩ −(P)1, Al

n = T k−l(Akn).

2 Aln = −Al

n ∈ Ul .3 ±xn ∈ Ak

A δ-net on c0

Let k be a positive integer and let 0 < δ < 1 be such that

(1 + δ)1−k = δ.

Let ∆±k be the family of all maps

f : N→ {0,±(1 + δ)1−k ,±(1 + δ)2−k , . . . ,±(1 + δ)−1,±1},

which attain at least one of the values ±1, and such thatsupp(f ) = {n ∈ N | f (n) 6= 0} is finite.

∆±k is a δ-net on Sc0 , i.e.

Sc0 =⋃

f ∈∆±k

Sc0(f , δ).

A δ-net on c0

(1 + δ)1−k = δ.

f : N→ {0,±(1 + δ)1−k ,±(1 + δ)2−k , . . . ,±(1 + δ)−1,±1},

Sc0 =⋃

f ∈∆±k

Sc0(f , δ).

A δ-net on c0

(1 + δ)1−k = δ.

f : N→ {0,±(1 + δ)1−k ,±(1 + δ)2−k , . . . ,±(1 + δ)−1,±1},

Sc0 =⋃

f ∈∆±k

Sc0(f , δ).

A δ-net on c0

Consider the function φ : R→ R,

φ(x) =log |x |

log((1 + δ)−1).

Notice that φ(±(1 + δ)h−k) = k − h.

We define the map Φ : Sc0 → FIN±k by

Φ(f )(n) = sign(f (n)) ·max{0, k − bφ(f (n))c}.

Thus, if f ∈ ∆±k and f (n) = ±(1 + δ)h−k we have that

Φ(f )(n) = ±max{0, h}.

A δ-net on c0

φ(x) =log |x |

log((1 + δ)−1).

Φ(f )(n) = ±max{0, h}.

A δ-net on c0

φ(x) =log |x |

log((1 + δ)−1).

Φ(f )(n) = ±max{0, h}.

A δ-net on c0

φ(x) =log |x |

log((1 + δ)−1).

Φ(f )(n) = ±max{0, h}.

A δ-net on c0

Hence Φ|∆±k

is a bijection onto FIN±k .

For every f ∈ ∆±k and 0 ≤ λ ≤ 1.

Φ(λ · f ) = T j(Φ(f ))

for j = min{k , bφ(λ)c}.

Corollary

For any finite partition of ∆±k , there is an infinite dimensional blocksubspace X of c0 and there is some piece P of the partition such thatSX ⊆ (P)δ.

Indeed, since (1 + δ)1−k = δ, we have that Φ((A)δ) = (Φ(A))1.

A δ-net on c0

Hence Φ|∆±k

Φ(λ · f ) = T j(Φ(f ))

Corollary

A δ-net on c0

Hence Φ|∆±k

Φ(λ · f ) = T j(Φ(f ))

Corollary

A δ-net on c0

Hence Φ|∆±k

Φ(λ · f ) = T j(Φ(f ))

Corollary

The oscillation-stability problem

Theorem

A sketch of the proof:• Let K be the Lipschitz constant of F .• Find k > 0 such that if (1 + δ)1−k = δ then δ · K ≤ ε/2.• Since the range of F is bounded, we can finitely partition into sets ofdiameter ≤ ε/2.• We conclude by applying the previous corollary.

Theorem

The importance of Gowers’ Theorem

Theorem (Hindman, on finite sums)

For every finite colouring of N, there is an infinite sequence {bn} ⊆ N suchthat the family of all finite sums of elements of {bn} is monochromatic.

Theorem (Hindman, on finite unions)

Let Pf be the family of all finite nonempty subsets of N. For every finitecolouring of Pf , there exists an infinite sequence {bn} of disjoint subsetsof N such that the family of all finite unions of finite nonempty subfamiliesof {bn} is monochromatic.

Theorem (Hindman, on finite sums)

For every finite colouring of N, there is an infinite sequence {bn} ⊆ N suchthat the family of all finite sums of elements of {bn} is monochromatic.

If we consider FINk instead of FIN±k , one has a Ramsey result:

Theorem (Gowers)

For every finite colouring of FINk , there is an infinite block sequence B ofelements of FINk such that the partial semigroup generated by B ismonochromatic.

If we take k = 1, one has

Theorem

For every finite colouring of FIN1, there is an infinite block sequence B ofelements of FIN1 such that the partial semigroup generated by B ismonochromatic.

If we consider FINk instead of FIN±k , one has a Ramsey result:

Theorem (Gowers)

For every finite colouring of FINk , there is an infinite block sequence B ofelements of FINk such that the partial semigroup generated by B ismonochromatic.

If we take k = 1, one has

Theorem

- Thanks for your attention -

Presentazione Tesi Magistrale

Documents

Transcript of Presentazione Tesi Magistrale