# Brunn–Minkowski theorem

In mathematics, the Brunn–Minkowski theorem (or Brunn–Minkowski inequality) is an inequality relating the volumes (or more generally Lebesgue measures) of compact subsets of Euclidean space. The original version of the Brunn–Minkowski theorem (Hermann Brunn 1887; Hermann Minkowski 1896) applied to convex sets; the generalization to compact nonconvex sets stated here is due to Lazar Lyusternik (1935).

## Statement

Let n ≥ 1 and let μ denote the Lebesgue measure on R$^n$. Let A and B be two nonempty compact subsets of R$^n$. Then the following inequality holds:
    $[\mu (A+B)]^{1/n}\geq [\mu (A)]^{1/n}+[\mu (B)]^{1/n},$
where A + B denotes the Minkowski sum:
    $A+B:=\{\,a+b\in \mathbb {R} ^{n}\mid a\in A,\ b\in B\,\}.$
The theorem is also true in the setting where A, B, A+B{\textstyle A, B, A+B} are only assumed to be measurable and non-empty.

### Multiplicative version

The multiplicative form of Brunn–Minkowski inequality states that μ(λA+(1−λ)B)≥μ(A)$^λ$μ(B)$^{1−λ}${\textstyle \mu (\lambda A+(1-\lambda )B)\geq \mu (A)^{\lambda }\mu (B)^{1-\lambda }} for all λ∈[0, 1]{\textstyle \lambda \in [0, 1]}.
The Brunn–Minkowski inequality is equivalent to the multiplicative version.
To prove the equivalence one direction (from Brunn–Minkowski inequality to its multiplicative form), apply the Brunn–Minkowski inequality to sets λA{\textstyle \lambda A} and (1−λ)B{\textstyle (1-\lambda )B}, which gives
μ(λA+(1−λ)B)≥(μ(λA)$^{1/n}$+μ((1−λ)B)$^{1/n}$)$^n$=(λμ(A)$^{1/n}$+(1−λ)μ(B)$^{1/n}$)$^n$, {\textstyle \mu (\lambda A+(1-\lambda )B)\geq (\mu (\lambda A)^{1/n}+\mu ((1-\lambda )B)^{1/n})^{n}=(\lambda \mu (A)^{1/n}+(1-\lambda )\mu (B)^{1/n})^{n}, }
where we used the fact that μ(⋅)$^{1/n}${\textstyle \mu (\cdot )^{1/n}} is homogeneous. Using now the inequality λx+(1−λ)y≥x$^λ$y$^{1−λ}${\textstyle \lambda x+(1-\lambda )y\geq x^{\lambda }y^{1-\lambda }}, which holds for all x, y≥0, λ∈[0, 1]{\textstyle x, y\geq 0, \lambda \in [0, 1]} (coming from concavity of the logarithm log⁡(λx+(1−λ)y)≥λlog⁡(x)+(1−λ)log⁡(y){\textstyle \log(\lambda x+(1-\lambda )y)\geq \lambda \log(x)+(1-\lambda )\log(y)}), we find that (λμ(A)$^{1/n}$+(1−λ)μ(B)$^{1/n}$)$^n$≥μ(A)$^λ$μ(B)$^{1−λ}${\textstyle (\lambda \mu (A)^{1/n}+(1-\lambda )\mu (B)^{1/n})^{n}\geq \mu (A)^{\lambda }\mu (B)^{1-\lambda }}, concluding the proof.
Conversely, using the multiplicative form, we find
μ(A+B)=μ(λ A/λ+(1−λ) B/1−λ)≥(μ(A)/λ$^n$)$^λ$(μ(B)/(1−λ)$^n$)$^{1−λ}$.{\textstyle \mu (A+B)=\mu (\lambda {\frac {A}{\lambda }}+(1-\lambda ){\frac {B}{1-\lambda }})\geq {\bigl{\frac {\mu (A)}{\lambda ^{n}}}{\bigr )}^{\lambda }{\bigl{\frac {\mu (B)}{(1-\lambda )^{n}}}{\bigr )}^{1-\lambda }.}
The right side is maximized at λ=μ(A)$^{1/n}$/(μ(A)$^{1/n}$+μ(B)$^{1/n}$) {\textstyle \lambda ={\frac {\mu (A)^{1/n}}{\mu (A)^{1/n}+\mu (B)^{1/n}}}}, which gives
μ(A+B)≥(μ(A)$^{1/n}$+μ(B)$^{1/n}$)$^n${\textstyle \mu (A+B)\geq (\mu (A)^{1/n}+\mu (B)^{1/n})^{n}} concluding the proof.
The Prékopa–Leindler inequality is a functional generalization of this version of Brunn–Minkowski.

## On the hypothesis
### Measurability

It is possible for A, B{\textstyle A, B} to be Lebesgue measurable and A+B{\textstyle A+B} to not be; a counter example can be found in "Measure zero sets with non-measurable sum." On the other hand, if A, B{\textstyle A, B} are Borel measurable, then A+B{\textstyle A+B} is the continuous image of the Borel set A×B{\textstyle A\times B}, so analytic and thus measurable. See the discussion in Gardner's survey for more on this, as well as ways to avoid measurability hypothesis.
In the case that A and B are compact, so is A + B, being the image of the compact set A×B{\textstyle A\times B} under the continuous addition map : +:R$^n$×R$^n$→R$^n${\textstyle +:\mathbb {R} ^{n}\times \mathbb {R} ^{n}\to \mathbb {R} ^{n}}, so the measurability conditions are easy to verify.

### Non-emptiness

The condition that A, B{\textstyle A, B} are both non-empty is clearly necessary. This condition is not part of the multiplicative versions of BM stated below.

## Proofs

We give two well known proofs of Brunn–Minkowski.

## Important corollaries

The Brunn–Minkowski inequality gives much insight into the geometry of high dimensional convex bodies. In this section we sketch a few of those insights.

### Concavity of the radius function (Brunn's theorem)

Consider a convex body K⊆R$^n${\textstyle K\subseteq \mathbb {R} ^{n}}. Let K(x)=K∩{x$_1$=x}{\textstyle K(x)=K\cap \{x_{1}=x\}} be vertical slices of K. Define r(x)=μ(K(x))$^{1/n−1}${\textstyle r(x)=\mu (K(x))^{\frac {1}{n-1}}} to be the radius function; if the slices of K are discs, then r(x) gives the radius of the disc K(x), up to a constant. For more general bodies this radius function does not appear to have a completely clear geometric interpretation beyond being the radius of the disc obtained by packing the volume of the slice as close to the origin as possible; in the case when K(x) is not a disc, the example of a hypercube shows that the average distance to the center of mass can be much larger than r(x). Sometimes in the context of a convex geometry, the radius function has a different meaning, here we follow the terminology of this lecture.
By convexity of K, we have that K(λx+(1−λ)y)⊇λK(x)+(1−λ)K(y){\textstyle K(\lambda x+(1-\lambda )y)\supseteq \lambda K(x)+(1-\lambda )K(y)}. Applying the Brunn–Minkowski inequality gives r(K(λx+(1−λ)y))≥λr(K(x))+(1−λ)r(K(y)){\textstyle r(K(\lambda x+(1-\lambda )y))\geq \lambda r(K(x))+(1-\lambda )r(K(y))}, provided K(x)≠∅, K(y)≠∅{\textstyle K(x)\not =\emptyset , K(y)\not =\emptyset }. This shows that the radius function is concave on its support, matching the intuition that a convex body does not dip into itself along any direction. This result is sometimes known as Brunn's theorem.

### Brunn–Minkowski symmetrization of a convex body

Again consider a convex body K{\textstyle K}. Fix some line l{\textstyle l} and for each t∈l{\textstyle t\in l} let H$_t${\textstyle H_{t}} denote the affine hyperplane orthogonal to l{\textstyle l} that passes through t{\textstyle t}. Define, r(t)=Vol(K∩H$_t$){\textstyle r(t)=Vol(K\cap H_{t})}; as discussed in the previous section, this function is concave. Now, let K$^′$=⋃$_{t∈l, K∩Ht≠∅}$B(t, r(t))∩H$_t${\textstyle K'=\bigcup _{t\in l, K\cap H_{t}\not =\emptyset }B(t, r(t))\cap H_{t}}. That is, K$^′${\textstyle K'} is obtained from K{\textstyle K} by replacing each slice H$_t$∩K{\textstyle H_{t}\cap K} with a disc of the same (n−1){\textstyle (n-1)}-dimensional volume centered l{\textstyle l} inside of H$_t${\textstyle H_{t}}. The concavity of the radius function defined in the previous section implies that that K$^′${\textstyle K'} is convex. This construction is called the Brunn–Minkowski symmetrization.

### Grunbaum's theorem

Theorem (Grunbaum's theorem): Consider a convex body K⊆R$^n${\textstyle K\subseteq \mathbb {R} ^{n}}. Let H{\textstyle H} be any half-space containing the center of mass of K{\textstyle K}; that is, the expected location of a uniform point sampled from K.{\textstyle K.} Then μ(H∩K)≥(n/(n+1))$^n$μ(K)≥ 1/e μ(K){\textstyle \mu (H\cap K)\geq ({\frac {n}{n+1}})^{n}\mu (K)\geq {\frac {1}{e}}\mu (K)}.
Grunbaum's theorem can be proven using Brunn–Minkowski inequality, specifically the convexity of the Brunn–Minkowski symmetrization.
Grunbaum's inequality has the following fair cake cutting interpretation. Suppose two players are playing a game of cutting up an n{\textstyle n} dimensional, convex cake. Player 1 chooses a point in the cake, and player two chooses a hyperplane to cut the cake along. Player 1 then receives the cut of the cake containing his point. Grunbaum's theorem implies that if player 1 chooses the center of mass, then the worst that an adversarial player 2 can do is give him a piece of cake with volume at least a 1/e{\textstyle 1/e} fraction of the total. In dimensions 2 and 3, the most common dimensions for cakes, the bounds given by the theorem are approximately .444, .42{\textstyle .444, .42} respectively. Note, however, that in n{\textstyle n} dimensions, calculating the centroid is #P{\textstyle \#P} hard, limiting the usefulness of this cake cutting strategy for higher dimensional, but computationally bounded creatures.
Applications of Grunbaum's theorem also appear in convex optimization, specifically in analyzing the converge of the center of gravity method.

### Isoperimetric inequality

Let B=B(0, 1)={x∈R$^n$:||x||$_2$≤1}{\textstyle B=B(0, 1)=\{x\in \mathbb {R} ^{n}:||x||_{2}\leq 1\}} denote the unit ball. For a convex body, K, let S(K)=lim$_{ϵ→0}$ (μ(K+ϵB)−μ(K))/ϵ {\textstyle S(K)=\lim _{\epsilon \to 0}{\frac {\mu (K+\epsilon B)-\mu (K)}{\epsilon }}} define its surface area. This agrees with the usual meaning of surface area by the Minkowski-Steiner formula. Consider the function c(X)=μ(K)$^{1/n}$/S(K)$^{1/(n−1)}$ {\textstyle c(X)={\frac {\mu (K)^{1/n}}{S(K)^{1/(n-1)}}}}. The isoperimetric inequality states that this is maximized on Euclidean balls.

### Applications to inequalities between mixed volumes

The Brunn–Minkowski inequality can be used to deduce the following inequality V(K, …, K, L)$^n$≥V(K)$^{n−1}$V(L){\textstyle V(K, \ldots , K, L)^{n}\geq V(K)^{n-1}V(L)}, where the V(K, …, K, L){\textstyle V(K, \ldots , K, L)} term is a mixed-volume. Equality holds if and only if K,L are homothetic. (See theorem 3.4.3 in Hug and Weil's course on convex geometry.)

### Concentration of measure on the sphere and other strictly convex surfaces

We prove the following theorem on concentration of measure, following notes by Barvinok and notes by Lap Chi Lau. See also Concentration of measure#Concentration on the sphere.
Theorem: Let S{\textstyle S} be the unit sphere in R$^n${\textstyle \mathbb {R} ^{n}}. Let X⊆S{\textstyle X\subseteq S}. Define X$_ϵ$={z∈S:d(z, X)≤ϵ}{\textstyle X_{\epsilon }=\{z\in S:d(z, X)\leq \epsilon \}}, where d refers to the Euclidean distance in R$^n${\textstyle \mathbb {R} ^{n}}. Let ν{\textstyle \nu } denote the surface area on the sphere. Then, for any ϵ∈(0, 1]{\textstyle \epsilon \in (0, 1]} we have that ν(X$_ϵ$)/ν(S) ≥1−ν(S)/ν(X) e$^{−nϵ2/4}${\textstyle {\frac {\nu (X_{\epsilon })}{\nu (S)}}\geq 1-{\frac {\nu (S)}{\nu (X)}}e^{-{\frac {n\epsilon ^{2}}{4}}}}.
Version of this result hold also for so-called strictly convex surfaces, where the result depends on the modulus of convexity. However, the notion of surface area requires modification, see: the aforementioned notes on concentration of measure from Barvinok.

## Remarks

The proof of the Brunn–Minkowski theorem establishes that the function
    $A\mapsto [\mu (A)]^{1/n}$
is concave in the sense that, for every pair of nonempty compact subsets A and B of R$^n$ and every 0 ≤ t ≤ 1,
    $\left[\mu (tA+(1-t)B)\right]^{1/n}\geq t[\mu (A)]^{1/n}+(1-t)[\mu (B)]^{1/n}.$
For convex sets A and B of positive measure, the inequality in the theorem is strict for 0 < t < 1 unless A and B are positive homothetic, i.e. are equal up to translation and dilation by a positive factor.

## Examples
### Rounded cubes

It is instructive to consider the case where A{\textstyle A} an l×l{\textstyle l\times l} square in the plane, and B{\textstyle B} a ball of radius ϵ{\textstyle \epsilon }. In this case, A+B{\textstyle A+B} is a rounded square, and its volume can be accounted for as the four rounded quarter circles of radius ϵ{\textstyle \epsilon }, the four rectangles of dimensions l×ϵ{\textstyle l\times \epsilon } along the sides, and the original square. Thus,
    ${\begin{aligned}\mu (A+B)&=l^{2}+4\epsilon l+{\frac {4}{4}}\pi \epsilon ^{2}=\mu (A)+4\epsilon l+\mu (B)\geq \mu (A)+2{\sqrt {\pi }}\epsilon l+\mu (B)\\&=\mu (A)+2{\sqrt {\mu (A)\mu (B)}}+\mu (B)=(\mu (A)^{1/2}+\mu (B)^{1/2})^{2}.\end{aligned}}$
This example also hints at the theory of mixed-volumes, since the terms that appear in the expansion of the volume of A+B{\textstyle A+B} correspond to the differently dimensional pieces of A. In particular, if we rewrite Brunn–Minkowski as μ(A+B)≥(μ(A)$^{1/n}$+μ(B)$^{1/n}$)$^n${\textstyle \mu (A+B)\geq (\mu (A)^{1/n}+\mu (B)^{1/n})^{n}}, we see that we can think of the cross terms of the binomial expansion of the latter as accounting, in some fashion, for the mixed volume representation of μ(A+B)=V(A, …, A)+nV(B, A, …, A)+…+(n/j)V(B, …, B, A, …, A)+…nV(B, …, B, A)+μ(B){\textstyle \mu (A+B)=V(A, \ldots , A)+nV(B, A, \ldots , A)+\ldots +{n \choose j}V(B, \ldots , B, A, \ldots , A)+\ldots nV(B, \ldots , B, A)+\mu (B)}. This same phenomenon can also be seen for the sum of an n-dimensional l×l{\textstyle l\times l} box and a ball of radius ϵ{\textstyle \epsilon }, where the cross terms in (μ(A)$^{1/n}$+μ(B)$^{1/n}$)$^n${\textstyle (\mu (A)^{1/n}+\mu (B)^{1/n})^{n}}, up to constants, account for the mixed volumes. This is made precise for the first mixed volume in the section above on the applications to mixed volumes.

### Examples where the lower bound is loose

The left-hand side of the BM inequality can in general be much larger than the right side. For instance, we can take X to be the x-axis, and Y the y-axis inside the plane; then each has measure zero but the sum has infinite measure. Another example is given by the Cantor set. If C{\textstyle C} denotes the middle third Cantor set, then it is an exercise in analysis to show that C+C=[0, 2]{\textstyle C+C=[0, 2]}.

## Connections to other parts of mathematics

The Brunn–Minkowski inequality continues to be relevant to modern geometry and algebra. For instance, there are connections to algebraic geometry, and combinatorial versions about counting sets of points inside the integer lattice.