Gowers' theorem

In mathematics, Gowers' theorem, also known as Gowers' Ramsey theorem and Gowers' FIN_k theorem, is a theorem in Ramsey theory and combinatorics. It is a Ramsey-theoretic result about functions with finite support. Timothy Gowers originally proved the result in 1992, motivated by a problem regarding Banach spaces. The result was subsequently generalised by Bartošová, Kwiatkowska, and Lupini.

Definitions

The presentation and notation is taken from Todorčević, and is different to that originally given by Gowers.

For a function $f\colon \mathbb {N} \to \mathbb {N}$, the support of $f$ is defined $\operatorname {supp} (f)=\{n:f(n)\neq 0\}$. Given $k\in \mathbb {N}$, let $\mathrm {FIN} _{k}$ be the set

$\mathrm {FIN} _{k}={\big \{}f\colon \mathbb {N} \to \mathbb {N} \mid \operatorname {supp} (f){\text{ is finite and }}\max(\operatorname {range} (f))=k{\big \}}$

If $f\in \mathrm {FIN} _{n}$, $g\in \mathrm {FIN} _{m}$ have disjoint supports, we define $f+g\in \mathrm {FIN} _{k}$ to be their pointwise sum, where $k=\max\{n,m\}$. Each $\mathrm {FIN} _{k}$ is a partial semigroup under $+$.

The tetris operation $T\colon \mathrm {FIN} _{k+1}\to \mathrm {FIN} _{k}$ is defined $T(f)(n)=\max\{0,f(n)-1\}$. Intuitively, if $f$ is represented as a pile of square blocks, where the $n$th column has height $f(n)$, then $T(f)$ is the result of removing the bottom row. The name is in analogy with the video game. $T^{(k)}$ denotes the $k$th iterate of $T$.

A block sequence $(f_{n})$ in $\mathrm {FIN} _{k}$ is one such that $\max(\operatorname {supp} (f_{m}))<\min(\operatorname {supp} (f_{m+1}))$ for every $m$.

The theorem

Note that, for a block sequence $(f_{n})$, numbers $k_{1},\ldots ,k_{n}$ and indices $m_{1}<\cdots <m_{n}$, the sum $T^{(k_{1})}(f_{m_{1}})+\cdots +T^{(k_{n})}(f_{m_{n}})$ is always defined. Gowers' original theorem states that, for any finite colouring of $\mathrm {FIN} _{k}$, there is a block sequence $(f_{n})$ such that all elements of the form $T^{(k_{1})}(f_{m_{1}})+\cdots +T^{(k_{n})}(f_{m_{n}})$ have the same colour.

The standard proof uses ultrafilters, or equivalently, nonstandard arithmetic.

Generalisation

Intuitively, the tetris operation can be seen as removing the bottom row of a pile of boxes. It is natural to ask what would happen if we tried removing different rows. Bartošová and Kwiatkowska considered the wider class of generalised tetris operations, where we can remove any chosen subset of the rows.

Formally, let $F\colon \mathbb {N} \to \mathbb {N}$ be a nondecreasing surjection. The induced tetris operation ${\hat {F}}\colon \mathrm {FIN} _{k}\to \mathrm {FIN} _{F(k)}$ is given by composition with $F$, i.e. ${\hat {F}}(f)(n)=F(f(n))$. The generalised tetris operations are the collection of ${\hat {F}}$ for all nondecreasing surjections $F\colon \mathbb {N} \to \mathbb {N}$. In this language, the original tetris operation is induced by the map $T\colon n\mapsto \max\{n-1,0\}$.

Bartošová and Kwiatkowska showed that the finite version of Gowers' theorem holds for the collection of generalised tetris operations. Lupini later extended this result to the infinite case.