8
$\begingroup$

I have a family of possibly related questions. Let me start with an elementary one:

Question 1. Fix an integer $n$. For which collections of real numbers $a_{ij}$, $i, j = 1, \dots, n$, is it true that, for all trees $T$ and points $x_1, \dots, x_n$ in $T$, $$ \sum_{i<j} a_{ij} d(x_i, x_j)^2 > 0? \tag{1} $$

That is, I want to characterize the quadratic length inequalities that hold in trees.

A related fact (if you drop "quadratic") is that a set of distances $d_{ij}$ can be realized inside a tree iff the $d_{ij}$ satisfy $$ d_{ik} + d_{jl} \le \max(d_{ij} + d_{kl}, d_{il} + d_{jk}) $$ for all $i,j,k,l$. (If you take $j=l$ you recover the triangle inequality.)

But any quadratic relation as above will also hold for a product of trees (using the Euclidean-like product metric). In particular, it will also hold for Euclidean spaces. For Euclidean spaces, the inequality $(1)$ holds iff the matrix with off-diagonal entries $-a_{ij}$ and rows summing to $0$ is positive semi-definite. But not all such inequalities hold for trees.

Examples. For any points $x_1,\dots,x_4$ in a metric space, $ 2 d_{12}{}^2 + 2d_{13}{}^2 \ge d_{23}{}^2. $ This follows from the triangle inequality, and the corresponding matrix $$ \pmatrix{4&-2&-2\\-2&1&1\\-2&1&1} $$ is positive semi-definite. Likewise the four-point inequality $$ d_{13}{}^2 + d_{24}{}^2 \le d_{12}{}^2 + d_{23}{}^2 + d_{34}{}^2 + d_{14}{}^2 \tag{2} $$ is true in any tree. But the inequality $$ 3(d_{14}{}^2 + d_{24}{}^2 + d_{34}{}^2) \ge d_{12}{}^2 + d_{23}{}^2 + d_{13}{}^2 \tag{3} $$ is true for Euclidean spaces, but not for trees. (Take a tripod, where $x_4$ is the central point of the tripod and the other three points are on different branches.) The best such inequality that is true for trees is $$ 4(d_{14}{}^2 + d_{24}{}^2 + d_{34}{}^2) \ge d_{12}{}^2 + d_{23}{}^2 + d_{13}{}^2. \tag{4} $$

Given that any inequality satisfying $(1)$ will also hold for products of trees, it is natural to ask about CAT(0) spaces as well.

Question 2. Which inequalities of the form $(1)$ hold for CAT(0) spaces? More generally, what length inequalities characterize when a finite set of points can be embedded in a CAT(0) space?

You could also ask the questions in a dual form.

Question 3. Which squared pairwise distances occur between a finite subset of a CAT(0) space? (This is a convex subset of $\mathbb{R}^{n(n-1)/2}$.)

For all the questions, I'm looking for a "nice" description, along the lines of the positive semi-definite description for Euclidean spaces.

It's worth mentioning that Berg and Nikolaev [Geom. Dedicata (2008) 133:1995-218)] proved that inequality $(2)$ characterizes CAT(0) spaces among geodesic metric spaces. But that inequality is not enough to guarantee that even a set of 4 points is embeddable in a CAT(0) space.

Update: It appears that Question 2 is a known hard question. But it also appears that Question 1 and Question 2 are different, although the stated reference gives only the barest sketch of a proof; I'd like to see some explicit example. I'm also most interested in Question 1.

$\endgroup$
  • 1
    $\begingroup$ Do you have a full answer to question 1 for small values of $n$? is the set of solutions a polyhedral cone? What are its extremal rays? $\endgroup$ – YCor Apr 22 '14 at 15:04
  • $\begingroup$ I don't know a full answer to question 1 even for $n=4$, though possibly the answer is in a paper of Gromov (CAT(k)-Spaces: Construction and Concentration, Journal of Mathematical Sciences Vol. 119, 2004). It is a semi-algebraic set which is not polyhedral even for $n=3$, like the cone of positive semi-definite matrices. The extremal rays come from lengths on metric trees, almost by definition. $\endgroup$ – Dylan Thurston Apr 22 '14 at 20:52
  • $\begingroup$ Is there really no more detail here? It's hard for me to believe that no one has thought much about this. $\endgroup$ – Dylan Thurston Apr 27 '14 at 14:27
4
$\begingroup$

These are open questions, but there are some partial answers. Check section 7 in our paper ("Alexandrov meets Kirszbraun" by Alexander, Kapovitch and me).

P.S. More partial answers in our bipolar comparison and you may also check my quest for 5-point condition a la Alexandrov.

$\endgroup$
  • $\begingroup$ Thanks! In that paper, you comment that "the set of metrics which can be embedded in a product of trees and hyperbolic spaces admits a simple description". This seems like it answers my Question 1, but you don't seem to give the explicit answer; is it written anywhere? $\endgroup$ – Dylan Thurston Apr 18 '14 at 1:27
  • $\begingroup$ Close, but not the same. We ment something like that: mathoverflow.net/questions/7794/ (you will not need the consition on rank. For Lobachevsky space or sphere you need to use hyperbolic/spherical cosine rule instead.) $\endgroup$ – Anton Petrunin Apr 18 '14 at 2:03
  • $\begingroup$ I know how to characterize embeddings in Euclidean, hyperbolic, or spherical spaces (I mention the Euclidean case in my question), but I don't know how to characterize embeddings in products of such; can you explain a little? $\endgroup$ – Dylan Thurston Apr 18 '14 at 3:22
  • $\begingroup$ @Anton Petrunin : In the paper "quest for 5-point condition a la Alexandrov", for a three points $x_i$, define a matrix $f(v)=(Wv,v)$ where $W$ is a linear map on $\mathbb{R}^3$ : If $e_i$ is a canonical basis on $\mathbb{R}^3$, then $W(e_1+e_2+e_3)=0$ and $f(e_i-e_j)={\rm dist}\ (x_i,x_j)^2$. Then $W\geq 0$ i.e. positive definite iff $x_i$ satisfies the triangle inequality. How can we prove this ? (There is no hint) For me, direct computation is not easy. It is a direct computation ? $\endgroup$ – Hee Kwon Lee Aug 12 '18 at 2:33
  • 1
    $\begingroup$ @HeeKwonLee it should be $\mathbb{R}^2$, not $\mathbb{R}^3$. If $W>0$ then it defines a Euclidean metric on $\mathbb{R}^2$ and if $W\ge 0$ the metric might degenerate to a line or one-point set. In all the cases the triangle inequality holds. In the opposite direction if all triangle inequalities hold then you can embed the triple in the plane, therefore $W\ge 0$. $\endgroup$ – Anton Petrunin Aug 12 '18 at 2:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.