## January 31, 2017

### The Brunn-Minkowski Inequality

#### Posted by Tom Leinster Let $A$ and $B$ be measurable subsets of $\mathbb{R}^n$. Then

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

where $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 $A$ and $B$ 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 + B$ is known as a Minkowski sum. You can think of $A + B$ as $A$ smeared out in a pattern dictated by $B$:

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

For instance, if $A$ is an egg shape (green) and $B$ is a quadrilateral (blue) then $A + B$ looks like the entire shape here: (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 $A$ is egg-like and $B$ is a line segment then $A + B$ looks like this: Of course, there’s also a complementary viewpoint: $A + B$ is $B$ smeared out in a pattern dictated by $A$:

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

In any case, an important observation is that

$A + B$ can have large volume even if $A$ and $B$ both have volume zero.

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

The Brunn-Minkowski inequality does this, but it’s really about linearized volume, $Vol^{1/n}$, rather than volume itself. If length is measured in metres then so is $Vol^{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/n} \geq Vol(A)^{1/n} + Vol(B)^{1/n}$

and raise each side to the power of $n$. 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) \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 $A$ and $B$ be measurable subsets of $\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 + B$ contains almost-disjoint translates of $A$ and of $B$, where by “almost disjoint” I mean that their intersection has measure zero. The inequality will follow.

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

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

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

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

But we can also write $x = a^- + b$ for some $b \in B$, and a similar argument gives $h(x) \leq h(a^- + b^+)$. So we’ve shown that every $x \in (A + b^+) \cap (a^- + B)$ belongs to the hyperplane $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 \subseteq \mathbb{R}^n$, and take $B$ to be a ball of radius tending to zero, then the Brunn-Minkowski inequality becomes the isoperimetric inequality in $\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 $\mathbb{R}^2$ with a prescribed perimeter, the one with the greatest area is the disc. But I mean the general $n$-dimensional version, which I’ll now state.

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

$V_n(A) \leq V_n(r B^n)$

where the radius $r$ is chosen so that

$V_{n - 1}(A) = V_{n - 1}(r B^n).$

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

$\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 \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$ and surface area is measured in metres${}^{n - 1}$, we can get a dimensionless quantity by linearizing both things before we take the ratio. In other words, take the $n$th root of the volume and the $(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)$th power of the volume and the $(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 $A$, of thickness $\varepsilon \approx 0$, should be approximately $\varepsilon$ times the surface area. So, we define

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

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

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

where $B^n$ means the $n$-dimensional unit ball.

I confess that I don’t know exactly when the limit above exists; I guess there are measurable sets $A$ 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 $A$ is convex and compact, since then $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 $A$ is convex and compact.

Now we’ll use this formula to calculate the surface area of the unit ball. Taking $A = 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_n$ is homogeneous of degree $n$. So,

$V_{n - 1}(B^n) = n V_n(B^n).$

For instance, in $\mathbb{R}^3$, the volume of the unit ball is $(4/3) \pi$ and the surface area of the unit sphere is $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)$th powers, which also appear in the Brunn-Minkowski inequality. So things are looking promising… Here goes.

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

$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

$\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 $\varepsilon \to 0$. The left-hand side is just the definition of $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 \subseteq \mathbb{R}^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_{n - 1}(B^n) = n V_n(B^n)$. Using this to get rid of the $n$ in the inequality, and doing one last bit of elementary rearrangement, we get

$\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:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2934

### 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 $A$, $B$, and $A + B$ are all Lebesgue measurable”, since $A + B$ need not be measurable when $A$ and $B$ are (although you can modify the definition of $A + B$ to work for arbitrary measurable $A$ and $B$; this is discussed by Gardner).

You raised the question of when the limit defining $V_{n-1}(A)$ exists. As you note, it does exist for compact convex sets. It also holds if $A$ is compact with piecewise $C^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 + B$. I think I knew that $A$ and $B$ being measurable doesn’t guarantee that $A + 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 $\left\{ \sum_{j=1}^\infty \frac{\sigma_j}{3^j} | \sigma_j\in\{\pm 1\} \right\} \qquad (Cantor)$ while the interval $[-1,1]$ can similarly be described as $\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 $x$ a $\sum$ of the form $Balanced3$ can be written in about $2^{\aleph_0}$ ways as a sum $a+b$ of two $\sum$s of the form $Cantor$; but Importantly: the nonzero terms of $x$ must be matched in sign by the corresponding terms in both the sums $a$ and $b$. $2=1+1$ and $-2 = -1 - 1$ and there are no carry operations to confuse us.

So, idea: choose a nonprincipal ultrafilter $U$ on the naturals, and let $A$ be the $Cantor$ Sums such that the set of exponents of positive terms are in $U$. $A$ has measure zero because it’s a subset of a rather thin Cantor set. The set $A+A$ is the subset of those $x$ in $Balanced3$ whose set of positive terms is in $U$; 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 $U$. 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 $B$ for $\mathbb{R}$ (as a $\mathbb{Q}$-vector space) that has Lebesgue measure zero. (In fact, he also shows that if a Hamel basis $B$ is Lebesgue-measurable, then its measure must be $0$.)

He then gives a tricky inductive argument that with such a $B$, if the set $P_n$ of linear combinations of basis elements $\sum_i r_i b_i$ with at most $n$ non-zero $r_i$ is Lebesgue measurable, then its measure must be $0$. (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 $B$ can be an analytic set.) But since $\bigcup_n P_n = \mathbb{R}$, we may conclude that one of the $P_n$ must be non-measurable (otherwise $\mathbb{R}$, being a countable union of measure zero sets, would have measure zero).

Now $P_1 = \sum_{r \in \mathbb{Q}} r B$ is measurable if $B$ is measurable. If $P_n$ is the first non-measurable set in the sequence $P_1, P_2, \ldots$, then $P_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 $B$ and form a codimension $1$ subspace $V$ of $\mathbb{R}$ given by the span of $B \setminus \{b\}$ for some $b \in B$, and then argue that $V$ must be non-measurable (see e.g. Wikipedia). This gives me the idea that maybe you could find a splitting $B = B_1 + B_2$ where if you do it right, then (let’s say $b \in B_2$) $span(B_1)$ and $span(B_2)$ both have measure $0$, but $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:

conv(f)= the convex envelope of $f$ 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))