1 Introduction
A metric space (X,d) is doubling with constant at most \lambda if every ball in X is covered by at most \lambda balls of half its radius, with centers in X. A map f:X\to\R^k is a bi-Lipschitz embedding with distortion at most D if there is a scale a>0 such that
Both the target dimension k and the distortion D are required to be finite.
Every subset of a finite-dimensional Euclidean space is doubling. Lang and Plaut asked whether every doubling subset of Hilbert space admits a bi-Lipschitz embedding into some finite-dimensional Euclidean space; see [12, Question 2.4], restated in [13, Question 1]. Gupta, Krauthgamer, and Lee independently formulated the question in the context of algorithmic dimension reduction [8, Section 6, Question 1]. The hypothesis already supplies a Hilbert-space realization, so the issue is whether a bound on metric covering complexity permits a reduction to finitely many Euclidean coordinates while preserving all distances up to a fixed factor.
Assouad’s theorem gives a positive result after changing the metric: every doubling metric space admits such an embedding for the distance d^\alpha, where 0<\alpha<1 [1]. This operation is called snowflaking. Naor and Neiman proved that, when \alpha is close to 1, the target dimension can be bounded in terms of the doubling constant alone, independently of \alpha [13, Theorem 1.2]. The distortion bound still depends on the snowflake exponent. For finite Hilbert subsets, Gottlieb and Krauthgamer obtained embeddings of snowflakes with distortion arbitrarily close to one, with dimension depending on the doubling constant, exponent, and permitted distortion [7, Theorem 1.2]. The Lang–Plaut question concerns the original distance d, even when arbitrary finite dimension and distortion are allowed.
For exponents p>2, Lafforgue and Naor constructed doubling subsets of L_p admitting no bi-Lipschitz embedding into any finite-dimensional Euclidean space [11, Theorem 1.1]. Independently, Bartal, Gottlieb, and Neiman obtained dimension-reduction obstructions for doubling subsets of \ell_p using thin Laakso configurations [2]. Baudier, Święcicki, and Swift later gave an elementary proof of the corresponding fixed-set theorem for \ell_q, q>2 [3, Theorem 1]. These results concern ambient exponents strictly greater than two and do not settle the Hilbert case. Schioppa announced a negative answer in [15], but withdrew the preprint after reporting a possible issue with its duality argument.
We give a negative answer to this question.
Theorem 1. There is a fixed subset S of real \ell_2, equipped with its induced Hilbert distance, whose doubling constant is at most 76800 and which admits no bi-Lipschitz embedding into \R^k for any positive integer k, at any finite distortion.
In particular, dimension and distortion bounds depending only on the doubling constant cannot hold for all doubling Hilbert subsets.
The same metric space has an isometric realization in L_p([0,1];\R) for every 1\le p<\infty, by a normalized Gaussian series; Section 6 gives this consequence and its relation to earlier L_p obstructions. Section 7 constructs a compact obstruction in every infinite-dimensional real Banach space, including Hilbert space, with a universal doubling constant and with no bi-Lipschitz embedding into any finite-dimensional real normed space.
1.1 The construction and proof strategy
The proof couples a covering argument with a derivative obstruction. Differentiation has a substantial history as a method for ruling out Euclidean embeddings: Cheeger’s framework gives such obstructions under doubling-measure and Poincaré-inequality hypotheses [5, Section 14, Theorem 14.3]. Laakso’s nonembedding argument gives a related separation-versus-stretch principle: separated branches force an increase in stretch along a subsegment [10, Section 4, Theorem 4.1]. Here the analytic step uses ordinary Euclidean differentiation of Lipschitz maps on open subsets of \R^2 and a quadratic variance identity. A lexicographic extremum treats the two derivative columns successively, and crossings turn their small variation into a packing obstruction. We describe the geometry first.
Sparse scales and common sheets. At each scale r_j=1000^{-j}, we color horizontal strips of width r_j and vertical strips of width W_jr_j periodically with N_j colors. Here N_j,W_j are positive integers, fixed in advance so that every pair occurs infinitely often. Choose unit vectors e_{j,i}, one for each level and color, mutually orthogonal and orthogonal to the base plane. For a base point p\in\R^2, color i permits a displacement r_je_{j,i} whenever p is in a horizontal or a vertical strip of that color. Points of S carry finitely many such displacements. Section 2 defines this set and proves the doubling bound: at any observation radius, the coarser coordinates are fixed, the finer coordinates have a small total diameter, and at most one intermediate level contributes labels to the cover.
Now suppose that an embedding f exists, normalized to have lower Lipschitz constant one and upper constant D. Fixing a finite-support tuple of displacement coordinates and varying p gives a map from an open part of the base plane to \R^k; we call this map a sheet. If F is one sheet and F_i is obtained by adding a color-i displacement at an unused level of size r, then
wherever the added displacement is permitted. The horizontal and vertical restrictions belong to the same map F_i. Our objective is to find one horizontal line and one vertical line of each color along which the relative offset (F_i-F)/r is nearly constant.
Two derivative extrema and two different error bounds. The derivative of each sheet has horizontal and vertical columns. Section 3 takes the closure of all pairs of their squared norms, chooses the largest first coordinate A, and then chooses the largest second coordinate B among pairs whose first coordinate is A. Near this extremal pair, a mean derivative close to a reference vector forces small mean-square variation. This elementary rigidity is the analytic input.
Fix the embedding parameters k,D, and then fix a color count N larger than the number of points with pairwise distances greater than one that can fit in a radius-D ball of \R^k. For each positive integer n, use a recurring level with (N_j,W_j)=(N,n) inside a sufficiently small region of a nearly extremal sheet. Writing r for its displacement scale, one period block contains one row and one column of each color and has width Nnr and height Nr. In Section 4, the first extremum gives horizontal derivative error whose mean square, multiplied by n^2, tends to zero. This factor compensates for the longer horizontal lines. The wide vertical strips first force the mean squared horizontal derivative norm of the vertically selected sheets toward A. The second extremum then gives vertical mean-square error tending to zero, with no growing factor required. Compactness suffices for this latter estimate; no quantitative modulus of the second extremum is needed.
Crossings turn small variation into a contradiction. Section 5 selects one period block and a line of every color in each direction with the required small errors. Absolute continuity turns the derivative estimates into nearly constant relative offsets on those lines. At the crossing of a color-i row and a color-m column with i\ne m, both displacements are permitted, and the corresponding source points are separated by \sqrt2\,r. Transport to the selected same-color intersections therefore produces N separated vectors in a radius-D ball of \R^k. Euclidean volume comparison contradicts the choice of N. The fixed set is used throughout; only the sheets, local rectangles, and recurring level vary with n.
1.2 Conventions
Write \N=\{1,2,\ldots\}. In the proof of Theorem 1, all norms are Euclidean or Hilbert norms. For a Lipschitz map F on an open subset of \R^2, write F_x,F_y for its derivative columns, defined almost everywhere. For an integrable function h on a set E of positive finite area, write
The notation \langle h\rangle omits E when the averaging domain has been specified.
2 The subset and its doubling bound
We first construct the set independently of any target map. The rapid separation of the displacement scales will give a uniform covering bound even though the number of colors is unbounded.
Fix, once and for all, a sequence (N_j,W_j)_{j\ge1} of pairs in \N^2 in which every pair occurs infinitely often. For example, concatenate the finite lists \{1,\ldots,m\}^2 for m=1,2,\ldots. Put r_j=1000^{-j} and let
be the Hilbert direct sum. This is isometric to real \ell_2. Let e_{j,i}, 1\le i\le N_j, denote the coordinate vectors in its jth summand.
At level j, color the horizontal strips
by the residue i\in\{1,\ldots,N_j\} determined by q\equiv i-1\pmod{N_j}. Give the vertical strips
the same periodic coloring. Denote their unions of color i by H_{j,i} and V_{j,i}, respectively, and put
In particular, U_{j,i} is open.
Define S\subset\mathcal H to consist of the points
where w has finite support and, independently at each level,
The zero choice is always allowed, including on strip boundaries. Neither S nor its defining parameters will subsequently depend on a proposed embedding.
Proposition 2. The doubling constant of S is at most 300\cdot16^2=76800.
Proof. Fix a ball of radius t>0 centered at a point of S. Distinct choices of w_j have distance at least r_j. Thus at every level with r_j>t, all points of the ball have the same coordinate as its center.
There is at most one intermediate level satisfying t/64<r_j\le t, since consecutive radii have ratio 1000. The projection of the ball onto each base coordinate lies in an interval of length 2t. Such an interval meets at most \lfloor2t/r_j\rfloor+2\le129 strips of width r_j, and the same upper bound applies to strips of width W_jr_j\ge r_j. Consequently, at the intermediate level there are fewer than 300 available labels, including zero.
For any two points of the ball, the fine-coordinate distance is bounded by
Partition a base square of side 2t containing the projection into 16^2 cells of side t/8, assigning their boundaries arbitrarily. Group the ball’s points according to their cell and their intermediate coordinate, if one exists. In a group, the coarse and intermediate coordinates agree, the base diameter is at most \sqrt2\,t/8, and (2) bounds the fine coordinates. Each group therefore has diameter less than
Choosing one point from each nonempty group as a center gives the required cover by balls in S.
3 Sheets and extremal derivatives
We now assume an embedding exists and extract one compact set of derivative data from all its sheets. Maximizing the two coordinates in order will constrain variation in the two directions separately.
Since S contains the base plane with all displacement coordinates zero, it cannot embed into \R^0. Suppose, for a contradiction, that for some finite k\ge1 and D\ge1 there is a map f:S\to\R^k satisfying
For a fixed finite-support tuple w of coordinate choices, let
If w_j=r_je_{j,i_j} at its nonzero levels, then
This is a finite intersection of open sets; the empty intersection for the zero tuple is \R^2. Whenever the domain is nonempty, the map
is called a sheet. It is D-Lipschitz, since the corresponding source points differ only in their base coordinates. This holds even when its domain is disconnected.
Rademacher’s theorem gives differentiability almost everywhere on each sheet domain [9, Theorem 3.1]. Its derivative columns have norm at most D. By Lebesgue differentiation, almost every point p is also a Lebesgue point of these columns; see [16, Theorem 32 and Exercise 33]. At such a point, with u=F_x(p) and v=F_y(p), the mean-square error satisfies
where Q(p,l) is the centered square of side l. Indeed, boundedness upgrades the Lebesgue mean-norm conclusion to mean-square convergence, and squares may replace balls by area comparison. Call these differentiability and Lebesgue points good; they form a set of full measure in each sheet domain.
Let K be the closure in [0,D^2]^2 of all pairs
from all sheets and their good points. It is nonempty and compact. Define
Thus (A,B)\in K. This single compact set and these two numbers remain fixed throughout the argument. The next lemma explains the benefit of maximizing the coordinates in this order: if the mean deficit from A tends to zero, then the mean second coordinate cannot exceed B in the limit.
Lemma 3 (Near the lexicographic maximum). Let D>0, let K\subseteq[0,D^2]^2 be nonempty and compact, and define A=\max\{s:(s,t)\in K\} and B=\max\{t:(A,t)\in K\}. For every \varepsilon>0 there is \delta>0 such that
Consequently, if measurable pairs (s_n,t_n) take values in K on probability spaces and \mathbb E(A-s_n)\to0, then \limsup_n\mathbb E t_n\le B.
Proof. Failure of the first assertion would give a sequence in K with first coordinate tending to A and second coordinate greater than B+\varepsilon. A convergent subsequence would contradict the definition of B. For the second assertion, Markov’s inequality gives
First let n\to\infty, and then \varepsilon\downarrow0.
The lemma supplies an upper bound on a mean squared norm. To turn that bound into small variation around a reference vector, we will also control the mean vector and use the elementary identity
We also use integration along line segments. A Lipschitz map on an interval is absolutely continuous, and its increments equal integrals of its derivative, componentwise [9, Theorem 3.3]. By Fubini, on almost every horizontal or vertical segment in an open sheet domain, these line derivatives agree almost everywhere with the corresponding partial derivatives. At excluded endpoints we take the unique one-sided limits of the Lipschitz restriction. Bounds for the map persist in those limits.
4 Near-extremal rectangles and two energy estimates
The output of this section is small variation of the added-sheet offsets: a horizontal estimate strong enough for increasingly long rows, and a vertical estimate for columns of fixed normalized height. The compact set K and the embedding are already fixed.
Fix an integer
For each positive integer n, choose a sheet F and a good point with derivative columns u,v such that
This is possible since (A,B)\in K is in the closure of actual good-point pairs. Choose a square Q^0 of side l, centered at that point, with closure in the sheet domain and
The sheet, the vectors, and l may all depend on n.
Choose a level j beyond the finite support of this sheet such that
Infinite recurrence of each pair permits this choice. Set r=r_j. The level-j period blocks have width Nnr and height Nr, with corners at (aNnr,bNr) for integers a,b. Take inside Q^0 a rectangle Q tiled, up to boundary lines, by complete period blocks. Each coordinate interval loses at most two periods by trimming to the grid, so its side lengths L_x,L_y satisfy L_x,L_y\ge l/2. In particular,
For each 1\le i\le N, let F_i be the sheet obtained from F by adding re_{j,i} at level j. Writing w for the tuple of F, this is a valid finite-support tuple with domain exactly \Omega_w\cap U_{j,i}. In particular, the same map F_i is defined on the portions of both H_{j,i} and V_{j,i} in Q. By (3),
Off the grid boundaries, define G_H^x by selecting (F_i)_x according to the horizontal strip color i. Define G_V^x,G_V^y by selecting (F_i)_x,(F_i)_y according to the vertical strip color. Almost everywhere on Q,
Indeed, the good points have full measure for each of the finitely many sheets in use. The map f, its target parameters k,D, the set K, and the numbers A,B,N remain fixed throughout.
Proposition 4 (Anisotropic energy estimates). For each n\in\N, let F,F_i,Q,u,v,r and the selected derivative fields be chosen as above, satisfying (8)–(12). Then, as n\to\infty,
The factor n^2 compensates for horizontal segments of length Nnr; the vertical segments have length Nr.
Proof. All averages in this proof are over Q.
Horizontal selection. On an interior horizontal strip of color i, the sheet F_i spans the full width of Q. Integrating (F_i-F)_x along a horizontal segment and using (13) gives an endpoint difference of norm at most 2Dr. Averaging in y, and applying Cauchy–Schwarz to (11), yields
Equations (6), (8), and (14) therefore imply
Using (11) and (12) gives the explicit estimate
which proves (15).
For the vertical selection, we first average the horizontal derivative over strips of width nr. Dividing the same endpoint error 2Dr by this wider strip width makes the selected horizontal mean approach u. The selected derivative has squared norm at most A almost everywhere, so its mean squared norm must then approach A. Lemma 3 will control the mean vertical squared norm without requiring a rate.
Vertical selection: the first derivative column. Integrate in x separately over the full vertical strips of width nr. Within each strip the endpoint error for F_i-F is at most 2Dr. Thus
The estimate sums the separate strip integrals and therefore allows jumps in the selection at strip boundaries.
Put \eta_n=\langle A-\norm{G_V^x}^2\rangle. By (14), it is nonnegative. The identity (6), with its nonnegative left side discarded, gives
Apply Lemma 3 to the pairs in (14), with normalized area measure on Q. We obtain
Vertical selection: the second derivative column. Each interior vertical strip spans the full height of Q. Integration in y, followed by (11), gives
Since \norm v\le D and \norm v^2\to B, Equations (6), (21), and (22) imply
The upper bound has limsup at most zero, so the nonnegative variance tends to zero. In particular, convergence of the vectors v themselves is unnecessary. Combining this with (11) proves (16).
5 Crossings force a packing contradiction
We use the two energy estimates to find one line of every color in each direction on a common period block. Their intersections will supply the separated vectors needed for the Euclidean packing bound.
Choose a complete period block P\subset Q on which the mean of the nonnegative combined energy
is no greater than its mean on Q. Denote its mean on P by \varepsilon_n. Proposition 4 gives \varepsilon_n\to0. The block has width Nnr and height Nr, and contains exactly one row and one column of each color.
For every color i, its row has area |P|/N. Fubini therefore permits a horizontal segment y=y_i in its interior, spanning P, such that
Similarly choose x=x_i in the interior of column i with
These lines can simultaneously be chosen from the full-measure sets where partial derivatives agree with line derivatives. If \varepsilon_n=0, use lines of zero energy. The choices of the horizontal and vertical coordinates are independent.
Write h_i=(F_i-F)/r on its domain in P. Absolute continuity and Cauchy–Schwarz give, on each chosen horizontal segment,
The identical bound on each chosen vertical segment follows from (24), with length Nr. Set
By (13), \norm{z_i}\le D. Oscillation on a Lipschitz line is controlled at every point by its derivative integral, so no differentiability assertion is required at the crossings.
Figure 1: A schematic period block, for i\ne m. At c, both labels are allowed: i by the row and m by the column. Their normalized offsets are separated by at least \sqrt2. Transport along the arrows changes h_i and h_m by at most \omega_n each, so z_i=h_i(p_i) and z_m=h_m(p_m) are separated by at least \sqrt2-2\omega_n. The block and strip proportions are schematic.
For i\ne m, both added labels re_{j,i} and re_{j,m} are permitted at (x_m,y_i): the first by row i, the second by column m. The corresponding source points have distance exactly \sqrt2\,r, so (3) gives
Transporting along row i and column m, as in Figure 1, yields
for all pairs when n is sufficiently large. This is simultaneous because N is fixed.
We have obtained N points in the radius-D ball of \R^k with pairwise distances greater than one. Their open radius-1/2 balls are disjoint and contained in the radius-(D+1/2) ball. Comparing Euclidean volumes gives
contrary to (7). No map satisfying (3) exists. Together with Proposition 2, this proves Theorem 1.
6 A consequence for finite-p function spaces
A normalized Gaussian series gives isometric realizations of the same fixed metric space in real L_p[0,1] for every finite p\ge1.
Corollary 5 (Finite-p function-space obstruction). For every real 1\le p<\infty, the fixed metric space S of Theorem 1 is isometric to a subset S_p of L_p([0,1];\R), where [0,1] carries Lebesgue measure. With its induced L_p metric, S_p has doubling constant at most 76800 and admits no bi-Lipschitz embedding into any finite-dimensional real normed space at any finite distortion.
Proof. Fix p and choose independent standard real Gaussian random variables (g_i)_{i\ge1} on Lebesgue [0,1]. Put c_p=(\mathbb E|g_1|^p)^{1/p}\in(0,\infty). For every finitely supported real sequence a, the sum \sum_i a_i g_i is centered Gaussian with variance \sum_i a_i^2, and hence
For x\in\ell_2, the same identity for tails makes the partial sums Cauchy in L_p. Completeness, including at p=1, therefore defines
Passing to limits proves that J_p is linear and that \norm{J_p x-J_p y}_{L_p}=\norm{x-y}_2. Thus S_p=J_p(S) is isometric to S, so its doubling constant is unchanged.
A zero-dimensional target cannot contain an injective copy of S_p. If f:S_p\to Y were a bi-Lipschitz embedding into a real normed space of finite positive dimension k, choose a linear isomorphism T:Y\to\R^k. Equivalence of finite-dimensional norms makes T bi-Lipschitz with finite distortion. The composition T\circ f\circ J_p|_S would then contradict Theorem 1.
Lafforgue and Naor proved the qualitative fixed-set obstruction with Euclidean targets for p>2 and, in the paragraph following their Theorem 1.1, recorded the corresponding question for 1<p\le2 as open at that time, while noting stronger known results for p=1 [11, Theorem 1.1 and the following paragraph]. Theorem 1 treats p=2, and Corollary 5 answers that qualitative fixed-set question with finite-dimensional Euclidean targets when 1<p<2. This transfer adds no new metric construction. Corollary 5 concerns function-space sources L_p[0,1], not coordinate \ell_p sources; the compact result below is a separate transfer to arbitrary infinite-dimensional Banach sources.
Finite-set dimension reduction in L_p, for 1<p<\infty and p\ne2, allows the target dimension to depend on cardinality [14, Theorem 1.1], unlike the fixed infinite-set obstruction of Corollary 5.
7 Compact obstructions in infinite-dimensional Banach spaces
Finite witnesses to Theorem 1 can be placed in any infinite-dimensional real Banach space by the classical Dvoretzky theorem. A geometrically shrinking union of these finite clusters, with its limit point adjoined, is compact and retains a uniform doubling bound.
Corollary 6 (Compact Banach-space obstruction). There is a universal constant \Lambda such that every infinite-dimensional real Banach space B contains a compact subset K_B whose doubling constant is at most \Lambda and which admits no bi-Lipschitz embedding into any finite-dimensional real normed space at any finite distortion. The subset K_B may depend on B, but is chosen independently of the target dimension and distortion.
Proof. Write d_S for the induced Hilbert distance on S and put \lambda=76800. We use closed balls below; the same estimates work for open balls.
Finite witnesses. For every k\in\N and every finite A\ge1, there is a finite subset of S admitting no embedding into \R^k with distortion at most A. Indeed, suppose every finite subset admitted such an embedding, and fix o\in S. For each x\in S, let
The product \prod_{x\in S}Q_x is compact. In this product, each constraint
defines a closed set. These closed sets have the finite-intersection property: finitely many constraints involve finitely many points, and an embedding of those points together with o, translated to send o to zero and divided by its lower scale, satisfies the constraints and lies in the corresponding Q_x. Set all other coordinates to zero. Product compactness then supplies a map satisfying every constraint, contrary to Theorem 1.
Choose, for each j\in\N, a finite X_j\subset S that admits no embedding into \R^j with distortion at most j. Each X_j has at least two points. These choices are made before any target for K_B is considered.
Placement and cluster doubling. Fix an infinite-dimensional real Banach space B. The classical finite-dimensional Dvoretzky theorem [6, Section 7], in the formulation recalled in [4, Theorem 1.1], gives a linear embedding T_j of the finite Hilbert span of X_j into B with distortion strictly below two; the one-dimensional case is immediate. After rescaling T_j, we may use
Only this qualitative finite-dimensional form of Dvoretzky is used.
Each Y_j=T_j(X_j) has doubling constant at most \lambda_0=\lambda^4, uniformly in j and B. To see this, the preimage E of a ball in Y_j of radius R centered at T_jx lies in the S-ball of radius R centered at x. Four halvings cover that S-ball by at most \lambda^4 S-balls of radius R/16. For each one meeting E, choose x_0\in E in it. Every other x'\in E in the same ball satisfies
Thus the chosen points T_jx_0 give the required cover with centers in Y_j.
Compact assembly and its covering bound. Fix a unit vector v\in B, and put a_j=2^{-j} and \eta=1/100. Since Y_j is finite, a translation and positive rescaling place it as a cluster
This placement has distortion strictly below two as a map from X_j, and C_j is still \lambda_0-doubling. Set
For z\in C_j, one has \norm z_B\le(1+\eta)a_j. Every sequence in K_B therefore has either a constant subsequence among 0 and finitely many clusters, or a subsequence whose cluster indices tend to infinity and which converges to 0. Hence K_B is compact.
Fix x\in K_B and r>0. Every cluster with a_j\le r/4, together with 0, is covered by the single K_B-ball B_{K_B}(0,r/2), since
The center 0 need not belong to the ball being covered. Let
This is finite. If i<j, p\in C_i, and q\in C_j, then a_j\le a_i/2 and
If |I|\ge2, take its least index i and any other j\in I. Points from the two intersections with B_{K_B}(x,r) are at distance at most 2r, so a_i\le400r/97. All scales indexed by I then lie in (r/4,(400/97)r]. Their largest-to-smallest ratio is strictly less than 1600/97<32, so there are at most five such dyadic scales. If |I|=1, its one scale can be arbitrarily large, but no bound on that scale is needed.
For each j\in I, choose y_j\in C_j\cap B_{K_B}(x,r). The intersection is contained in the intrinsic C_j-ball B_{C_j}(y_j,2r), which two applications of cluster doubling cover by at most \lambda_0^2 C_j-balls of radius r/2. The K_B-balls with these same centers and radii also cover the intersection. There are at most five clusters to cover, including the single-cluster case, so the tail ball and these covers use at most
balls, all centered in K_B. This proves a universal doubling bound; one may take \Lambda=1+6\lambda^8.
Obstruction for every finite-dimensional target. Suppose K_B admitted a finite-distortion bi-Lipschitz embedding into a finite-dimensional real normed space. The zero-dimensional case is impossible because K_B has more than one point. Otherwise, choose a linear isomorphism from the target onto \R^k. Equivalence of finite-dimensional norms makes this isomorphism bi-Lipschitz, so composition gives an embedding f:K_B\to\R^k with some finite distortion D. Choose an integer j\ge k with j\ge2D. Composing the distortion-below-two placement of X_j onto C_j, the restriction of f, and the isometric inclusion \R^k\hookrightarrow\R^j gives an embedding of X_j into \R^j with distortion strictly below 2D\le j. This contradicts the choice of X_j.
References
- [1]P. Assouad, Plongements lipschitziens dans \R^n, Bulletin de la Société Mathématique de France 111 (1983), 429–448. doi:10.24033/bsmf.1997.
- [2]Y. Bartal, L.-A. Gottlieb, and O. Neiman, On the impossibility of dimension reduction for doubling subsets of \ell_p, SIAM Journal on Discrete Mathematics 29 (2015), 1207–1222. doi:10.1137/140977655.
- [3]F. P. Baudier, K. Święcicki, and A. Swift, No dimension reduction for doubling subsets of \ell_q when q>2 revisited, Journal of Mathematical Analysis and Applications 504 (2021), no. 2, 125407. doi:10.1016/j.jmaa.2021.125407.
- [4]F. Catrina, S. Ostrovska, and M. I. Ostrovskii, Dvoretzky-type theorem for locally finite subsets of a Hilbert space, Annales de l’Institut Fourier 75 (2025), no. 6, 2565–2607. doi:10.5802/aif.3672.
- [5]J. Cheeger, Differentiability of Lipschitz functions on metric measure spaces, Geometric and Functional Analysis 9 (1999), no. 3, 428–517. doi:10.1007/s000390050094.
- [6]A. Dvoretzky, Some results on convex bodies and Banach spaces, in Proceedings of the International Symposium on Linear Spaces (Jerusalem, 1960), Jerusalem Academic Press, Jerusalem; Pergamon Press, Oxford, 1961, 123–160.
- [7]L.-A. Gottlieb and R. Krauthgamer, A nonlinear approach to dimension reduction, Discrete & Computational Geometry 54 (2015), no. 2, 291–315. doi:10.1007/s00454-015-9707-9.
- [8]A. Gupta, R. Krauthgamer, and J. R. Lee, Bounded geometries, fractals, and low-distortion embeddings, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (2003), 534–543. doi:10.1109/SFCS.2003.1238226.
- [9]J. Heinonen, Lectures on Lipschitz Analysis, Report 100, Department of Mathematics and Statistics, University of Jyväskylä, 2005.
- [10]T. J. Laakso, Ahlfors Q-regular spaces with arbitrary Q>1 admitting weak Poincaré inequality, Geometric and Functional Analysis 10 (2000), no. 1, 111–123. doi:10.1007/s000390050003. Erratum: ibid. 12 (2002), no. 3, 650.
- [11]V. Lafforgue and A. Naor, A doubling subset of L_p for p>2 that is inherently infinite dimensional, Geometriae Dedicata 172 (2014), 387–398. doi:10.1007/s10711-013-9924-4.
- [12]U. Lang and C. Plaut, Bilipschitz embeddings of metric spaces into space forms, Geometriae Dedicata 87 (2001), 285–307. doi:10.1023/A:1012093209450.
- [13]A. Naor and O. Neiman, Assouad’s theorem with dimension independent of the snowflaking, Revista Matemática Iberoamericana 28 (2012), no. 4, 1123–1142. doi:10.4171/RMI/706.
- [14]OpenAI, Subpolynomial dimension reduction in L_p, OpenAI Math Release preprint PDF, 2026. Reading view on this site: Subpolynomial dimension reduction in Lp.
- [15]A. Schioppa, An example of a doubling “inherently” infinite-dimensional subset of l_2, withdrawn preprint, 2017; withdrawal posted April 22, 2017. arXiv:1703.10265.
- [16]T. Tao, 245A, Notes 5: Differentiation theorems, 16 October 2010, https://terrytao.wordpress.com/2010/10/16/245a-notes-5-differentiation-theorems/.