Jump to content

Gowers' theorem

From Wikipedia, the free encyclopedia

In mathematics, Gowers' theorem, also known as Gowers' Ramsey theorem and Gowers' FINk 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

[edit]

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

For a function , the support of is defined . Given , let be the set

If , have disjoint supports, we define to be their pointwise sum, where . Each is a partial semigroup under .

The tetris operation is defined . Intuitively, if is represented as a pile of square blocks, where the th column has height , then is the result of removing the bottom row. The name is in analogy with the video game. denotes the th iterate of .

A block sequence in is one such that for every .

The theorem

[edit]

Note that, for a block sequence , numbers and indices , the sum is always defined. Gowers' original theorem states that, for any finite colouring of , there is a block sequence such that all elements of the form have the same colour.

The standard proof uses ultrafilters,[1][4] or equivalently, nonstandard arithmetic.[5]

Generalisation

[edit]

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 be a nondecreasing surjection. The induced tetris operation is given by composition with , i.e. . The generalised tetris operations are the collection of for all nondecreasing surjections . In this language, the original tetris operation is induced by the map .

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

[edit]
  1. ^ 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.
  2. ^ 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.
  3. ^ 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.
  4. ^ a b 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.