(Related to previous post but can be read independently). The triangle inequality, one of the axioms of a metric space, can be visualized by coloring the vertices of a triangle by red and blue.
The inequality says that the sum of monochromatic distances must not exceed the sum of dichromatic distances. That is, for every assignment of the vertices to points in the space, the sum of all red-red and blue-blue distances does not exceed the sum of red-blue distances. An assignment is just a map from the set of vertices to the metric space ; it need not be injective.
But why stop at the triangle? We can take any number of points (vertices), color them in some way, and require the same polygonal inequality:
Already for the square we have two distinct plausible colorings to explore: even red-blue split
and predominantly red square
But it turns out that the second coloring is useless: the inequality it defines fails in every metric space with more than one point. More generally, suppose we have red points and blue ones, and . Pick two distinct points . Assign one red point to and all others to . The sum of monochromatic distances is while the sum of dichromatic distances is , which is strictly less.
So, we are limited to nearly-even colorings: those with . For even numbers of vertices this means even split, while odd numbers should be divided as evenly as possible: like 3+2 for the pentagon.
The inequalities turn out to be related. For every , the -gonal inequality implies the -gonal inequality, because if we assign two opposite-colored vertices to the same point, their contributions cancel out. More interestingly: when is odd, the -gonal inequality implies the -gonal inequality. Indeed, suppose we have points, evenly colored. Add an arbitrary th point. Whether the added point is blue or red, the -gonal inequality holds. Averaging these two inequalities, we see the effect of the added points canceling out.
So, if the -gonal inequality holds for all odd , it holds for all . This property is exactly the hypermetric property from the previous post. Except it was stated there in a different form:
for every finite sequence of points and every choice of integers such that . But if the point is repeated times, we can replace by . Then represent +1 as blue and -1 as red.
The hypermetric inequalities were introduced by John B. Kelly (a student of William Ted Martin) in late 1960s. He showed they are necessary for the space to be embeddable into the space . It would be great if they were also sufficient (and for some classes of spaces they are), but this is not so: a counterexample was given by Patrice Assouad in 1977.
It is also interesting to consider the -gonal inequalities for even only. By repetition of vertices, they are equivalent to requiring
for every finite sequence of points and every choice of integers such that . But of course then we have (1) for rational (just clear the denominators), hence for all real (by approximation), as long as they sum to . So, the requirement amounts to the matrix being negative semidefinite on the subspace . Such metrics are called metrics of negative type.
Their relation to embeddability of the space is well-known: is of negative type if and only if the “snowflake” isometrically embeds into a Hilbert space. In other words, we can “draw” any finite metric space of negative type in a Euclidean space, with the understanding that Euclidean distances represent the square roots of the actual distances. This embedding result is a 1935 theorem of Isaac Schoenberg who is also known for connecting dots naturally (introducing splines).