Gowers' theorem
 | 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". (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,[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 [math]\displaystyle{ f\colon \N \to \N }[/math], the support of [math]\displaystyle{ f }[/math] is defined [math]\displaystyle{ \operatorname{supp}(f) = \{ n : f(n) \neq 0 \} }[/math]. Given [math]\displaystyle{ k \in \N }[/math], let [math]\displaystyle{ \mathrm{FIN}_k }[/math] be the set
- [math]\displaystyle{ \mathrm{FIN}_k = \big\{ f\colon \N \to \N \mid \operatorname{supp}(f) \text{ is finite and } \max(\operatorname{range}(f)) = k \big\} }[/math]
If [math]\displaystyle{ f \in \mathrm{FIN}_n }[/math], [math]\displaystyle{ g \in \mathrm{FIN}_m }[/math] have disjoint supports, we define [math]\displaystyle{ f+g \in \mathrm{FIN}_k }[/math] to be their pointwise sum, where [math]\displaystyle{ k = \max \{ n, m \} }[/math]. Each [math]\displaystyle{ \mathrm{FIN}_k }[/math] is a partial semigroup under [math]\displaystyle{ + }[/math].
The tetris operation [math]\displaystyle{ T\colon \mathrm{FIN}_{k+1} \to \mathrm{FIN}_k }[/math] is defined [math]\displaystyle{ T(f)(n) = \max \{ 0, f(n)-1 \} }[/math]. Intuitively, if [math]\displaystyle{ f }[/math] is represented as a pile of square blocks, where the [math]\displaystyle{ n }[/math]th column has height [math]\displaystyle{ f(n) }[/math], then [math]\displaystyle{ T(f) }[/math] is the result of removing the bottom row. The name is in analogy with the video game. [math]\displaystyle{ T^{(k)} }[/math] denotes the [math]\displaystyle{ k }[/math]th iterate of [math]\displaystyle{ T }[/math].
A block sequence [math]\displaystyle{ (f_n) }[/math] in [math]\displaystyle{ \mathrm{FIN}_k }[/math] is one such that [math]\displaystyle{ \max(\operatorname{supp}(f_m)) \lt \min(\operatorname{supp}(f_{m+1})) }[/math] for every [math]\displaystyle{ m }[/math].
The theorem
Note that, for a block sequence [math]\displaystyle{ (f_n) }[/math], numbers [math]\displaystyle{ k_1, \ldots, k_n }[/math] and indices [math]\displaystyle{ m_1 \lt \cdots \lt m_n }[/math], the sum [math]\displaystyle{ T^{(k_1)}(f_{m_1}) + \cdots + T^{(k_n)}(f_{m_n}) }[/math] is always defined. Gowers' original theorem states that, for any finite colouring of [math]\displaystyle{ \mathrm{FIN}_k }[/math], there is a block sequence [math]\displaystyle{ (f_n) }[/math] such that all elements of the form [math]\displaystyle{ T^{(k_1)}(f_{m_1}) + \cdots + T^{(k_n)}(f_{m_n}) }[/math] 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 [math]\displaystyle{ F\colon \N \to \N }[/math] be a nondecreasing surjection. The induced tetris operation [math]\displaystyle{ \hat{F}\colon \mathrm{FIN}_k \to \mathrm{FIN}_{F(k)} }[/math] is given by composition with [math]\displaystyle{ F }[/math], i.e. [math]\displaystyle{ \hat{F}(f)(n) = F(f(n)) }[/math]. The generalised tetris operations are the collection of [math]\displaystyle{ \hat{F} }[/math] for all nondecreasing surjections [math]\displaystyle{ F\colon \N \to \N }[/math]. In this language, the original tetris operation is induced by the map [math]\displaystyle{ T\colon n \mapsto \max \{ n-1, 0 \} }[/math].
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
- ↑ 1.0 1.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.0 2.1 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. doi:10.1016/j.jcta.2017.02.002. ISSN 0097-3165. http://dx.doi.org/10.1016/j.jcta.2017.02.002.
- ↑ 3.0 3.1 Lupini, Martino (July 2017). "Gowers' Ramsey Theorem for generalized tetris operations". Journal of Combinatorial Theory, Series A 149: 101–114. doi:10.1016/j.jcta.2017.02.001. ISSN 0097-3165. http://dx.doi.org/10.1016/j.jcta.2017.02.001.
- ↑ 4.0 4.1 Stevo., Todorcevic (2010). Introduction to Ramsey spaces. Princeton University Press. ISBN 978-0-691-14541-9. OCLC 879209040. http://worldcat.org/oclc/879209040.
- ↑ Di Nasso, Mauro; Goldbring, Isaac; Lupini, Martino (2019). Nonstandard Methods in Ramsey Theory and Combinatorial Number Theory. Lecture Notes in Mathematics. 2239. doi:10.1007/978-3-030-17956-4. ISBN 978-3-030-17955-7. http://dx.doi.org/10.1007/978-3-030-17956-4.
 |  |
