Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem

Assaf Naor and I have just uploaded to the arXiv our joint paper “Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem“.

Consider a finite metric space , with being a set of points. It is not always the case that this space can be isometrically embedded into a Hilbert space such as ; for instance, in a Hilbert space every pair of points has a unique midpoint, but uniqueness can certainly fail for finite metric spaces (consider for instance the graph metric on a four-point diamond). The situation improves, however, if one allows (a) the embedding to have some distortion, and (b) one is willing to embed just a subset of , rather than all of . More precisely, for any integer and any distortion , let be the largest integer with the property that given every -point metric space , there exists a -point subset of , and a map , which has distortion at most in the sense that

for all .

Bourgain, Figiel, and Milman established that for any fixed , one has the lower bound , and also showed for sufficiently close to there was a matching upper bound . This type of result was called a nonlinear Dvoretsky theorem, in analogy with the linear Dvoretsky theorem that asserts that given any -dimensional normed vector space and , there existed a -dimensional subspace which embedded with distortion into , with . In other words, one can ensure that about of the points in an arbitrary metric space behave in an essentially Euclidean manner, and that this is best possible if one wants the distortion to be small.

Bartel, Linial, Mendel, and Naor observed that there was a threshold phenomenon at . Namely, for , the Bourgain-Figiel-Milman bounds were sharp with ; but for one instead had a power law

for some . In other words, once one allows distortion by factors greater than , one can now embed a polynomial portion of the points, rather than just a logarithmic portion, into a Hilbert space. This has some applications in theoretical computer science to constructing “approximate distance oracles” for high-dimensional sets of data. (The situation at the critical value is still unknown.)

In the special case that the metric is an ultrametric, so that the triangle inequality is upgraded to the ultra-triangle inequality , then it is an easy exercise to show that can be embedded isometrically into a Hilbert space, and in fact into a sphere of radius . Indeed, this can be established by an induction on the cardinality of , using the ultrametric inequality to partition any finite ultrametric space of two or more points into sets of strictly smaller diameter that are all separated by , and using the inductive hypothesis and Pythagoras’ theorem.

One can then replace the concept of embedding into a Hilbert space, with the apparently stronger concept of embedding into an ultrametric space; this is useful for the computer science applications as ultrametrics have a tree structure which allows for some efficient algorithms for computing distances in such spaces. As it turns out, all the preceding constructions carry over without difficulty to this setting; thus, for , one can embed a logarithmic number of points with distortion into an ultrametric space, and for one can embed a polynomial number of points.

One can view the task of locating a subset of a metric space that is equivalent (up to bounded distortion) to an ultrametric as that of fragmenting a metric space into a tree-like structure. For instance, the standard metric on the arithmetic progression of length is not an ultrametric (and in fact needs a huge distortion factor of in order to embed into an ultrametric space), but if one restricts to the Cantor-like subset of integers in whose base expansion consists solely of s and s, then one easily verifies that the resulting set is fragmented enough that the standard metric is equivalent (up to a distortion factor of ) to an ultrametric, namely the metric where is the largest integer for which divides and .

The above fragmentation constructions were somewhat complicated and deterministic in nature. Mendel and Naor introduced a simpler probabilistic method, based on random partition trees of , which reproved the above results in the high-distortion case (with in the limit ). However, this method had inherent limitations in the low-distortion case, in particular failing for (basically because the method would establish a stronger embedding result which fails in that regime).

In this paper, we introduce a variant of the random partition tree method, which involves a random fragmentation at a randomly chosen set of scales, that works all the way down to and gives a clean value for the exponent , namely ; in fact we have the more precise result that we can take to be , where is the unique solution to the equation

and that this is the limit of the method if one chooses a “scale-oblivious” approach that applies uniformly to all metric spaces, ignoring the internal structure of each individual metric space.

The construction ends up to be relatively simple (taking about three pages). The basic idea is as follows. Pick two scales , and let be a random sequence of points in (of course, being finite, every point in will almost surely be visited infinitely often by this sequence). We can then partition into pieces , by defining to be the set of points for which is the first point in the sequence to lie in the ball . We then let be the subset of in which actually falls in the smaller ball . As a consequence, we see that each is contained in a ball of radius (namely ), but that any two are separated by a distance of at least (from the triangle inequality). This gives one layer of a quasi-ultrametric tree structure on ; if one iterates this over many different pairs of scales , one gets a full quasi-ultrametric tree structure, which one can then adjust with bounded distortion to a genuine ultrametric structure. The game is then to optimise the choice of so as to maximise the portion of that remains in the tree; it turns out that a suitably random choice of such scales is the optimal one.

Random Martingales and localization of maximal inequalities

Assaf Naor and I have just uploaded to the arXiv our paper “Random Martingales and localization of maximal inequalities“, to be submitted shortly. This paper investigates the best constant in generalisations of the classical Hardy-Littlewood maximal inequality

for any absolutely integrable , where is the Euclidean ball of radius centred at , and denotes the Lebesgue measure of a subset of . This inequality is fundamental to a large part of real-variable harmonic analysis, and in particular to Calderón-Zygmund theory. A similar inequality in fact holds with the Euclidean norm replaced by any other convex norm on .

The exact value of the constant is only known in , with a remarkable result of Melas establishing that . Classical covering lemma arguments give the exponential upper bound when properly optimised (a direct application of the Vitali covering lemma gives , but one can reduce to by being careful). In an important paper of Stein and Strömberg, the improved bound was obtained for any convex norm by a more intricate covering norm argument, and the slight improvement obtained in the Euclidean case by another argument more adapted to the Euclidean setting that relied on heat kernels. In the other direction, a recent result of Aldaz shows that in the case of the norm, and in fact in an even more recent preprint of Aubrun, the lower bound for any has been obtained in this case. However, these lower bounds do not apply in the Euclidean case, and one may still conjecture that is in fact uniformly bounded in this case.

Unfortunately, we do not make direct progress on these problems here. However, we do show that the Stein-Strömberg bound is extremely general, applying to a wide class of metric measure spaces obeying a certain “microdoubling condition at dimension “; and conversely, in such level of generality, it is essentially the best estimate possible, even with additional metric measure hypotheses on the space. Thus, if one wants to improve this bound for a specific maximal inequality, one has to use specific properties of the geometry (such as the connections between Euclidean balls and heat kernels). Furthermore, in the general setting of metric measure spaces, one has a general localisation principle, which roughly speaking asserts that in order to prove a maximal inequality over all scales , it suffices to prove such an inequality in a smaller range uniformly in . It is this localisation which ultimately explains the significance of the growth in the Stein-Strömberg result (there are essentially distinct scales in any range ). It also shows that if one restricts the radii to a lacunary range (such as powers of ), the best constant improvees to ; if one restricts the radii to an even sparser range such as powers of , the best constant becomes .