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.

January 31, 2017

The Brunn-Minkowski Inequality

Posted by Tom Leinster

Let AA and BB be measurable subsets of n\mathbb{R}^n. Then

Vol(A+B) 1/nVol(A) 1/n+Vol(B) 1/n Vol(A + B)^{1/n} \geq Vol(A)^{1/n} + Vol(B)^{1/n}

where A+B={a+b:aA,bB}A + B = \{ a + b : a \in A, b \in B \}. This is the Brunn-Minkoswki inequality. It’s most often mentioned in the case where AA and BB are convex, but it’s true in the vast generality of measurable sets (except for \emptyset, where it obviously fails).

Here I want to explain just a few basic things about this inequality and its consequences. For instance, it easily implies the famous isoperimetric inequality: that among all sets with a given surface area, the one that maximizes the volume is the ball.

There’s a fantastic expository paper that covers everything I’m about to say and much, much more:

Richard Gardner, The Brunn-Minkowski inequality. Bulletin of the American Mathematical Society 39 (2002), 355-405.

Thanks to Mark Meckes for mentioning this paper to me years ago. Cognoscenti like him may prefer this earlier, longer version. Both versions contain, among other things, a nice short proof of the inequality (Section 4 of the published version and Section 6 of the longer version). But I won’t give the proof here, nor will I mention the conditions for equality to hold.

The term A+BA + B is known as a Minkowski sum. You can think of A+BA + B as AA smeared out in a pattern dictated by BB:

A+B= bB(A+b). A + B = \bigcup_{b \in B} (A + b).

For instance, if AA is an egg shape (green) and BB is a quadrilateral (blue) then A+BA + B looks like the entire shape here:

Minkowski sum of oval and quadrilateral

(When I wrote those words, I didn’t mean to invoke the mental image of smearing an egg around a table. But maybe it’s not such a bad image to have.) Or again, if AA is egg-like and BB is a line segment then A+BA + B looks like this:

Minkowski sum of oval and line segment

Of course, there’s also a complementary viewpoint: A+BA + B is BB smeared out in a pattern dictated by AA:

A+B= aA(a+B). A + B = \bigcup_{a \in A} (a + B).

In any case, an important observation is that

A+BA + B can have large volume even if AA and BB both have volume zero.

For instance, this happens in the plane when AA is a horizontal line segment and BB is a vertical line segment. There’s obviously no hope of getting an equation for Vol(A+B)Vol(A + B) in terms of Vol(A)Vol(A) and Vol(B)Vol(B). But this example suggests that we might be able to get an inequality, stating that Vol(A+B)Vol(A + B) is at least as big as some function of Vol(A)Vol(A) and Vol(B)Vol(B).

The Brunn-Minkowski inequality does this, but it’s really about linearized volume, Vol 1/nVol^{1/n}, rather than volume itself. If length is measured in metres then so is Vol 1/nVol^{1/n}. There’s also a much cruder corollary of Brunn-Minkowski that concerns actual volume. Take the Brunn-Minkowski inequality

Vol(A+B) 1/nVol(A) 1/n+Vol(B) 1/n Vol(A + B)^{1/n} \geq Vol(A)^{1/n} + Vol(B)^{1/n}

and raise each side to the power of nn. The right-hand side can be expanded using the binomial theorem, and throwing away all except the first and last terms gives

Vol(A+B)Vol(A)+Vol(B) Vol(A + B) \geq Vol(A) + Vol(B)

as a corollary of Brunn-Minkowski.

This is a much weaker statement than the Brunn-Minkowski inequality, because in deriving it we threw away a huge number of positive terms. But it’s interesting in its own right, and has an easy direct proof. Here’s an argument I was told by Joe Fu. I’ll indent it for easy skippability.

Let AA and BB be measurable subsets of n\mathbb{R}^n, and assume they’re both bounded. (Once we’ve proved the bounded case, it’s not hard to deduced the general case, but I’ll leave that as a puzzle.) We’re going to prove that A+BA + B contains almost-disjoint translates of AA and of BB, where by “almost disjoint” I mean that their intersection has measure zero. The inequality will follow.

The idea is that we shift AA as high as possible and BB as low as possible. Formally, define h: nh: \mathbb{R}^n \to \mathbb{R} by as h(x 1,,x n)=x nh(x_1, \ldots, x_n) = x_n. (That’s hh for “height”, but any other nonzero linear functional would work just as well.) Choose b +Bb^+ \in B maximizing h(b +)h(b^+) and a Aa^- \in A minimizing h(a )h(a^-). It’s enough to show that

(A+b +)(a +B) (A + b^+) \cap (a^- + B)

is a subset of a hyperplane, since then it has measure zero. So, let xx be any point in this intersection. We can write x=a+b +x = a + b^+ for some aAa \in A, and so

h(x)=h(a+b +)=h(a)+h(b +)h(a )+h(b +)=h(a +b +). h(x) = h(a + b^+) = h(a) + h(b^+) \geq h(a^-) + h(b^+) = h(a^- + b^+).

But we can also write x=a +bx = a^- + b for some bBb \in B, and a similar argument gives h(x)h(a +b +)h(x) \leq h(a^- + b^+). So we’ve shown that every x(A+b +)(a +B)x \in (A + b^+) \cap (a^- + B) belongs to the hyperplane h 1(h(a +b +))h^{-1}(h(a^- + b^+)), and that completes the proof.

That was a very weak consequence of the Brunn-Minkowski inequality, but here’s a more powerful and interesting one. In a slogan:

Brunn-Minkowski for small balls is the isoperimetric inequality.

In other words, if you take any A nA \subseteq \mathbb{R}^n, and take BB to be a ball of radius tending to zero, then the Brunn-Minkowski inequality becomes the isoperimetric inequality in n\mathbb{R}^n.

To explain this, I first need to explain what the isoperimetric inequality is. The word “isoperimetric” suggests the two-dimensional version: that among all subsets of 2\mathbb{R}^2 with a prescribed perimeter, the one with the greatest area is the disc. But I mean the general nn-dimensional version, which I’ll now state.

Every reasonable subset A nA \subseteq \mathbb{R}^n has a volume (its Lebesgue measure), which I’ll write now as V n(A)V_n(A). It also has a surface area, which I’ll write as V n1(A)V_{n - 1}(A). The isoperimetric inequality states that for nice enough subsets A nA \subseteq \mathbb{R}^n (and I’ll come back to what that means),

V n(A)V n(rB n) V_n(A) \leq V_n(r B^n)

where the radius rr is chosen so that

V n1(A)=V n1(rB n). V_{n - 1}(A) = V_{n - 1}(r B^n).

We can easily solve for rr in this last equation, using the fact that V n1V_{n - 1} is homogeneous of degree n1n - 1. After a little bit of elementary algebraic rearranging, we find an equivalent form of the isoperimetric inequality that doesn’t have an “rr” in it:

V n(A) 1/nV n1(A) 1/(n1)V n(B n) 1/nV n1(B n) 1/(n1) \frac{V_n(A)^{1/n}}{V_{n - 1}(A)^{1/(n -1)}} \leq \frac{V_n(B^n)^{1/n}}{V_{n - 1}(B^n)^{1/(n - 1)}}

for all A nA \subseteq \mathbb{R}^n.

This can be understood as follows.

Loosely speaking, the isoperimetric inequality says that the ratio of a shape’s volume to its surface area is greatest for balls. But we shouldn’t take the word “ratio” literally: for if we simply divided volume by surface area then we’d get a quantity measured in metres, so we could make it bigger simply by scaling the set up! What we want this ratio to be is a dimensionless quantity.

Since volume is measured in metres n{}^n and surface area is measured in metres n1{}^{n - 1}, we can get a dimensionless quantity by linearizing both things before we take the ratio. In other words, take the nnth root of the volume and the (n1)(n - 1)th root of surface area, so that both are measured in metres. Then the ratio will come out to be dimensionless.

(If you’re feeling perverse, you could instead take the (17/n)(17/n)th power of the volume and the (17/(n1))(17/(n - 1))th power of the surface area, then divide one by the other. This would be a dimensionless quantity. But since it’s just the 17th power of the ratio in the last paragraph, and taking the 17th power is an order-preserving operation, it wouldn’t change the meaning of the inequality.)

To get much further, we need to ask: what is surface area? The usual idea is that the volume of a thin shell around AA, of thickness ε0\varepsilon \approx 0, should be approximately ε\varepsilon times the surface area. So, we define

V n1(A)=lim ε0+V n(A ε)V n(A)ε, V_{n - 1}(A) = \lim_{\varepsilon \to 0+} \frac{V_n(A_\varepsilon) - V_n(A)}{\varepsilon},

where A εA_\varepsilon means the set of all points within distance ε\varepsilon of AA. Since we’re talking about Minkowski sums, it’s useful to observe that

A ε=A+εB n A_\varepsilon = A + \varepsilon B^n

where B nB^n means the nn-dimensional unit ball.

I confess that I don’t know exactly when the limit above exists; I guess there are measurable sets AA for which it doesn’t. And among those sets for which the limit does exist, I don’t know when it’s the right definition of surface area. But certainly everything works as it should when AA is convex and compact, since then V n(A ε)V_n(A_\varepsilon) is actually a polynomial in ε\varepsilon whose linear term is the surface area. (That’s part of Steiner’s theorem.) So let’s just assume that AA is convex and compact.

Now we’ll use this formula to calculate the surface area of the unit ball. Taking A=B nA = B^n,

V n1(B n) =lim ε0V n((1+ε)B n)V n(B n)ε =V n(B n)lim ε0(1+ε) n1ε =nV n(B n), \begin{aligned} V_{n - 1}(B^n) & = \lim_{\varepsilon \to 0} \frac{V_n((1 + \varepsilon)B^n) - V_n(B^n)}{\varepsilon} \\ & = V_n(B^n) \cdot \lim_{\varepsilon \to 0} \frac{(1 + \varepsilon)^n - 1}{\varepsilon} \\ & = n V_n(B^n), \end{aligned}

using the fact that V nV_n is homogeneous of degree nn. So,

V n1(B n)=nV n(B n). V_{n - 1}(B^n) = n V_n(B^n).

For instance, in 3\mathbb{R}^3, the volume of the unit ball is (4/3)π(4/3) \pi and the surface area of the unit sphere is 3(4/3)π=4π3 \cdot (4/3) \pi = 4\pi.

Back to Brunn-Minkowski! I promised to show you that the isoperimetric inequality is just the Brunn-Minkowski inequality in the case where one of the two sets involved is a small ball. We’ve put the isoperimetric inequality into a form where it involves (1/n)(1/n)th powers, which also appear in the Brunn-Minkowski inequality. So things are looking promising… Here goes.

Take A nA \subseteq \mathbb{R}^n (definitely measurable, probably convex and compact). The Brunn-Minkowski inequality tells us that for all ε>0\varepsilon \gt 0,

V n(A+εB n) 1/nV n(A) 1/n+V n(εB n) 1/n. V_n(A + \varepsilon B^n)^{1/n} \geq V_n(A)^{1/n} + V_n(\varepsilon B^n)^{1/n}.

Rearranging, this is equivalent to

V n(A+εB n)V n(A)ε(V n(A) 1/n+εV n(B n) 1/n) nV n(A)ε. \frac{V_n(A + \varepsilon B^n) - V_n(A)}{\varepsilon} \geq \frac{(V_n(A)^{1/n} + \varepsilon V_n(B^n)^{1/n})^n - V_n(A)}{\varepsilon}.

Now let ε0\varepsilon \to 0. The left-hand side is just the definition of V n1(A)V_{n - 1}(A). The right-hand side is recognizable as a derivative, give or take a constant factor. So the Brunn-Minkowski inequality for (vanishingly) small balls states that for nice enough A nA \subseteq \mathbb{R}^n,

V n1(A)nV n(A) (n1)/nV n(B n) 1/n. V_{n - 1}(A) \geq n V_n(A)^{(n - 1)/n} V_n(B^n)^{1/n}.

This looks like a mess until we remember the formula for the surface area of the unit ball: V n1(B n)=nV n(B n)V_{n - 1}(B^n) = n V_n(B^n). Using this to get rid of the nn in the inequality, and doing one last bit of elementary rearrangement, we get

V n(A) 1/nV n1(A) 1/(n1)V n(B n) 1/nV n1(B n) 1/(n1). \frac{V_n(A)^{1/n}}{V_{n - 1}(A)^{1/(n -1)}} \leq \frac{V_n(B^n)^{1/n}}{V_{n - 1}(B^n)^{1/(n - 1)}}.

And that’s exactly the isoperimetric inequality.

Posted at January 31, 2017 10:48 PM UTC

TrackBack URL for this Entry:

8 Comments & 0 Trackbacks

Re: The Brunn-Minkowski Inequality

Nice post, Tom. To readers whose background isn’t in certain areas of geometry and analysis, it’s not obvious that the Brunn–Minkowski inequality is more than a curiosity, the proof of the isoperimetric inequality notwithstanding. So let me add that Brunn–Minkowski is an absolutely vital tool in many parts of geometry, analysis, and probability theory, with extremely diverse applications. Gardner’s survey is a great place to start, but by no means exhaustive.

I’ll also add a couple remarks about regularity issues. You point out that Brunn–Minkowski holds “in the vast generality of measurable sets”, but it may not be initially obvious that this needs to be interpreted as “when AA, BB, and A+BA + B are all Lebesgue measurable”, since A+BA + B need not be measurable when AA and BB are (although you can modify the definition of A+BA + B to work for arbitrary measurable AA and BB; this is discussed by Gardner).

You raised the question of when the limit defining V n1(A)V_{n-1}(A) exists. As you note, it does exist for compact convex sets. It also holds if AA is compact with piecewise C 1C^1 boundary (see the appendix here). More generally, if you replace the limit with a lim inf, you get something called the Minkowski–Steiner formula. The standard reference for when this turns out to be the “right” notion of surface area is Federer’s famously impenetrable book. I believe that all this is related to “sets with positive reach”. I don’t know anything about those, but I know that Joe Fu does, so if I wanted to learn about them I’d ask him where to start.

Posted by: Mark Meckes on February 2, 2017 3:03 PM | Permalink | Reply to this

Re: The Brunn-Minkowski Inequality

Thanks for the correction on the measurability of A+BA + B. I think I knew that AA and BB being measurable doesn’t guarantee that A+BA + B is, but I overlooked it when I was writing, and I don’t think I’ve ever seen an explanation.

It’s interesting, because it means that the class of measurable sets isn’t as stable a setting as I’d thought. I mean, you can’t even do addition!

Posted by: Tom Leinster on February 3, 2017 11:08 PM | Permalink | Reply to this

Re: The Brunn-Minkowski Inequality

It’s not quite the usual presentation, but everyone’s first favourite Cantor set is the set of sums { j=1 σ j3 j|σ j{±1}}(Cantor) \left\{ \sum_{j=1}^\infty \frac{\sigma_j}{3^j} | \sigma_j\in\{\pm 1\} \right\} \qquad (Cantor) while the interval [1,1][-1,1] can similarly be described as { j=1 η j3 j|η j{2,0,2}}(Balanced3) \left\{ \sum_{j=1}^\infty \frac{\eta_j}{3^j} | \eta_j \in\{-2,0,2\} \right\} \qquad (Balanced3) in which almost all representations are Unique (this isn’t the usual presentation either, but it simplifies other things); In the Meantime, almost every xx a \sum of the form Balanced3Balanced3 can be written in about 2 02^{\aleph_0} ways as a sum a+ba+b of two \sums of the form CantorCantor; but Importantly: the nonzero terms of xx must be matched in sign by the corresponding terms in both the sums aa and bb. 2=1+12=1+1 and 2=11-2 = -1 - 1 and there are no carry operations to confuse us.

So, idea: choose a nonprincipal ultrafilter UU on the naturals, and let AA be the CantorCantor Sums such that the set of exponents of positive terms are in UU. AA has measure zero because it’s a subset of a rather thin Cantor set. The set A+AA+A is the subset of those xx in Balanced3Balanced3 whose set of positive terms is in UU; the point is that this should be, in a very uniform way, “about a third” of those sums, since exactly one of the positive, zero, or negative term sets is in UU. But Lebesgue Measure won’t let us have a measurable set that’s uniformly “about a third” of anything except a Null set.

Posted by: Jesse C. McKeown on February 4, 2017 3:50 AM | Permalink | Reply to this

Re: The Brunn-Minkowski Inequality

Tracking down references leads to this old paper of Sierpinski where he shows among other things that there is a Hamel basis BB for \mathbb{R} (as a \mathbb{Q}-vector space) that has Lebesgue measure zero. (In fact, he also shows that if a Hamel basis BB is Lebesgue-measurable, then its measure must be 00.)

He then gives a tricky inductive argument that with such a BB, if the set P nP_n of linear combinations of basis elements ir ib i\sum_i r_i b_i with at most nn non-zero r ir_i is Lebesgue measurable, then its measure must be 00. (He doesn’t show this directly, but in effect remarks towards the end of the paper that it is a porism of the proof of Théorème II, where it is shown that no Hamel basis BB can be an analytic set.) But since nP n=\bigcup_n P_n = \mathbb{R}, we may conclude that one of the P nP_n must be non-measurable (otherwise \mathbb{R}, being a countable union of measure zero sets, would have measure zero).

Now P 1= rrBP_1 = \sum_{r \in \mathbb{Q}} r B is measurable if BB is measurable. If P nP_n is the first non-measurable set in the sequence P 1,P 2,P_1, P_2, \ldots, then P n=P n1+P 1P_n = P_{n-1} + P_1 is the additive sum of two measurable sets that is non-measurable.

He also recalls in this paper the famous example of a non-measurable set (due to Vitali?) where you take any old Hamel basis BB and form a codimension 11 subspace VV of \mathbb{R} given by the span of B{b}B \setminus \{b\} for some bBb \in B, and then argue that VV must be non-measurable (see e.g. Wikipedia). This gives me the idea that maybe you could find a splitting B=B 1+B 2B = B_1 + B_2 where if you do it right, then (let’s say bB 2b \in B_2) span(B 1)span(B_1) and span(B 2)span(B_2) both have measure 00, but V=span(B 1)+span(B 2{b})V = span(B_1) + span(B_2 \setminus \{b\}) is non-measurable. However, I don’t have a fleshed-out proof nailed down.

Posted by: Todd Trimble on February 4, 2017 6:41 PM | Permalink | Reply to this

Re: The Brunn-Minkowski Inequality

In a different direction, it’s worth remembering that, according to a famous theorem of Solovay, if you don’t care that much for the Axiom of Choice, then you can assume that all sets of real numbers are Lebesgue measurable.

Posted by: Mark Meckes on February 4, 2017 7:13 PM | Permalink | Reply to this

Re: The Brunn-Minkowski Inequality

In the same context, I proved, with A. Trad (2001) that the shortest curve among all they are less than a function is its convex envelope:

Posted by: Fethi Kadhi on February 4, 2017 7:35 AM | Permalink | Reply to this

Re: The Brunn-Minkowski Inequality

How is this related to the Brunn-Minkowski inequality?

Posted by: Tom Leinster on February 4, 2017 1:29 PM | Permalink | Reply to this

Re: The Brunn-Minkowski Inequality

conv(f)= the convex envelope of ff in 1 dimension (n=1) vol(f)=vol(f-conv(f)+conv(f))\geq vol(f-conv(f))+ vol(conv(f)) Then vol(f)\geq vol(conv(f))

Posted by: Fethi Kadhi on February 4, 2017 4:34 PM | Permalink | Reply to this

Post a New Comment