Earlier results and the exact-distortion contrast

Ball proved the exact-coordinate upper bound \(\binom n2\) and its quadratic-order sharpness for \(1\le p<2\) [1]. Lemma 2 recalls the distance-cone and Carathéodory argument for that upper bound. The lower bound in (3) uses an antipodal row-and-column configuration. Its disjoint-support test is the classical equality criterion for the \(p\)-parallelogram defect [12]; in particular, the argument includes even integers \(p>2\).

Approximate finite-set bounds and linear-subspace discretization have different dimension parameters. Below \(2\), Schechtman’s finite-set estimates progressed from \(O_D(n\log n)\) coordinates to \(O_{p,D}(n)\) [22, 23]. The subspace results of Bourgain–Lindenstrauss–Milman and Talagrand instead preserve all vectors in a given \(r\)-dimensional subspace by a linear map [3, 25]. Applying such a theorem to the span of the translated data gives \(r\le n-1\); it does not give the present subpolynomial bound in cardinality. Bourgain’s embedding of arbitrary finite metrics into Hilbert space allows distortion growing with \(n\) [2], another different guarantee.

The absence of a linearity requirement is essential: fixed-distortion linear maps on selected \(L_p\) configurations can require dimension proportional to their cardinality when \(p\ne2\) [13]. At the endpoint \(p=1\), the obstruction of Brinkman–Charikar applies even to nonlinear maps; see also Lee–Naor’s proof [4, 14]. For \(p>2\), Naor–Ren’s recent lower bound [16] rules out \(O_{p,D}(\log n)\) coordinate dimension: along arbitrarily large cardinalities it requires dimension of order at least \((\log n/(\log\log n)^2)^{p/2}\) at fixed distortion. This is compatible with (2); neither its upper exponent nor its elementary logarithmic lower bound is asserted to be optimal.

The dependence on cardinality also distinguishes this problem from embedding one infinite space into a fixed finite-dimensional target. A metric space is doubling if every ball can be covered by a fixed number of balls of half its radius. A separate construction gives an infinite doubling subset of real Hilbert space with no bi-Lipschitz embedding into any finite-dimensional Euclidean space at any finite distortion [17]. This is compatible with finite-set dimension reduction and is not an input to our proof.

Method and organization

Our starting point is a bounded distribution of scalar images of the input points. After dividing each increment by the corresponding original distance, we seek nearly equal \(p\)th moments for every pair. Lemma 3 reduces this simultaneous requirement to a weighted-average condition for each strictly positive probability on the pairs. Crucially, the common moment \(b\) and magnitude bound \(K\) are uniform over those probabilities. Convex separation produces one distribution working for all pairs; independent sampling then supplies the coordinates of a finite embedding. This sampling step belongs to Maurey’s empirical method, as presented by Pisier [19]. A close distance-matrix antecedent is Eskenazis’s use of that method for incompressible sets [6]; that theorem controls additive errors, with a bound depending on the incompressibility of the data. Here the weighted-moment construction supplies the uniform relative control needed for arbitrary configurations.

The geometric input in Section 4 is a projection onto normalized increments that come from scalar labels on the points. It is an \(L_2\) contraction for a suitable choice of pair weights, and its \(L_\infty\) norm is \(O(\log n)\). We obtain the latter property by a fixed-point reweighting of the electrical-flow localization estimate of Gurel-Gurevich, Nachmias, and Sachdeva [7]. Their estimate improves the earlier \(O(\log^2 n)\) localization bound of Schild–Rao–Srivastava [24]. Appendix 9 presents the heat-kernel and entropy proof from [7] in our notation.

After the common homogeneous-increment and signed-Poisson setup, the two ranges require different random increments. Section 6 constructs symmetric \(p\)-stable marginals, clips them, and projects back to consistent increments. Stable projections and truncated heavy-tail moments have earlier geometric uses, including Indyk’s work [10]; the required marginal construction and tail bounds are proved here. For \(p>2\), Section 7 uses overlapping magnitude truncations followed by signed Poisson sampling. Their overlap enlarges the input energy relative to the projection error. The moment comparison is of Rosenthal type [21, 18]; Appendix 10 proves the specific leading coefficient \(1+\epsilon\) needed for distortion arbitrarily close to one. The final main-text section inserts the resulting \(b,K\) into the sampling estimate and proves the packing and exact embedding lower bounds.

We use finite-dimensional convexity, Brouwer’s fixed-point theorem, and standard probability; the specialized electrical-localization and Poisson-moment arguments are supplied in the appendices.

Throughout, logarithms are natural. Constants \(C,c>0\) are absolute; subscripts indicate the parameters on which a constant may depend. Their values may change from line to line.

A common heavy-tailed marginal

We first construct a random vector \(Y\in V\) by symmetric Poisson sampling of the vector \(v\) against the intensity \(\nu\). On the region \(\{\|v\|_\infty>1\}\), this is an ordinary signed compound Poisson sum: the region has measure at most \(|E|\) by (11). For each \(j\ge0\), independently sample the region \[A_j=\{2^{-j-1}<\|v\|_\infty\le2^{-j}\},\] and denote its signed compound Poisson sum by \(Y^{(j)}\). Each \(A_j\) has finite measure, at most \(|E|2^{p(j+1)}\). These are centered independent vectors. For every edge \(e\), \[\sum_{j\ge0}\mathbb E|Y^{(j)}_e|^2 =\int_{0<\|v\|_\infty\le1}|v_e|^2\,d\nu \le\int_{0<|v_e|\le1}|v_e|^2\,d\nu =\frac{p}{2-p}.\] Consequently \(\sum_{j\ge0}Y^{(j)}\) converges in \(L_2\) with values in the finite dimensional space \(\mathbb R^E\). Adding the sum on \(\{\|v\|_\infty>1\}\) defines \(Y\). Every partial sum belongs to \(V\); since \(V\) is closed, \(Y\in V\) almost surely.

The compound Poisson formula and convergence in probability give \[ \mathbb Ee^{i\theta Y_e} =\exp\left(\int\bigl(\cos(\theta v_e)-1\bigr)\,d\nu\right) =\exp\left(p\int_0^\infty \bigl(\cos(\theta u)-1\bigr)u^{-p-1}\,du\right). \tag{16}\] The integrals converge absolutely: near zero the integrand is \(O_\theta(u^{1-p})\), and at infinity it is \(O(u^{-p-1})\). The second equality follows from (12) and the evenness of cosine. In particular, uniqueness of characteristic functions [5] shows that all the \(Y_e\) have the same distribution, depending only on \(p\).

For later use we prove directly that \[ c_p a^{-p}\le\mathbb P(|Y_e|>a)\le C_p a^{-p} \qquad(a\ge1). \tag{17}\] Fix \(e\) and \(a\ge1\). By Poisson splitting, or by the characteristic function (16), \(Y_e\) has the distribution of an independent sum \(B_a+S_a\). Here \(B_a\) is the signed compound Poisson sum on \(\{|v_e|>a\}\), whose number \(N_a\) of jumps is Poisson with mean \(a^{-p}\), while \(S_a\) is the \(L_2\) limit of the small-jump sums on \(\{0<|v_e|\le a\}\). Thus \[\mathbb ES_a=0, \qquad \mathbb E|S_a|^2=\int_{0<|v_e|\le a}|v_e|^2\,d\nu =\frac{p}{2-p}a^{2-p}.\] Chebyshev’s inequality gives \[\mathbb P(|Y_e|>a) \le\mathbb P(N_a\ge1)+\mathbb P(|S_a|>a) \le\left(1+\frac{p}{2-p}\right)a^{-p}.\] For the reverse inequality, condition on \(N_a=1\), the magnitude \(u>a\) of its jump, and \(S_a=s\). At least one of \(|s+u|\) and \(|s-u|\) exceeds \(a\), and the jump’s two signs are equally likely. Therefore \[\mathbb P(|Y_e|>a) \ge\frac12\mathbb P(N_a=1) =\frac12 a^{-p}e^{-a^{-p}} \ge\frac{1}{2e}a^{-p}.\] This proves (17).

Clipping and projection

Let \(\lambda\) be a strictly positive probability on \(E\), and choose \(\sigma\) and \(P\) from Lemma 5. Thus \(\sigma\ge\lambda/2\), and \(P\) has absolute row sums at most \(H\). For \(T>1\), let \([Y]_T\) denote coordinatewise clipping to \([-T,T]\), and set \[F=P[Y]_T.\] Then \(F\in V\) and \(\|F\|_\infty\le HT\) almost surely. Since \(Y=PY\) and \(p>1\), integration of (17) yields \[\begin{align*} \mathbb E|Y_e-F_e| &\le\sum_{f\in E}|P_{ef}|\, \mathbb E\bigl(|Y_f|-T\bigr)_+ \\ &\le C_p H T^{1-p}. \tag{18}\end{align*}\] Orthogonal contraction, together with the same tail bound, gives \[\begin{align*} \sum_e\sigma_e\mathbb E|F_e|^2 &\le\sum_e\sigma_e\mathbb E\min\{|Y_e|,T\}^2 \\ &\le C_p T^{2-p}. \tag{19}\end{align*}\]

We compare moments below a second level \(a\). The Lipschitz comparison will cost \(H(a/T)^{p-1}\), while the quadratic estimate for the remaining tail will cost \((T/a)^{2-p}\). Balancing these gives \(a=T/H\). Suppose \(a\ge2\), and define the common capped moment \[b=\mathbb E\min\{|Y_e|,a\}^p.\] The common marginal law makes \(b\) independent of \(e\) and \(\lambda\). Moreover, the layer-cake formula and (17) imply \[ b=p\int_0^a t^{p-1}\mathbb P(|Y_e|>t)\,dt \ge c_p\log a. \tag{20}\] The function \(h_a(t)=\min\{|t|,a\}^p\) is \(pa^{p-1}\)-Lipschitz. Hence (18) implies, for every \(e\), \[\bigl|\mathbb Eh_a(F_e)-b\bigr| \le C_p a^{p-1}HT^{1-p} =C_p H^{2-p}.\] The part above this cap is controlled in weighted average. Since \(p<2\), for every real \(t\) we have \[0\le |t|^p-h_a(t)\le a^{p-2}|t|^2.\] Using (19), we obtain \[\sum_e\sigma_e\mathbb E\bigl(|F_e|^p-h_a(F_e)\bigr) \le C_p a^{p-2}T^{2-p} =C_p H^{2-p}.\] Combining the two estimates proves \[ \sum_e\sigma_e\bigl|\mathbb E|F_e|^p-b\bigr| \le C_p H^{2-p}. \tag{21}\]

Choose \[T=\exp\bigl(A_{p,\eta}H^{2-p}\bigr), \qquad K=HT,\] where \(A_{p,\eta}\) is sufficiently large. Since \(\log H=o(H^{2-p})\), for all sufficiently large \(n\) we have \(a\ge2\) and \[b\ge c_p\log(T/H) \ge\frac{c_pA_{p,\eta}}2 H^{2-p}\ge1.\] By (21) and \(\lambda\le2\sigma\), increasing \(A_{p,\eta}\) if necessary ensures \[\sum_e\lambda_e\bigl|\mathbb E|F_e|^p-b\bigr|\le\eta b.\] Both \(b\) and \(K\) are independent of the test probability \(\lambda\). Finally, \[\log K=\log H+A_{p,\eta}H^{2-p} =O_{p,\eta}\bigl((\log n)^{2-p}\bigr).\] These are the parameters required by Lemma 3 in this range.

A ramp of truncations

The overlapping truncations below create a triangular multiplicity profile of height \(\ell\). We will show that its \(p\)-energy is of order \(\ell^{p+1}\), whereas the \(p\)th power of the projection error is at most \(C_pH^{p-2}\ell\). This gain determines the choice of \(\ell\).

For \(a>0\), let \(v_{\le a}\) denote the vector obtained by replacing \(v_e\) by \(v_e\mathbf 1_{\{|v_e|\le a\}}\) at each edge; put \(v_{>a}=v-v_{\le a}\). For an integer \(\ell\ge1\), to be chosen below, set \[ u=\sum_{k=0}^{\ell-1} \bigl(v_{\le 2^{k+\ell}}-v_{\le 2^k}\bigr), \qquad Z=Pu. \tag{22}\] Thus \(u_e\) is \(v_e\) multiplied by the number of intervals \((2^k,2^{k+\ell}]\), \(0\le k<\ell\), containing \(|v_e|\). The successive nonzero multiplicities on the dyadic magnitude intervals are \[1,2,\ldots,\ell-1,\ell,\ell-1,\ldots,2,1.\] The magnitude-density identity (12) therefore gives the same \(p\)-energy at every edge: \[ b:=\int |u_e|^p\,d\nu =p\log2\left(\ell^p+2\sum_{j=1}^{\ell-1}j^p\right), \qquad c_p\ell^{p+1}\le b\le C_p\ell^{p+1}. \tag{23}\] In particular, \(b\ge p\log2>1\), and \(b\) is independent of both the input points and \(\lambda\). Figure 1 illustrates this energy calculation for four overlapping intervals.

The same identity gives \[\int |v_e|^2\mathbf 1_{\{|v_e|>a\}}\,d\nu =\frac{p}{p-2}a^{2-p}.\] The triangle inequality in \(L_2(\nu)\), applied to (22), consequently yields \[\left(\int |u_e|^2\,d\nu\right)^{1/2} \le \left(\frac{p}{p-2}\right)^{1/2} \sum_{k=0}^{\ell-1}2^{(1-p/2)k} \le C_p.\] Using the contraction of \(P\) in \(\ell_2(\sigma)\) and its row-sum bound, we obtain \[ \|Z\|_{L_2(\rho)}^2\le C_p, \qquad \sup_e\int |Z_e|^2\,d\nu\le C_pH^2, \qquad \sup_{e,r,t}|Z_e(r,t)|\le H2^{2\ell}. \tag{24}\] In particular, the coordinatewise quadratic estimate follows from \[\left(\int|Z_e|^2\,d\nu\right)^{1/2} \le\sum_f|P_{ef}|\left(\int|u_f|^2\,d\nu\right)^{1/2} \le C_pH.\] For the supremum bound in (24), each summand defining \(u_e\) has magnitude at most \(2^{k+\ell}\), and their sum is less than \(2^{2\ell}\).

The projection error

We claim that \[ \|Z-u\|_{L_p(\rho)}^p \le C_p H^{p-2}(\ell+1). \tag{25}\] For \(0\le k<2\ell\), define the pointwise vector function \[A_k=(P-I)v_{\le2^k}.\] Although \(v_{\le2^k}\) need not belong to \(L_2(\rho)\), the identity \(Pv=v\) holds pointwise and gives \(A_k=-(P-I)v_{>2^k}\). Thus \(A_k\) does belong to \(L_2(\rho)\), and \[ \|A_k\|_\infty\le 2H2^k, \qquad \|A_k\|_{L_2(\rho)}\le C_p2^{(1-p/2)k}. \tag{26}\] Here the second inequality uses the \(\ell_2(\sigma)\) contraction of \(I-P\) and the preceding tail integral. Moreover, \[Z-u=\sum_{k=\ell}^{2\ell-1}A_k-\sum_{k=0}^{\ell-1}A_k.\] Summing the two bounds in (26) separately shows that this signed sum has \(L_2(\rho)\) norm at most \(C_p\) and supremum norm at most \(CH2^{2\ell}\).

For a level \(\tau\ge16H\), split the sum at \(2^k\le\tau/(16H)\). The sum of the supremum norms of these smaller terms is at most \(\tau/2\). By geometric decay, the remaining terms have total \(L_2(\rho)\) norm at most \(C_p(\tau/H)^{1-p/2}\). Chebyshev’s inequality, together with the global \(L_2\) bound for smaller levels, gives \[\rho\bigl(|Z-u|>\tau\bigr)\le \begin{cases} C_p\tau^{-2},&0<\tau<16H,\\ C_pH^{p-2}\tau^{-p},&\tau\ge16H. \end{cases}\] This tail vanishes for \(\tau>CH2^{2\ell}\). Integrating it against \(p\tau^{p-1}\,d\tau\) proves (25): the smaller levels contribute \(C_pH^{p-2}\), and the larger levels contribute at most \(C_pH^{p-2}(\ell+1)\).

Since \(\|u\|_{L_p(\rho)}^p=b\), the pointwise power-difference inequality and Hölder’s inequality imply \[\begin{align*} \sum_e\sigma_e\left|\int|Z_e|^p\,d\nu-b\right| &\le p\|Z-u\|_{L_p(\rho)} \bigl(\|u\|_{L_p(\rho)}+ \|Z-u\|_{L_p(\rho)}\bigr)^{p-1}. \tag{27}\end{align*}\] By (23) and (25), \[ \frac{\|Z-u\|_{L_p(\rho)}}{b^{1/p}} \le C_p\frac{H^\gamma}{\ell}. \tag{28}\] Choose \[ \ell=\left\lceil L H^\gamma\right\rceil, \tag{29}\] where \(L\ge1\) depends only on \(p,\eta\) and will be enlarged once more below. First choose it large enough that (27) is at most \(\eta b/8\).

Poisson sampling

We need the leading coefficient in the next estimate to be arbitrarily close to one, since the desired distortion \(D\) may be arbitrarily close to one.

A proof using independent symmetric sums is given in Appendix 10.

The function \(Z\) vanishes outside \[S=\{(r,t):\max_e|v_e(r,t)|>1\}, \qquad \nu(S)\le |E|,\] because \(u\) vanishes there. Hence we may take the signed Poisson sum \(W\) of \(Z\) on this finite-measure region. Every summand is in \(V\), so \(W\in V\) almost surely.

Write \(m_e=\int|Z_e|^p\,d\nu\) and \(a_e=\int|Z_e|^2\,d\nu\). Lemma 7 gives, for every \(\epsilon>0\), \[0\le \mathbb E|W_e|^p-m_e \le \epsilon m_e+C_{p,\epsilon}a_e^{p/2}.\] The two quadratic estimates in (24) imply \[ \sum_e\sigma_e a_e^{p/2} \le \left(\max_e a_e\right)^{p/2-1}\sum_e\sigma_e a_e \le C_pH^{p-2}. \tag{31}\] Set \(\epsilon=\eta/32\). The projection estimate gives \(\sum_e\sigma_e m_e\le(1+\eta/8)b\), so the averaged \(\epsilon m_e\) term is at most \(\eta b/16\). Further, \[\frac{H^{p-2}}{b} \le C_p\frac{H^{p-2}}{\ell^{p+1}} \le C_pL^{-(p+1)}H^{-\gamma} \le C_pL^{-(p+1)}.\] Enlarge \(L\), still depending only on \(p,\eta\), until the contribution of (31), including its constant \(C_{p,\epsilon}\), is at most \(\eta b/16\). We have proved \[ \sum_e\sigma_e\left|\mathbb E|W_e|^p-b\right| \le \frac{\eta b}{8}+\frac{\eta b}{16} +\frac{\eta b}{16} =\frac{\eta b}{4}. \tag{32}\]

A bounded random gradient

Choose a constant \(C_p'\) so that \[J=C_p'H2^{2\ell}\ge1\] dominates both \(\sup_{e,r,t}|Z_e(r,t)|\) and \(\sup_e a_e^{1/2}\). The exponential-moment formula for signed Poisson sums gives \[\mathbb E\exp(\pm W_e/J) =\exp\left(\int\bigl(\cosh(Z_e/J)-1\bigr)\,d\nu\right) \le e^{C_0},\] where \(C_0\) is absolute: use \(\cosh s-1\le C_0s^2\) for \(|s|\le1\) and \(a_e\le J^2\). Consequently, for \(z\ge0\), \[ \mathbb P(|W_e|>Jz)\le2e^{C_0-z}, \qquad \mathbb E|W_e|^{2p}\le C_pJ^{2p}. \tag{33}\] Set \[K=8J\log(2n),\qquad \mathcal B=\{\max_e|W_e|>K\},\qquad F=W\mathbf 1_{\mathcal B^c}.\] Discarding the entire vector on a bad event preserves membership in \(V\), so \(F\in V\) and \(\|F\|_\infty\le K\). By the union bound and (33), \[\mathbb P(\mathcal B) \le2|E|e^{C_0}(2n)^{-8}\le Cn^{-6}.\] For every edge, Cauchy–Schwarz therefore gives \[ 0\le\mathbb E|W_e|^p-\mathbb E|F_e|^p \le (\mathbb E|W_e|^{2p})^{1/2}\mathbb P(\mathcal B)^{1/2} \le C_pJ^pn^{-3}. \tag{34}\] By (29), \[\log J=O_{p,\eta}(H^\gamma)=o(\log n).\] Thus the last bound in (34) tends to zero uniformly over the input points and \(\lambda\). Since \(b\ge1\), it is at most \(\eta b/4\) for all sufficiently large \(n\), with the threshold depending only on \(p,\eta\). Combining this with (32) and \(\lambda\le2\sigma\) yields \[\sum_e\lambda_e\left|\mathbb E|F_e|^p-b\right| \le2\sum_e\sigma_e\left|\mathbb E|F_e|^p-b\right| \le\eta b.\] The parameters \(b\ge1\) and \(K\ge1\) are independent of \(\lambda\) and of the input points, as required by Lemma 3. Finally, \[\log K=O_{p,\eta}(H^\gamma) =O_{p,\eta}\bigl((\log n)^{1-2/p}\bigr).\] These are the parameters required by Lemma 3 in this range.

Completion of the upper bound

In Sections 6 and 7, the constructed parameters satisfy \(b,K\ge1\), the weighted moment condition (4), and \[\log K\le C_{p,\eta}(\log n)^{\gamma(p)}\] for all sufficiently large \(n\), with a threshold depending only on \(p,\eta\). Lemma 3 and (10) give an embedding of distortion at most \(D\). Since \(b\ge1\), its dimension satisfies \[\log d\le C_{p,\eta}+2p\log K+\log\log(2n) \le C_{p,D}(\log n)^{\gamma(p)}.\] This proves the upper bound in (2) for sufficiently large \(n\). For the remaining finitely many values of \(n\), enlarge \(C_{p,D}\) and use Lemma 2.

The packing bound

The coordinate unit vectors in \(\ell_p^n\) form an equilateral set. After translating and scaling any distortion-\(D\) image in \(\ell_p^d\), its points are \(1\)-separated and lie in the ball of radius \(D\) about the first point. Their open balls of radius \(1/2\) are disjoint and lie in the ball of radius \(D+1/2\) about that point. Comparing \(d\)-dimensional Lebesgue volumes gives \[n(1/2)^d\le(D+1/2)^d, \qquad\text{hence}\qquad n\le(1+2D)^d.\] This proves the lower bound in (2).

A quadratic obstruction to exact embeddings

For real \(a,b\), define \[\Delta_p(a,b)=|a+b|^p+|a-b|^p-2|a|^p-2|b|^p.\] If \(ab=0\), this is zero. If \(ab\ne0\), it has strictly the sign of \(p-2\). To verify this, apply convexity for \(p>2\), or concavity for \(p<2\), to the two numbers \((a+b)^2\) and \((a-b)^2\) raised to the power \(p/2\). Their average is \(a^2+b^2\). Next use the strict inequality \[(a^2+b^2)^{p/2} \begin{cases} >|a|^p+|b|^p,&p>2,\\ <|a|^p+|b|^p,&p<2. \end{cases}\] Thus, for \(u,v\in\ell_p^d\) and \(p\ne2\), \[ \|u+v\|_p^p+\|u-v\|_p^p =2\|u\|_p^p+2\|v\|_p^p \quad\Longleftrightarrow\quad \operatorname{supp}(u)\cap\operatorname{supp}(v)=\varnothing. \tag{35}\] Indeed, the difference of the two sides is \(\sum_{a=1}^d\Delta_p(u_a,v_a)\), whose nonzero summands all have the same sign.

Fix \(k\ge2\). Index the coordinates of \(\ell_p^{k^2}\) by \(\{1,\ldots,k\}^2\). Let \(r_i\) be the indicator of row \(i\), and \(c_j\) the indicator of column \(j\). Consider the \(4k+1\) distinct points \[\mathcal X_k=\{0\}\cup\{r_i,-r_i:1\le i\le k\} \cup\{c_j,-c_j:1\le j\le k\}.\] Suppose that \(\mathcal X_k\) embeds with distortion one into \(\ell_p^d\). Translate and rescale to obtain an isometry \(f\) with \(f(0)=0\). Strict convexity of \(\ell_p^d\) implies \[ f(-x)=-f(x)\qquad(x\in\mathcal X_k). \tag{36}\] In fact, \(\|f(x)-f(-x)\|_p=2\|x\|_p\) and both \(\|f(x)\|_p\) and \(\|f(-x)\|_p\) equal \(\|x\|_p\), so equality in the triangle inequality forces the two vectors \(f(x)\) and \(-f(-x)\) to coincide.

By (36), the expression in (35) is determined by distances among the given points and is preserved by \(f\). Distinct rows have disjoint supports, so the supports of \(f(r_1),\ldots,f(r_k)\) are pairwise disjoint. The same holds for \(f(c_1),\ldots,f(c_k)\). In contrast, each row and column intersect in exactly one coordinate. Their defect is \[\|r_i+c_j\|_p^p+\|r_i-c_j\|_p^p -2\|r_i\|_p^p-2\|c_j\|_p^p=2^p-4\ne0.\] Consequently \(\operatorname{supp}(f(r_i))\) meets \(\operatorname{supp}(f(c_j))\) for every \((i,j)\). A single coordinate can belong to at most one row support and at most one column support, so it can account for at most one of these \(k^2\) intersections. It follows that \(d\ge k^2\).

For \(n\ge9\), take \(k=\lfloor(n-1)/4\rfloor\) and add distinct points if necessary to obtain an \(n\)-point set. Any exact embedding of that set restricts to one of \(\mathcal X_k\), proving the lower bound in (3). The upper bound is Lemma 2. Finally, \(0<\gamma(p)<1\), so the logarithmic limits in Theorem 1 follow from the stated bounds.