### Hadwiger’s Theorem, Part 1

#### Posted by Tom Leinster

Hugo Hadwiger was a Swiss mathematician active in the middle
part of the 20th century. An old-fashioned encyclopaedia might follow his name
with something like “(*fl.* 1930–1970)”. Here
“*fl.*”
means “flourished”. I love that usage. (Are you flourishing right now?) Here’s a photo of Hadwiger,
flourishing:

Hadwiger proved—among other things—a really fundamental theorem on the geometry of Euclidean space. Simon and I have both mentioned it on this blog before, but it’s so beautiful that it deserves its own space.

It’s all about ways of measuring the size of subsets of $\mathbb{R}^n$. For
example, *perimeter* and *area* are both ways of measuring the size
of (sufficiently nice) subsets of $\mathbb{R}^2$. Hadwiger’s theorem neatly
classifies all such measures of size.

This is the first of a pair of posts. In this one, I’ll take my time explaining Hadwiger’s original theorem. In the next one, I’ll tell you something new.

Hadwiger’s theorem says something like this:

The only measures of size for subsets of $\mathbb{R}^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 $\mathbb{R}^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 $\mathbb{R}^n$. Here $n$ is a natural number
that I’ll regard as fixed.

A “measure of size” will be a map

$\phi: \{{convex subsets of } \mathbb{R}^n\} \to \mathbb{R}$

satisfying three properties.

1. It’s a

valuation. This means that $\phi(\emptyset) = 0$ and that $\phi$ satisfies the inclusion-exclusion principle:$\phi(X \cup Y) = \phi(X) + \phi(Y) - \phi(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 $\mathbb{R}^n$, and any convex set $X$, we have $\phi(g X) = \phi(X)$.I want to emphasize that $\mathbb{R}^n$ is being treated here as a metric space only (with the Euclidean metric). These are not necessarily

linearisometries. 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, $\mathbb{R}^n$), the Hausdorff metric is a metric on the set of nonempty compact subsets of $A$. For $X \subseteq A$ and $\delta \gt 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 $\mathbb{R}^n$, for any $n$.
- Euler characteristic is a continuous invariant valuation on convex subsets of $\mathbb{R}^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 $\mathbb{R}^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 $\mathbb{R}^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
$\phi$ is **homogeneous** of degree $i$ if

$\phi(t X) = t^i \phi(X)$

for all convex $X$ and all $t \gt 0$, where $t X = \{ t x : 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,

$area - 5\cdot perimeter$

is a perfectly good continuous invariant valuation on convex subsets of $\mathbb{R}^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 $Val_n$ for the real vector space of continuous invariant valuations on convex subsets of $\mathbb{R}^n$.

### What measures of size are there?

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

Let’s try to guess the sequence

$dim(Val_0), dim(Val_1), dim(Val_2), \ldots$

by working out the first few entries.

For $n = 0$, we’re looking at valuations on convex subsets of $\mathbb{R}^0$. Well, $\mathbb{R}^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 $\mathbb{R}^0 \subseteq \mathbb{R}^0$. This can be any real number. Thus, $Val_0 \cong \mathbb{R}$ and $dim(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(Val_1) \geq 2$. Now, the only convex subsets of $\mathbb{R}$ 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(Val_1) \leq 2$, giving $dim(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(Val_2) \geq 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 $\mathbb{R}^2$ is a linear combination of the ones mentioned. So $dim(Val_2) = 3$.

The sequence therefore begins

$1, 2, 3, \ldots.$

The obvious guess is that $dim(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, \ldots, 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 $\mathbb{R}^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 $\mathbb{R}^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, \ldots, 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 \leq i \leq n$. Take a convex subset $X \subseteq \mathbb{R}^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 $Vol(\pi_P X)$ for a random $i$-dimensional linear subspace $P$ of $\mathbb{R}^n$

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

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

$V_i(X) = c_{n, i} \int_{Gr_{n, i}} Vol(\pi_P X)\, d P$

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

ExampleThis construction gives a 2-dimensional valuation $V_2$ on convex subsets of $\mathbb{R}^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

anyconvex 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 \leq i \leq n}$ of constants with the following two properties:

- For all $n$, the valuation $V_n$ on $\mathbb{R}^n$ is volume (Lebesgue measure).
- Let $X$ be a subset of $\mathbb{R}^n$, and let $0 \leq i \leq n$. Embed $\mathbb{R}^n$ into $\mathbb{R}^{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 $\mathbb{R}^n$ or of $\mathbb{R}^{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 $Val_n$ has dimension $n + 1$, and the intrinsic volumes $V_0, \ldots, 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, \ldots, 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, \ldots, V_n$ are linearly independent: just test against the $i$-dimensional cube for each $i = 0, \ldots, n$. The work is to show that they span $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 $\mathbb{R}^n$ is **simple** if it takes value zero on all sets
of dimension $\lt 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, $\phi$. We may assume that $\phi([0, 1]^2) = 0$: for if not, subtract from $\phi$ a suitable scalar multiple of area. So, we know that $\phi$ takes value zero on both the square and all convex sets of dimension $\lt 2$, and our task is to show that $\phi$ 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 $\phi([0, 1/2]^2) = 0$. The same kind of cutting and pasting argument shows that $\phi(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 $\phi(X) = 0$ whenever $X$ is a right-angled triangle. A couple more steps gives you the same thing for all triangles. It follows that $\phi(X) = 0$ for all convex polygons $X$. And the space of convex polygons is dense in the space of convex subsets of $\mathbb{R}^2$, so by continuity, $\phi$ 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?

## Re: Hadwiger’s Theorem, Part 1

It seems clear that the scaling group should act on Val_n. It’s not clear to me (absent the theorem) why it acts semisimply, with integer eigenvalues.

That is, given a valuation v, we could let k = log_r v(r * unit cube), then let v’(X) = lim v(r*X) / r^k, and hope to show that v’ must be a multiple of V_k. But why must k be an integer (much less in 0..n)? Huh.