Presentazione Tesi Magistrale

Post on 19-Mar-2017

28 views 0 download

Transcript of 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).

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

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 ,

sup

{|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.

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

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 ,

sup

{|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.

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

The distortion 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).

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

The distortion 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).

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

The distortion 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).

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

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.

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

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.

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

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 .

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

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 .

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

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.

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

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 .

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

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 .

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

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.

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

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.

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

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 .

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

Filters and ultrafilters

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 .

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

Filters and ultrafilters

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 .

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

Filters and ultrafilters

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 .

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

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 .

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

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 .

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

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 .

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

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 .

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

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 , ∗).

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

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 , ∗).

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

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 , ∗).

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

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) = ∅.

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

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) = ∅.

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

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) = ∅.

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

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.

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

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.

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

Ultrafilters on FIN±k

We extend the sum to the partial semigroup

FIN±[1,k] =k⋃

i=1

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⋃

i=1

γFIN±i

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

Ultrafilters on FIN±k

We extend the sum to the partial semigroup

FIN±[1,k] =k⋃

i=1

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⋃

i=1

γFIN±i

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

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.

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

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.

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

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.

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

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.

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

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.

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

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.

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

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 .

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

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 .

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

Subsymmetric ultrafilters

Lemma

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

Lemma

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

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

Subsymmetric ultrafilters

Lemma

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

Lemma

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

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

Do subsymmetric ultrafilters exist?

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

Lemma

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.

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

Do subsymmetric ultrafilters exist?

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

Lemma

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.

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

Do subsymmetric ultrafilters exist?

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

Lemma

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.

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

Gowers’ Ramsey Theorem

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.

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

Gowers’ Ramsey Theorem

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.

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

Gowers’ Ramsey Theorem

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.

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

Gowers’ Ramsey Theorem

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.

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

Gowers’ Ramsey Theorem

To prove Gowers’ Theorem we need the following lemma:

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 .

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

Gowers’ Ramsey Theorem

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 .

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

Gowers’ Ramsey Theorem

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 .

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

Gowers’ Ramsey Theorem

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 .

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

Gowers’ Ramsey Theorem

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 .

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

Gowers’ Ramsey Theorem

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 .

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

Gowers’ Ramsey Theorem

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

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

Gowers’ Ramsey Theorem

ε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.

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

max{l ,j}m } ∈ Ul .

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

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

Gowers’ Ramsey Theorem

ε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.

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

max{l ,j}m } ∈ Ul .

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

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

Gowers’ Ramsey Theorem

ε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.

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

max{l ,j}m } ∈ Ul .

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

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

Gowers’ Ramsey Theorem

ε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.

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

max{l ,j}m } ∈ Ul .

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

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

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 , δ).

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

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 , δ).

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

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 , δ).

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

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}.

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

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}.

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

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}.

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

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}.

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

A δ-net on c0

Hence Φ|∆±k

is a bijection onto FIN±k .

Lemma

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.

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

A δ-net on c0

Hence Φ|∆±k

is a bijection onto FIN±k .

Lemma

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.

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

A δ-net on c0

Hence Φ|∆±k

is a bijection onto FIN±k .

Lemma

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.

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

A δ-net on c0

Hence Φ|∆±k

is a bijection onto FIN±k .

Lemma

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.

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

The oscillation-stability problem

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 ε.

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.

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

The oscillation-stability problem

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 ε.

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.

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

The oscillation-stability problem

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 ε.

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.

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

The oscillation-stability problem

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 ε.

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.

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

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.

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

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.

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

The importance of Gowers’ Theorem

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.

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

The importance of Gowers’ Theorem

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.

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

The importance of Gowers’ Theorem

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.

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.

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

- Thanks for your attention -

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