# Pentagrams and hypermetrics

The Wikipedia article Metric (mathematics) offers a plenty of flavors of metrics, from common to obscure: ultrametric, pseudometric, quasimetric, semimetric, premetric, hemimetric and pseudoquasimetric (I kid you not).

One flavor it does not mention is a hypermetric. This is a metric ${d}$ on a set ${X}$ such that the inequality

$\displaystyle \sum_{i,j}b_i b_j d(x_i , x_j ) \le 0 \ \ \ \ \ \ \ \ \ (1)$

holds for every finite sequence of points ${x_i\in X}$ and every choice of integers ${b_i}$ such that ${\sum_i b_i=1}$. The requirement that ${b_i}$ be integers gives some combinatorial meaning to (1); this is not just some quadratic form being negative semidefinite.

As a warm-up, observe that (1) contains in it the triangle inequality: with ${b_1=b_2=1}$ and ${b_3=-1}$ we get ${d(x_1,x_2)-d(x_1,x_3)-d(x_2,x_3)\le 0}$. But it appears that (1) says something about “polygons” with more vertices too.

To make (1) worth thinking about, it should be satisfied by some important metric space. Such as the real line ${\mathbb R}$, for example. It is not quite obvious that the inequality

$\displaystyle \sum_{i,j}b_i b_j |a_i - a_j| \le 0 \ \ \ \ \ \ \ \ \ (2)$

holds for all reals ${a_i}$ and all integers ${b_i}$ adding up to ${1}$. It helps to order the numbers: ${a_1\le \dots\le a_m}$ and focus on the contribution of a particular gap ${[a_k,a_{k+1}]}$ to the sum (2). The amount it contributes is ${|a_k-a_{k+1}|}$ multiplied by

$\displaystyle \sum_{i\le k k} b_j \right) = \left(\sum_{i\le k} b_i \right) \left(1-\sum_{i\le k} b_i \right) \le 0$

because ${n(1-n)\le 0}$ for every integer ${n}$. This proves (2).

Now that we have one hypermetric space, ${\mathbb R}$, other such spaces can be created easily. If ${X}$ is any set and ${f \colon X\rightarrow\mathbb R}$ any function, consider ${d(x,y) = |f(x)-f(y)|}$, the pullback pseudometric on ${X}$. By applying (2) to the numbers ${f(x_i)}$, we see that ${d}$ satisfies the hypermetric inequality. Since (1) is additive in ${d}$, we can take any family of functions ${f_\alpha \colon X\rightarrow\mathbb R}$ and add together the corresponding pseudometrics. Or even integrate them against a positive measure: ${d(x,y)=\int |f_\alpha(x)-f_\alpha(y)|\,d\mu(\alpha)}$.

For example, the plane ${\mathbb R^2}$ is a hypermetric space, because the distance between two points ${(x_1,y_1)}$ and ${(x_2,y_2)}$, besides the familiar form

$\displaystyle \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$

can also be represented as an integral of the aforementioned pullbacks:

$\displaystyle \frac12 \int_0^\pi \big| (x_1-x_2)\cos \alpha + (y_1-y_2) \sin\alpha \big| \,d\alpha$

A similar integral representation holds in all dimensions; thus, all Euclidean spaces are hypermetric.

Okay, what is not a hypermetric then? For example, the cube distance induced by the norm ${\|x\|_\infty=\max |x_i|}$ is not, in dimensions 3 and higher. Specifically, (1) fails as the five-point inequality with ${(b_1,\dots,b_5) =(1,1,1,-1,-1)}$. I’ll call it the pentagram inequality:

It says that for any five points in the space the sum of monochromatic distances does not exceed the sum of all bi-chromatic (red-blue) distances.

The pentagram inequality fails when ${x_1,\dots,x_5}$ are the columns of the matrix

$\displaystyle \begin{pmatrix} 1& 1& 1& 2& 0\\ 0& 2& 2& 1& 1\\ 0& 1& 0& 1& 0\\ \end{pmatrix}$

(first three columns blue, the last two red). Indeed, the sum of monochromatic distances is ${2+1+2+2=7}$ while the sum of bichromatic distances is ${1+1+1+1+1+1=6}$.

If the above example does not look conceptual enough, it’s because I found it via computer search. I don’t have much intuition for the pentagram inequality.

Anyway, the example delivers another proof that taking the maximum of three numbers is hard. More precisely, there is no isometric embedding of ${\mathbb R^3}$ with the maximum metric into ${\ell_1}$. Unlike the earlier proof, this one does not assume the embedding is linear.

A good reference for hypermetric inequalities is the book Geometry of cuts and metrics by Deza and Laurent.

This site uses Akismet to reduce spam. Learn how your comment data is processed.