## June 29, 2011

#### 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 ${ℝ}^{n}$. For example, perimeter and area are both ways of measuring the size of (sufficiently nice) subsets of ${ℝ}^{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 ${ℝ}^{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

satisfying three properties.

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

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

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 \left(gX\right)=\varphi \left(X\right)$.

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\left[\delta \right]$ 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\left[\delta \right]$ and $Y\subseteq X\left[\delta \right]$.

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 \left(X\right)=1$ if $X$ is nonempty, and $\chi \left(X\right)=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 \left(tX\right)={t}^{i}\varphi \left(X\right)$

for all convex $X$ and all $t>0$, where $tX=\left\{tx:x\in X\right\}$. 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 $\mathrm{dim}\left({\mathrm{Val}}_{n}\right)$. But it will in particular tell us $\mathrm{dim}\left({\mathrm{Val}}_{n}\right)$.

Let’s try to guess the sequence

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 $\mathrm{dim}\left({\mathrm{Val}}_{0}\right)=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 $\mathrm{dim}\left({\mathrm{Val}}_{1}\right)\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 $\left\{0\right\}$ and $\left[0,1\right]$. So $\mathrm{dim}\left({\mathrm{Val}}_{1}\right)\le 2$, giving $\mathrm{dim}\left({\mathrm{Val}}_{1}\right)=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 $\mathrm{dim}\left({\mathrm{Val}}_{2}\right)\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 $\mathrm{dim}\left({\mathrm{Val}}_{2}\right)=3$.

The sequence therefore begins

$1,2,3,\dots .$

The obvious guess is that $\mathrm{dim}\left({\mathrm{Val}}_{n}\right)=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}\left(X\right)$ is

the expected value of $\mathrm{Vol}\left({\pi }_{P}X\right)$ 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\left(n\right)$ on ${\mathrm{Gr}}_{n,i}$, and it’s a fact that there’s a unique-up-to-scaling $O\left(n\right)$-invariant measure on ${\mathrm{Gr}}_{n,i}$. Then

${V}_{i}\left(X\right)={c}_{n,i}{\int }_{{\mathrm{Gr}}_{n,i}}\mathrm{Vol}\left({\pi }_{P}X\right)\phantom{\rule{thinmathspace}{0ex}}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 $\left({c}_{n,i}{\right)}_{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}\left(X\right)$ 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 ℕ$. 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 $. 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 \left(\left[0,1{\right]}^{2}\right)=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 $\left[0,1{\right]}^{2}$ into four smaller squares of equal size. Using simplicity, invariance, and the valuation property, we find that $\varphi \left(\left[0,1/2{\right]}^{2}\right)=0$. The same kind of cutting and pasting argument shows that $\varphi \left(X\right)=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 \left(X\right)=0$ whenever $X$ is a right-angled triangle. A couple more steps gives you the same thing for all triangles. It follows that $\varphi \left(X\right)=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?

Posted at June 29, 2011 2:54 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2413

### 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.

Posted by: Allen Knutson on June 29, 2011 5:36 AM | Permalink | Reply to this

### Re: Hadwiger’s Theorem, Part 1

Interesting point. Why, for instance, is there no $1.7$-dimensional measure on convex subsets of ${ℝ}^{2}$?

(From now on I’ll use “$d$-dimensional measure” as a synonym for “continuous invariant valuation, homogeneous of degree $d$”.)

I think the answer is very much to do with the nature of convex sets. If we were allowing fractal subsets of the plane, we should probably have $1.7$-dimensional measures available.

At the end of my post, I said that the kernel of the proof of Hadwiger’s theorem is the following result, which I’ll state here for $n=2$:

Let $\varphi$ be a continuous invariant valuation on ${ℝ}^{2}$ that vanishes on convex sets of dimension $\le 1$. Then $\varphi$ is a scalar multiple of area (and in particular is $2$-dimensional).

(I didn’t say what the “dimension” of a convex set was. It’s simply the dimension of the smallest affine subspace that contains it.)

The proof of this result should reveal why we can’t have a $1.7$-dimensional measure, since any such would vanish on sets of dimension $\le 1$. And the proof has two steps:

1. Prove it for convex polygons, by a cutting and pasting argument.
2. Conclude that it’s true in general, by continuity and the fact that convex polygons are dense in the space of all convex subsets of ${ℝ}^{2}$.

I think we can see our answer in the first step. Just consider dividing the square $\left[0,1{\right]}^{2}$ into four smaller squares. Since the intersections of those smaller squares are cells of dimension $\le 1$, we have $\varphi \left(\left[0,1{\right]}^{2}\right)=4\varphi \left(\left[0,1/2{\right]}^{2}\right),$ that is, $\varphi \left(2X\right)={2}^{2}\varphi \left(X\right)$ where $X=\left[0,1/2{\right]}^{2}$. But if $\varphi$ is $1.7$-dimensional then also $\varphi \left(2X\right)={2}^{1.7}\varphi \left(X\right).$ So $\varphi \left(X\right)=0$. Since $\varphi$ is a scalar multiple of area, this forces $\varphi =0$.

Perhaps the “integer eigenvalue” phenomenon comes down to the following.

A convex polytope in ${ℝ}^{n}$ is most easily defined as the convex hull of a finite subset of ${ℝ}^{n}$. That definition doesn’t mention the integers. But it’s a fact that any convex polytope can be represented as a gluing-together of simplices along faces. Those simplices and their faces have integer dimensions (in $\left\{0,\dots ,n\right\}$). So the integers are hiding in the definition of convex polytope.

Posted by: Tom Leinster on June 29, 2011 8:43 PM | Permalink | Reply to this

### Re: Hadwiger’s Theorem, Part 1

McMullen a similar result in his classic paper on the polytope algebra. Here is how I think of his proof.

The differences between McMullen’s setup and this one are (1) McMullen only works with sets that are finite unions of (bounded) convex polytopes (2) There is no continuity condition (3) McMullen only requires invariance under translation, not under rotations. I haven’t thought about how alter the argument for the new setup.

Let $A$ be the abelian group spanned by convex polytopes, modulo the relations that $\left[P\right]+\left[Q\right]=\left[P\cup Q\right]+\left[P\cap Q\right]$ and $\left[P\right]=\left[\tau \left(P\right)\right]$ for every translation $\tau$. So valuations are linear functions $A\to ℝ$. Let $\delta \left(t\right):A\to A$ be dilation by $t$.

Lemma: Let $\sigma$ be a simplex. Then there is a finite rank subgroup $W\left(\sigma \right)$ of $A$ such that, for every positive integer $t$, $\delta \left(t\right)$ preserves $W\left(\sigma \right)$, and the action of $\delta \left(t\right)$ on $W\left(\sigma \right)$ is by a matrix whose entries are polynomials in $t$ of degree $\le n$.

Proof: Without loss of generality, $\sigma$ is the convex hull of the origin and the $n$ basis vectors. Consider the hyperplane arrangement in ${ℝ}^{n}$ made up of the hyperplanes ${\sum }_{i\in I}{x}_{i}=k$, for $I$ any subset of $\left\{1,2,\dots ,n\right\}$ and any integer $k$. This is the type $\stackrel{˜}{A}$ affine hyperplane arrangement. Up to translation, there are finitely many faces in this hyperplane arrangement. Let $W$ be the span of these faces.

For any positive integer $t$, and any face $\tau$ in this hyperplane arrangement, $\delta \left(t\right)\tau$ is a union of faces of this hyperplane arrangement. A direct combinatorial computation shows that the number of faces of each type is a polynomial in $t$. QED

Let the above matrix be $g\left(t\right)$. So $g\left(\mathrm{tu}\right)=g\left(t\right)g\left(u\right)$ and $g\left(1\right)=\mathrm{Id}$. This means that $g$ defines a map from ${𝔾}_{m}$ to $\mathrm{GL}\left(W\right)$. So $W$ must break up as a sum of weight spaces. Moreover, all the entries of $g$ are polynomials (not just Laurent polynomials), so the weight spaces are non-negative.

Now, this handles the action on $W$. Since every polytope is triangulable, the space $A$ is spanned by classes of simplices, and we see that any finite dimensional subspace of $A$ is contained in a sum of such $W\left(\sigma \right)$’s. From here, some formal nonsense finishes you off.

Remark: The matrix $g$ is block upper triangular because, if $\tau$ has dimension $d$, then $\delta \left(t\right)\tau$ is made up of faces of dimension $\le d$. Let $U$ be the quotient of $W$ by the lower dimensional faces. Then $U$ is naturally indexed by ${S}_{n}$ (the affine symmetric group modulo translations). The action of dilation by $t$ on ${S}_{n}$ is (up to a normalizing factor) precisely the action of performing a random $t$-handed riffle shuffle according to the model of Bayer and Diaconis. The polynomiality statement is theorem 3 in their paper, where their $\alpha$ is our $t$, and the denominator reflects their different normalization.

Posted by: David Speyer on June 29, 2011 8:47 PM | Permalink | Reply to this

### Re: Hadwiger’s Theorem, Part 1

An example might be helpful. Let $n=2$, and let $\sigma$ be a triangle. Then a basis for $W\left(\sigma \right)$ will be

${e}_{1}$: The class of $\sigma$.

${e}_{2}$: The class of $\sigma$ rotated by $\pi$ radians.

${e}_{3}$: The class of one side of $\sigma$ (a line segment).

${e}_{4}$: The class of the second side of $\sigma$.

${e}_{5}$: The class of the third side of $\sigma$.

${e}_{6}$: The class of a point.

We have $\delta \left(t\right)\left({e}_{6}\right)={e}_{6}$. We have $\delta \left(t\right){e}_{3}=t{e}_{3}-\left(t-1\right){e}_{6}$, and similarly for ${e}_{4}$ and ${e}_{5}$. (Draw a picture of $t$ times a line segment cut up into $t$ pieces.) And, finally,

$\delta \left(t\right){e}_{1}=\left(\genfrac{}{}{0}{}{t+1}{2}\right){e}_{1}+\left(\genfrac{}{}{0}{}{t}{2}\right){e}_{2}-\left(\genfrac{}{}{0}{}{t}{2}\right)\left({e}_{3}+{e}_{4}+{e}_{5}\right)+\left(\genfrac{}{}{0}{}{t-1}{2}\right){e}_{6}.$

So the matrix $g\left(t\right)$ is

$\left(\begin{array}{cccccc}\left(\genfrac{}{}{0}{}{t+1}{2}\right)& \left(\genfrac{}{}{0}{}{t}{2}\right)& -\left(\genfrac{}{}{0}{}{t}{2}\right)& -\left(\genfrac{}{}{0}{}{t}{2}\right)& -\left(\genfrac{}{}{0}{}{t}{2}\right)& \left(\genfrac{}{}{0}{}{t-1}{2}\right)\\ \left(\genfrac{}{}{0}{}{t}{2}\right)& \left(\genfrac{}{}{0}{}{t+1}{2}\right)& -\left(\genfrac{}{}{0}{}{t}{2}\right)& -\left(\genfrac{}{}{0}{}{t}{2}\right)& -\left(\genfrac{}{}{0}{}{t}{2}\right)& \left(\genfrac{}{}{0}{}{t-1}{2}\right)\\ & & t& & & -\left(t-1\right)\\ & & & t& & -\left(t-1\right)\\ & & & & t& -\left(t-1\right)\\ & & & & & 1\end{array}\right)$

Posted by: David Speyer on June 29, 2011 9:03 PM | Permalink | Reply to this

### Re: Hadwiger’s Theorem, Part 1

David, something’s wrong with the statement of your lemma: the hypothesis mentions $\sigma$, but the conclusion doesn’t. (So you could always take $W\left(\sigma \right)$ to be trivial.) I guess you also mean to require that $\left[\sigma \right]\in W\left(\sigma \right)$?

Posted by: Tom Leinster on June 30, 2011 12:27 AM | Permalink | Reply to this

### Re: Hadwiger’s Theorem, Part 1

Yup, thanks for the correction.

Posted by: David Speyer on June 30, 2011 11:53 AM | Permalink | Reply to this

### Re: Hadwiger’s Theorem, Part 1

Thanks, David. Actually, I was just about to write a second answer to Allen’s comment, involving a different classic paper by McMullen:

Peter McMullen, Valuations and Euler-type relations on certain classes of convex polytopes. Proceedings of the London Mathematical Society 35 (1977), 113–135.

Here he studies the vector space ${\mathrm{TVal}}_{n}$ of continuous translation-invariant valuations on convex ($=$ compact convex) subsets of ${ℝ}^{n}$. This is much bigger than the space ${\mathrm{Val}}_{n}$ involved in Hadwiger’s theorem, where invariance under rotations and reflections is demanded too. For example, if we fix any compact convex set $K$ then

$X↦\mathrm{Vol}\left(X+K\right)$

is a continuous translation-invariant valuation, where $+$ denotes Minkowski sum. So it’s easy to see that ${\mathrm{TVal}}_{n}$ is infinite-dimensional.

Even so, McMullen showed that it’s spanned by homogeneous valuations. That is, there’s a direct sum decomposition

${\mathrm{TVal}}_{n}=\underset{i=0}{\overset{n}{⨁}}{\mathrm{TVal}}_{n}\left(i\right)$

where ${\mathrm{TVal}}_{n}\left(i\right)$ consists of the valuations that are homogeneous of degree $i$.

He derives this as a corollary of the following theorem.

Theorem  Let $\varphi$ be a continuous translation-invariant valuation on convex subsets of ${ℝ}^{n}$. Let ${X}_{1},\dots ,{X}_{k}$ be a finite sequence of convex subsets of ${ℝ}^{n}$. Then the function

$\left({t}_{1},\dots ,{t}_{k}\right)↦\varphi \left({t}_{1}{X}_{1}+\cdots +{t}_{k}{X}_{k}\right)$

(${t}_{i}\ge 0$) is a polynomial of degree at most $n$.

Again, the ‘$+$’ here means Minkowski sum. It’s a powerful theorem, nontrivial even for $k=1$.

I’m sure this is related to the results you mention, David, but I haven’t had time yet to think about how.

Posted by: Tom Leinster on June 29, 2011 9:12 PM | Permalink | Reply to this

### Re: Hadwiger’s Theorem, Part 1

I think that, for our purposes, the two McMullen papers are pretty similar. They both prove semisimple decomposition under dilation, and they both do the proof by reducing to a simplex and making explicit combinatorial counts.

In the paper you cite, there is a continuity hypothesis, and we are allowed non-polyhedral sets, so that makes it a little closer to Hadwiger. In the paper I cite, there is more discussion of the additional algebra structure coming from the Minkowski sum.

Posted by: David Speyer on June 29, 2011 9:39 PM | Permalink | Reply to this

### Re: Hadwiger’s Theorem, Part 1

This is very interesting to me as it seems to have some clear analogies to calculations of entanglement entropy in quantum systems. Suppose we have a quantum field theory. The entanglement entropy of some given region X in the ground state gives a mapping from regions (not necessarily convex) to nonnegative reals. If the field theory is translation and rotation invariant, this obeys condition (2). Condition (3) is more subtle if there are divergences, but let us assume it is true. Condition (1) in this language is the statement that strong subadditivity is saturated for any three regions in the ground state. So, we are left with only a few choices for the ground state entropy for such systems, and the things written are basically known terms (area law term=perimeter and topological term=Euler characteristic). Some subtleties are that in reality we should be interested in lattice theories, not field theories, where we only have some discrete translations and rotations (this might be associated with the fact that we also get corner terms). And we often won’t have exact saturation of subadditivity. But to me the analogy is fairly close.

Posted by: matt on June 29, 2011 7:49 PM | Permalink | Reply to this

### Re: Hadwiger’s Theorem, Part 1

I should have mentioned: five years ago, Dan Piponi wrote a nice pair of posts about Hadwiger’s theorem (1, 2), with connections to the kind of counting/cardinality questions that John’s also been interested in.

Posted by: Tom Leinster on June 30, 2011 1:46 PM | Permalink | Reply to this
Read the post Definitions of Ultrafilter
Weblog: The n-Category Café
Excerpt: Several equivalent definitions of ultrafilter, including a particularly simple one that I'd like to find a reference for.
Tracked: July 2, 2011 11:54 PM

### Re: Hadwiger’s Theorem, Part 1

In the paper “Gitterpunktanzahl im Simplex und Wills’sche Vermutung.” (German) Math. Ann. 239 (1979), no. 3, 271-288. He diproved in dimensions greater than 441 a conjecture by Wills relating “lattice-points valuations” with quermassintegrals.
(A related paper “Betke, Ulrich; Henk, Martin
“Intrinsic volumes and lattice points of crosspolytopes.”
Monatsh. Math. 115 (1993), no. 1-2, 27-33. )

Posted by: Gil Kalai on July 16, 2011 6:51 PM | Permalink | Reply to this

### Re: Hadwiger’s Theorem, Part 1

Thanks, Gil. So, he was still flourishing in 1979!

Posted by: Tom Leinster on July 17, 2011 4:26 AM | Permalink | Reply to this