Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

June 29, 2011

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, with beer

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\mathbb{R}^n. For example, perimeter and area are both ways of measuring the size of (sufficiently nice) subsets of 2\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 n\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 n\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 n\mathbb{R}^n. Here nn is a natural number that I’ll regard as fixed.

A “measure of size” will be a map

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

satisfying three properties.

1. It’s a valuation. This means that ϕ()=0\phi(\emptyset) = 0 and that ϕ\phi satisfies the inclusion-exclusion principle:

ϕ(XY)=ϕ(X)+ϕ(Y)ϕ(XY) \phi(X \cup Y) = \phi(X) + \phi(Y) - \phi(X \cap Y)

whenever XX and YY are convex sets with XYX \cup Y convex. (Then XYX \cap Y is automatically convex.)

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

I want to emphasize that n\mathbb{R}^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 AA (here, n\mathbb{R}^n), the Hausdorff metric is a metric on the set of nonempty compact subsets of AA. For XAX \subseteq A and δ>0\delta \gt 0, write X[δ]X[\delta] for the set of points within distance δ\delta of some point of XX. Then the Hausdorff distance between XX and YY is the least δ\delta such that XY[δ]X \subseteq Y[\delta] and YX[δ]Y \subseteq X[\delta].

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

Let’s have some examples.

  • nn-dimensional Lebesgue measure is a continuous invariant valuation on convex subsets of n\mathbb{R}^n, for any nn.
  • Euler characteristic is a continuous invariant valuation on convex subsets of n\mathbb{R}^n, for any nn. Since we’re dealing only with convex sets, it’s extremely simple: χ(X)=1\chi(X) = 1 if XX is nonempty, and χ(X)=0\chi(X) = 0 if XX is empty. (You might think that “Euler characteristic” is a pretentious name for what is basically the function with constant value 11. 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\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 3\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 ii if

ϕ(tX)=t iϕ(X) \phi(t X) = t^i \phi(X)

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

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

area5perimeter area - 5\cdot perimeter

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

What measures of size are there?

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

Let’s try to guess the sequence

dim(Val 0), dim(Val 1), dim(Val 2),  dim(Val_0),  dim(Val_1),  dim(Val_2),  \ldots

by working out the first few entries.

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

For n=1n = 1, we’ve already seen two different valuations: Euler characteristic and Lebesgue measure (length). One is homogeneous of degree 00, and the other is homogeneous of degree 11. It follows that they’re linearly independent, and so dim(Val 1)2dim(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}\{0\} and [0,1][0, 1]. So dim(Val 1)2dim(Val_1) \leq 2, giving dim(Val 1)=2dim(Val_1) = 2.

For n=2n = 2, we’ve seen three different valuations: Euler characteristic, perimeter, and 2-dimensional Lebesgue measure (area). They’re homogeneous of degrees 00, 11 and 22, and therefore linearly independent. So dim(Val 2)3dim(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 2\mathbb{R}^2 is a linear combination of the ones mentioned. So dim(Val 2)=3dim(Val_2) = 3.

The sequence therefore begins

1,2,3,. 1, 2, 3, \ldots.

The obvious guess is that dim(Val n)=n+1dim(Val_n) = n + 1 for all nn. Moreover, we’ve seen that for small values of nn, there’s a basis consisting of one homogeneous valuation of degree ii for each i=0,1,,ni = 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=3n = 3. We have a continuous invariant valuation that’s homogeneous of degree 00: Euler characteristic. We have one of degree 22: surface area. And we have one of degree 33: volume. But we’re missing one. How can we cook up a measure of size of convex subsets of 3\mathbb{R}^3 that’s homogeneous of degree 11—that is, measured in metres?

Here’s how to do it. Let XX be a convex subset of 3\mathbb{R}^3.

  • Choose at random a line LL through the origin.
  • Take the orthogonal projection π LX\pi_L X of XX onto LL, which is a line segment.
  • Take the length of π LX\pi_L X.

The expected value of that length is our 11-dimensional measure of XX. It’s called the mean width of XX. 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=3n = 3: we’ve constructed continuous invariant valuations of degrees 00, 11, 22 and 33. What about general nn?

Our mission is to construct continuous invariant valuations

V 0,V 1,,V n V_0, V_1, \ldots, V_n

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

Now we just imitate the definition of mean width. There n=3n = 3 and i=1i = 1; here nn is any natural number and 0in0 \leq i \leq n. Take a convex subset X nX \subseteq \mathbb{R}^n. For a ii-dimensional linear subspace PP, write π P\pi_P for orthogonal projection onto PP. Informally, V i(X)V_i(X) is

the expected value of Vol(π PX)Vol(\pi_P X) for a random ii-dimensional linear subspace PP of n\mathbb{R}^n

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

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

V i(X)=c n,i Gr n,iVol(π PX)dP V_i(X) = c_{n, i} \int_{Gr_{n, i}} Vol(\pi_P X)\, d P

where c n,ic_{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 2V_2 on convex subsets of 3\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π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,ic_{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) 0in(c_{n, i})_{0 \leq i \leq n} of constants with the following two properties:

  1. For all nn, the valuation V nV_n on n\mathbb{R}^n is volume (Lebesgue measure).
  2. Let XX be a subset of n\mathbb{R}^n, and let 0in0 \leq i \leq n. Embed n\mathbb{R}^n into n+1\mathbb{R}^{n + 1} in the usual way. Then the value of V i(X)V_i(X) does not depend on whether XX is viewed as a subset of n\mathbb{R}^n or of n+1\mathbb{R}^{n + 1}. (This is what makes it safe to write V iV_i rather than V n,iV_{n, i}.)

With this normalization, the valuation V iV_i is called the iith 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 nn \in \mathbb{N}. Then the vector space Val nVal_n has dimension n+1n + 1, and the intrinsic volumes V 0,,V nV_0, \ldots, V_n are a basis.

It’s a corollary that the only continuous invariant valuations that are homogeneous of degree ii are the scalar multiples of V iV_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,,V nV_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,,V nV_0, \ldots, V_n are linearly independent: just test against the ii-dimensional cube for each i=0,,ni = 0, \ldots, n. The work is to show that they span Val nVal_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\mathbb{R}^n is simple if it takes value zero on all sets of dimension <n\lt n. For example, V nV_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 nV_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=2n = 2. Take a simple continuous invariant valuation, ϕ\phi. We may assume that ϕ([0,1] 2)=0\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 <2\lt 2, and our task is to show that ϕ\phi is zero on all convex sets.

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

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

Given that sketch of n=2n = 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

14 Comments & 4 Trackbacks

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.71.7-dimensional measure on convex subsets of 2\mathbb{R}^2?

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

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.71.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=2n = 2:

Let ϕ\phi be a continuous invariant valuation on 2\mathbb{R}^2 that vanishes on convex sets of dimension 1\leq 1. Then ϕ\phi is a scalar multiple of area (and in particular is 22-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.71.7-dimensional measure, since any such would vanish on sets of dimension 1\leq 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\mathbb{R}^2.

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

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

A convex polytope in n\mathbb{R}^n is most easily defined as the convex hull of a finite subset of n\mathbb{R}^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 {0,,n}\{0, \ldots, n\}). 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 AA be the abelian group spanned by convex polytopes, modulo the relations that [P]+[Q]=[PQ]+[PQ][P] + [Q] = [P \cup Q] + [P \cap Q] and [P]=[τ(P)][P] = [\tau(P)] for every translation τ\tau. So valuations are linear functions AA \to \mathbb{R}. Let δ(t):AA\delta(t): A \to A be dilation by tt.

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

Proof: Without loss of generality, σ\sigma is the convex hull of the origin and the nn basis vectors. Consider the hyperplane arrangement in n\mathbb{R}^n made up of the hyperplanes iIx i=k\sum_{i \in I} x_i = k, for II any subset of {1,2,,n}\{ 1, 2, \ldots, n \} and any integer kk. This is the type A˜\tilde{A} affine hyperplane arrangement. Up to translation, there are finitely many faces in this hyperplane arrangement. Let WW be the span of these faces.

For any positive integer tt, and any face τ\tau in this hyperplane arrangement, δ(t)τ\delta(t) \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 tt. QED

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

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

Remark: The matrix gg is block upper triangular because, if τ\tau has dimension dd, then δ(t)τ\delta(t) \tau is made up of faces of dimension d\leq d. Let UU be the quotient of WW by the lower dimensional faces. Then UU is naturally indexed by S nS_n (the affine symmetric group modulo translations). The action of dilation by tt on S nS_n is (up to a normalizing factor) precisely the action of performing a random tt-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 tt, 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=2n=2, and let σ\sigma be a triangle. Then a basis for W(σ)W(\sigma) will be

e 1e_1: The class of σ\sigma.

e 2e_2: The class of σ\sigma rotated by π\pi radians.

e 3e_3: The class of one side of σ\sigma (a line segment).

e 4e_4: The class of the second side of σ\sigma.

e 5e_5: The class of the third side of σ\sigma.

e 6e_6: The class of a point.

We have δ(t)(e 6)=e 6\delta(t) (e_6) = e_6. We have δ(t)e 3=te 3(t1)e 6\delta(t) e_3 = t e_3 - (t-1) e_6, and similarly for e 4e_4 and e 5e_5. (Draw a picture of tt times a line segment cut up into tt pieces.) And, finally,

δ(t)e 1=(t+12)e 1+(t2)e 2(t2)(e 3+e 4+e 5)+(t12)e 6.\delta(t) e_1 = \binom{t+1}{2} e_1 + \binom{t}{2} e_2 - \binom{t}{2} (e_3+e_4+e_5) + \binom{t-1}{2} e_6.

So the matrix g(t)g(t) is

((t+12) (t2) (t2) (t2) (t2) (t12) (t2) (t+12) (t2) (t2) (t2) (t12) t (t1) t (t1) t (t1) 1)\begin{pmatrix} \binom{t+1}{2} & \binom{t}{2} & -\binom{t}{2} & - \binom{t}{2} & - \binom{t}{2} & \binom{t-1}{2} \\ \binom{t}{2} & \binom{t+1}{2} & -\binom{t}{2} & - \binom{t}{2} & - \binom{t}{2} & \binom{t-1}{2} \\ & & t & & & -(t-1) \\ & & & t & & -(t-1) \\ & & & & t & -(t-1) \\ & & & & & 1 \end{pmatrix}

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(σ)W(\sigma) to be trivial.) I guess you also mean to require that [σ]W(σ)[\sigma] \in W(\sigma)?

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 TVal nTVal_n of continuous translation-invariant valuations on convex (== compact convex) subsets of n\mathbb{R}^n. This is much bigger than the space Val nVal_n involved in Hadwiger’s theorem, where invariance under rotations and reflections is demanded too. For example, if we fix any compact convex set KK then

XVol(X+K) X \mapsto Vol(X + K)

is a continuous translation-invariant valuation, where ++ denotes Minkowski sum. So it’s easy to see that TVal nTVal_n is infinite-dimensional.

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

TVal n= i=0 nTVal n(i) TVal_n = \bigoplus_{i = 0}^n TVal_n(i)

where TVal n(i)TVal_n(i) consists of the valuations that are homogeneous of degree ii.

He derives this as a corollary of the following theorem.

Theorem  Let ϕ\phi be a continuous translation-invariant valuation on convex subsets of n\mathbb{R}^n. Let X 1,,X kX_1, \ldots, X_k be a finite sequence of convex subsets of n\mathbb{R}^n. Then the function

(t 1,,t k)ϕ(t 1X 1++t kX k) (t_1, \ldots, t_k) \mapsto \phi(t_1 X_1 + \cdots + t_k X_k)

(t i0t_i \geq 0) is a polynomial of degree at most nn.

Again, the ‘++’ here means Minkowski sum. It’s a powerful theorem, nontrivial even for k=1k = 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

Hadwiger had a brilliant result in 1979.
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
Read the post Mixed Volume
Weblog: The n-Category Café
Excerpt: Several explanations of the mixed volume of convex bodies.
Tracked: August 26, 2011 1:14 AM
Read the post Hadwiger's Theorem, Part 2
Weblog: The n-Category Café
Excerpt: Generalizing Hadwiger's theorem to arbitrary metric spaces, especially R^n with the 1-norm.
Tracked: August 29, 2011 5:16 AM
Read the post Universal Measures
Weblog: The n-Category Café
Excerpt: Groemer's integral theorem recast as a universal property.
Tracked: September 14, 2011 2:20 AM

Re: Hadwiger’s Theorem, Part 1

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

Of course, this now raises the question of when he “languished”. Do we have any data on that?

Posted by: Todd Trimble on January 22, 2014 10:08 PM | Permalink | Reply to this

Re: Hadwiger’s Theorem, Part 1

Wow, what a memory! I should obviously have linked to this post, not women laughing alone with salad.

Posted by: Tom Leinster on January 22, 2014 10:30 PM | Permalink | Reply to this

Post a New Comment