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,^[1] motivated by a problem regarding Banach spaces. The result was subsequently generalised by Bartošová, Kwiatkowska,^[2] and Lupini.^[3]

Definitions

The presentation and notation is taken from Todorčević,^[4] 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,^[1]^[4] or equivalently, nonstandard arithmetic.^[5]

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^[2] 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^[2] showed that the finite version of Gowers' theorem holds for the collection of generalised tetris operations. Lupini^[3] later extended this result to the infinite case.

References

^ ^a ^b Gowers, W.T. (May 1992). "Lipschitz functions on classical spaces". European Journal of Combinatorics. 13 (3): 141–151. doi:10.1016/0195-6698(92)90020-z. ISSN 0195-6698.
^ ^a ^b ^c Bartošová, Dana; Kwiatkowska, Aleksandra (August 2017). "Gowers' Ramsey theorem with multiple operations and dynamics of the homeomorphism group of the Lelek fan". Journal of Combinatorial Theory, Series A. 150: 108–136. arXiv:1411.5134. doi:10.1016/j.jcta.2017.02.002. ISSN 0097-3165. S2CID 5509501.
^ ^a ^b Lupini, Martino (July 2017). "Gowers' Ramsey Theorem for generalized tetris operations". Journal of Combinatorial Theory, Series A. 149: 101–114. arXiv:1603.09365. doi:10.1016/j.jcta.2017.02.001. ISSN 0097-3165. S2CID 37972507.
^ ^a ^b Stevo., Todorcevic (2010). Introduction to Ramsey spaces. Princeton University Press. ISBN 978-0-691-14541-9. OCLC 879209040.
^ Di Nasso, Mauro; Goldbring, Isaac; Lupini, Martino (2019). Nonstandard Methods in Ramsey Theory and Combinatorial Number Theory. Lecture Notes in Mathematics. Vol. 2239. doi:10.1007/978-3-030-17956-4. ISBN 978-3-030-17955-7. ISSN 0075-8434. S2CID 119677934.

[:0-1] Gowers, W.T. (May 1992). "Lipschitz functions on classical spaces". European Journal of Combinatorics. 13 (3): 141–151. doi:10.1016/0195-6698(92)90020-z. ISSN 0195-6698.

[:2-2] Bartošová, Dana; Kwiatkowska, Aleksandra (August 2017). "Gowers' Ramsey theorem with multiple operations and dynamics of the homeomorphism group of the Lelek fan". Journal of Combinatorial Theory, Series A. 150: 108–136. arXiv:1411.5134. doi:10.1016/j.jcta.2017.02.002. ISSN 0097-3165. S2CID 5509501.

[:3-3] Lupini, Martino (July 2017). "Gowers' Ramsey Theorem for generalized tetris operations". Journal of Combinatorial Theory, Series A. 149: 101–114. arXiv:1603.09365. doi:10.1016/j.jcta.2017.02.001. ISSN 0097-3165. S2CID 37972507.

[:1-4] Stevo., Todorcevic (2010). Introduction to Ramsey spaces. Princeton University Press. ISBN 978-0-691-14541-9. OCLC 879209040.

[5] Di Nasso, Mauro; Goldbring, Isaac; Lupini, Martino (2019). Nonstandard Methods in Ramsey Theory and Combinatorial Number Theory. Lecture Notes in Mathematics. Vol. 2239. doi:10.1007/978-3-030-17956-4. ISBN 978-3-030-17955-7. ISSN 0075-8434. S2CID 119677934.

[1]

[2]

[3]

[4]

[5]