# Questions tagged [metric-embeddings]

The metric-embeddings tag has no usage guidance.

33
questions

**10**

votes

**0**answers

627 views

### Two questions around the $abc$-conjecture

Let $d(a,b) = 1-\frac{2 \gcd(a,b)}{a+b}$, $d_{ABC}(a,b) = 1-\frac{2\gcd(a,b)^3}{ab(a+b)}$ be two metrics on natural numbers.
The abc-conjecture can be formulated using these two metrics as:
For ...

**2**

votes

**0**answers

96 views

### Is the matrix $\mu_f(X_i \cap X_j)$ positive definite?

Let $X_1,\ldots, X_n$ be finite subsets of some larger finite set $Z$.
Let $f:Z \rightarrow \mathbb{R}_{>0}$ be any function, and define a (counting) measure $\mu_f(X) = \sum_{x \in X} f(x)$ for a ...

**2**

votes

**0**answers

43 views

### Partitions of unity with arbitrary Lip-constants

Lets make things simple. Suppose we have a compact metric space $(X,d)$ and then some Lipschitz partition of unity exists, say a collection $\mathcal{F}=\{f_n\}$ subordinate to some open cover $\...

**2**

votes

**0**answers

95 views

### Embedding a binary subspace to $l_2$ in a much lower dimension

I'm trying to find a way to embed a binary linear subspace of dimension $n$ (a linear code) to the Euclidian space while reducing the dimension significantly.
The subspace (or code) contains points ...

**5**

votes

**0**answers

201 views

### Is this function embeddable in Euclidean space?

Let $X = \{v_1,\ldots,v_n\}$ be a set of vectors non-zero vectors $v_i \ge 0$ and such that the vectors are pairwise linear independent. Define a function on this set $X$:
$$d(v,w) = 1-\frac{2 \...

**31**

votes

**5**answers

1k views

### Trigonometry / Euclidean Geometry for natural numbers?

Let $d(a,b) = 1 - \frac{2\gcd(a,b)^3}{ab(a+b)}$ be a metric on natural numbers without $0$.
The metric space $X = \{x_0,x_1,\cdots,x_n\},n>2$ is isometric embeddable in $\mathbb{R}^n$ if and only ...

**3**

votes

**0**answers

96 views

### “Hoelder conjugate” version of the Johnson-Lindenstrauss transform

A variation of the well-known Johnson-Lindenstrauss transform (JLT) asserts that for $x_1,\ldots,x_m\in\mathbb{R}^n$ there exists a linear transformation $A:\mathbb{R}^n\to\mathbb{R}^k$ with $k=\...

**4**

votes

**1**answer

335 views

### Fast Bourgain embedding (or similar embeddings)?

Currently I am working on applications of Bourgain Embedding (or similar embeddings of finite metric spaces to $l_2$) to automatic feature engineering for machine learning/data science ( http://www....

**2**

votes

**1**answer

59 views

### Lower Estimate of A Lipschitz Map

Suppose that $(X,d_X)$ and $(Y,d_Y)$ are complete doubling metric spaces and let $f:X\rightarrow Y$ be a non-constant Lipschitz map. Then can does there exist a lsc function
$\rho:(0,\infty)\...

**0**

votes

**0**answers

56 views

### Green's Function for Fractional Laplacian on the Union of Two Balls

I have two disjoint open intervals $B_1, B_2 \subset \mathbb{R}$, and variables $0 < s < 1$ and $t \in B_1 \cup B_2$. I want to solve:
$$r_{B_1 \cup B_2}(\Delta^{s} f) = \delta_t$$ for $f$. ...

**5**

votes

**2**answers

569 views

### Isometric embedding of a genus g surface

Can a genus $g$ surface with constant negative curvature and $g>1$ be isometrically embedded in $\mathbb{R}^4?$

**3**

votes

**1**answer

146 views

### Suppose that a metric space allows David–Semmes regular map to some Euclidean space. Does it allow bi-Lipschitz embedding into some Euclidean space?

I want to ask about the progress on Question 8 from "Thirty-three yes or no questions about mappings, measures, and metrics" by Juha Heinonen and Stephen Semmes. Is it still open? If yes, was some ...

**2**

votes

**0**answers

88 views

### Inclusion of convex polytopes and embedding from $\ell_2$ to $\ell_\infty$

I would like to dig deeper into the problem posted Probability that a convex shape contains the unit ball:
If you pick n points uniformly at random from the surface of a d
dimensional sphere of ...

**6**

votes

**0**answers

140 views

### Do manifolds with non-negative Ricci curvature allow bi-Lipschitz embeddings into Euclidean spaces?

QUESTION: Let $n$ be a natural number. Is it true that there exist $N(n), D(n) > 0$ such that any complete $n$-dimensional Riemannian manifold of nonnegative Ricci curvature can be embedded into $N$...

**7**

votes

**1**answer

123 views

### Embedding Turing machine [closed]

I have some questions about Turing machines. Is there an embedding method where you embed Turing machines, finite automata into continuous space or graphs? Or are there geometrical approaches to ...

**2**

votes

**2**answers

174 views

### Johnson-Lindenstrauss Lemma on $S^{d-1}$

Consider the Johnson-Lindenstrauss lemma in the case where we can assume the $n$ input points $x_i$ in $\mathbb{R}^d$ are actually located on the sphere
$$S^{d-1}(r):=\{u=(u_1,\ldots,u_{d}): u_1^2+\...

**1**

vote

**0**answers

110 views

### Expectation of a combinatorial extremal random variable?

Consider the finite set $\chi(D)$ of all sets of integer points in $\Bbb Z^n$ around origin which have distance at most $D$ from each other and pick a set $\mathcal P(D)$ from set of sets $\chi(D)$ ...

**2**

votes

**0**answers

53 views

### Totally distance non-preserving transformations

JL lemma (https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma)
guarantees if you have a set of $K$ points in $\Bbb R^N$ a random transformation guarantees that the set can be projected ...

**4**

votes

**2**answers

256 views

### Finitely isometrically persistent metric spaces

The goal of this question is to develop further the discussion
initiated in Under which conditions is it possible to find points with same distances under bi-Lipschitz map. The mentioned question was ...

**11**

votes

**1**answer

481 views

### Is $\ell_p$ $(1<p<\infty)$ finitely isometrically distortable?

Let $Y$ be a Banach space isomorphic to $\ell_p$, $1<p<\infty$. Is it true that any finite subset of $\ell_p$ is isometric to some finite subset of $Y$?
It seems to me that it is an interesting ...

**31**

votes

**0**answers

794 views

### Isometric embeddings of finite subsets of $\ell_2$ into infinite-dimensional Banach spaces

Question: Does there exist a finite subset $F$ of $\ell_2$ and an infinite-dimensional Banach space $X$ such that $F$ does not admit an isometric embedding into $X$?
There are some results of the ...

**4**

votes

**1**answer

438 views

### Embedding graphs into hyperbolic spaces

Do we know of a characterization as to when does a graph have a "good" embedding into a hyperbolic space? (And does having such an embedding have a spectral or wavelet analysis signature?)
I don't ...

**12**

votes

**2**answers

498 views

### Does every CAT(0) space embed in a measurable integral of $\mathbb{R}$-trees?

Question 1. Does every CAT(0) space embed isometrically inside an integral of $\mathbb{R}$-trees?
Here an integral of $\mathbb{R}$ trees means the set of functions from a measure space $\mathcal{F}$ ...

**17**

votes

**1**answer

545 views

### Canonical Immersion of the Double Torus

It is easy to check that the immersion $\mathbb{T}^2=\mathbb{S}^1\times \mathbb{S}^1\longrightarrow\mathbb{R}^4$, $(\alpha,\beta)\longmapsto(\cos\alpha,\sin\alpha,\cos\beta,\sin\beta)$ induces the ...

**7**

votes

**1**answer

305 views

### Embedding Euclidean buildings into products of trees

A Euclidean building has a natural metric space structure. (A definition of Euclidean building can be found on Wikipedia, or, more expansively, in Section 4 of Kleiner-Leeb.)
Question: Is it true ...

**17**

votes

**0**answers

419 views

### Large almost equilateral sets in finite-dimensional Banach spaces

Question: Does there exist a function $C:~(0,1)\to
(0,\infty)$ such that for each $\varepsilon\in(0,1)$ every Banach space
$X$ of dimension $\ge C(\varepsilon)\log n$ contains an $n$-point
set $\{x_i\...

**2**

votes

**0**answers

228 views

### Finitely generated groups non-embeddable into $L_1(0,1)$

I am interested in finitely generated groups which, endowed with their word metrics, do not admit bilipschitz embeddings into $L_1(0,1)$. I know two classes of such groups:
(1) Heisenberg group $\...

**11**

votes

**1**answer

347 views

### Embeddings of finitely generated groups into uniformly convex Banach spaces

de Cornulier, Tessera, and Valette (Geom. Funct. Anal. 17 (2007), 770-792) conjectured that a finitely generated group $G$ with its word metric admits a bilipschitz embedding into a Hilbert space if ...

**6**

votes

**1**answer

241 views

### Reference request: embedding the hyperbolic triangulation in $\mathbb{R}^3$

Let $T_d$ be the infinite valence $d$ triangulation of the hyperbolic plane, where each triangle is equilateral and $d \ge 7$. Question: Is there an isometric embedding from $T_d \to \mathbb{R}^3$? ...

**5**

votes

**3**answers

426 views

### How hard is it to determine if a weighted graph can be isometrically embedded in R^3?

Consider a graph $G$ with nonnegative edge weights.
Question: In $\mathbb{R}^3$, how hard is it to assign coordinates to vertices such that the Euclidean length of each edge is equal to its weight?
...

**1**

vote

**1**answer

261 views

### Probabilistic Johnson-Lindenstrauss Lemma for arbitrary points

Consider the following standard formulation of the Johnson-Lindenstrauss lemma:
Lemma (JL).
For any $0<\epsilon < 1$ and any integer $n$, let $k$ be a positive integer such that $k\geq C\...

**15**

votes

**3**answers

584 views

### Embedding expanders in CAT(0) spaces

It is well-known that expanders are hard to embed into Hilbert (or $\ell^p$) spaces - any embedding of an expander with $n$ vertices has distortion $\Omega(\log n)$.
Can anyone provide a reference (...

**7**

votes

**0**answers

163 views

### Can two random graphs be metrically embedded into one another?

Let $X, Y$ be two random graphs on $n$ vertices (say, in $G(n, p)$ model for some $p$). Can anything (expectation, value with high probabiity, ...) be said about $D(X, Y)$, where $D$ is the minimal ...