A D V E R T |
I S E M E N T |
| Math Sites: lean ages 13-∞ readme referees parents | >>> MAITH GAMES <<< | all 372 compute stand |
|
LEVEL 1 OF 1 · A negative answer to the Lang–Plaut problem
A doubling Hilbert subset with no finite-dimensional bi-Lipschitz embedding
expertly designed by an internal OpenAI model · released 2026-09-25
· original PDF
IntroductionA 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\mathbb R^k\) is a bi-Lipschitz embedding with distortion at most \(D\) if there is a scale \(a>0\) such that \[a\,d(x,y)\le\left\lVert f(x)-f(y)\right\rVert\le Da\,d(x,y) \qquad(x,y\in X).\] 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 [LP], restated in [NN]. Gupta, Krauthgamer, and Lee independently formulated the question in the context of algorithmic dimension reduction [GKL]. 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\) [NN]. 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 [GK]. 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 [LN]. Independently, Bartal, Gottlieb, and Neiman obtained dimension-reduction obstructions for doubling subsets of \(\ell_p\) using thin Laakso configurations [BGN]. Baudier, Święcicki, and Swift later gave an elementary proof of the corresponding fixed-set theorem for \(\ell_q\), \(q>2\) [BSS]. These results concern ambient exponents strictly greater than two and do not settle the Hilbert case. Schioppa announced a negative answer in [Schioppa], 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 \(\mathbb 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];\mathbb 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. The construction and proof strategyThe 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 [Cheeger]. Laakso’s nonembedding argument gives a related separation-versus-stretch principle: separated branches force an increase in stretch along a subsegment [Laakso]. Here the analytic step uses ordinary Euclidean differentiation of Lipschitz maps on open subsets of \(\mathbb 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\mathbb 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 \(\mathbb 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 \[\left\lVert F_i(p)-F(p)\right\rVert\le Dr\] 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 \(\mathbb 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 \(\mathbb 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\). ConventionsWrite \(\mathbb 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 \(\mathbb 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 \[\langle h\rangle_E=\frac{1}{|E|}\int_E h.\] The notation \(\langle h\rangle\) omits \(E\) when the averaging domain has been specified. The subset and its doubling boundWe 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 \(\mathbb 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 \[\mathcal H=\mathbb R^2\oplus\bigoplus_{j\ge1}\mathbb R^{N_j}\] 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 \(j\)th summand. At level \(j\), color the horizontal strips \[\{(x,y):qr_j<y<(q+1)r_j\},\qquad q\in\mathbb Z,\] by the residue \(i\in\{1,\ldots,N_j\}\) determined by \(q\equiv i-1\pmod{N_j}\). Give the vertical strips \[\{(x,y):qW_jr_j<x<(q+1)W_jr_j\}\] the same periodic coloring. Denote their unions of color \(i\) by \(H_{j,i}\) and \(V_{j,i}\), respectively, and put \[U_{j,i}=H_{j,i}\cup V_{j,i}.\] In particular, \(U_{j,i}\) is open. Define \(S\subset\mathcal H\) to consist of the points \[ (p,w),\qquad p\in\mathbb R^2,\quad w=(w_j)_{j\ge1}, \tag{1}\] where \(w\) has finite support and, independently at each level, \[w_j=0\quad\text{or}\quad w_j=r_je_{j,i}\text{ for some }i\text{ with }p\in U_{j,i}.\] 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 \[ \sum_{r_j\le t/64}\left\lVert w_j-w'_j\right\rVert^2 \le 2\sum_{r_j\le t/64}r_j^2 \le\frac{2}{1-10^{-6}}\left(\frac{t}{64}\right)^2 <\left(\frac{t}{32}\right)^2. \tag{2}\] 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 \[t\sqrt{\frac{2}{64}+\frac{1}{1024}}=\frac{\sqrt{33}}{32}t<\frac t2.\] Choosing one point from each nonempty group as a center gives the required cover by balls in \(S\). ◻ Sheets and extremal derivativesWe 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 \(\mathbb R^0\). Suppose, for a contradiction, that for some finite \(k\ge1\) and \(D\ge1\) there is a map \(f:S\to\mathbb R^k\) satisfying \[ \left\lVert z-z'\right\rVert\le\left\lVert f(z)-f(z')\right\rVert\le D\left\lVert z-z'\right\rVert \qquad(z,z'\in S). \tag{3}\] For a fixed finite-support tuple \(w\) of coordinate choices, let \[\Omega_w=\{p:(p,w)\in S\}.\] If \(w_j=r_je_{j,i_j}\) at its nonzero levels, then \[\Omega_w=\bigcap_{j:w_j\ne0}U_{j,i_j}.\] This is a finite intersection of open sets; the empty intersection for the zero tuple is \(\mathbb R^2\). Whenever the domain is nonempty, the map \[F_w:\Omega_w\to\mathbb R^k,\qquad F_w(p)=f(p,w),\] 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 [Heinonen]. Its derivative columns have norm at most \(D\). By Lebesgue differentiation, almost every point \(p\) is also a Lebesgue point of these columns; see [Tao]. At such a point, with \(u=F_x(p)\) and \(v=F_y(p)\), the mean-square error satisfies \[ \lim_{l\downarrow0}\left\langle\left\lVert F_x-u\right\rVert^2+\left\lVert F_y-v\right\rVert^2\right\rangle_{Q(p,l)}=0, \tag{4}\] 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 \[(\left\lVert F_x(p)\right\rVert^2,\left\lVert F_y(p)\right\rVert^2)\] from all sheets and their good points. It is nonempty and compact. Define \[ A=\max\{s:(s,t)\in K\},\qquad B=\max\{t:(A,t)\in K\}. \tag{5}\] 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 \[(s,t)\in K,\quad s>A-\delta\quad\Longrightarrow\quad t\le B+\varepsilon.\] 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 \[\mathbb P\{A-s_n\ge\delta\}\le\frac{\mathbb E(A-s_n)}{\delta}, \qquad \mathbb E t_n\le B+\varepsilon+ D^2\frac{\mathbb E(A-s_n)}{\delta}.\] 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 \[ \left\langle\left\lVert G-a\right\rVert^2\right\rangle =\left\langle\left\lVert G\right\rVert^2\right\rangle-\left\lVert a\right\rVert^2 -2\langle a,\langle G\rangle-a\rangle. \tag{6}\] 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 [Heinonen]. 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. Near-extremal rectangles and two energy estimatesThe 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 \[ N>(1+2D)^k. \tag{7}\] For each positive integer \(n\), choose a sheet \(F\) and a good point with derivative columns \(u,v\) such that \[ 0\le A-\left\lVert u\right\rVert^2<n^{-4},\qquad |B-\left\lVert v\right\rVert^2|<n^{-4}. \tag{8}\] 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 \[ \left\langle\left\lVert F_x-u\right\rVert^2+\left\lVert F_y-v\right\rVert^2\right\rangle_{Q^0}<n^{-8}. \tag{9}\] The sheet, the vectors, and \(l\) may all depend on \(n\). Choose a level \(j\) beyond the finite support of this sheet such that \[ (N_j,W_j)=(N,n),\qquad Nnr_j<\frac{l n^{-8}}{100}. \tag{10}\] 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, \[\begin{align*} \left\langle\left\lVert F_x-u\right\rVert^2+\left\lVert F_y-v\right\rVert^2\right\rangle_Q&<4n^{-8},\tag{11}\\ \frac r{L_x},\frac r{L_y}&<\frac{n^{-9}}{50N}. \tag{12}\end{align*}\] 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), \[ \left\lVert F_i-F\right\rVert\le Dr \quad\text{on }Q\cap(H_{j,i}\cup V_{j,i}). \tag{13}\] 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\), \[ \left\lVert G_H^x\right\rVert^2\le A,\qquad (\left\lVert G_V^x\right\rVert^2,\left\lVert G_V^y\right\rVert^2)\in K. \tag{14}\] 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\mathbb 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\), \[\begin{align*} n^2\left\langle\left\lVert G_H^x-F_x\right\rVert^2\right\rangle_Q&\longrightarrow0,\tag{15}\\ \left\langle\left\lVert G_V^y-F_y\right\rVert^2\right\rangle_Q&\longrightarrow0. \tag{16}\end{align*}\] 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 \[ \left\lVert\langle G_H^x\rangle-u\right\rVert \le\frac{2Dr}{L_x}+2n^{-4}. \tag{17}\] Equations (6), (8), and (14) therefore imply \[\begin{align*} \left\langle\left\lVert G_H^x-u\right\rVert^2\right\rangle &\le A-\left\lVert u\right\rVert^2+2\left\lVert u\right\rVert\left\lVert\langle G_H^x\rangle-u\right\rVert\\ &\le(1+4D)n^{-4}+4D^2r/L_x. \end{align*}\] Using (11) and (12) gives the explicit estimate \[ n^2\left\langle\left\lVert G_H^x-F_x\right\rVert^2\right\rangle \le 2(1+4D)n^{-2}+\frac{4D^2}{25N}n^{-7}+8n^{-6}, \tag{18}\] 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 \[ \left\lVert\langle G_V^x\rangle-u\right\rVert\le\frac{2D}{n}+2n^{-4}. \tag{19}\] The estimate sums the separate strip integrals and therefore allows jumps in the selection at strip boundaries. Put \(\eta_n=\langle A-\left\lVert G_V^x\right\rVert^2\rangle\). By (14), it is nonnegative. The identity (6), with its nonnegative left side discarded, gives \[\begin{align*} 0\le\eta_n &\le A-\left\lVert u\right\rVert^2+2\left\lVert u\right\rVert\left\lVert\langle G_V^x\rangle-u\right\rVert\\ &\le (1+4D)n^{-4}+\frac{4D^2}{n}\longrightarrow0. \tag{20}\end{align*}\] Apply Lemma 3 to the pairs in (14), with normalized area measure on \(Q\). We obtain \[ \limsup_{n\to\infty}\left\langle\left\lVert G_V^y\right\rVert^2\right\rangle\le B. \tag{21}\] Vertical selection: the second derivative column.Each interior vertical strip spans the full height of \(Q\). Integration in \(y\), followed by (11), gives \[ \left\lVert\langle G_V^y\rangle-v\right\rVert\le\frac{2Dr}{L_y}+2n^{-4}\longrightarrow0. \tag{22}\] Since \(\left\lVert v\right\rVert\le D\) and \(\left\lVert v\right\rVert^2\to B\), Equations (6), (21), and (22) imply \[0\le\left\langle\left\lVert G_V^y-v\right\rVert^2\right\rangle \le\left\langle\left\lVert G_V^y\right\rVert^2\right\rangle-\left\lVert v\right\rVert^2 +2D\left\lVert\langle G_V^y\rangle-v\right\rVert.\] 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). ◻ Crossings force a packing contradictionWe 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 \[n^2\left\lVert G_H^x-F_x\right\rVert^2+\left\lVert G_V^y-F_y\right\rVert^2\] 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 \[ \frac{1}{Nnr}\int_{\text{row segment}} n^2\left\lVert(F_i-F)_x\right\rVert^2\,dx\le2N\varepsilon_n. \tag{23}\] Similarly choose \(x=x_i\) in the interior of column \(i\) with \[ \frac{1}{Nr}\int_{\text{column segment}} \left\lVert(F_i-F)_y\right\rVert^2\,dy\le2N\varepsilon_n. \tag{24}\] 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, \[\mathop{\mathrm{diam}}h_i(\text{segment}) \le\frac{Nnr}{r}\left(\frac{1}{Nnr}\int\left\lVert(F_i-F)_x\right\rVert^2\,dx\right)^{1/2} \le N\sqrt{2N\varepsilon_n}.\] The identical bound on each chosen vertical segment follows from (24), with length \(Nr\). Set \[ \omega_n=N\sqrt{2N\varepsilon_n}\longrightarrow0, \qquad z_i=h_i(x_i,y_i). \tag{25}\] By (13), \(\left\lVert z_i\right\rVert\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. 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 \[\left\lVert h_i(x_m,y_i)-h_m(x_m,y_i)\right\rVert\ge\sqrt2.\] Transporting along row \(i\) and column \(m\), as in Figure 1, yields \[\left\lVert z_i-z_m\right\rVert\ge\sqrt2-2\omega_n>1\] 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 \(\mathbb 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 \[N(1/2)^k\le(D+1/2)^k,\qquad N\le(1+2D)^k,\] contrary to (7). No map satisfying (3) exists. Together with Proposition 2, this proves Theorem 1. ◻ A consequence for finite-\(p\) function spacesA 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];\mathbb 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 \[\left\lVert\sum_i a_i g_i\right\rVert_{L_p}=c_p\left(\sum_i a_i^2\right)^{1/2}.\] 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 \[J_p x=c_p^{-1}\lim_{m\to\infty}\sum_{i=1}^m x_i g_i \quad\text{in }L_p([0,1];\mathbb R).\] Passing to limits proves that \(J_p\) is linear and that \(\left\lVert J_p x-J_p y\right\rVert_{L_p}=\left\lVert x-y\right\rVert_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\mathbb 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\) [LN]. 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 [OpenAI2026LpReduction], unlike the fixed infinite-set obstruction of Corollary 5. Compact obstructions in infinite-dimensional Banach spacesFinite 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\mathbb N\) and every finite \(A\ge1\), there is a finite subset of \(S\) admitting no embedding into \(\mathbb 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 \[Q_x=\{u\in\mathbb R^k:\left\lVert u\right\rVert\le A d_S(o,x)\}.\] The product \(\prod_{x\in S}Q_x\) is compact. In this product, each constraint \[d_S(x,y)\le\left\lVert f(x)-f(y)\right\rVert\le A d_S(x,y)\] 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\mathbb N\), a finite \(X_j\subset S\) that admits no embedding into \(\mathbb 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 [Dvoretzky], in the formulation recalled in [COO], 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 \[d_S(x,y)\le\left\lVert T_jx-T_jy\right\rVert_B\le2d_S(x,y) \qquad(x,y\in X_j).\] 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 \[\left\lVert T_jx'-T_jx_0\right\rVert_B \le2d_S(x',x_0) \le2\left(\frac R{16}+\frac R{16}\right) =\frac R4\le\frac R2.\] 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 \[C_j\subset B_B(a_jv,\eta a_j).\] This placement has distortion strictly below two as a map from \(X_j\), and \(C_j\) is still \(\lambda_0\)-doubling. Set \[K_B=\{0\}\cup\bigcup_{j\ge1}C_j.\] For \(z\in C_j\), one has \(\left\lVert z\right\rVert_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 \[\left\lVert z\right\rVert_B\le(1+\eta)a_j\le\frac{101}{400}r<\frac r2 \qquad(z\in C_j,\ a_j\le r/4).\] The center \(0\) need not belong to the ball being covered. Let \[I=\{j:C_j\cap B_{K_B}(x,r)\ne\varnothing,\ a_j>r/4\}.\] This is finite. If \(i<j\), \(p\in C_i\), and \(q\in C_j\), then \(a_j\le a_i/2\) and \[\left\lVert p-q\right\rVert_B \ge(a_i-a_j)-\eta(a_i+a_j) \ge\left(\frac12-\frac{3\eta}{2}\right)a_i =\frac{97}{200}a_i.\] 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 \[1+5\lambda_0^2\le1+6\lambda^8\] 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 \(\mathbb R^k\). Equivalence of finite-dimensional norms makes this isomorphism bi-Lipschitz, so composition gives an embedding \(f:K_B\to\mathbb 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 \(\mathbb R^k\hookrightarrow\mathbb R^j\) gives an embedding of \(X_j\) into \(\mathbb R^j\) with distortion strictly below \(2D\le j\). This contradicts the choice of \(X_j\). ◻
|
| ||||||||
|