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.