Jump to content

Doubling space

From Wikipedia, the free encyclopedia
(Redirected from Doubling dimension)
In the Euclidean plane, seven disks of radius r/2 can cover any disk of radius r, so the plane is a doubling space with doubling constant 7 and doubling dimension log2 7.

In mathematics, a metric space X with metric d is said to be doubling if there is some doubling constant M > 0 such that for any xX and r > 0, it is possible to cover the ball B(x, r) = {y | d(x, y) < r} with the union of at most M balls of radius r/2.[1] The base-2 logarithm of M is called the doubling dimension of X.[2] Euclidean spaces equipped with the usual Euclidean metric are examples of doubling spaces where the doubling constant M depends on the dimension d. For example, in one dimension, M = 3; and in two dimensions, M = 7.[3] In general, Euclidean space has doubling dimension .[2][4]

Assouad's embedding theorem

[edit]

An important question in metric space geometry is to characterize those metric spaces that can be embedded in some Euclidean space by a bi-Lipschitz function. This means that one can essentially think of the metric space as a subset of Euclidean space. Not all metric spaces may be embedded in Euclidean space. Doubling metric spaces, on the other hand, would seem like they have more of a chance, since the doubling condition says, in a way, that the metric space is not infinite dimensional. However, this is still not the case in general. The Heisenberg group with its Carnot-Caratheodory metric is an example of a doubling metric space which cannot be embedded in any Euclidean space.[5]

Assouad's Theorem states that, for a M-doubling metric space X, if we give it the metric d(x, y)ε for some 0 < ε < 1, then there is a L-bi-Lipschitz map , where d and L depend on M and ε.

Doubling Measures

[edit]

Definition

[edit]

A nontrivial measure on a metric space X is said to be doubling if the measure of any ball is finite and approximately the measure of its double, or more precisely, if there is a constant C > 0 such that

for all x in X and r > 0. In this case, we say μ is C-doubling. In fact, it can be proved that, necessarily, C  2.[6]

A metric measure space that supports a doubling measure is necessarily a doubling metric space, where the doubling constant depends on the constant C. Conversely, every complete doubling metric space supports a doubling measure.[7][8]

Examples

[edit]

A simple example of a doubling measure is Lebesgue measure on a Euclidean space. One can, however, have doubling measures on Euclidean space that are singular with respect to Lebesgue measure. One example on the real line is the weak limit of the following sequence of measures:[9]

One can construct another singular doubling measure μ on the interval [0, 1] as follows: for each k ≥ 0, partition the unit interval [0,1] into 3k intervals of length 3k. Let Δ be the collection of all such intervals in [0,1] obtained for each k (these are the triadic intervals), and for each such interval I, let m(I) denote its "middle third" interval. Fix 0 < δ < 1 and let μ be the measure such that μ([0, 1]) = 1 and for each triadic interval I, μ(m(I)) = δμ(I). Then this gives a doubling measure on [0, 1] singular to Lebesgue measure.[10]

Applications

[edit]

The definition of a doubling measure may seem arbitrary, or purely of geometric interest. However, many results from classical harmonic analysis and computational geometry extend to the setting of metric spaces with doubling measures.

See also

[edit]

References

[edit]
  1. ^ Heinonen, Juha (2001). Lectures on Analysis on Metric Spaces. Universitext. New York: Springer-Verlag. pp. x+140. ISBN 0-387-95104-0.
  2. ^ a b Gupta, A.; Krauthgamer, R.; Lee, J.R. (2003). "Bounded geometries, fractals, and low-distortion embeddings". 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. pp. 534–543. doi:10.1109/SFCS.2003.1238226. ISBN 0-7695-2040-5. S2CID 796386.
  3. ^ W., Weisstein, Eric. "Disk Covering Problem". mathworld.wolfram.com. Retrieved 2018-03-03.{{cite web}}: CS1 maint: multiple names: authors list (link)
  4. ^ Zhou, Felix (21 Feb 2023). "Doubling Dimension and Treewidth" (PDF).
  5. ^ Pansu, Pierre (1989). "Métriques de Carnot-Carathéodory et quasiisométries des espaces symétriques de rang un". Ann. of Math. 2. 129 (1): 1–60. doi:10.2307/1971484. JSTOR 1971484.
  6. ^ Soria, Javier; Tradacete, Pedro (2019). "The least doubling constant of a metric measure space". Ann. Acad. Sci. Fenn. Math. 44 (2): 1015–1030. doi:10.5186/aasfm.2019.4457.
  7. ^ Luukainen, Jouni; Saksman, Eero (1998). "Every complete doubling metric space carries a doubling measure". Proc. Amer. Math. Soc. 126 (2): 531–534. doi:10.1090/s0002-9939-98-04201-4.
  8. ^ Jouni, Luukkainen (1998). "ASSOUAD DIMENSION: ANTIFRACTAL METRIZATION, POROUS SETS, AND HOMOGENEOUS MEASURES". Journal of the Korean Mathematical Society. 35 (1). ISSN 0304-9914.
  9. ^ Zygmund, A. (2002). Trigonometric Series. Vol. I, II. Cambridge Mathematical Library (Third ed.). Cambridge University Press. pp. xii, Vol. I: xiv+383 pp., Vol. II: viii+364. ISBN 0-521-89053-5.
  10. ^ Kahane, J.-P. (1969). "Trois notes sur les ensembles parfaits linéaires". Enseignement Math. (2). 15: 185–192.