Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Source. Karamanlis, published p. 6, Proposition 8 (canonical PDF). The corresponding arXiv v1–v3 result is Proposition 3.6.

Statement. For every integer k≥1k\ge1, every finite X⊆RkX\subseteq\mathbb R^k and every δ>0\delta>0, there are an integer m≥2m\ge2 and a real r>0r>0 such that XX has a δ\delta-embedding into Tm,rkT_{m,r}^{k}.

Proof. For each coordinate projection πa(X)\pi_a(X) containing at least two points, list its positive pairwise distances. There are finitely many such distances over all coordinates. Choose one integer n0≥1n_0\ge1 large enough that every listed distance belongs to [1/n0,n0][1/n_0,n_0]. If there are no listed distances, choose n0=1n_0=1.

Apply the repaired Lemma 7 with tolerance δ/k\delta/k, using a single integer

n≥max⁡{2,n0,2πn03k/δ}.n\ge\max\{2,n_0,2\pi n_0^3k/\delta\}.

It gives the same m=n3m=n^3 and r=n0n/(2π)r=n_0n/(2\pi) for every nonsingleton projection. For a singleton projection, map its sole value to one vertex of the same polygon; its distance error is zero and the map is injective. An empty XX has the empty embedding, so assume XX nonempty below. Let fa:πa(X)→Tm,rf_a:\pi_a(X)\to T_{m,r} denote the chosen coordinate maps.

Set f(x)=(f1(π1x),…,fk(πkx))f(x)=(f_1(\pi_1x),\ldots,f_k(\pi_kx)). Distinct points of XX differ in some coordinate, where faf_a is injective, so ff is injective. Orthogonality and the triangle inequality give

∣∥f(x)−f(x′)∥2−∥x−x′∥2∣≤∑a=1k∣∥fa(πax)−fa(πax′)∥2−∣πax−πax′∣2∣<k(δ/k)=δ.\begin{aligned} \left|\|f(x)-f(x')\|^2-\|x-x'\|^2\right| &\le\sum_{a=1}^{k} \left|\|f_a(\pi_ax)-f_a(\pi_ax')\|^2-|\pi_ax-\pi_ax'|^2\right|\\ &<k(\delta/k)=\delta. \end{aligned}

This proves the assertion. A configuration initially in R0\mathbb R^0 is empty or a singleton and may first be placed in R\mathbb R. □\square

Source precision. The common separation bound and singleton-coordinate cases expand the source's choice of a common (m,r)(m,r). This is an existential approximation; no equality of distances is claimed here. The missing correction is supplied by Proposition 11.