Decompositions, approximate structure, transference, and the Hahn–Banach theorem

By William T. Gowers. 2008

125 citations recorded by the source corpus.

We discuss three major classes of theorems in additive and extremal combinatorics: decomposition theorems, approximate structure theorems, and transference principles. We also show how the finite‐dimensional Hahn–Banach theorem can be used to give short and transparent proofs of many results of these kinds. Among the applications of this method is a much shorter proof of one of the major steps in the proof of Green and Tao that the primes contain arbitrarily long arithmetic progressions. In order to explain the role of this step, we include a brief description of the rest of their argument. A similar proof has been discovered independently by Reingold, Trevisan, Tulsiani, and Vadhan (‘Electronic Colloquium on Computational Complexity’, Dense subsets of pseudorandom sets, Proceedings of 49th IEEE FOCS, 2008).

Subfields: Discrete Mathematics and Combinatorics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/67b58e4ab0a9f7f401fbc9fade0260d718df7e2e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

The Inverse Conjecture for the Gowers Norm over Finite Fields in Low Characteristic (2011, methodology): “ection we deduce Theorem 1.11 from Theorem 1.20. This deduction can be done in either a ﬁnitary or an inﬁnitary setting. In the ﬁnitary setting, one uses structural decomposition theorems as in [40], [13], [22], [15], [16]; the arguments in [16] are particularly close to those here. In the inﬁnitary”
Higher order Fourier analysis of multiplicative functions and applications (2014, methodology): “1 consists of a Fourier analysis energy increment argument, and avoids the use of finitary ergodic theory and the use of the Hahn-Banach theorem, tools that are typically used for other decomposition results (see [14, 15, 16, 21, 42]).”
Linear Forms and Higher-Degree Uniformity for Functions On $${\mathbb{F}^{n}_{p}}$$ (2010, unknown): “to use inverse theorems to prove that a bounded function can be decomposed into a structured part, a uniform part and a small part. We shall use the following abstract result, which is Theorem 5.7 of [G08]. It is a general “arithmetic regularity lemma” of a kind that was introduced by Green [Gr05], ”
Leakage-Resilient Cryptography (2008, background): “This result (i n a more general form) has independently been discovered by [34, 16].”
On the KŁR conjecture in random graphs (2013, methodology): “The method employed by Conlon and Gowers [17] to determine probabilistic thresholds for combinatorial theorems hinges on proving a transference principle [39, 40, 71].”