View source for Brunn–Minkowski theorem

In [[mathematics]], the '''Brunn–Minkowski theorem''' (or '''Brunn–Minkowski inequality''') is an inequality relating the volumes (or more generally [[Lebesgue measure]]s) of [[compact space|compact]] [[subset]]s 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'''<sup>''n''</sup>. Let ''A'' and ''B'' be two nonempty compact subsets of '''R'''<sup>''n''</sup>. Then the following [[inequality (mathematics)|inequality]] holds:

:<math>[ \mu (A + B) ]^{1/n} \geq [\mu (A)]^{1/n} + [\mu (B)]^{1/n},</math>

where ''A'' + ''B'' denotes the [[Minkowski sum]]:

:<math>A + B := \{\, a + b \in \mathbb{R}^{n} \mid a \in A,\ b \in B \,\}.</math>

The theorem is also true in the setting where <math display="inline"> A, B, A + B </math> are only assumed to be measurable and non-empty.<ref>Gardner, Richard J. (2002). "The Brunn–Minkowski inequality". Bull. Amer. Math. Soc. (N.S.) 39 (3): pp. 355–405 (electronic). doi:10.1090/S0273-0979-02-00941-2. {{issn|0273-0979}}.</ref>

===Multiplicative version===
The multiplicative form of Brunn–Minkowski inequality states that <math display="inline">  \mu(\lambda A + (1 - \lambda) B) \geq \mu(A)^{\lambda} \mu(B)^{1 - \lambda} </math> for all <math display="inline"> \lambda \in [0,1] </math>.

The Brunn–Minkowski inequality is equivalent to the multiplicative version. 

In one direction, use the inequality <math display="inline"> \lambda x + (1 - \lambda) y \geq x^{\lambda} y^{1-\lambda} </math> (exponential is convex), which holds for  <math display="inline"> x,y \geq 0, \lambda \in [0,1] </math>. In particular, <math display="inline">  \mu(\lambda A + (1 - \lambda) B) \geq ( \lambda \mu(A)^{1/n} + ( 1 - \lambda) \mu(B)^{1/n})^n \geq \mu(A)^{\lambda} \mu(B)^{1 - \lambda} </math>. 

Conversely, using the multiplicative form, we find

<math display="inline"> \mu(A+B) = \mu(\lambda \frac{A}{\lambda} + (1 - \lambda) \frac{B}{1 - \lambda}) \geq \frac{\mu(A)^{\lambda} \mu(B)^{1 - \lambda}}{\lambda^{n\lambda}(1 - \lambda)^{n(1 - \lambda)}} </math>

The right side is maximized at <math>  \lambda = \frac{1}{1+e^C}, C = \frac 1 n \ln\frac{\mu(A)}{\mu(B)} </math>, which gives 

<math display="inline"> \mu(A+B) \geq (\mu(A)^{1/n}+\mu(B)^{1/n})^n </math>.

The [[Prékopa–Leindler inequality]] is a functional generalization of this version of Brunn–Minkowski.

==On the hypothesis==

===Measurability===
It is possible for <math display="inline"> A,B </math> to be Lebesgue measurable and <math display="inline"> A + B </math> to not be; a counter example can be found in [https://projecteuclid.org/euclid.rae/1212412875 "Measure zero sets with non-measurable sum."] On the other hand, if <math display="inline"> A,B </math> are Borel measurable, then <math display="inline"> A + B </math> is the continuous image of the Borel set  <math display="inline"> A \times B </math>, so [[Analytic set|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 <math display="inline"> A \times B </math> under the continuous addition map : <math display="inline"> + : \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}^n </math>, so the measurability conditions are easy to verify.

===Non-emptiness===

The condition that <math display="inline"> A,B </math> 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. 

{{Collapse top|title= Geometric proof via cuboids and measure theory}}

We give a well-known argument that follows a general recipe of arguments in measure theory; namely, it establishes a simple case by direct analysis, uses induction to establish a finitary extension of that special case, and then uses general machinery to obtain the general case as a limit. A discussion of this history of this proof can be found in Theorem 4.1 in [https://www.ams.org/journals/bull/2002-39-03/S0273-0979-02-00941-2/ Gardner's survey on Brunn–Minkowski].

We prove the version of the Brunn–Minkowski theorem that only requires <math display="inline"> A, B, A+ B </math> to be measurable and non-empty. 

* The case that ''A'' and ''B'' are axis aligned boxes:

By translation invariance of volumes, it suffices to take <math display="inline">A = \prod_{i = 1}^n [0,a_i], B = \prod_{i = 1}^n [0,b_i] </math>. Then <math display="inline"> A + B = \prod_{i = 1}^n [0, a_i + b_i] </math>. In this special case, the Brunn–Minkowski inequality asserts that <math display="inline"> \prod ( a_i + b_i)^{1/n} \geq \prod a_i^{1/n} + \prod b_i^{1/n} </math>. After dividing both sides by <math display="inline"> \prod ( a_i + b_i)^{1/n} </math> , this follows from the [[Inequality of arithmetic and geometric means|AM–GM inequality]]: <math display="inline"> (\prod \frac{ a_i}{a_i + b_i})^{1/n} + (\prod \frac{ b_i}{a_i + b_i})^{1/n} \leq \sum \frac{1}{n} \frac{ a_i + b_i} {a_i + b_i} = 1 </math>.

* The case where ''A'' and ''B'' are both disjoint unions of finitely many such boxes:

We will use induction on the total number of boxes, where the previous calculation establishes the base case of two boxes. First, we observe that there is an axis aligned hyperplane ''H'' that such that each side of ''H'' contains an entire box of ''A.'' To see this, it suffices to reduce to the case where ''A'' consists of two boxes, and then calculate that the negation of this statement implies that the two boxes have a point in common.

For a body X, we let <math display="inline"> X^{-}, X^+ </math> denote the intersections of ''X'' with the "right" and "left" halfspaces defined by H. Noting again that the statement of Brunn–Minkowski is translation invariant, we then translate B so that <math display="inline"> \frac{ \mu(A^+)}{\mu(B^+)} = \frac{ \mu(A^-)} { \mu(B^-)} </math>; such a translation exists by the intermediate value theorem because <math display="inline"> t \to \mu( (B + tv)^+) </math> is a continuous function, if ''v'' is perpendicular to ''H'' <math display="inline"> \frac{ \mu((B + tv) ^+)} { \mu((B + tv)^-)}  </math> has limiting values ''0'' and <math display="inline"> \infty </math> as <math> t \to -\infty, t \to \infty </math>, so takes on  <math display="inline"> \frac{ \mu(A^+)}{\mu(A^-)} </math> at some point.

We now have the pieces in place to complete the induction step. First, observe that <math display="inline"> A^+ + B^+ </math> and <math> A^- + B^- </math> are disjoint subsets of <math display="inline"> A + B </math>, and so <math display="inline">\mu(A+B)\geq \mu(A^++B^+)+\mu(A^-+B^-).</math> Now, <math display="inline"> A^+, A^- </math> both have one fewer box than ''A'', while <math display="inline"> B^+, B^- </math> each have at most as many boxes as ''B.'' Thus, we can apply the induction hypothesis: <math display="inline"> \mu(A^+ +B^+) \geq (\mu(A^+)^{1/n}+\mu(B^+)^{1/n})^n </math> and <math display="inline"> \mu(A^{-} +B^{-}) \geq (\mu(A^-)^{1/n}+\mu(B^-)^{1/n})^n </math>.

Elementary algebra shows that if <math display="inline"> \frac{ \mu(A^+)}{\mu(B^+)} = \frac{ \mu(A^-)} { \mu(B^-)} </math>, then also <math display="inline"> \frac{ \mu(A^+)}{\mu(B^+)} = \frac{ \mu(A^-)} { \mu(B^-)} = \frac{ \mu(A)} { \mu(B)} </math>, so we can calculate:

:<math> 
\begin{align}

\mu(A+B) \geq \mu(A^+ +B^+)+\mu(A^{-} +B^{-}) \geq (\mu(A^+)^{1/n}+\mu(B^+)^{1/n})^n+(\mu(A^-)^{1/n}+\mu(B^-)^{1/n})^n \\=\mu(B^+)  ( 1 +  \frac{ \mu(A^+)^{1/n}}{\mu(B^+)^{1/n}})^n + \mu(B^-) ( 1 + \frac{ \mu(A^-)^{1/n}} { \mu(B^-)^{1/n}})^n =( 1 + \frac{ \mu(A)^{1/n}} { \mu(B)^{1/n}})^n (  \mu(B^+) + \mu(B^-) ) =(\mu(B)^{1/n}+\mu(A)^{1/n})^n

\end{align}
 </math>

* The case that ''A'' and ''B'' are bounded open sets:

In this setting, both bodies can be approximated arbitrarily well by unions of disjoint axis aligned rectangles contained in their interior; this follows from general facts about the Lebesgue measure of open sets. That is, we have a sequence of bodies <math display="inline"> A_k \subseteq A </math>, which are disjoint unions of finitely many axis aligned rectangles, where <math display="inline"> \mu ( A \setminus A_k) \leq 1/k </math>, and likewise <math display="inline"> B_k \subseteq B </math>. Then we have that <math display="inline"> A + B \supseteq A_k + B_k </math>, so <math display="inline">\mu(A + B)^{1/n} \geq \mu(A_k + B_k)^{1/n} \geq \mu(A_k)^{1/n} + \mu(B_k)^{1/n} </math>. The right hand side converges to <math display="inline">\mu(A)^{1/n} + \mu(B)^{1/n} </math> as <math display="inline"> k \to \infty </math>, establishing this special case.

* The case that ''A'' and ''B'' are compact sets:

For a compact body ''X'', define <math display="inline"> X_{\epsilon} = X + B(0,\epsilon) </math> to be the <math display="inline"> \epsilon </math>-thickening of ''X.'' Here each <math display="inline"> B(0,\epsilon) </math> is the open ball of radius <math display="inline"> \epsilon </math>, so that <math display="inline"> X_{\epsilon} </math> is a bounded, open set. <math display="inline"> \bigcap_{\epsilon > 0} X_{\epsilon} = \text{cl}(X) </math>, so that if ''X'' is compact, then <math display="inline"> \lim_{\epsilon \to 0} \mu(X_\epsilon) = \mu(X) </math>. By using associativity and commutativity of Minkowski sum, along with the previous case, we can calculate that <math display="inline">\mu( (A + B)_{2 \epsilon})^{1/n} = \mu(A_{\epsilon} + B_{\epsilon})^{1/n} 
\geq \mu(A_{\epsilon})^{1/n} + \mu(B_{\epsilon})^{1/n} </math>. Sending  <math display="inline"> \epsilon </math> to ''0'' establishes the result.

* The case of bounded measurable sets:

Recall that by the [[regularity theorem for Lebesgue measure]] for any bounded measurable set ''X,'' and for any <math display="inline"> k>\geq </math>, there is a compact set <math display="inline"> X_{k} \subseteq X </math> with  <math display="inline"> \mu( X \setminus X_{k} ) < 1/k </math>. Thus, <math display="inline"> \mu(A + B) \geq \mu(A_k + B_k) \geq ( \mu(A_k)^{1/n} + \mu(B_k)^{1/n})^n </math> for all ''k,'' using the case of Brunn–Minkowski shown for compact sets. Sending <math display="inline">  k \to \infty </math> establishes the result.

* The case of measurable sets:

We let <math display="inline"> A_k = [-k,k]^n \cap A, B_k = [-k,k]^n \cap B </math>, and again argue using the previous case that <math display="inline"> \mu(A + B) \geq \mu(A_k + B_k) \geq ( \mu(A_k)^{1/n} + \mu(B_k)^{1/n})^n </math>, hence the result follows by sending k to infinity.
{{Collapse bottom}}

{{Collapse top|title= Proof as a corollary of the Prékopa–Leindler inequality}}

We give a proof of the Brunn–Minkowski inequality as a corollary to the [[Prékopa–Leindler inequality]], a functional version of the BM inequality. We will first prove PL, and then show that PL implies a multiplicative version of BM, then show that multiplicative BM implies additive BM. The argument here is simpler than the proof via cuboids, in particular, we only need to prove the BM inequality in one dimensions. This happens because the more general statement of the PL-inequality than the BM-inequality allows for an induction argument.

* The multiplicative form of the BM inequality

First, the Brunn–Minkowski inequality implies a multiplicative version, using the inequality <math display="inline"> \lambda x + (1 - \lambda) y \geq x^{\lambda} y^{\lambda} </math>, which holds for  <math display="inline"> x,y \geq 0, \lambda \in [0,1] </math>. In particular, <math display="inline">  \mu(\lambda A + (1 - \lambda) B) \geq ( \lambda \mu(A)^{1/n} + ( 1 - \lambda) \mu(B)^{1/n})^n \geq \mu(A)^{\lambda} \mu(B)^{1 - \lambda} </math>. The Prékopa–Leindler inequality is a functional generalization of this version of Brunn–Minkowski. 

* Prékopa–Leindler inequality

'''Theorem ([[Prékopa–Leindler inequality]])''': Fix <math display="inline"> \lambda \in (0,1) </math>. Let <math display="inline"> f,g,h : \mathbb{R}^n \to \mathbb{R}_+ </math> be non-negative, measurable functions satisfying <math display="inline">  h( \lambda x + (1 - \lambda)y) \geq f(x)^{\lambda} g(y)^{1 - \lambda} </math> for all <math display="inline"> x,y \in \mathbb{R}^n </math>. Then  <math display="inline"> \int_{\mathbb{R}^n} h(x) dx \geq (\int_{\mathbb{R}^n} f(x) dx)^{\lambda} (\int_{\mathbb{R}^n} g(x) dx)^{1 - \lambda}  </math>.

'''Proof''' (Mostly following [https://www.youtube.com/watch?v=5YI6wKw2Jdo this lecture]): 

We will need the one dimensional version of BM, namely that if <math display= "inline" > A, B, A + B \subseteq \mathbb{R} </math> are measurable, then <math display= "inline" > \mu (A + B) \geq \mu(A) + \mu(B) </math>. First, assuming that <math display= "inline" > A, B </math> are bounded, we shift <math display= "inline" > A, B </math> so that <math display= "inline" > A \cap B = \{0\} </math>. Thus, <math display= "inline" > A + B \supset A \cup B </math>, whence by almost disjointedness we have that <math display= "inline" > \mu(A + B) \geq \mu(A) + \mu(B) </math>. We then pass to the unbounded case by filtering with the intervals <math display= "inline" > [-k,k].</math>

We first show the <math display="inline"> n = 1 </math> case of the PL inequality. Let  <math display="inline"> L_h(t) = \{x : h(x) \geq t \} </math>.  <math display="inline"> L_h(t) \supseteq \lambda L_f(t) + (1 - \lambda) L_g(t) </math>. Thus, by the one-dimensional version of Brunn–Minkowski, we have that <math display="inline"> \mu( L_h(t)) \geq  \mu( \lambda L_f(t) + (1 - \lambda) L_g(t) ) \geq \lambda \mu(L_f(t)) + (1 - \lambda) \mu( L_g(t)) </math>. We recall that if <math display="inline"> f(x) </math> is non-negative, then Fubini's theorem implies <math display="inline">  \int_{\mathbb{R}} h(x) dx = \int_{t \geq 0} \mu( L_h(t)) dt </math>. Then, we have that  <math display="inline">  \int_{\mathbb{R}} h(x) dx = \int_{t \geq 0} \mu( L_h(t)) dt \geq \lambda \int_{t \geq 0} \mu( L_f(t)) + (1 - \lambda) \int_{t \geq 0} \mu( L_g(t)) = \lambda \int_{\mathbb{R}} f(x) dx + (1 - \lambda) \int_{\mathbb{R}} g(x) dx \geq (\int_{\mathbb{R}} f(x) dx)^{\lambda} (\int_{\mathbb{R}} g(x) dx)^{1 - \lambda} </math>, where in the last step we use the [[Inequality of arithmetic and geometric means#Weighted AM–GM inequality|weighted AM–GM inequality]], which asserts that <math display="inline"> \lambda x + (1 - \lambda) y \geq x^{\lambda} y^{1- \lambda} </math> for <math display="inline"> \lambda \in (0,1), x,y \geq 0</math>.

Now we prove the  <math display="inline"> n > 1 </math> case. For <math display="inline"> x,y \in \mathbb{R}^{n-1}, \alpha,\beta \in \mathbb{R} </math>, we pick <math display="inline"> \lambda \in [0,1] </math> and set <math display="inline"> \gamma = \lambda \alpha + (1 - \lambda) \beta </math>. For any c, we define <math display="inline"> h_{c}(x) = h(x, c)</math>, that is, defining a new function on n-1 variables by setting the last variable to be  <math display="inline"> c </math>. Applying the hypothesis and doing nothing but formal manipulation of the definitions, we have that <math display="inline"> h_{\gamma} ( \lambda x + (1 - \lambda)y ) = h ( \lambda x + (1 - \lambda) y , \lambda \alpha + ( 1 - \lambda) \beta) ) = h ( \lambda ( x, \alpha) + (1 - \lambda) (y, \beta) ) \geq f(x, \alpha)^{\lambda} g( y, \beta)^{1 - \lambda} = f_{\alpha}(x)^{\lambda} g_{\beta}(y)^{1 - \lambda} </math>.

Thus, by the inductive case applied to the functions <math display="inline"> h_{\gamma}, f_{\alpha}, g_{\beta} </math>, we obtain <math display="inline"> \int_{\mathbb{R}^{n-1}} h_{\gamma}(z) dz \geq (\int_{ \mathbb{R}^{n-1} } f_{\alpha}(z) dz )^{\lambda}  (\int_{ \mathbb{R}^{n-1} } g_{\beta}(z) dz )^{1 - \lambda} </math>. We define <math display="inline"> H(\gamma) := \int_{\mathbb{R}^{n-1}} h_{\gamma}(z) dz </math> and <math display="inline"> F(\alpha), G(\beta) </math> similarly. In this notation, the previous calculation can be rewritten as: <math display="inline"> H( \lambda \alpha + (1 - \lambda) \beta) \geq F(\alpha)^{\lambda} G(\beta)^{1 - \lambda} </math>. Since we have proven this for any fixed <math display="inline"> \alpha, \beta \in \mathbb{R}</math>, this means that the function <math display="inline">  H,F,G </math> satisfy the hypothesis for the one dimensional version of the PL theorem. Thus, we have that <math display="inline"> \int_{\mathbb{R}} H(\gamma) d \gamma \geq ( \int_{\mathbb{R}} F(\alpha) d \alpha)^{\lambda}  ( \int_{\mathbb{R}} F(\beta) d \beta)^{1 - \lambda} </math>, implying the claim by Fubini's theorem. QED

* PL implies multiplicative BM

The multiplicative version of Brunn–Minkowski follows from the PL inequality, by taking  <math display="inline"> h = 1_{\lambda A + (1 - \lambda) B}, f = 1_A, g = 1_B </math>. 

* Multiplicative BM implies Additive BM

We now explain how to derive the BM-inequality from the PL-inequality. First, by using the indicator functions for <math display="inline"> A, B, \lambda A + (1 - \lambda) B</math>  Prékopa–Leindler inequality quickly gives the multiplicative version of Brunn–Minkowski: <math display= "inline" > \mu ( \lambda A + (1 - \lambda) B) \geq \mu(A)^{\lambda} \mu(B)^{1 - \lambda} </math>. We now show how the multiplicative BM-inequality implies the usual, additive version.

We assume that both ''A,B'' have positive volume, as otherwise the inequality is trivial, and normalize them to have volume 1 by setting <math display="inline"> A' = \frac{ A}{ \mu(A)^{1/n}}, B' = \frac{B}{\mu(B)^{1/n}} </math>. We define <math display="inline"> \lambda' = \frac{ \lambda \mu(B)^{1/n}}{ (1 - \lambda) \mu(A)^{1/n} + \lambda \mu(B)^{1/n} } </math>; <math display="inline">1 - \lambda' = \frac{ (1 - \lambda) \mu(A)^{1/n}}{ (1 - \lambda) \mu(A)^{1/n} + \lambda \mu(B)^{1/n} } </math>. With these definitions, and using that <math display="inline"> \mu(A') = \mu(B') = 1 </math>, we calculate using the multiplicative Brunn–Minkowski inequality that:

:<math> \mu ( \frac { (1 - \lambda) A + \lambda B }{  (1 - \lambda) \mu(A)^{1/n} + \lambda \mu(B)^{1/n} } ) = \mu ( (1 - \lambda') A' + \lambda'B) \geq \mu(A')^{1 - \lambda'} \mu(B')^{\lambda'} = 1. </math>

The additive form of Brunn–Minkowski now follows by pulling the scaling out of the leftmost volume calculation and rearranging.
{{Collapse bottom}}

==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 <math display= "inline" > K \subseteq \mathbb{R}^n </math>. Let <math display="inline"> K(x) = K \cap \{ x_1 = x \} </math> be vertical slices of ''K.'' Define <math display="inline"> r(x) = \mu(K(x))^{\frac{1}{n-1}} </math> 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 [https://www.youtube.com/watch?v=UHvT1MxFuvo this lecture].

By convexity of ''K,'' we have that <math display="inline"> K( \lambda x + (1 - \lambda)y ) \supseteq \lambda K(x) + (1 - \lambda) K(y) </math>. Applying the Brunn–Minkowski inequality gives <math display="inline">r(K( \lambda x + (1 - \lambda)y )) \geq \lambda r ( K(x)) + (1 - \lambda) r ( K(y)) </math>, provided <math display="inline"> K(x) \not = \emptyset, K(y) \not = \emptyset </math>. 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  <math display = "inline" > K </math>. Fix some line  <math display = "inline" > l </math> and for each  <math display = "inline" > t \in l </math> let  <math display = "inline" > H_t </math> denote the affine hyperplane orthogonal to  <math display = "inline" > l</math> that passes through  <math display = "inline" > t </math>. Define,  <math display = "inline" > r(t) = Vol( K \cap H_t) </math>; as discussed in the previous section, this function is concave. Now, let <math display = "inline" > K' = \bigcup_{t \in l, K \cap H_t \not = \emptyset } B(t, r(t)) \cap H_t </math>. That is, <math display = "inline" > K' </math> is obtained from <math display = "inline" > K </math> by replacing each slice  <math display = "inline" > H_t \cap K </math> with a disc of the same <math display = "inline" > (n-1) </math>-dimensional volume centered  <math display = "inline" > l </math> inside of  <math display = "inline" > H_t </math>. The concavity of the radius function defined in the previous section implies that that <math display = "inline" > K' </math> is convex. This construction is called the Brunn–Minkowski symmetrization. 

===Grunbaum's theorem===

'''Theorem''' (Grunbaum's theorem):<ref>{{cite journal |last=Grünbaum |first=B. |author-link=Branko Grünbaum |year=1960 |title=Partitions of mass-distributions and of convex bodies by hyperplanes |url=https://projecteuclid.org/euclid.pjm/1103038065 |journal=Pacific Journal of Mathematics |volume=10 |issue=4 |pages=1257–1261 |doi=10.2140/pjm.1960.10.1257 |mr=124818}}</ref> Consider a convex body <math display="inline" > K \subseteq \mathbb{R}^n </math>. Let <math display="inline" > H </math> be any half-space containing the center of mass of  <math display="inline" > K </math>; that is, the expected location of a uniform point sampled from <math display="inline" > K. </math> Then <math display="inline"> \mu( H \cap K) \geq (\frac{n}{n+1})^n \mu(K) \geq \frac{1}{e} \mu(K) </math>. 

Grunbaum's theorem can be proven using Brunn–Minkowski inequality, specifically the convexity of the Brunn–Minkowski symmetrization.<ref>See [https://cs.uwaterloo.ca/~lapchi/cs798/L19.pdf these lecture notes] for a proof sketch.</ref>

Grunbaum's inequality has the following [[Fair cake-cutting|fair cake cutting]] interpretation. Suppose two players are playing a game of cutting up an <math display="inline"> n </math> 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 <math display="inline"> 1/e </math> fraction of the total. In dimensions 2 and 3, the most common dimensions for cakes, the bounds given by the theorem are approximately <math display="inline"> .444, .42 </math> respectively. Note, however, that in <math display="inline" > n </math> dimensions, calculating the centroid is <math display="inline"> \# P </math> hard,<ref>{{cite conference
 | last = Rademacher | first = Luis
 | editor-last = Erickson | editor-first = Jeff
 | contribution = Approximating the centroid is hard
 | doi = 10.1145/1247069.1247123
 | pages = 302–305
 | title = Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, South Korea, June 6–8, 2007
 | year = 2007| isbn = 978-1-59593-705-6
 }}</ref> 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.<ref>See theorem 2.1 in [http://sbubeck.com/Bubeck15.pdf these notes.]</ref>

===Isoperimetric inequality===

Let <math display="inline"> B = B(0,1) = \{ x \in \mathbb{R}^n : ||x||_2 \leq 1 \} </math> denote the unit ball. For a convex body, ''K'', let <math display="inline"> S(K) = \lim_{\epsilon \to 0} \frac{ \mu(K + \epsilon B) - \mu(K)}{\epsilon} </math> define its surface area. This agrees with the usual meaning of surface area by the [[Minkowski–Steiner formula|Minkowski-Steiner formula]]. Consider the function <math display="inline"> c(X) = \frac{ \mu(K)^{1/n} }{ S(K)^{1/(n-1)}}  </math>. The isoperimetric inequality states that this is maximized on Euclidean balls.

{{Collapse top|title=Proof of isoperimetric inequality via Brunn–Minkowski}}
First, observe that Brunn–Minkowski implies <math display="inline"> \mu( K + \epsilon B) \geq ( \mu(K)^{1/n} + \epsilon V(B)^{1/n} )^n = \mu(K) ( 1 + \epsilon (\frac{ \mu(B)}{\mu(K)})^{1/n})^n \geq \mu(K) ( 1 + n \epsilon (\frac{ \mu(B)}{\mu(K)})^{1/n}), </math> where in the last inequality we used that <math display="inline"> (1 + x)^n \geq 1 + nx </math> for <math display="inline"> x \geq 0 </math>. We use this calculation to lower bound the surface area of  <math display="inline"> K </math> via <math display="inline"> S(K) = \lim_{\epsilon \to 0} \frac{ \mu(K + \epsilon B) - \mu(K)}{\epsilon} \geq n \mu(K) (\frac{ \mu(B)}{\mu(K)})^{1/n}. </math> Next, we use the fact that  <math display="inline"> S(B) = n \mu(B) </math>, which follows from the [[Minkowski–Steiner formula|Minkowski-Steiner formula]], to calculate <math display="inline"> \frac{ S(K) }{S(B)} = \frac{ S(K) }{n \mu(B) } \geq \frac{ \mu(K) (\frac{ \mu(B)}{\mu(K)})^{1/n} }{\mu(B)} = \mu(K)^{\frac{n-1}{n}} \mu(B)^{\frac{ 1  -n }{n}}. </math> Rearranging this yields the isoperimetric inequality: <math display="inline">\frac{ \mu(B)^{1/n} }{ S(B)^{1/(n-1)}} \geq \frac{ \mu(K)^{1/n} }{ S(K)^{1/(n-1)}}. </math>
{{Collapse bottom}}

===Applications to inequalities between mixed volumes===

The Brunn–Minkowski inequality can be used to deduce the following inequality  <math display="inline"> V(K, \ldots, K, L)^n \geq V(K)^{n-1} V(L) </math>, where the  <math display="inline"> V(K, \ldots, K,L) </math> term is a [[Mixed volume|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.)

{{Collapse top|title= Proof }} 
We recall the following facts about [[Mixed volume|mixed volumes]] :  <math display="inline"> \mu ( \lambda_1 K_1 + \lambda_2 K_2 ) = \sum_{j_1, \ldots, j_n = 1}^r V(K_{j_1}, \ldots, V(K_{j_n}) \lambda_{j_1} \ldots \lambda_{j_n} </math>, so that in particular if  <math display="inline"> g(t) = \mu ( K + tL) = \mu(V) + n V(K, \ldots, K, L) t + \ldots  </math>, then <math display="inline"> g'(0) = n V(K, \ldots, K, L) </math>.

Let  <math display="inline"> f(t) := \mu( K + tL)^{1/n} </math>. Brunn's theorem implies that this is concave for  <math display="inline"> t \in [0,1] </math>. Thus,  <math display="inline"> f^+(0) \geq f(1) - f(0) = \mu(K + L)^{1/n} - V(K)^{1/n} </math>, where  <math display="inline"> f^+(0) </math> denotes the right derivative. We also have that  <math display="inline"> f^+(0) = \frac{1}{n} \mu(K)^{ \frac{n - 1}{n}} n V(K,\ldots, K,L) </math>. From this we get  <math display="inline">  \mu(K)^{ \frac{n - 1}{n}} V(K, \ldots, K,L) \geq \mu(K + L)^{1/n} - V(K)^{1/n} \geq V(L)^{1/n}</math>, where we applied BM in the last inequality.
{{Collapse bottom}}

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

We prove the following theorem on concentration of measure, following [http://www.math.lsa.umich.edu/~barvinok/total710.pdf notes by Barvinok] and [https://cs.uwaterloo.ca/~lapchi/cs798/L20.pdf notes by Lap Chi Lau]. See also [[Concentration of measure#Concentration on the sphere]].

'''Theorem''': Let <math display="inline">  S </math> be the unit sphere in <math display="inline"> \mathbb{R}^n </math>. Let <math display="inline">  X \subseteq S </math>. Define <math display="inline">  X_{\epsilon} = \{ z \in S : d(z,X) \leq \epsilon \} </math>, where d refers to the Euclidean distance in <math display="inline">  \mathbb{R}^n </math>. Let <math display="inline">  \nu </math> denote the surface area on the sphere. Then, for any <math display="inline"> \epsilon \in (0,1 ]</math> we have that <math display="inline"> \frac{\nu(X_{\epsilon})}{\nu(S) } \geq 1 - \frac{ \nu(S)}{\nu(X)} e^{ - \frac{n \epsilon^2}{4}} </math>.

{{Collapse top|title= Proof}}
'''Proof:''' Let  <math display="inline"> \delta = \epsilon^2 / 8 </math>, and let  <math display="inline"> Y = S \setminus X_{\epsilon} </math>. Then, for <math display="inline">  x \in X, y \in Y </math> one can show, using  <math display="inline"> \frac{1}{2} ||x + y||^2 = ||x||^2 + ||y||^2 - \frac{1}{2}||x - y||^2 </math> and  <math display="inline">  \sqrt{1 - x} \leq 1 - x/2 </math> for  <math display="inline">  x \leq 1 </math>, that  <math display="inline"> || \frac{ x + y}{2} || \leq 1 - \delta </math>. In particular,  <math display="inline"> \frac{x + y}{2} \in (1 - \delta) B(0,1) </math>. 

We let  <math display="inline">  \overline{X} = \text{Conv}(X, \{0\}), \overline{Y} = \text{Conv}(Y, \{0\}) </math>, and aim to show that  <math display="inline"> \frac{ \overline{X} + \overline{Y} }{2} \subseteq  (1 - \delta) B(0,1) </math>. Let   <math display="inline"> x \in X, y \in Y, \alpha, \beta \in [0,1] , \bar{x} = \alpha x, \bar{y} = \alpha y </math>. The argument below will be symmetric in   <math display="inline"> \bar{x}, \bar{y} </math>, so we assume without loss of generality that   <math display="inline"> \alpha \geq \beta </math> and set  <math display="inline"> \gamma = \beta / \alpha \leq 1 </math>. Then,

:<math> \frac{ \bar{x} + \bar{y}}{2} = \frac{ \alpha x + \beta y}{2} = \alpha \frac{ x + \gamma y}{2} = \alpha ( \gamma \frac{ x + y}{2} + (1 - \gamma) \frac{x}{2} ) = \alpha \gamma \frac{ x + y}{2} + \alpha ( 1 - \gamma) \frac{x}{2} </math>.

This implies that  <math display="inline"> \frac{ \bar{x} + \bar{y}}{2} \in \alpha \gamma (1 - \delta) B + \alpha ( 1 - \gamma) ( 1 - \delta) B = \alpha ( 1 - \delta) B \subseteq (1 - \delta) B </math>. (Using that for any convex body K and <math display="inline"> \gamma \in [0,1] </math>, <math display="inline"> \gamma K + (1 - \gamma) K = K </math>.)

Thus, we know that  <math display="inline"> \frac{ \overline{X} + \overline{Y} }{2} \subseteq  (1 - \delta) B(0,1) </math>, so  <math display="inline"> \mu ( \frac{ \overline{X} + \overline{Y} }{2} ) \leq  (1 - \delta)^n \mu(B(0,1)) </math>. We apply the multiplicative form of the Brunn–Minkowski inequality to lower bound the first term by  <math display="inline">  \sqrt{ \mu(\bar{X}) \mu( \bar{Y}) } </math>, giving us  <math display="inline"> (1 - \delta)^n \mu(B) \geq \mu(\bar{X})^{1/2} \mu( \bar{Y})^{1/2} </math>.

<math> 1 - \frac{ \nu(X_{\epsilon}) } { \nu(S)} = \frac{ \nu(Y) }{\nu(S)} = \frac{ \mu( \bar{Y} )}{\mu( B)} \leq ( 1 - \delta)^{2n} \frac{ \mu(B)}{\mu(\bar{X} )} \leq (1 - \delta)^{2n} \frac{\nu(S)}{\nu(X)} \leq  e^{ - 2n \delta}  \frac{\nu(S)}{\nu(X)} = e^{ - n \epsilon^2 / 4}  \frac{\nu(S)}{\nu(X)}  </math>. QED
{{collapse bottom}}
Version of this result hold also for so-called ''strictly convex surfaces,'' where the result depends on the [[Modulus and characteristic of convexity|modulus of convexity]]. However, the notion of surface area requires modification, see: [http://www.math.lsa.umich.edu/~barvinok/total710.pdf the aforementioned notes on concentration of measure from Barvinok.]

==Remarks==
The proof of the Brunn–Minkowski theorem establishes that the function

:<math>A \mapsto [\mu (A)]^{1/n}</math>

is [[concave function|concave]] in the sense that, for every pair of nonempty compact subsets ''A'' and ''B'' of '''R'''<sup>''n''</sup> and every 0 ≤ ''t'' ≤ 1,

:<math>\left[ \mu (t A + (1 - t) B ) \right]^{1/n} \geq t [ \mu (A) ]^{1/n} + (1 - t) [ \mu (B) ]^{1/n}.</math> 

For [[convex set|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 transformation|homothetic]], i.e. are equal up to [[translation (geometry)|translation]] and [[Scaling (geometry)|dilation]] by a positive factor.

==Examples==

===Rounded cubes===
It is instructive to consider the case where <math display="inline"> A </math> an <math display="inline"> l \times l </math> square in the plane, and <math display="inline"> B </math> a ball of radius  <math display="inline"> \epsilon </math>. In this case, <math display="inline"> A + B </math> is a rounded square, and its volume can be accounted for as the four rounded quarter circles of radius  <math display="inline"> \epsilon </math>, the four rectangles of dimensions  <math display="inline"> l \times \epsilon </math> along the sides, and the original square. Thus,
:<math>
\begin{align} \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{align} </math>

This example also hints at the theory of [[Mixed volume|mixed-volumes]], since the terms that appear in the expansion of the volume of  <math display="inline"> A + B </math> correspond to the differently dimensional pieces of ''A.'' In particular, if we rewrite Brunn–Minkowski as <math display="inline"> \mu( A + B) \geq ( \mu(A)^{1/n} + \mu(B)^{1/n})^n </math>, 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 <math display="inline">  \mu(A + B) = V(A, \ldots, A) + n V(B, A, \ldots, A) + \ldots + {n \choose j} V(B,\ldots, B, A,\ldots,A) + \ldots n V(B,\ldots, B,A) + \mu(B) </math>. This same phenomenon can also be seen for the sum of an ''n''-dimensional <math display="inline"> l \times l </math> box and a ball of radius <math display="inline"> \epsilon </math>, where the cross terms in  <math display="inline"> ( \mu(A)^{1/n} + \mu(B)^{1/n})^n </math>, up to constants, account for the mixed volumes. This is made precise for the first mixed volume in the section above [[Brunn–Minkowski theorem#Applications to inequalities between mixed volumes|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 <math display="inline"> C </math> denotes the middle third Cantor set, then it is an exercise in analysis to show that <math display="inline"> C + C = [0,2] </math>.

== 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,<ref name="GROMOV 1990 pp. 1–38">{{cite book | last=GROMOV | first=M. | title=Advances in Differential Geometry and Topology | chapter=CONVEX SETS AND KÄHLER MANIFOLDS | publisher=WORLD SCIENTIFIC | year=1990 | isbn=978-981-02-0494-5 | doi=10.1142/9789814439381_0001 | pages=1–38}}</ref><ref name="Neeb 2015">{{cite arXiv | last=Neeb | first=Karl-Hermann | title=Kaehler Geometry, Momentum Maps and Convex Sets | date=2015-10-12 | class=math.SG |eprint=1510.03289v1}}</ref> and combinatorial versions about counting sets of points inside the integer lattice.<ref name="Hernández Cifre Iglesias Nicolás 2018 pp. 1840–1856">{{cite journal | last1=Hernández Cifre | first1=María A. | last2=Iglesias | first2=David | last3=Nicolás | first3=Jesús Yepes | title=On a Discrete Brunn--Minkowski Type Inequality | journal=SIAM Journal on Discrete Mathematics | publisher=Society for Industrial & Applied Mathematics (SIAM) | volume=32 | issue=3 | year=2018 | issn=0895-4801 | doi=10.1137/18m1166067 | pages=1840–1856}}</ref>
<!--- connections to matroid theory? http://fpsac2019.fmf.uni-lj.si/resources/Proceedings/84.pdf>-->
<!--- todo: high level overviews in this section would be great. --->

==See also==
* [[Isoperimetric inequality]]
* [[Milman's reverse Brunn–Minkowski inequality]]
* [[Minkowski–Steiner formula]]
* [[Prékopa–Leindler inequality]]
* [[Vitale's random Brunn–Minkowski inequality]]
* [[Mixed volume]]

==References==
* {{cite book | author=Brunn, H. | author-link=Hermann Brunn | title=Über Ovale und Eiflächen | year = 1887 | version=Inaugural Dissertation, München}}
*{{cite book
 | last=Fenchel
 | first=Werner
 | author-link = Werner Fenchel
 |author2=Bonnesen, Tommy
 | title=Theorie der konvexen Körper
 | series=Ergebnisse der Mathematik und ihrer Grenzgebiete
 | volume=3
 | publisher=1. Verlag von Julius Springer
 | location=Berlin
 | year=1934
}}
*{{cite book
 | last=Fenchel
 | first=Werner
 | author-link=Werner Fenchel
 |author2=Bonnesen, Tommy
 | title=Theory of convex bodies
 | url=https://archive.org/details/theoryofconvexbo0000bonn
 | url-access=registration
 | publisher=L. Boron, C. Christenson and B. Smith. BCS Associates
 | location=Moscow, Idaho
 | year=1987
| isbn=9780914351023
 }}
* {{cite book | last=Dacorogna | first=Bernard | title=Introduction to the Calculus of Variations | publisher=Imperial College Press | location=London | year=2004 | isbn=1-86094-508-2}}
* [[Heinrich Guggenheimer]] (1977) ''Applicable Geometry'', page 146, Krieger, Huntington {{ISBN|0-88275-368-1}} .
* {{cite journal | last=Lyusternik | first=Lazar A. | authorlink=Lazar Lyusternik | title=Die Brunn–Minkowskische Ungleichnung für beliebige messbare Mengen | journal = Comptes Rendus de l'Académie des Sciences de l'URSS |series=Nouvelle Série | volume = III | year = 1935 | pages = 55&ndash;58}}
* {{cite book | last=Minkowski | first=Hermann | authorlink=Hermann Minkowski | title = Geometrie der Zahlen | location = Leipzig | publisher = Teubner | year = 1896}}
* {{cite journal|last=Ruzsa|first=Imre&nbsp;Z.|authorlink=Imre Z. Ruzsa|title=The Brunn–Minkowski inequality and nonconvex sets|journal=Geometriae Dedicata|volume=67|doi=10.1023/A:1004958110076|year=1997|number=3|pages=337–348|mr=1475877|s2cid=117749981 }}
* [[Rolf Schneider]], ''Convex bodies: the Brunn–Minkowski theory,'' Cambridge University Press, Cambridge, 1993.

==References==
{{reflist}}

{{Lp spaces}}
{{Measure theory}}

{{DEFAULTSORT:Brunn-Minkowski theorem}}
[[Category:Calculus of variations]]
[[Category:Geometric inequalities]]
[[Category:Hermann Minkowski]]
[[Category:Sumsets]]
[[Category:Theorems in convex geometry]]
[[Category:Theorems in measure theory]]