# Length inequalities in trees and CAT(0) spaces

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.

• 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? – YCor Apr 22 '14 at 15:04
• 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. – Dylan Thurston Apr 22 '14 at 20:52
• Is there really no more detail here? It's hard for me to believe that no one has thought much about this. – Dylan Thurston Apr 27 '14 at 14:27

• @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 ? – Hee Kwon Lee Aug 12 '18 at 2:33
• @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$. – Anton Petrunin Aug 12 '18 at 2:58