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.

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