• Call for Social Sciences Papers
  • Science Sessions: The PNAS Podcast Program

Quantitative geometry

  1. Assaf Naor1
  1. Courant Institute, New York University, New York, NY 10012

Rather than describing a traditional field of mathematics, “quantitative geometry” refers to a modern way of thinking about geometry and its applications that occur in a wide range of mathematical disciplines. The overarching theme here is that certain geometric problems can only be formulated after the introduction of auxiliary quantitative parameters and asking for their asymptotic or approximate behavior. This leads to meaningful questions that do not necessarily have counterparts in classical “qualitative” geometric investigations, a viewpoint that allows one to uncover deep and useful structural information that appears only in the quantitative regime. Quantitative reasoning allows one to tame complicated objects and phenomena that are unwieldy if one insists on exact measurements. It is often the case that a rich yet structured picture emerges only if one asks the correct questions by allowing for controlled errors.

The term quantitative geometry was coined as an attempt to formulate the widespread understanding of many researchers worldwide that in recent years numerous natural questions have emerged that mandate the study of geometric problems from an approximate perspective. This trend is sometimes dictated by application areas in which exact computation is infeasible yet approximate measurements are of crucial importance, but it arises most often as a natural modern development of traditional mathematical disciplines, where quantitative refinements of classical investigations are necessary to probe deeper and fully understand basic mathematical objects.

What Is Quantitative Geometry?

Rather than attempting to give formal definitions, we shall illustrate the above discussion through examples from various areas of mathematics.

Geometric Group Theory.

A group G that is generated by a finite symmetric set S becomes a geometric object if one endows it with the word metric that is induced by S. If one nevertheless wants to study groups as algebraic entities, the generating set itself is of minor or no importance, but replacing S by another generating set T changes the word metric in a bi-Lipschitz way. One is therefore led to consider groups as metric spaces that are indistinguishable under bi-Lipschitz deformations. This viewpoint is of monumental importance to group theory and geometry, Gromov’s characterization of groups of polynomial growth (1) being a seminal work in this area (see also ref. 2). The third article (3) in the present volume (to be described below) answers a question of Gromov related to his polynomial growth theorem, and the first article (4) in this volume also resolves a basic question in geometric group theory, exhibiting for the first time that two natural quantitative geometric parameters of groups (homological and homotopical Dehn functions) can have different asymptotics for the same group.

Whether or not a given finitely generated group admits a geometrically faithful embedding into a certain well-behaved space, say, into Hilbert space or into an Graphic space, is a basic question in geometric group theory, with many important algebraic and topological implications (see ref. 5 for a striking example). Here the notion of a “geometrically faithful” embedding can take several meanings; there is, for example, great interest in bi-Lipschitz and coarse embeddings. Focusing on the bi-Lipschitz case, it is an intriguing and beautiful conjecture (6) that a finitely generated group G admits a bi-Lipschitz embedding into Hilbert space if and only if G has an Abelian subgroup of finite index. Therefore, to classify non-virtually-Abelian groups G in terms of their embeddability into Hilbert space, one must quantify the extent to which G does not admit a bi-Lipschitz embedding into Hilbert space. There is more than one natural (and fruitful) way to do this. For every Graphic, one can ask what is the largest Hilbertian bi-Lipschitz distortion of an n-point subset of G, and denoting this number by Graphic, investigate the rate at which Graphic tends to infinity. This rate does not depend on a specific finite generating set, so it is a genuine algebraic invariant of G. It turns out to be quite difficult to evaluate the asymptotic behavior of Graphic, and this has been computed in only a few cases, e.g., Graphic if G is a free group on at least two generators (5), and Graphic if G is the Heisenberg group (8). Similar questions with Hilbert space replaced by Graphic are of fundamental importance to theoretical computer science (9). Another way to quantify the extent to which a group G that is generated by a finite symmetric set S fails to embed bi-Lipschitzly into Hilbert space was introduced by Guentner and Kaminker (10): they define the Hilbert compression exponent of G, denoted Graphic, to be the supremum over those Graphic for which there exists a Lipschitz mapping Graphic satisfying Graphic for every Graphic. Here Graphic denotes the word metric induced by S and Graphic may depend on Graphic but not on Graphic. Again, being independent of the specific choice of a finite generating set, Graphic is an algebraic invariant of G, yet there are only a few known methods to compute it, some of which involve interesting links to harmonic analysis and probability theory. Note that both the asymptotics of Graphic and the Hilbert compression exponent Graphic are quantitative invariants that encode structural information about the group G, yet they do not have qualitative counterparts.

Geometric Topology.

Topology is another source of a wealth of important quantitative geometric questions. Despite the numerous remarkable achievements of algebraic topology, the difficulty of understanding classical qualitative topological problems quantitatively has been emphasized by Gromov (11). For example, suppose that Graphic are finite complexes and Y is simply connected. If Graphic are homotopic “well-behaved” maps, are they also homotopic through maps that are equally well behaved? There are many ways to interpret what well behaved means in this general context. Here we take this term to mean that the mappings in question are Lipschitz. Therefore, supposing that Graphic are homotopic L-Lipschitz functions, can they be homotoped through KL-Lipschitz functions, or perhaps one can even find a homotopy that is itself KL-Lipschitz? Here K is allowed to depend on Graphic but not on Graphic. The seventh article (12) of the present volume treats this question by obtaining a necessary and sufficient condition for the existence of a KL-Lipschitz homotopy but also shows that sometimes one cannot find Lipschitz homotopies despite the fact that homotopies through Lipschitz functions are possible. We have indicated just one example of quantitative geometric refinements of topological concepts and questions, but the literature contains many investigations (and many open questions) of this type, all of which belong under the quantitative geometry rubric.

Differential Geometry.

Geometric flows and limiting constructions such as blow-ups and tangent cones are commonly studied in differential geometry, and it is very natural (and useful) to refine these investigations quantitatively. The fifth article (13) of the present volume describes interesting contributions to this aspect of quantitative geometry. It introduces new monotone quantities for the heat and Laplace equations on manifolds and uses them to prove new uniqueness results for tangent cones. While the existence of tangent cones is often proved through the use of monotone quantities, proving the uniqueness of tangent cones is inherently quantitative, relying on showing that the monotone quantity approaches its limit at a definite rate. The new quantities that are introduced in the above-mentioned article are sufficiently well behaved to yield the desired convergence rates and hence prove the uniqueness of tangent cones at infinity for any Ricci-flat manifold with Euclidean volume growth, provided that one such tangent cone has a smooth cross section.

Local Theory of Banach Spaces and the Ribe Program.

Answering questions that were raised in the late 1920s and early 1930s (14, 15), a deep theorem of Kadec (16) asserts that any two separable infinite dimensional Banach spaces are homeomorphic. On the other hand, Ribe proved (17) that any two Banach spaces Graphic that are uniformly homeomorphic (i.e., the homeomorphism and its inverse are both uniformly continuous) have the same isomorphic local linear structure, i.e., there exists Graphic such that for any finite dimensional linear subspace Graphic there exists a linear subspace Graphic that is linearly isomorphic to E via a linear mapping Graphic satisfying Graphic. Thus, while the rich world of separable infinite dimensional Banach spaces collapses to a single object when one considers them as topological spaces, a lot of structure remains if one insists that homeomorphisms are quantitatively continuous. For example, since for distinct Graphic the sequence spaces Graphic and Graphic do not have the same isomorphic local linear structure, it follows from Ribe’s theorem that Graphic and Graphic are not uniformly homeomorphic.

Note a crucial feature of Ribe’s theorem: its conclusion involves an unspecified constant K, so it can be used only if one considers properties of Banach spaces that are insensitive to deformations that result in a loss of such a constant factor. Moreover, the conclusion of Ribe’s theorem involves properties of finite dimensional subspaces (a.k.a. local properties), and since all of the norms on Graphic are equivalent, finite dimensional normed spaces become distinguishable only if one studies them in the quantitative regime. This point of view gives rise to the local theory of Banach spaces: a deep and rich theory (18, 19) that over the last five decades has had a transformative impact on functional analysis, in addition to many applications to a variety of mathematical disciplines. The sixth (20) and eighth (21) articles of the present volume (to be described below) contain new applications of the local theory of Banach spaces.

Inspired by Ribe’s theorem and formulated in print for the first time by Bourgain (22), the Ribe program asks for an explicit dictionary that translates local linear concepts and phenomena from the linear setting of Banach spaces to general metric spaces. Thus, besides being a very satisfactory rigidity statement in itself, Ribe’s theorem is a beginning rather than an end: the source and motivation of a quest to recast quantitative aspects of Banach space theory while using only the notion of distance, without reference to the linear structure whatsoever, and through this dictionary proceeding to ask questions and apply insights that previously made sense only for linear spaces to more general metric spaces such as graphs, manifolds, and groups. We refer to the surveys (23, 24) for more on this topic. The ninth article (25) of the present volume (to be described below) belongs to the Ribe program.

Aspects of Discrete Mathematics.

Several areas of discrete mathematics are well suited for quantitative geometric investigations. In theoretical computer science, the field of approximation algorithms and the complementary viewpoint of hardness of approximation are inherently related to geometric considerations of a quantitative nature. NP-hard discrete optimization problems are often relaxed to continuous optimization problems that are efficiently solvable, and the resulting “rounding problem” asks for an efficient way to generate a discrete solution from a continuous solution while losing a (hopefully small) definite multiplicative factor. Conversely, through mechanisms such as Khot’s Unique Games Conjecture (26), one can relate the computational complexity of certain optimization problems and specifically the “hardness threshold,” above which it becomes feasible to find an approximate solution to continuous quantitative geometric questions; see ref. 22 for more on this topic. In graph theory, one sometimes relates geometric invariants to combinatorial graphs [e.g., the Lovász theta function (28)], leading naturally to interesting geometric problems of a quantitative/asymptotic nature (29). The fourth article (30) in the present volume contains results along these lines. As a last example, we consider the area of incidence geometry. Classically, one is interested here in understanding the constraints that are imposed on a finite set of points in Euclidean space, under the assumption that the points obey certain algebraic restrictions of a qualitative nature, e.g., the number of distinct pairwise distances is small, or every line that passes through two of the points must also pass through a third point. The latter example is addressed by the classical Sylverster–Gallai theorem, which asserts that if a finite set Graphic has the property that every line that passes through two distinct points of S also passes through a third point of S, then S consists of collinear points. The second (31) article of the present volume relaxes this rigid question by studying scenarios in which we only know that a constant fraction of the lines that pass through two distinct points of S also passes through a third point of S. While this formulation leads to combinatorial (counting) asymptotic questions, one can make it less qualitative by not considering exact incidences but rather examining lines that pass near points of S or equivalently replacing lines by tubes. This is the topic of subsequent investigations (32) that will appear elsewhere.

Quantitative Geometry at Mathematical Sciences Research Institute

In the fall semester of 2011, the Mathematical Sciences Research Institute (MSRI) at Berkeley hosted a research program called quantitative geometry (QG). This program was what MSRI calls a “jumbo program” in the sense that, while MSRI typically runs two semester-long programs in parallel, the QG program pooled the resources that are normally intended for two separate programs into one big program to which the MSRI activities of fall 2011 were devoted in their entirety. The QG program featured extended stays of more than 80 mathematicians, ranging from senior researchers to postdoctoral fellows and graduate students. Many additional mathematicians passed through the QG program for shorter visits, some of which came to MSRI to participate in one of the five focused workshops that took place as part of the program. The present special feature of PNAS contains some highlights of new results that relate to the QG program. Through the auspices of MSRI, the QG program created an exceptionally fertile research environment that led to the discovery of many additional results that appeared (or will appear) elsewhere, so the articles that follow should be viewed as a sample of recent developments rather than a comprehensive account of the program’s outcome and impact.

Quantitative Geometry Special Feature of PNAS

We shall now proceed to describe the content of some of the articles that appear herein. Our goal is to illustrate the flavor of the research that is done in the context of quantitative geometry, and we do so by choosing to discuss only a subset of the ensuing works. We refer to the papers themselves for full details.

Rate of Convergence to Pansu’s Limit.

Let G be a finitely generated group, equipped with a left-invariant word metric that is associated to a finite symmetric generating set. For Graphic let Graphic be the ball of radius n centered at the identity element. Gromov’s famous polynomial growth theorem (1) asserts that there exists Graphic such the cardinality of Graphic satisfies Graphic for all Graphic if and only if G has a nilpotent subgroup of finite index. Pansu proved (33) that if G is nilpotent then there exists Graphic and Graphic such that Graphic. Answering a question of Gromov (2), the third article (3) in the present volume obtains the first known quantitative estimate for the term Graphic: it is shown there that Graphic, where r is the nilpotency class of G. In fact, Pansu proved that if we rescale the word metric by Graphic, then the resulting metric spaces converge as Graphic in the Gromov-Hausdorff topology to a certain explicit left-invariant sub-Finsler metric on a nilpotent Lie group, and Gromov asked (2) for quantitative estimates on the rate of convergence in Pansu’s theorem. The third paper (3) of the present volume solves Gromov’s question by showing that the (Gromov-Hausdorff) distance between the rescaled metric and Pansu’s limit metric is Graphic.

Deterministic Volume Estimation.

Suppose that a convex body Graphic is given to us in terms of a well-guaranteed membership oracle (32), i.e., for every point Graphic we can ask the oracle whether or not x belongs to K, and we also know that K is sandwiched between two Euclidean balls whose ratio of radii grows at most exponentially with n. The goal is to find a fast algorithm that is guaranteed to be within a hopefully small constant factor of the volume of K, where fast is measured in terms of the number of times that the algorithm makes a membership query to the oracle. The sixth article (20) of the present volume shows for the first time that for every Graphic there is a deterministic algorithm that computes a Graphic approximation to the volume of a centrally symmetric convex body that is given by a well-guaranteed membership oracle in time Graphic. As shown in ref. 35, no deterministic volume-computation algorithm can have a better performance [up to the implicit constants in the Graphic term]. The proof of this fact relies on the design of the first deterministic exponential time algorithm that computes an M-ellipsoid of the given body, which is an important type of ellipsoid whose existence was discovered by Milman (36). This is achieved through a clever iterative argument that uses important tools from the local theory of Banach spaces—a beautiful example of the interplay between geometry and algorithms.

Quantitative Characterization of Commutators and the Kadison–Singer Problem.

A classical fact in linear algebra asserts that if Graphic is an n × n matrix with complex entries whose trace vanishes then there exist Graphic such that Graphic. This identity clearly implies the operator norm bound Graphic. The eighth article of the present volume (21) addresses the question whether or not one can find such matrices Graphic for which the ratio Graphic is small. It turns out that proving such a quantitative version of a linear algebraic fact can be quite difficult, and the argument here uses tools that were developed in the context of the local theory of Banach spaces [notably, the restricted invertibility principle of Bourgain and Tzafriri (37)]. The theorem proved in the eighth article (21) of the present volume asserts that given a matrix Graphic of trace zero there exist Graphic with Graphic andFormulaThe key point here is that the term Graphic is asymptotically smaller than any power of n, but it remains open whether or not it can be replaced by a universal constant. It is shown in ref. 21 how one could replace this term by Graphic if a sharp form of (the paving formulation of) the Kadison–Singer problem were true. Although the Kadison–Singer problem was recently solved affirmatively by Marcus et al. (38), at present this solution does not seem to supply the desired quantitative estimates.

Ultrametric Skeletons.

The ninth article of the present volume (25) shows that for every Graphic there exists Graphic such that if Graphic is a compact metric space and μ is a Borel probability measure on X, then there exists a compact subset Graphic, a Borel probability measure ν that is supported on S, and an ultrametric Graphic such thatFormulaandFormulaHere Graphic is the closed ball of radius r centered at x that is induced by the metric d. Recall that the fact that ρ is an ultrametric means that, for every Graphic, it satisfies the improved triangle inequality Graphic.

The metric measure space Graphic is called an “ultrametric skeleton” of the metric measure space Graphic for several reasons. One expects from the notion of a skeleton that it surrounds the macroscopic features of X to which μ gives positive mass (by no means do we expect a skeleton to be dense). This is indeed the case in the present setting, since if μ assigns positive mass to two balls Graphic and Graphic whose centers are sufficiently distant with respect to the scale r, i.e., Graphic, then the probability measure ν (which is supported on S) cannot assign full mass to one of these balls. More importantly, the term skeleton appears here because of the way the above theorem is used in applications: one can prove theorems about general metric spaces by extracting a skeleton and arguing that it can be used to imply a statement about the ambient metric space that does not involve the skeleton itself. In particular, the ultrametric skeleton theorem can be used to obtain a new proof of Talagrand’s majorizing measure theorem (39), and it implies the only known proof that if Graphic is a compact metric space of Hausdorff dimension bigger than n, then there exists a surjective Lipschitz function Graphic (40). This theorem also has algorithmic implications, including the best known lower bound for the randomized k-server problem on general metric spaces (41, 42) and the only known construction of sharp approximate distance oracles with constant query time for general metric spaces (43, 44).

The ultrametric skeleton theorem is an outgrowth of the Ribe program because it was inspired by the search for a metric space analog of a very important theorem of Dvoretzky (45) that originated in the local theory of Banach spaces. Specifically, it implies a sharp solution of the nonlinear Dvoretzky problem that was formulated by Bourgain et al. (46), and it also implies a natural Hausdorff-dimensional variant of the nonlinear Dvoretzky problem (47) that was posed by Tao. This development is an example of one of the most exciting features of the Ribe program and its impact on metric geometry: analogy with Banach space theory initiates the search for a certain phenomenon, and it turns out that this leads to a discovery of a phenomenon that is very different from its linear counterpart, yet it (and its applications) was unearthed because of the Ribe program’s capacity to generate meaningful and useful questions (through a dictionary that translates Banach space phenomena into metric space questions). In the present context of metric Dvoretzky-type problems, following the initial work of Bourgain et al. (46), this point of view was later championed by Milman, who proceeded to make similar (successful) metric predictions inspired by his Quotient of Subspace theorem (48?50).

Acknowledgments

This work was supported by National Science Foundation Grant CCF-0832795, United States–Israel Binational Science Foundation Grant 2010021, and the Packard Foundation.

Footnotes

  • ?1E-mail: naor{at}cims.nyu.edu.
  • Author contributions: A.N. wrote the paper.

  • The author declares no conflict of interest.

References

  1. ?
  2. ?
  3. ?
  4. ?
  5. ?
  6. ?
  7. ?
  8. ?
  9. ?
  10. ?
  11. ?
  12. ?
  13. ?
  14. ?
  15. ?
  16. ?
  17. ?
  18. ?
  19. ?
  20. ?
  21. ?
  22. ?
  23. ?
  24. ?
  25. ?
  26. ?
  27. ?
  28. ?
  29. ?
  30. ?
  31. ?
  32. ?
  33. ?
  34. ?
  35. ?
  36. ?
  37. ?
  38. ?
  39. ?
  40. ?
  41. ?
  42. ?
  43. ?
  44. ?
  45. ?
  46. ?
  47. ?

Online Impact

                                                          1. 956115858 2018-01-22
                                                          2. 730379857 2018-01-22
                                                          3. 346624856 2018-01-22
                                                          4. 201609855 2018-01-22
                                                          5. 72549854 2018-01-21
                                                          6. 795928853 2018-01-21
                                                          7. 752345852 2018-01-21
                                                          8. 566508851 2018-01-21
                                                          9. 615722850 2018-01-21
                                                          10. 689612849 2018-01-21
                                                          11. 846903848 2018-01-21
                                                          12. 674896847 2018-01-21
                                                          13. 11197846 2018-01-21
                                                          14. 986896845 2018-01-21
                                                          15. 667601844 2018-01-21
                                                          16. 385442843 2018-01-21
                                                          17. 496686842 2018-01-21
                                                          18. 915288841 2018-01-21
                                                          19. 885256840 2018-01-21
                                                          20. 726268839 2018-01-21