The n-Category Café

Background  Let $A = \{ a_1, \ldots, a_m \}$ be a finite metric space. The similarity matrix $Z_A$ of $A$ is the $m\times m$ matrix $(e^{-d(a_i, a_j)})_{i, j}$. If $Z_A$ is invertible, we define the magnitude (or cardinality) of $A$ to be the sum of all $m^2$ entries of $Z_A^{-1}$.

(There are known to be metric spaces whose similarity matrix is not invertible. Magnitude can be sensibly defined under a weaker hypothesis than invertibility of $Z_A$; but still, it is not always defined.)

A finite metric space $A$ is positive definite if $Z_A$ is positive definite: that is, $\mathbf{c}^t Z_A \mathbf{c} \geq 0$ for all $\mathbf{c} \in \mathbb{R}^m$, with equality only if $\mathbf{c} = \mathbf{0}$. Positive definiteness turns out to be an important property for various reasons: see here, here, here or here (pp.12–14, 23–25). In essence: magnitude of metric spaces can behave in apparently weird ways, but not if you restrict to positive definite spaces. The positive definite spaces are the ‘non-weird’ ones.

In particular, since positive definite matrices are invertible, any positive definite space has a well-defined magnitude.

There are many well-known metrics on $\mathbb{R}^n$. For $n\in \mathbb{N}$ and $p \in [1, \infty)$, let $\ell_p^n$ denote $\mathbb{R}^n$ equipped with the metric coming from the $\ell_p$-norm $\Vert\cdot\Vert_p$, as a metric space: thus, $$d(\mathbf{a}, \mathbf{b}) = \Vert \mathbf{b} - \mathbf{a} \Vert_p    where    \Vert \mathbf{x} \Vert_p = \left( \sum_{i = 1}^n |x_i|^p \right)^{1/p}.$$ The ‘taxicab’ metric ($p = 1$) gets along very well with magnitude (ultimately because it comes from the tensor product of enriched categories). I’ve known for a long time that every finite subspace of $\ell_1^n$ is positive definite. In particular, the magnitude of every finite subspace of $\ell_1^n$ is well-defined.

But when I say that in seminars, no one cares! What everyone wants to know is whether the same is true for the Euclidean metric, $p = 2$. And if it’s true for $p = 1$ and $p = 2$, what about $1 \lt p \lt 2$?

The problem  Show that every finite subspace of $\ell_p^n$ is positive definite, for all $n \in \mathbb{N}$ and $p \in [1, 2]$.

(There are good reasons for believing this to be false when $p \gt 2$.)

It will follow that every finite subpace of $\ell_p^n$ has well-defined magnitude. In particular:

Every finite subspace of $\mathbb{R}^n$, with the Euclidean metric, has well-defined magnitude.

Consequently, I lose a small bet against Simon Willerton.

The solution  Here’s a 4-step outline of a proof. If you want more, you can read the detailed version that I wrote up. Much of it would be regarded as standard by (some) analysts. What I think is the hardest, or least standard, part of the proof is due to Mark Meckes. I’ll mention the other main contributors as we go along. Tell me if I’ve left you off!

Step 1: Find the connection with analysis  It turns out that this type of problem has been studied in analysis since the 1920s or 30s. The key concept is that of ‘positive definite function’. David Corfield and Yemon Choi were the first to point this out. Of course, until you know the terminology you have no idea what to look up, so this kind of information is vital.

A function $f: \mathbb{R}^n \to \mathbb{R}$ is positive definite if for all $m \in \mathbb{N}$ and $\mathbf{x}^1, \ldots, \mathbf{x}^m \in \mathbb{R}^n$, the $m \times m$ matrix $(f(\mathbf{x}^i - \mathbf{x}^j))_{i, j}$ is positive semidefinite (that is, $\sum_{i, j = 1}^m c_i f(\mathbf{x}^i - \mathbf{x}^j) c_j \geq 0$ for all $\mathbf{c} \in \mathbb{R}^m$). It is strictly positive definite if this same matrix is positive definite.

As you can see, there’s a terminological calamity here. An analyst friend tells me that many analysts call a real number ‘positive’ if it is $\geq 0$. (I thought only the French did that.) Presumably the terminology above, which by now is well entrenched, comes from that tradition. I’ll call a real number positive iff it is $\gt 0$.

Anyway, in this language the problem becomes:

The problem, version 2:  Show that for each $n \in \mathbb{N}$ and $p \in [1, 2]$, the real-valued function $\mathbf{x} \mapsto e^{-\Vert\mathbf{x}\Vert_p}$ on $\mathbb{R}^n$ is strictly positive definite.

Step 2: Harness the power of the Fourier transform  We want to prove that something is strictly positive definite. The following sufficient condition will do it for us:

Let $f: \mathbb{R}^n \to \mathbb{R}$ be a continuous, bounded, integrable function. If the Fourier transform of $f$ is everywhere positive then $f$ is strictly positive definite.

This result seems to be due to Holger Wendland, from a paper On the smoothness of positive definite and radial functions. David Speyer also found most of a proof of this (1, 2). It’s related to a result that’s well known in harmonic analysis, Bochner’s Theorem, but that’s about non-strict positive definiteness, which is what most people have concentrated on historically.

So, the problem reduces to:

The problem, version 3:  Show that for $n \in \mathbb{N}$ and $p \in [1, 2]$, the function $\mathbf{x} \mapsto e^{-\Vert\mathbf{x}\Vert_p}$ on $\mathbb{R}^n$ has everywhere positive Fourier transform.

If the Euclidean metric is all you care about, you can stop reading at the end of this sentence: for the Fourier transform of $\mathbf{x} \mapsto e^{-\Vert\mathbf{x}\Vert_2}$ can be calculated explicitly (Stein and Weiss, Introduction to Fourier Analysis on Euclidean Spaces, page 6), and it’s everywhere positive.

Step 3: Crack the hard nut that is the $\ell_p$-norm  This step and the next are due to Mark Meckes, via Math Overflow. Parts of the argument are from the book Fourier Analysis in Convex Geometry by Alexander Koldobsky.

We have to think about the Fourier transform of the function $$\mathbf{x} \mapsto e^{-\Vert\mathbf{x}\Vert_p} = e^{-(|x_1|^p + \cdots + |x_n|^p)^{1/p}}$$ on $\mathbb{R}^n$. If that $(1/p)$th power weren’t there, life would be simpler, because we’d just have a product of exponentials. It is there — but in some sense, this step shows how to make it disappear.

We’ll see that the function $$\begin{matrix} (0, \infty) &\to &(0, \infty) \\ \tau &\mapsto &e^{-\tau^{1/p}} \end{matrix}$$ can be re-expressed in a more convenient way. It is, in fact, an ‘infinite linear combination’, with nonnegative coefficients, of functions of the form $\tau \mapsto e^{-t \tau}$. That is, there is a finite nonnegative measure $\mu$ on $(0, \infty)$ such that for all $\tau \gt 0$, $$e^{-\tau^{1/p}} = \int_0^\infty e^{-t \tau} d\mu(t).$$ The $(1/p)$th power has gone!

For the cognoscenti, this follows by observing that the function $\tau \mapsto e^{-\tau^{1/p}}$ is completely monotone, then applying Bernstein’s theorem.

(Koldobsky’s book calls it ‘the celebrated Bernstein’s Theorem’. Whenever anyone describes a theorem as ‘celebrated’, I imagine a party thrown in its honour, with streamers and balloons.)

Step 4: Put it all together  Earlier, we reduced the problem to showing that, for $n \in \mathbb{N}$ and $p \in [1, 2]$, the Fourier transform of the function $\mathbf{x} \mapsto e^{-\Vert\mathbf{x}\Vert_p}$ on $\mathbb{R}^n$ is everywhere positive.

The previous step showed how to re-express $e^{-\Vert\mathbf{x}\Vert_p}$ in a more convenient way.

Now: work out the Fourier transform of $\mathbf{x} \mapsto e^{-\Vert\mathbf{x}\Vert_p}$ by using this re-expression. Following your nose, the problem reduces to:

The problem, version 4:  Show that the Fourier transform of the function $z \mapsto e^{-|z|^p}$ on $\mathbb{R}$ is everywhere positive.

Do we have a formula for the Fourier transform of $z \mapsto e^{-|z|^p}$? No, apparently not, except when $p = 1$ or $p = 2$. But Lemma 2.27 of Koldobsky’s book tells us that it is indeed everywhere positive, and that’s all we need to know.