The n-Category Café

Hadwiger’s theorem says something like this:

The only measures of size for subsets of ${ℝ}^n$ are the following.

So there are three things I need to explain.

First, what’s a “measure of size”?

Second, what’s meant by “the following”? In other words, what measures of size on ${ℝ}^n$ are there?

Third, why are these the only ones? In other words, how do you prove Hadwiger’s theorem?

What’s a “measure of size”?

I’ll begin by pointing out the major limitation of Hadwiger’s theorem, and probably the reason why it’s not better known: it concerns only measures of the size of convex sets. People have tried to extend the result to more general classes of space: see for instance Simon’s post on the Weyl tube formula. Nevertheless, the class of convex sets is not to be sniffed at: it includes sets with highly irregular, non-smooth boundaries, for instance.

Moreover, Hadwiger’s theorem can easily be extended to cover polyconvex sets, that is, finite unions of convex sets. Any figure can be represented to arbitrarily high accuracy by a polyconvex set. For example, the text you’re reading now is a finite union of square or round pixels, and therefore polyconvex.

I’ll stick to the convex setting, though. And by “convex set” I’ll always mean a compact convex subset of ${ℝ}^n$. Here $n$ is a natural number that I’ll regard as fixed.

A “measure of size” will be a map

$$\varphi :\{\mathrm{convex}\mathrm{subsets}\mathrm{of} {ℝ}^n\}\to ℝ$$

satisfying three properties.

1. It’s a valuation. This means that $\varphi (\varnothing )=0$ and that $\varphi$ satisfies the inclusion-exclusion principle:

$$\varphi (X\cup Y)=\varphi (X)+\varphi (Y)-\varphi (X\cap Y)$$

whenever $X$ and $Y$ are convex sets with $X\cup Y$ convex. (Then $X\cap Y$ is automatically convex.)

2. It’s invariant. More exactly, it’s invariant with respect to isometries: for any element $g$ of the isometry group of ${ℝ}^n$, and any convex set $X$, we have $\varphi (gX)=\varphi (X)$.

I want to emphasize that ${ℝ}^n$ is being treated here as a metric space only (with the Euclidean metric). These are not necessarily linear isometries. So invariance means invariance with respect to not only rotations and reflections, but also translations.

3. It’s continuous. More exactly, it’s continuous with respect to the Hausdorff metric.

What’s the Hausdorff metric? Well, given a metric space $A$ (here, ${ℝ}^n$), the Hausdorff metric is a metric on the set of nonempty compact subsets of $A$. For $X\subseteq A$ and $\delta >0$, write $X[\delta ]$ for the set of points within distance $\delta$ of some point of $X$. Then the Hausdorff distance between $X$ and $Y$ is the least $\delta$ such that $X\subseteq Y[\delta ]$ and $Y\subseteq X[\delta ]$.

So, the informal phrase “measure of size” really means “continuous invariant valuation on convex sets”.

Let’s have some examples.

• $n$-dimensional Lebesgue measure is a continuous invariant valuation on convex subsets of ${ℝ}^n$, for any $n$.
• Euler characteristic is a continuous invariant valuation on convex subsets of ${ℝ}^n$, for any $n$. Since we’re dealing only with convex sets, it’s extremely simple: $\chi (X)=1$ if $X$ is nonempty, and $\chi (X)=0$ if $X$ is empty. (You might think that “Euler characteristic” is a pretentious name for what is basically the function with constant value $1$. But if you venture outside the world of convex sets—to polyconvex sets, for instance—you’ll see that it really does deserve the name.)
• Perimeter is a continuous invariant valuation on convex subsets of ${ℝ}^2$. It’s worth spending a moment drawing a mental picture to convince yourself that perimeter really is a valuation.
• Similarly, surface area is a continuous invariant valuation on convex subsets of ${ℝ}^3$.

Actually, I don’t think it’s obvious how surface area, or even perimeter, should be defined in the full generality of convex, not necessarily smooth, sets. We’ll see how later. But for the moment, it should be intuitively plausible that they’re examples of continuous invariant valuations.

The examples listed have something in common: they’re homogeneous. A valuation $\varphi$ is homogeneous of degree $i$ if

$$\varphi (tX)=t^i\varphi (X)$$

for all convex $X$ and all $t>0$, where $tX=\{tx:x\in X\}$. For example, Euler characteristic is homogeneous of degree $0$.

It’s clear from the definitions that any real linear combination of continuous invariant valuations is again a continuous invariant valuation. For example,

$$\mathrm{area}-5\cdot \mathrm{perimeter}$$

is a perfectly good continuous invariant valuation on convex subsets of ${ℝ}^2$. It might seem strange, because whereas area is naturally measured in metres squared and perimeter in metres, this valuation has no natural units of measurement. But it’s a valuation, all the same.

I’ll write ${\mathrm{Val}}_n$ for the real vector space of continuous invariant valuations on convex subsets of ${ℝ}^n$.

What measures of size are there?

Hadwiger’s theorem will describe the vector space ${\mathrm{Val}}_n$. It will do more than just describing it up to isomorphism, that is, specifying $\dim ({\mathrm{Val}}_n)$. But it will in particular tell us $\dim ({\mathrm{Val}}_n)$.

Let’s try to guess the sequence

$$\dim ({\mathrm{Val}}_0), \dim ({\mathrm{Val}}_1), \dim ({\mathrm{Val}}_2), \dots$$

by working out the first few entries.

For $n=0$, we’re looking at valuations on convex subsets of ${ℝ}^0$. Well, ${ℝ}^0$ is a singleton, so has just two convex subsets: the empty set and itself. A valuation is obliged to take value $0$ on the empty set, so we have just one degree of freedom: its value on the subset ${ℝ}^0\subseteq {ℝ}^0$. This can be any real number. Thus, ${\mathrm{Val}}_0\cong ℝ$ and $\dim ({\mathrm{Val}}_0)=1$.

For $n=1$, we’ve already seen two different valuations: Euler characteristic and Lebesgue measure (length). One is homogeneous of degree $0$, and the other is homogeneous of degree $1$. It follows that they’re linearly independent, and so $\dim ({\mathrm{Val}}_1)\ge 2$. Now, the only convex subsets of $ℝ$ are the empty set and compact intervals, and from that you can convince yourself that a continuous invariant valuation is determined by its values on $\{0\}$ and $[0,1]$. So $\dim ({\mathrm{Val}}_1)\le 2$, giving $\dim ({\mathrm{Val}}_1)=2$.

For $n=2$, we’ve seen three different valuations: Euler characteristic, perimeter, and 2-dimensional Lebesgue measure (area). They’re homogeneous of degrees $0$, $1$ and $2$, and therefore linearly independent. So $\dim ({\mathrm{Val}}_2)\ge 3$. Things get harder now: although no other candidates suggest themselves, it’s not so obvious that these really are the only ones. Nonetheless, it’s true: every continuous invariant valuation on ${ℝ}^2$ is a linear combination of the ones mentioned. So $\dim ({\mathrm{Val}}_2)=3$.

The sequence therefore begins

$$1,2,3,\dots .$$

The obvious guess is that $\dim ({\mathrm{Val}}_n)=n+1$ for all $n$. Moreover, we’ve seen that for small values of $n$, there’s a basis consisting of one homogeneous valuation of degree $i$ for each $i=0,1,\dots ,n$. So it’s tempting to conjecture that this pattern continues indefinitely.

It’s tempting—and true. But that’s not obvious.

In fact, we find ourselves in unfamiliar territory as soon as we move up to $n=3$. We have a continuous invariant valuation that’s homogeneous of degree $0$: Euler characteristic. We have one of degree $2$: surface area. And we have one of degree $3$: volume. But we’re missing one. How can we cook up a measure of size of convex subsets of ${ℝ}^3$ that’s homogeneous of degree $1$—that is, measured in metres?

Here’s how to do it. Let $X$ be a convex subset of ${ℝ}^3$.

• Choose at random a line $L$ through the origin.
• Take the orthogonal projection ${\pi }_{L}X$ of $X$ onto $L$, which is a line segment.
• Take the length of ${\pi }_{L}X$.

The expected value of that length is our $1$-dimensional measure of $X$. It’s called the mean width of $X$. If you want to understand this stuff more deeply, you can take a moment to convince yourself that mean width really is a continuous invariant valuation—or you can just take my word for it.

That covers $n=3$: we’ve constructed continuous invariant valuations of degrees $0$, $1$, $2$ and $3$. What about general $n$?

Our mission is to construct continuous invariant valuations

$$V_0,V_1,\dots ,V_n$$

where $V_i$ is homogeneous of degree $i$. Really I should be writing “$V_{n,i}$” instead of $V_i$, because the valuations depend on $n$ as well as $i$; but for reasons I’ll explain later, it’s OK not to.

Now we just imitate the definition of mean width. There $n=3$ and $i=1$; here $n$ is any natural number and $0\le i\le n$. Take a convex subset $X\subseteq {ℝ}^n$. For a $i$-dimensional linear subspace $P$, write ${\pi }_P$ for orthogonal projection onto $P$. Informally, $V_i(X)$ is

the expected value of $\mathrm{Vol}({\pi }_{P}X)$ for a random $i$-dimensional linear subspace $P$ of ${ℝ}^n$

(up to a scale factor). Here $\mathrm{Vol}$ denotes $i$-dimensional Lebesgue measure on $P\cong {ℝ}^i$.

Formally, write ${\mathrm{Gr}}_{n,i}$ for the space of all $i$-dimensional linear subspaces of ${ℝ}^n$ (“Gr” for Grassmannian). There is a natural action of the orthogonal group $O(n)$ on ${\mathrm{Gr}}_{n,i}$, and it’s a fact that there’s a unique-up-to-scaling $O(n)$-invariant measure on ${\mathrm{Gr}}_{n,i}$. Then

$$V_i(X)=c_{n,i}{\int }_{{\mathrm{Gr}}_{n,i}}\mathrm{Vol}({\pi }_{P}X)dP$$

where $c_{n,i}$ is a positive constant. I’ll come back to that constant in a moment.

Example  This construction gives a 2-dimensional valuation $V_2$ on convex subsets of ${ℝ}^3$: it’s the expected area of the shadow cast on a random plane. But we’ve already seen another 2-dimensional valuation: surface area. Hadwiger’s theorem is going to tell us that these two measures must be the same up to a scalar factor.

You can work out what the factor is by considering the unit ball. The expected area of the shadow is $\pi$, whereas its surface area is $4\pi$. So for any convex body in three-dimensional space, the expected area of the shadow cast is a quarter of its surface area. This is known as “Cauchy’s theorem”.

What about that constant $c_{n,i}$? Any choice gives us a continuous invariant valuation, but some choices are more convenient than others. Here’s the one I like best. It turns out that there’s a unique family $(c_{n,i}{)}_{0\le i\le n}$ of constants with the following two properties:

1. For all $n$, the valuation $V_n$ on ${ℝ}^n$ is volume (Lebesgue measure).
2. Let $X$ be a subset of ${ℝ}^n$, and let $0\le i\le n$. Embed ${ℝ}^n$ into ${ℝ}^{n+1}$ in the usual way. Then the value of $V_i(X)$ does not depend on whether $X$ is viewed as a subset of ${ℝ}^n$ or of ${ℝ}^{n+1}$. (This is what makes it safe to write $V_i$ rather than $V_{n,i}$.)

With this normalization, the valuation $V_i$ is called the $i$th intrinsic volume, for reasons that I hope are self-explanatory.

Why are these the only measures?

It’s time to state Hadwiger’s theorem formally:

Theorem (Hadwiger)  Let $n\in \mathbb{N}$. Then the vector space ${\mathrm{Val}}_n$ has dimension $n+1$, and the intrinsic volumes $V_0,\dots ,V_n$ are a basis.

It’s a corollary that the only continuous invariant valuations that are homogeneous of degree $i$ are the scalar multiples of $V_i$. (We implicitly used this corollary in the example with surface area and shadows.) That’s just because a linear combination of valuations that are homogeneous of different degrees can never be homogeneous, except in the most trivial way. So $V_0,\dots ,V_n$ is a canonical basis, up to scaling.

What about the proof? Hadwiger’s own proof is said to have been extremely involved. Dan Klain simplified it enormously in the mid-1990s. His original paper is here, and you can find a nice account of it in the book Introduction to Geometric Probability by Klain and Gian-Carlo Rota. I gather that it was simplified further in a 2004 paper of Beifang Chen, but I haven’t seen that.

Here’s a very rough outline, based on my understanding of Klain’s proof. It’s easy to see that $V_0,\dots ,V_n$ are linearly independent: just test against the $i$-dimensional cube for each $i=0,\dots ,n$. The work is to show that they span ${\mathrm{Val}}_n$: that is, every continuous invariant valuation is a linear combination of the intrinsic volumes.

What this boils down to is a theorem characterizing volume. Say that a valuation on ${ℝ}^n$ is simple if it takes value zero on all sets of dimension $<n$. For example, $V_n$, Lebesgue measure, is simple, as are all its scalar multiples. The volume characterization theorem states the converse: every simple continuous invariant valuation is a scalar multiple of $V_n$. This must be true if Hadwiger’s theorem is to hold, and it’s not too hard to reduce Hadwiger’s theorem to this case.

To prove the volume characterization theorem, you have to get out the scissors and glue. Let’s try it for $n=2$. Take a simple continuous invariant valuation, $\varphi$. We may assume that $\varphi ([0,1{]}^2)=0$: for if not, subtract from $\varphi$ a suitable scalar multiple of area. So, we know that $\varphi$ takes value zero on both the square and all convex sets of dimension $<2$, and our task is to show that $\varphi$ is zero on all convex sets.

Chop the square $[0,1{]}^2$ into four smaller squares of equal size. Using simplicity, invariance, and the valuation property, we find that $\varphi ([0,1/2{]}^2)=0$. The same kind of cutting and pasting argument shows that $\varphi (X)=0$ whenever $X$ is a rectangle with rational side-lengths. By continuity, the same is true for all rectangles $X$.

Now take a rectangle and cut it down the diagonal. Arguing in the same way, we deduce that $\varphi (X)=0$ whenever $X$ is a right-angled triangle. A couple more steps gives you the same thing for all triangles. It follows that $\varphi (X)=0$ for all convex polygons $X$. And the space of convex polygons is dense in the space of convex subsets of ${ℝ}^2$, so by continuity, $\varphi$ is identically zero.

Given that sketch of $n=2$, you can see why it’s no mean feat to produce a graceful proof of the general case. I wouldn’t call Klain’s proof “graceful”, actually, but it’s pretty short.

Next time:  What happens if you replace Euclidean space by another metric space?