Gromov-Hausdorff 距离笔记：不同维球面之间能多近？

旧博客原文

原题：How to compute the Gromov-Hausdorff distance between spheres $latex S_n$ and $latex S_m$?

There is the question, because when we consider the Gromov-Hausdorff distance, we must fix the metric, so we use the natural metric induced from the embedding $\mathbb{S}_n \to \mathbb{R}^{n+1}$ . Is it possible for us to compute the Gromov-Hausdorff distance $d_{G-H}(\mathbb{S}_n,\mathbb{S}_m)$ for two different spheres $\mathbb{S}_n$ and $\mathbb{S}_m$ , $m\neq n$ ?

For example if we want to calculate $d_{G-H}(\mathbb{S}_2,\mathbb{S}_3)=\inf_{M,f,g}d_{M}(\mathbb{S}_2,\mathbb{S}_3)$ , where $M$ ranges over all possible metric space and $f:\mathbb{S}_2\to M$ and $g:\mathbb{S}_3\to M$ range over all possible isometric (distance-preserving) embeddings.

At least we can embed $\mathbb{S}_2$ , $\mathbb{S}_3$ into $\mathbb{R}^3$ in a canonical way. This will lead to a upper bound: $d_{G-H}(\mathbb{S}_2,\mathbb{S}_3)\leq \sqrt{2}$ . And in general case we have $d_{G-H}(\mathbb{S}_m,\mathbb{S}_n)\leq d_{G-H}(point,S_m)+d_{G-H}(point,S_n)\leq 2,\forall 0\leq n\leq m$ . But it is difficult to get a lower bound control for me. Because we need to take the inf in all possible metric spaces $M$ . Especially I conjecture $d_{G-H}(\mathbb{S}_m,\mathbb{S}_n)\geq \lambda_{m,n}\frac{m-n}{m},\forall 0\leq n\leq m$ , where $\liminf_{m,n\to \infty}\lambda_{m,n}>0$ .

I only know the knowledge of Gromov-Hausdorff from Peterson’s Riemann Geometry. Unfortunately there is not enough information to compute the Gromov-Hausdorff distance, so this problem may be very stupid, I will appreciate any pointer.

And we know for the case $S_n,S_m$ , if $n,m$ is very near to each other,then the two space should be more near, and there is a canonical embed $S_0\subset S_1 \subset S_2 ....\subset S_n \subset ...$ . So it is natural to conjecture if $m,n$ is very near then the distance $d_{G-H}(S_n,S_m)$ is very small. I have a very rough strategy to prove the conjecture, that is inspired by the Nash embedding theorem. I just mean if we consider the problem in this frame $d_{G-H}(S_n,S_m)=\inf_{M,g,f}(d_M(f(S_n),g(S_m)))$ then the difficult is the deformation space of $M,g,f$ is too large. so the first step is to establish a regular lemma, to prove the function $d_M(f(S_n),g(S_m))$ is continues under the small perbutation of $M$ and reduced to the situation of space $M,g,f$ with very nice regularity. the second part is to embed $M$ to a big euclid space $R^N$ as subspace, and the embedding stay the length of geodesic.locally this is determine by a group of pde: $u_i(x)u_j(x)=g_{ij}(x)$ ,at least in the cut locus.but there should be some critical point,and I do not know how to deal with them.the third,i.e. the last step is to calculate $d_{G-H}(S_n,S_m)$ in the very some deformation space $M,f,g$ .

@Mark Sapir,Appreciate for help!I am reading the article you point out,it seems this article mainly focus on investigating the Gromov-Hausdorff limit space of a sequence of hyperbolic group equipped with modified G-H metric defined in 2.A with some special condition to ensure the limit space exists.and take a sequences corvarage to the limit space,the hyperbolic property and some other thing is stayed by the process of take limit.
@Mark Sapir,So it is natural for us to investigate the original space by some information from the limit space.there is a series of bi-product state in 3.B.but I do not see where the author exactly calculate some groom-hausdorff distance of two different space,may you point out it?appreciate again!
@MarianoSuárez-Álvarez,Corrected, thanks.

Y:
I fixed numerous typos. In particular, you should use spacing after each punctuation mark; capitals to begin sentences and names.

H:
Thank you very much for helping me to correct the mistakes! I will know how to write in a correct style.

Y:
23.1k
Your conjecture would imply that the GH distance is unbounded. But it’s clearly bounded, since the GH distance of any sphere to a point is equal to 2 (when the sphere is endowed with the restriction of Euclidean distance, as you seem to assume, or $\pi$ when endowed with geodesic distance) and hence the GH distance between any two spheres is $\le 4$ .

H:
73
You are right,In fact if we use the canonical embed, then we can get $d_{G-H}(S_n,S_m)\leq 2$ by another equivalent definition of GH distance.I confuse the geometry picture of the pairs $T_n,S_n$ with the pairs $S_n,S_m$ ,for $S_n,S_m$ case,I thick the seems correct conjecture will be $d_{G-H}(S_n,S_m)\sim \frac{m-n}{m},0\leq n\leq m,m,n\to \infty$ .

Y:
16:37
Clearly from standard embeddings we get $d_{GH}(S_n,S_m)\le\sqrt{2}$ for all $n,m\ge 0$ . Would it be reasonable to simply conjecture that it’s an equality whenever $n\neq m$ ?

H:
73
Yeah, you are right, $d_{G-H}(S_n,S_m)\leq \sqrt{2}$ for all $n,m\geq 0$ .I find the interesting problem when I want to find a toy model of a kind of problem,roughly speaking is to investigate a map $f:X\to Y$ from low-dimensions space $X$ to high-dimension space $Y$ stay some affine structure of the low-dimension space $X$ . This structure could have some control by the distance function on the low-dimension space, so if we can get some control on the variation of the Energy of distance function, this will share some line on the original problem I consider.
And we know for the case $S_n,S_m$ , if $n,m$ is very near to each other,then the two space should be more near, and there is a canonical embed $S_0\subset S_1 \subset S_2 ....\subset S_n \subset ...$ . So it is natural to conjecture if $m,n$ is very near then the distance $d_{G-H}(S_n,S_m)$ is very small. .
I have a very rough strategy to prove the conjecture, that is inspired by the Nash embedding theorem. I just mean if we consider the problem in this frame $d_{G-H}(S_n,S_m)=\inf_{M,g,f}(d_M(f(S_n),g(S_m)))$ then the difficult is the deformation space of $M,g,f$ is too large. so the first step is to establish a regular lemma, to prove the function $d_M(f(S_n),g(S_m))$ is continues under the small perbutation of $M$ and reduced to the situation of space $M,g,f$ with very nice regularity.
The second part is to embed $M$ to a big euclid space $R^N$ as subspace, and the embedding stay the length of geodesic.locally this is determine by a group of pde: $u_i(x)u_j(x)=g_{ij}(x)$ ,at least in the cut locus.but there should be some critical point,and I do not know how to deal with them.the third,i.e. the last step is to calculate $d_{G-H}(S_n,S_m)$ in the very some deformation space $M,f,g$ .
I need come back to explain why we expect the groom-hausdorff distance $d_{G-H}(S_d,S_m),0\leq n\leq m$ should be much small than $\sqrt 2$ when $frac{n}{m}$ is small.
Let consider a toy model of the problem,in a graph model,i.e. now we do not consider to take the Infimum in all space but in discrete space endow with metric. this can be view as a complete graph equipped metric, i.e. $M=\{(G,d_G)\}$ . So there is also some space very like $S_n$ ,$S_m$ in the Euclid space, Let remark them as $G_{S_n},G_{S_m}$ .
, oberseve that $(G,d_G)\in M$ then $(G,\hat d_{G})\in M$ , $\hat d_{G}$ is a scaling of $d_G$ so it is natural to consider a cut off of $M$ ,called $M_{\lambda}$ which is just a subset of $M$ and satisfied if $(G,d_G)\in M_{\lambda}$ ,then $\inf_{x\neq y}d_{G}(x,y)\geq d$ .
Now,in the space $M_{\lambda}$ let us consider a Distance distribution: $\mu_G((a,b))=\frac{\#\{x,y\in G|a<d_G(x,y)<b\}}{\#G\times G}$ . Then this distribution will give us some information of the distance of the two different set $G_1,G_2$ in $M_{\lambda}$ .
(removed)
Now,in the space $M_{\lambda}$ let us consider a Distance distribution: $\mu_G((a,b))=\frac{\#\{x,y\in G|a<d_G(x,y)<b\}}{\#G\times G}$ . Then this distribution will give us some information of the distance of the two different set $G_1,G_2$ in $M_{\lambda}$ .
and obviously we will see that if $n,m$ is close,then the distribution of fuzzy approximation $G_{S_n},G_{S_m}$ is near, and the reverse is also true. I think this can explain why the conjecture $d_{G-H}(S_n,S_m) =O(\frac{m-n}{m})$ may be right.

by the way,it is a very good exercise to proof $d_{G-H}(S_n,S_0)=1,\forall n\in N^*$ .

补充说明

以下是新整理的中文说明；上方旧博客原文保持不变。

问 $S^n$ 和 $S^m$ 的 Gromov-Hausdorff 距离，第一步必须先固定 metric。球面可以带内蕴测地距离，也可以带作为欧氏空间子集的 chordal distance；不同选择会给出不同数值。真正稳定的对象不是某个嵌入，而是所有可能 correspondences 的 distortion。

Gromov-Hausdorff 距离笔记：不同维球面之间能多近？ — 比较不同维球面时，标准嵌入只给出上界；真正的 GH 距离要在所有 correspondences 上取最优。

1. 定义提醒

紧 metric spaces $X,Y$ 的 Gromov-Hausdorff 距离可以用 correspondences 表示：

$$d_{GH}(X,Y)=\frac12\inf_R \operatorname{dis}(R),$$

其中 $R\subset X\times Y$ 是 correspondence，distortion 定义为

$$\operatorname{dis}(R)=\sup_{(x,y),(x’,y’)\in R}
\bigl|d_X(x,x’)-d_Y(y,y’)\bigr|.$$

这一定义强调：我们不是只比较两个空间在某个欧氏空间中的位置，而是允许把它们同时嵌入任意 metric space，再取最优比较。

2. 先用标准嵌入给上界

若 $n

$$d_{GH}(S^n,S^m)\le \sqrt2.$$

若用 geodesic metric，对应上界是 $\pi/2$。这只是上界，不自动说明最优。

3. 为什么不能猜它随维数增长

一个容易犯的错误是认为维数差越大，距离越大。但 GH 距离由直径控制。对任意紧空间 $X$，

$$d_{GH}(X,\{\ast\})=\frac12\operatorname{diam}(X).$$

因此两单位球面之间的 GH 距离总是被一个统一常数控制，不可能随着 $m-n$ 无界增长。维数差体现为拓扑和覆盖数的差异，但 GH 距离本身仍然是 metric 层面的量。

4. 下界为什么难

要证明 equator 嵌入给出的上界是最优，需要排除所有更聪明的 correspondences。这通常要找一个 metric invariant，例如 covering number、packing number、waist phenomenon 或同调信息，说明低维球面无法在小 distortion 下模拟高维球面。

例如，如果 $S^m$ 中有许多两两相距较远的点，而 $S^n$ 在同样尺度下容纳不了这么多点，就可以得到下界。这类 argument 本质上是把维数信息转化成 packing 数据。

5. 一个合理的 toy problem

这个问题真正有意思的地方在于，它是“低维空间如何嵌入高维空间并保留距离结构”的 toy model。若把球面换成带变形 metric 的流形，还会涉及 Nash embedding、cut locus、距离函数能量的变化以及正则性问题。

所以比较 $S^n$ 和 $S^m$ 不只是为了得到一个数值；它逼迫我们区分三件事：具体嵌入给出的 Hausdorff 上界、抽象 GH 距离的最优 correspondence、以及维数信息如何通过 metric invariant 被读出来。

Gromov-Hausdorff 距离笔记：不同维球面之间能多近？

旧博客原文

补充说明

1. 定义提醒

2. 先用标准嵌入给上界

3. 为什么不能猜它随维数增长

4. 下界为什么难

5. 一个合理的 toy problem

评论

发表回复 取消回复

更多文章

从支撑接触到 Hausdorff 分层：凸 k-Hessian 解的四步证明机制

From Sum-Free Sets to Strongly 2-Primitive Sets: Localization, Patching, and the Search for Stability

[后端同步测试] 富媒体、代码与数学公式渲染

1

发表回复取消回复