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.
