Misplaced Pages

Gowers' theorem

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles; try the Find link tool for suggestions. (May 2021)
This article needs attention from an expert in mathematics. The specific problem is: Exposit the connection between the combinatorial Gowers' theorem and the "distortion problem". WikiProject Mathematics may be able to help recruit an expert. (April 2021)

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, 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 : N → N {\displaystyle f\colon \mathbb {N} \to \mathbb {N} } , the support of f {\displaystyle f} is defined supp ⁡ ( f ) = { n : f ( n ) ≠ 0 } {\displaystyle \operatorname {supp} (f)=\{n:f(n)\neq 0\}} . Given k ∈ N {\displaystyle k\in \mathbb {N} } , let F I N k {\displaystyle \mathrm {FIN} _{k}} be the set

F I N k = { f : N → N ∣ supp ⁡ ( f )  is finite and  max ( range ⁡ ( f ) ) = k } {\displaystyle \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 ∈ F I N n {\displaystyle f\in \mathrm {FIN} _{n}} , g ∈ F I N m {\displaystyle g\in \mathrm {FIN} _{m}} have disjoint supports, we define f + g ∈ F I N k {\displaystyle f+g\in \mathrm {FIN} _{k}} to be their pointwise sum, where k = max { n , m } {\displaystyle k=\max\{n,m\}} . Each F I N k {\displaystyle \mathrm {FIN} _{k}} is a partial semigroup under + {\displaystyle +} .

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

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

The theorem

Note that, for a block sequence ( f n ) {\displaystyle (f_{n})} , numbers k 1 , … , k n {\displaystyle k_{1},\ldots ,k_{n}} and indices m 1 < ⋯ < m n {\displaystyle m_{1}<\cdots <m_{n}} , the sum T ( k 1 ) ( f m 1 ) + ⋯ + T ( k n ) ( f m n ) {\displaystyle 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 F I N k {\displaystyle \mathrm {FIN} _{k}} , there is a block sequence ( f n ) {\displaystyle (f_{n})} such that all elements of the form T ( k 1 ) ( f m 1 ) + ⋯ + T ( k n ) ( f m n ) {\displaystyle 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 : N → N {\displaystyle F\colon \mathbb {N} \to \mathbb {N} } be a nondecreasing surjection. The induced tetris operation F ^ : F I N k → F I N F ( k ) {\displaystyle {\hat {F}}\colon \mathrm {FIN} _{k}\to \mathrm {FIN} _{F(k)}} is given by composition with F {\displaystyle F} , i.e. F ^ ( f ) ( n ) = F ( f ( n ) ) {\displaystyle {\hat {F}}(f)(n)=F(f(n))} . The generalised tetris operations are the collection of F ^ {\displaystyle {\hat {F}}} for all nondecreasing surjections F : N → N {\displaystyle F\colon \mathbb {N} \to \mathbb {N} } . In this language, the original tetris operation is induced by the map T : n ↦ max { n − 1 , 0 } {\displaystyle 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.

References

  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. ^ 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. ^ 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. ^ 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.
Categories: