The Work of William Timothy Gowers

Béla Bollobás

It gives me great pleasure to report on the beautiful mathematics of William Timothy Gowers that earned him a Fields Medal at ICM’98.

Gowers has made spectacular contributions to the theory of Banach spaces, pure combinatorics, and combinatorial number theory. His hallmark is his exceptional ability to attack difficult and fundamental problems the right way: a way that with hindsight is very natural but a priori is novel and extremely daring.

In functional analysis Gowers has solved many of the best-known and most important problems, several of which originated with Banach in the early 1930s. The shock-waves from these results will reverberate for many years to come, and will dramatically change the theory of Banach spaces. The great success of Gowers is due to his exceptional talent for combining techniques of analysis with involved and ingenious combinatorial arguments.

In combinatorics, Gowers has made fundamental contributions to the study of randomness: his tower type lower bound for Szemerédi’s lemma is a tour de force. In combinatorial number theory, he has worked on the notoriously difficult problem of finding arithmetic progressions in sparse sets of integers. The ultimate aim is to prove Szemerédi’s theorem with the optimal bound on the density that suffices to ensure long arithmetic progressions. Gowers proved a deep result for progressions of length four, thereby hugely improving the previous bound. The difficult and beautiful proof, which greatly extends Roth’s argument, and makes clever use of Freiman’s theorem, amply demonstrates Gowers’ amazing mathematical power.

1 Banach Spaces

A major aim of functional analysis is to understand the connection between the geometry of a Banach space X and the algebra L(X) of bounded linear operators from the space X into itself. In particular, what conditions imply that a space X contains ‘nice’ subspaces, and that L(X) has a rich structure?

In order to start this global project, over the past sixty years numerous major concrete questions had to be answered. As Hilbert said almost one hundred years ago, “Wie überhaupt jedes menschliche Unternehmen Ziele verfolgt, so braucht die mathematische Forschung Probleme. Durch die Lösung von Problemen stählt sich die Kraft des Forschers; er findet neue Methoden und Ausblicke, er gewinnt einen weiteren und freieren Horizont.”

In this spirit, the theory of Banach spaces has been driven by a handful of fundamental problems, like the basis problem, the unconditional basic sequence problem, Banach’s hyperplane problem, the invariant subspace problem, the distortion problem, and the Schröder-Bernstein problem. For over half a century, progress with these major problems had been very slow: it is due to Gowers more than to anybody else that a few years ago the floodgates opened, and with the solutions of many of these problems the subject now has a ‘spacious, free horizon’.

If a space (infinite-dimensional separable Banch space) X can be represented as a sequence space then an operator T ∈ L(X) is simply given by an infinite matrix, so it is desirable to find a basis of the space. A Schauder basis or simply basis of a space X is a sequence (e_{n})_{n=1}^{∞} ⊂ X such that every vector x ∈ X has a unique representation as a norm-convergent sum x = ∑_{n=1}^{∞} a_{n}e_{n}. In 1973, solving a forty year old problem, Enflo [4] proved that not every separable Banach space has a basis, so our operators cannot always be given in this simple way. On the other hand, it is almost trivial that every Banach space contains a basic sequence: a sequence (x_{n})_{n=1}^{∞} that is a basis of its closed linear span.

The relationship between an operator T ∈ L(X) and closed subspaces of X can also be very involved. In the 1980s Enflo [5] and Read [22] solved in the negative the invariant subspace problem for Banach spaces, and a little later Read [23] showed that this phenomenon can arise on a ‘nice’ space as well: he constructed a bounded linear operator on ℓ_{1} that has only trivial invariant subspaces.

Although a basis (e_{n})_{n=1}^{∞} of a space X leads to a representation of the operators on X as matrices, it does not guarantee that L(X) has a rich structure. For example, it does not guarantee that L(X) contains many non-trivial projections. Thus, if x = ∑_{n=1}^{∞} a_{n}e_{n} and ϵ_{n} = 0, 1, then ∑_{n=1}^{∞} ϵ_{n}a_{n}e_{n} need not even converge. Similarly, a permutation of a basis need not be a basis, and if ∑_{n=1}^{∞} a_{n}e_{n} is convergent and π : ℕ → ℕ is a permutation then ∑_{n=1}^{∞} a_{π(n)}e_{π(n)} need not converge. A basis is said to be unconditional if it does have these very pleasant properties; equivalently, a basis (e_{n})_{n=1}^{∞} is unconditional if there is a constant C > 0 such that, if (a_{n})_{n=1}^{m} and (λ_{n})_{n=1}^{m} are scalar sequences with |λ_{n}| ≤ 1 for all n, then

|| ∑_{n=1}^{m} λ_{n}a_{n}e_{n}|| ≤ C|| ∑_{n=1}^{m} a_{n}e_{n}||.

Also, a sequence (x_{n})_{n=1}^{∞} is an unconditional basic sequence if it is an unconditional basis of its closed linear span. The standard bases of c_{0} and ℓ_{p}, 1 ≤ p < ∞, are all unconditional (and symmetric).

An unconditional basis guarantees much more structure than a basis, so it is not surprising that even classical spaces like C([0, 1]) and L_{1} fail to have unconditional bases. However, the fundamental question of whether every space has a subspace with an unconditional basis (or, equivalently, whether every space contains an unconditional basic sequence) was open for many years, even after Enflo’s result.

The search for a subspace with an unconditional basis is closely related to the search for other ‘nice’ subspaces. For example, it is trivial that not every space contains a Hilbert space, but it is far from clear whether every space contains c_{0} or ℓ_{p} for some 1 ≤ p < ∞. Indeed, this question was answered only in 1974, when Tsirelson [28] constructed a counterexample by a clever inductive procedure. This development greatly enhanced the prominence of the unconditional basic sequence problem.

The breakthrough came in the summer of 1991, when Gowers and Maurey [17] independently constructed spaces without unconditional basic sequences. As the constructions and proofs were almost identical, they joined forces to simplify the proofs and to exploit the consequences of the result. The Gowers-Maurey space X_{GM} is based on a construction of Schlumprecht [25] that eventually enabled Odell and Schlumprecht [21] to solve the famous distortion problem. Odell and Schlumprecht constructed a space isomorphic to ℓ_{2} that contains no subspace almost isometric to ℓ_{2}. The main difficulty Gowers and Maurey had to overcome in order to make use of Schlumprecht’s space X_{S} was that X_{S} itself had an unconditional basis.

Johnson observed that the proofs could be modified to show that the Gowers-Maurey space not only has no unconditional basic sequence, but it does not even have a decomposable subspace either: no subspace of X_{GM} can be written as a topological direct sum of two (infinite-dimensional) subspaces. Thus the space X_{GM} is not only the first example of a non-decomposable infinite-dimensional space, but it is also hereditarily indecomposable. Equivalently, every closed subspace Y of X_{GM} is such that every projection in L(Y) is essentially trivial: either its rank or its corank is finite. To appreciate how exotic a hereditarily indecomposable space is, note that a space X is hereditarily indecomposable if and only if the distance between the unit spheres of any two infinite-dimensional subspaces is 0: if Y and Z are infinite-dimensional subspaces then

inf{||y − z|| : y ∈ Y, z ∈ Z, ||y|| = ||z|| = 1} = 0.

In fact, Gowers and Maurey [16] showed that if X is a complex hereditarily indecomposable space then the algebra L(X) is rather small. An operator S ∈ L(X) is said to be strictly singular if there is no subspace Y ⊂ X such that the restriction of S to Y is an isomorphism. Equivalently, S ∈ L(X) is strictly singular if for every (infinite-dimensional) subspace Y ⊂ X and every ϵ > 0 there is a vector y ∈ Y with ||Sy|| < ϵ||y||.

Theorem. Let X be a complex hereditarily indecomposable space. Then every operator T ∈ L(X) is a linear combination of the identity and a strictly singular operator.

Gowers [9] was the first to solve Banach’s hyperplane problem when he constructed a space with an unconditional basis that is not isomorphic to any of its hyperplanes or even proper subspaces. The theorem above implies that every complex hereditarily indecomposable space answers Banach’s hyperplane problem since it is not isomorphic to any of its proper subspaces. In fact, Ferenczi [7] showed that a complex Banach space X is hereditarily indecomposable if and only if for every subspace Y ⊂ X, every bounded linear operator from Y into X is a linear combination of the inclusion map and a strictly singular operator. Recently, Argyros and Felouzis [1] showed that every Banach space contains either ℓ_{1} or a subspace that is a quotient of a hereditarily indecomposable space.

It was not by chance that in order to construct a space without an unconditional basis, Gowers and Maurey constructed a hereditarily indecomposable space.

As shown by the following stunning dichotomy theorem of Gowers [12], having an unconditional basis or being hereditarily indecomposable are the only two ‘pure states’ for a space.

Theorem. Every infinite-dimensional Banach space contains an infinite-dimen-sional subspace that either has an unconditional basis or is hereditarily indecomposable.

Gowers based his proof of the dichotomy theorem on a combinatorial game played on sequences and subspaces. In order to describe this game, we need some definitions. Given a space X with a basis (e_{n})_{n=1}^{∞}, the support of a vector a = ∑_{n=1}^{∞} a_{n}e_{n} ∈ X is supp(a) = {n : a_{n} ≠ 0}. A vector a = ∑_{n=1}^{∞} a_{n}e_{n} precedes a vector b = ∑_{n=1}^{∞} b_{n}e_{n} if n < m for all n ∈ supp(a) and m ∈ supp(b). A block basis is a sequence x_{1} < x_{2} < … of non-zero vectors, and a block subspace is the closed linear span of a block basis. For a subspace Y ⊂ X, write ∑(Y) for the set of all sequences (x_{i})_{1}^{n} of non-zero vectors of norm at most 1 in Y with x_{1} < ⋯ < x_{n}. Call a set σ ⊂ ∑(X) large if σ ∩ ∑(Y) ≠ ∅ for every (infinitedimensional) block subspace Y. For a set σ ⊂ ∑(X) and a sequence Δ = (δ_{i})_{i=1}^{∞} of positive reals, the enlargement of σ by Δ is

σ_{Δ} = {(x_{i})_{1}^{n} ∈ ∑(X) : ||x_{i} − y_{i}|| < δ_{i}, 1 ≤ i ≤ n, for some (y_{i})_{1}^{n} ∈ σ}.

And now for the two-player game (σ, Y) defined by a set σ ⊂ ∑(X) and a block subspace Y ⊂ X. The first player, Hider, chooses a block subspace Y_{1} ⊂ Y; the second player, Seeker, replies by picking a finitely supported vector y_{1} ∈ Y_{1}. Then Hider chooses a block subspace Y_{2} ⊂ Y, and Seeker picks a finitely supported vector y_{2} ∈ Y_{2}. Proceeding in this way, Seeker wins the (σ, Y)-game if, at any stage, the sequence (y_{i})_{1}^{n} is in σ. Hider wins if he manages to make the game go on for ever. Clearly, Seeker has a winning strategy for the (σ, Y) game if σ is big when measured by Y.

The combinatorial foundation of Gowers’ dichotomy theorem is then the following result [12].

Theorem. Let X be a Banach space with a basis and let σ ⊂ ∑(X) be large. Then for every positive sequence Δ there is a block subspace Y ⊂ X such that Seeker has a winning strategy for the (σ_{Δ}, Y)-game.

The beautiful proof of this result bears some resemblence to arguments of Galvin and Prikry [8] and Ellentuck [3] concerning Ramsey-type results for sequences.

Gowers’ dichotomy theorem has been the starting point of much new research on Banach spaces. For example, it can be used to tackle the still open problem of classifying minimal Banach spaces. A Banach space is minimal if it embeds into all of its infinite-dimensional subspaces. Casazza et al [2] used the dichotomy theorem to show that every minimal Banach space embeds into a minimal Banach space with an unconditional basis. Hence, a minimal space is either reflexive or embeds into c_{0} or ℓ_{1}.

The Schröder-Bernstein problem asks whether two Banach spaces are necessarily isomorphic if each is a complemented subspace of the other. In [13] Gowers gaver the first counterexample, and later with Maurey [16] constucted the following further examples with even stronger paradoxical properties.

Theorem. For every n ≥ 1 there is a Banach space X_{n} such that two finitecodimensional subspaces of X_{n} are isomorphic if and only if they have the same codimension modulo n. Also, there is a Banach space Z_{n} such that two product spaces Z_{n}^{r} and Z_{n}^{s} are isomorphic if and only if r and s are equal modulo n.

For n ≥ 2, the space Z_{n} can be used to solve the Schröder-Bernstein problem; even more, with X = Z_{3} and Y = Z_{3} ⊕ Z_{3} we have Y ⊕ Y = Z_{3}^{4} ≅ Z_{3} = X. Thus not only are X and Y complemented subspaces of each other, but X ≅ Y ⊕ Y and Y ≅ X ⊕ X. However, X = Z_{3} and Y = Z_{3}^{2} are not isomorphic.

The last result we shall discuss here is Gowers’ solution of Banach’s homogeneous spaces problem. A space is homogeneous if it is isomorphic to all of its subspaces. Banach asked whether there were any examples other than ℓ_{2}. Gowers proved the striking result that homogeneity, in fact, characterizes Hilbert space [12].

Theorem. The Hilbert space ℓ_{2} is the only homogeneous space.

To prove this, Gowers could make use of results of Szankowski [25], and Komorowski and Tomczak-Jaegermann [19] that imply that a homogeneous space with an unconditional basis is isomorphic to ℓ_{2}. What happens if X is homogeneous but does not have an unconditional basis? By the dichotomy theorem, X has a subspace Y that either has an unconditional basis or is hereditarily indecomposable. Since X ≅ Y and X does not have an unconditional basis, Y is hereditarily indecomposable. But this is impossible, since a hereditarily indecomposable space is not isomorphic to any of its proper subspaces, let alone all of them!

2 Arithmetic progressions

In 1936 Erdős and Turán [6] conjectured that, for every positive integer k and δ > 0, there is an integer N such that every subset of {1, …, N} of size at least δN numbers contains an arithmetic progression of length k. In 1953 Roth [24] used exponential sums to prove the conjecture in the special case k = 3: this was one of the results Davenport highlighted in 1958 when Roth was awarded a Fields Medal. In 1969 Szemerédi found an entirely combinatorial proof for the case k = 4, and six years later he proved the full Erdős-Turán conjecture. Szemerédi’s theorem trivially implies van der Waerden’s theorem.

In 1977 Fürstenberg [7] used techniques of ergodic theory to prove not only the full theorem of Szemerédi, but also a number of substantial extensions of it. This proof revolutionized ergodic theory.

In spite of these beautiful results, there is still much work to be done on the Erdős-Turán problem. Write f(k, δ) for the minimal value of N that will do in Szemerédi’s theorem. The proofs of Szemerédi and Fürstenberg give extremely weak bounds for f(k, δ), even in the case k = 4. In order to improve these bounds, and to make it possible to attack some considerable extensions of Szemerédi’s theorem, it would be desirable to use exponential sums to prove the general case.

Recently, Gowers [15] set out to do exactly this. He introduced a new notion of pseudorandomness, called quadratic uniformity and, using techniques of harmonic analysis, showed that a quadratically uniform set contains about the expected number of arithmetic progressions of length four. In order to find arithmetic progressions in a set that is not quadratically uniform, Gowers avoided the use of Szemerédi’s uniformity lemma or van der Waerden’s theorem, and instead made use of Weyl’s inequality and, more importantly, Freiman’s theorem. This theorem states that if for some finite set A ⊂ ℤ the sum A + A = {a + b : a, b ∈ A} is not much larger than A then A is not far from a generalized arithmetic progression. By ingenious and involved arguments Gowers proved the following result [14].

Theorem. There is an absolute constant C such that

f(4, δ) ≤ exp exp exp((1/δ)^{C}).

In other words, if A ⊂ {1, …, N} has size at least |A| = δN > 0 and N ≥ exp exp exp((1/δ)^{C}), then A contains an arithmetic progression of length 4.

The bound in this theorem is imcomparably better than the previous best bounds.

The entirely new approach of Gowers raises the hope that one could prove the full theorem of Szemerédi with good bounds on f(k, δ). In fact, there is even hope that Gowers’ method could lead to a proof of the Erdős conjecture that if A ⊂ ℕ is such that ∑_{a∈A} 1/a = ∞ then A contains arbitrarily long arithmetic progressions. The most famous special case of this conjecture is that the primes contain arbitrarily long arithmetic progressions.

3 Combinatorics

The basis of Szemerédi’s original proof of his theorem on arithmetic progressions was a deep lemma that has become an extremely important tool in the study of the structure of graphs. This result, Szemerédi’s uniformity lemma, states that the vertex set of every graph can be partitioned into boundedly many pieces V_{1}, …, V_{k} such that ‘most’ pairs (V_{i}, V_{j}) are ‘uniform’. In order to state this lemma precisely, recall that, for a graph G = (V, E), and sets U, W ⊂ V, the density d(U, W) is the proportion of the elements (u, w) of U × W such that uw is an edge of G. For ϵ, δ > 0 a pair (U, W) is called (ϵ, δ)-uniform if for any U′ ⊂ U and W′ ⊂ W with |U′| ≥ δ|U| and |W′| ≥ δ|W |, the densities d(U′, W′) and d(U, W) differ by at most ϵ/2.

Szemerédi’s uniformity lemma [27] claims that for all ϵ, δ, η > 0 there is a K = K(ϵ, δ, η) such that the vertex set of any graph G can be partitioned into at most K sets U_{1}, …, U_{k} of sizes differing by at most 1, such that at least (1 − η)k^{2} of the pairs (U_{i}, U_{j}) are (ϵ, δ)-uniform.

Loosely speaking, a ‘Szemerédi partition’ V (G) = ⋃_{i=1}^{k} U_{i} is one such that for most pairs (U_{i}, U_{j}) there are constants α_{ij} such that if U′_{i} ⊂ U_{i} and U′_{j} ⊂ U_{j} are not too small then G contains about α_{ij}|U′_{i}||U′_{j}| edges from U′_{i} to U′_{j}. In some sense, Szemerédi’s uniformity lemma gives a classification of all graphs. The main drawback of the lemma is that the bound K(ϵ, δ, η) is extremely large: in the case ϵ = δ = η, all we know about K(ϵ, ϵ, ϵ) is that it is at most a tower of 2s of height proportional to ϵ^{−5}. This is an enormous bound, and in many applications a smaller bound, say of the type e^{ϵ^{−100}} would be significantly more useful. As the lemma is rather easy to prove, it was not unreasonable to expect a bound like this.

It was a great surprise when Gowers [14] proved the deep result that K(ϵ, δ, η) is of tower type in 1/δ, even if ϵ and η are kept large.

Theorem. There are constants c_{0}, δ_{0} > 0 such that for 0 < δ < δ_{0} there is a graph G that does not have a (1/2, δ, 1/2)-uniform partition into K sets, where K is a tower of 2s of height at most c_{0}δ^{−1/16}.

It is well known that even exponential lower bounds are hard to come by, let alone tower type lower bounds, so this is a stunning result indeed! The proof, which makes use of clever random choices to construct graphs whose small sets of vertices do not behave like subsets of random graphs, goes some way towards clarifying the nature of randomness. It also indicates that any proof of an upper bound for K(ϵ, δ, η) must involve a long sequence of refinements of partitions, each exponentially larger than the previous one.

This sketch has been all too brief, and a deeper study of Gowers’ work would be needed to properly appreciate his clarity of thought and mastery of elaborate structures. However, I hope that enough has been said to give some taste of his remarkable mathematical achievements. In the theory of Banach spaces, not only has he solved many of the main classical problems of the century, but he has also opened up exciting new directions. In combinatorics, too, he has tackled some of the most notorious questions, bringing about their solution with the same exceptional blend of combinatorial power and technical skill. Hilbert would surely agree that Gowers has given us wider and freer horizons.

References

[1] S.A. Argyros and V. Felouzis, Interpolating H.I. Banach spaces, to appear

[2] P.G. Casazza, N.J. Kalton, D. Kutzerova and M. Mastyło, Complex interpolation and complementably minimal spaces, in Ineraction between Functional Analysis, Harmonic Analysis, and Probability, Lecture Notes in Pure and Applied Math., Dekker, N.Y., 1996, pp. 135–143.

[3] E. Ellentuck, A new proof that analytic sets are Ramsey, J. Symbolic Logic 39 (1974), 163–165.

[4] P. Enflo, A counterexample to the approximation property in Banach spaces, Acta Math. 130 (1973), 309–317.

[5] P. Enflo, On the invariant-subspace problem in Banach spaces, Acta Math. 158 (1987), 213–313.

[6] P. Erdős and P. Turán, On some sequences of integers, J. London Math. Soc. 11 (1936), 261–264.

[7] V. Ferenczi, Operators on subspaces of hereditarily indecomposable Banach spaces, Bull. London Math. Soc. 29 (1997), 338-344.

[8] F. Galvin and K. Prikry, Borel sets and Ramsey’s theorem, J. Symbolic Logic 38 (1973), 193–198.

[9] W.T. Gowers, A solution to Banach’s hyperplane problem, Bull. London math. Soc. 26 (1994), 523–530.

[10] W.T. Gowers, A Banach space not containing c_{0}, ℓ_{1} or a reflexive subspace, Trans. Amer. Math. Soc. 344 (1994), 407–420.

[11] W.T. Gowers, A hereditarily indecomposable space with an asymptotic unconditional basis, Oper. Theory: Adv. Appl. 77, (1995), 111–120.

[12] W.T. Gowers, A new dichotomy for Banach spaces, Geom. Funct. Anal. 6 (1996), 1083-1093.

[13] W.T. Gowers, A solution to the Schroeder-Bernstein problem for Banach spaces, Bull. London Math. Soc. 28 (1996), 297–304.

[14] W.T. Gowers, Lower bounds of tower type for Szemerédi’s uniformity lemma, Geom. Funct. Anal. 7 (1997), 322-337.

[15] W.T. Gowers, A new proof of Szemerédi’s theorem for arithmetic progressions of length four, Geom. Funct. Anal. bf 8 (1998), 529–551.

[16] W.T. Gowers and B. Maurey, The unconditional basis sequence problem, J. Amer. Math. Soc. 6 (1993), 851–874.

[17] W.T. Gowers and B. Maurey, Banach spaces with small spaces of operators, Math. Ann. 307 (1997), 543-568.

[18] R.C. James, Bases and reflexivity of Banach spaces, Ann. of Math. (2) 52 (1950), 518–527.

[19] R. Komorowski and N. Tomczak-Jaegermann, Banach spaces without local unconditional structure, Israel J. Math. 89 (1995), 205–226.

[20] J. Lindenstrauss and L. Tzafriri, Classical Banach Spaces I: Sequence Spaces, Springer-Verlag, Berlin and New York 1977.

[21] E. Odell and T. Schlumprecht, The distortion problem, Acta. Math. 173 (1994), 259–281.

[22] C.J. Read, A solution to the Invariant Subspace Problem, Bull. London Math. Soc. 16 (1984), 337–401.

[23] C.J. Read, A solution to the Invariant Subspace Problem on the space ℓ_{1}, Bull. London Math. Soc. 17 (1985), 305–317.

[24] K.F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953) 245– 252.

[25] T. Schlumprecht, An arbitrarily distortable Banach space, Israel J. Math. 76 (1991), 81–95.

[26] E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975), 199–245.

[27] E. Szemerédi, Regular partitions of graphs, in “Proc. Colloque Inter. CNRS” (J.C. Bermond, J.-C. Fournier, M. Las Vergnas, D. Sotteau, eds.), 1978, pp.399-401.

[28] B.S. Tsirelson, Not every Banach space contains ℓ_{p} or c_{0}, Functional Anal. Appl. 8 (1974), 139–141.

Béla Bollobás Trinity College University of Cambridge Cambridge CB2 1SB England and Dept. of Math. Sciences University of Memphis Memphis TN 38152, USA 118 Béla Bollobás

William Timothy Gowers

Department of Pure Mathematics & Mathematical Statistics, Cambridge University, Cambridge, England

Born:  November 20, 1963, Marlborough, England
Nationality:  British
Marital Status:  married, three children
1982–1985  Undergraduate at Cambridge
1985–1986  Postgraduate at Cambridge
1986–1990  Ph.D. at Cambridge under B. Bollobás
1989–1993  Research Fellow at Trinity College, Cambridge
1991–1994  Lecturer in Mathematics at University College London
1994–1995  Reader in Mathematics at University College London
1995  Lecturer at D.P.M.M.S., University of Cambridge, and

Teaching Fellow at Trinity College

Fields of Interest: Analysis and Combinatorics

Béla Bollobás and William Timothy Gowers