Brunn–Minkowski theorem explained

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ⁿ. Let A and B be two nonempty compact subsets of Rⁿ. 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 R ^{n} \mid a \in A, b \in B \}.

The theorem is also true in the setting where $A,\; B,\; A\; +\; B$ are only assumed to be measurable and non-empty.^[1]

Multiplicative version

The multiplicative form of Brunn–Minkowski inequality states that $\backslash mu(\backslash lambda\; A\; +\; (1\; -\; \backslash lambda)\; B)\; \backslash geq\; \backslash mu(A)^\; \backslash mu(B)^$ for all $\backslash lambda\; \backslash in\; [0,1]$.

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

In one direction, use the inequality $\backslash lambda\; x\; +\; (1\; -\; \backslash lambda)\; y\; \backslash geq\; x^\; y^$ (exponential is convex), which holds for $x,y\; \backslash geq\; 0,\; \backslash lambda\; \backslash in\; [0,1]$. In particular, $\backslash mu(\backslash lambda\; A\; +\; (1\; -\; \backslash lambda)\; B)\; \backslash geq\; (\backslash lambda\; \backslash mu(A)^\; +\; (1\; -\; \backslash lambda)\; \backslash mu(B)^)^n\; \backslash geq\; \backslash mu(A)^\; \backslash mu(B)^$.

Conversely, using the multiplicative form, we find

$\backslash mu(A+B)\; =\; \backslash mu(\backslash lambda\; \backslash frac\; +\; (1\; -\; \backslash lambda)\; \backslash frac)\; \backslash geq\; \backslash frac$

The right side is maximized at

λ = (1)/(1+ e ^{C}) , C = (1)/(ln n) (\mu(A))/(\mu(B)) , which gives

$\backslash mu(A+B)\; \backslash geq\; (\backslash mu(A)^+\backslash mu(B)^)^n$.

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$ to be Lebesgue measurable and $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$ are Borel measurable, then $A\; +\; B$ is the continuous image of the Borel set $A\; \backslash 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\; \backslash times\; B$ under the continuous addition map : $+\; :\; \backslash mathbb^n\; \backslash times\; \backslash mathbb^n\; \backslash to\; \backslash mathbb^n$, so the measurability conditions are easy to verify.

Non-emptiness

The condition that $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.

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 Gardner's survey on Brunn–Minkowski.

We prove the version of the Brunn–Minkowski theorem that only requires $A,\; B,\; A+\; B$ 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 $A\; =\; \backslash prod\_^n\; [0,a\_i],\; B\; =\; \backslash prod\_^n\; [0,b\_i]$. Then $A\; +\; B\; =\; \backslash prod\_^n\; [0,\; a\_i\; +\; b\_i]$. In this special case, the Brunn–Minkowski inequality asserts that $\backslash prod\; (a\_i\; +\; b\_i)^\; \backslash geq\; \backslash prod\; a\_i^\; +\; \backslash prod\; b\_i^$. After dividing both sides by $\backslash prod\; (a\_i\; +\; b\_i)^$, this follows from the AM–GM inequality: $(\backslash prod\; \backslash frac)^\; +\; (\backslash prod\; \backslash frac)^\; \backslash leq\; \backslash sum\; \backslash frac\; \backslash frac\; =\; 1$.

• 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 $X^,\; X^+$ 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 $\backslash frac\; =\; \backslash frac$; such a translation exists by the intermediate value theorem because $t\; \backslash to\; \backslash mu((B\; +\; tv)^+)$ is a continuous function, if v is perpendicular to H $\backslash frac$ has limiting values 0 and $\backslash infty$ as

t \to -inf ty, t \to inf ty , so takes on $\backslash frac$ at some point.

We now have the pieces in place to complete the induction step. First, observe that $A^+\; +\; B^+$ and

A ^{-} + B ^{-} are disjoint subsets of $A\; +\; B$, and so $\backslash mu(A+B)\backslash geq\; \backslash mu(A^++B^+)+\backslash mu(A^-+B^-).$ Now, $A^+,\; A^-$ both have one fewer box than A, while $B^+,\; B^-$ each have at most as many boxes as B. Thus, we can apply the induction hypothesis: $\backslash mu(A^+\; +B^+)\; \backslash geq\; (\backslash mu(A^+)^+\backslash mu(B^+)^)^n$ and $\backslash mu(A^\; +B^)\; \backslash geq\; (\backslash mu(A^-)^+\backslash mu(B^-)^)^n$.

Elementary algebra shows that if $\backslash frac\; =\; \backslash frac$, then also $\backslash frac\; =\; \backslash frac\; =\; \backslash frac$, so we can calculate:

\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 + (\mu(A ^{+)} ^{1/n})/(\mu(B ^{+)} ^{1/n}) ) ^{n} + \mu(B ^{-)} ( 1 + (\mu(A ^{-)} ^{1/n})/(\mu(B ^{-)} ^{1/n}) ) ^{n} = ( 1 + (\mu(A) ^{1/n})/(\mu(B) ^{1/n}) ) ^{n} ( \mu(B ^{+)} + \mu(B ^{-)} ) = (\mu(B) ^{1/n} + \mu(A) ^{1/n} ) ^{n \end{align}}

• 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 $A\_k\; \backslash subseteq\; A$, which are disjoint unions of finitely many axis aligned rectangles, where $\backslash mu\; (A\; \backslash setminus\; A\_k)\; \backslash leq\; 1/k$, and likewise $B\_k\; \backslash subseteq\; B$. Then we have that $A\; +\; B\; \backslash supseteq\; A\_k\; +\; B\_k$, so $\backslash mu(A\; +\; B)^\; \backslash geq\; \backslash mu(A\_k\; +\; B\_k)^\; \backslash geq\; \backslash mu(A\_k)^\; +\; \backslash mu(B\_k)^$. The right hand side converges to $\backslash mu(A)^\; +\; \backslash mu(B)^$ as $k\; \backslash to\; \backslash infty$, establishing this special case.

• The case that A and B are compact sets:

For a compact body X, define $X\_\; =\; X\; +\; B(0,\backslash epsilon)$ to be the $\backslash epsilon$-thickening of X. Here each $B(0,\backslash epsilon)$ is the open ball of radius $\backslash epsilon$, so that $X\_$ is a bounded, open set. $\backslash bigcap\_\; X\_\; =\; \backslash text(X)$, so that if X is compact, then $\backslash lim\_\; \backslash mu(X\_\backslash epsilon)\; =\; \backslash mu(X)$. By using associativity and commutativity of Minkowski sum, along with the previous case, we can calculate that $\backslash mu((A\; +\; B)\_)^\; =\; \backslash mu(A\_\; +\; B\_)^\; \backslash geq\; \backslash mu(A\_)^\; +\; \backslash mu(B\_)^$. Sending $\backslash epsilon$ 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 $k>\backslash geq$, there is a compact set $X\_\; \backslash subseteq\; X$ with . Thus, $\backslash mu(A\; +\; B)\; \backslash geq\; \backslash mu(A\_k\; +\; B\_k)\; \backslash geq\; (\backslash mu(A\_k)^\; +\; \backslash mu(B\_k)^)^n$ for all k, using the case of Brunn–Minkowski shown for compact sets. Sending $k\; \backslash to\; \backslash infty$ establishes the result.

• The case of measurable sets:

We let $A\_k\; =\; [-k,k]^n\; \backslash cap\; A,\; B\_k\; =\; [-k,k]^n\; \backslash cap\; B$, and again argue using the previous case that $\backslash mu(A\; +\; B)\; \backslash geq\; \backslash mu(A\_k\; +\; B\_k)\; \backslash geq\; (\backslash mu(A\_k)^\; +\; \backslash mu(B\_k)^)^n$, hence the result follows by sending k to infinity.

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 $\backslash lambda\; x\; +\; (1\; -\; \backslash lambda)\; y\; \backslash geq\; x^\; y^$, which holds for $x,y\; \backslash geq\; 0,\; \backslash lambda\; \backslash in\; [0,1]$. In particular, $\backslash mu(\backslash lambda\; A\; +\; (1\; -\; \backslash lambda)\; B)\; \backslash geq\; (\backslash lambda\; \backslash mu(A)^\; +\; (1\; -\; \backslash lambda)\; \backslash mu(B)^)^n\; \backslash geq\; \backslash mu(A)^\; \backslash mu(B)^$. 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 $\backslash lambda\; \backslash in\; (0,1)$. Let $f,g,h\; :\; \backslash mathbb^n\; \backslash to\; \backslash mathbb\_+$ be non-negative, measurable functions satisfying $h(\backslash lambda\; x\; +\; (1\; -\; \backslash lambda)y)\; \backslash geq\; f(x)^\; g(y)^$ for all $x,y\; \backslash in\; \backslash mathbb^n$. Then $\backslash int\_\; h(x)\; dx\; \backslash geq\; (\backslash int\_\; f(x)\; dx)^\; (\backslash int\_\; g(x)\; dx)^$.

Proof (Mostly following this lecture):

We will need the one dimensional version of BM, namely that if $A,\; B,\; A\; +\; B\; \backslash subseteq\; \backslash mathbb$ are measurable, then $\backslash mu\; (A\; +\; B)\; \backslash geq\; \backslash mu(A)\; +\; \backslash mu(B)$. First, assuming that $A,\; B$ are bounded, we shift $A,\; B$ so that $A\; \backslash cap\; B\; =\; \backslash$. Thus, $A\; +\; B\; \backslash supset\; A\; \backslash cup\; B$, whence by almost disjointedness we have that $\backslash mu(A\; +\; B)\; \backslash geq\; \backslash mu(A)\; +\; \backslash mu(B)$. We then pass to the unbounded case by filtering with the intervals $[-k,k].$

We first show the $n\; =\; 1$ case of the PL inequality. Let $L\_h(t)\; =\; \backslash$. $L\_h(t)\; \backslash supseteq\; \backslash lambda\; L\_f(t)\; +\; (1\; -\; \backslash lambda)\; L\_g(t)$. Thus, by the one-dimensional version of Brunn–Minkowski, we have that $\backslash mu(L\_h(t))\; \backslash geq\; \backslash mu(\backslash lambda\; L\_f(t)\; +\; (1\; -\; \backslash lambda)\; L\_g(t))\; \backslash geq\; \backslash lambda\; \backslash mu(L\_f(t))\; +\; (1\; -\; \backslash lambda)\; \backslash mu(L\_g(t))$. We recall that if $f(x)$ is non-negative, then Fubini's theorem implies $\backslash int\_\; h(x)\; dx\; =\; \backslash int\_\; \backslash mu(L\_h(t))\; dt$. Then, we have that $\backslash int\_\; h(x)\; dx\; =\; \backslash int\_\; \backslash mu(L\_h(t))\; dt\; \backslash geq\; \backslash lambda\; \backslash int\_\; \backslash mu(L\_f(t))\; +\; (1\; -\; \backslash lambda)\; \backslash int\_\; \backslash mu(L\_g(t))\; =\; \backslash lambda\; \backslash int\_\; f(x)\; dx\; +\; (1\; -\; \backslash lambda)\; \backslash int\_\; g(x)\; dx\; \backslash geq\; (\backslash int\_\; f(x)\; dx)^\; (\backslash int\_\; g(x)\; dx)^$, where in the last step we use the weighted AM–GM inequality, which asserts that $\backslash lambda\; x\; +\; (1\; -\; \backslash lambda)\; y\; \backslash geq\; x^\; y^$ for $\backslash lambda\; \backslash in\; (0,1),\; x,y\; \backslash geq\; 0$.

Now we prove the $n\; >\; 1$ case. For $x,y\; \backslash in\; \backslash mathbb^,\; \backslash alpha,\backslash beta\; \backslash in\; \backslash mathbb$, we pick $\backslash lambda\; \backslash in\; [0,1]$ and set $\backslash gamma\; =\; \backslash lambda\; \backslash alpha\; +\; (1\; -\; \backslash lambda)\; \backslash beta$. For any c, we define $h\_(x)\; =\; h(x,\; c)$, that is, defining a new function on n-1 variables by setting the last variable to be $c$. Applying the hypothesis and doing nothing but formal manipulation of the definitions, we have that $h\_\; (\backslash lambda\; x\; +\; (1\; -\; \backslash lambda)y)\; =\; h\; (\backslash lambda\; x\; +\; (1\; -\; \backslash lambda)\; y,\; \backslash lambda\; \backslash alpha\; +\; (1\; -\; \backslash lambda)\; \backslash beta))\; =\; h\; (\backslash lambda\; (x,\; \backslash alpha)\; +\; (1\; -\; \backslash lambda)\; (y,\; \backslash beta))\; \backslash geq\; f(x,\; \backslash alpha)^\; g(y,\; \backslash beta)^\; =\; f\_(x)^\; g\_(y)^$.

Thus, by the inductive case applied to the functions $h\_,\; f\_,\; g\_$, we obtain $\backslash int\_\; h\_(z)\; dz\; \backslash geq\; (\backslash int\_\; f\_(z)\; dz)^\; (\backslash int\_\; g\_(z)\; dz)^$. We define $H(\backslash gamma)\; :=\; \backslash int\_\; h\_(z)\; dz$ and $F(\backslash alpha),\; G(\backslash beta)$ similarly. In this notation, the previous calculation can be rewritten as: $H(\backslash lambda\; \backslash alpha\; +\; (1\; -\; \backslash lambda)\; \backslash beta)\; \backslash geq\; F(\backslash alpha)^\; G(\backslash beta)^$. Since we have proven this for any fixed $\backslash alpha,\; \backslash beta\; \backslash in\; \backslash mathbb$, this means that the function $H,F,G$ satisfy the hypothesis for the one dimensional version of the PL theorem. Thus, we have that $\backslash int\_\; H(\backslash gamma)\; d\; \backslash gamma\; \backslash geq\; (\backslash int\_\; F(\backslash alpha)\; d\; \backslash alpha)^\; (\backslash int\_\; F(\backslash beta)\; d\; \backslash beta)^$, 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 $h\; =\; 1\_,\; f\; =\; 1\_A,\; g\; =\; 1\_B$.

• 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 $A,\; B,\; \backslash lambda\; A\; +\; (1\; -\; \backslash lambda)\; B$ Prékopa–Leindler inequality quickly gives the multiplicative version of Brunn–Minkowski: $\backslash mu\; (\backslash lambda\; A\; +\; (1\; -\; \backslash lambda)\; B)\; \backslash geq\; \backslash mu(A)^\; \backslash mu(B)^$. 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 $A\text{'}\; =\; \backslash frac,\; B\text{'}\; =\; \backslash frac$. We define $\backslash lambda\text{'}\; =\; \backslash frac$; $1\; -\; \backslash lambda\text{'}\; =\; \backslash frac$. With these definitions, and using that $\backslash mu(A\text{'})\; =\; \backslash mu(B\text{'})\; =\; 1$, we calculate using the multiplicative Brunn–Minkowski inequality that:

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

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

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\; \backslash subseteq\; \backslash mathbb^n$. Let $K(x)\; =\; K\; \backslash cap\; \backslash$ be vertical slices of K. Define $r(x)\; =\; \backslash mu(K(x))^$ 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(\backslash lambda\; x\; +\; (1\; -\; \backslash lambda)y)\; \backslash supseteq\; \backslash lambda\; K(x)\; +\; (1\; -\; \backslash lambda)\; K(y)$. Applying the Brunn–Minkowski inequality gives $r(K(\backslash lambda\; x\; +\; (1\; -\; \backslash lambda)y))\; \backslash geq\; \backslash lambda\; r\; (K(x))\; +\; (1\; -\; \backslash lambda)\; r\; (K(y))$, provided $K(x)\; \backslash not\; =\; \backslash emptyset,\; K(y)\; \backslash not\; =\; \backslash 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$. Fix some line $l$ and for each $t\; \backslash in\; l$ let $H\_t$ denote the affine hyperplane orthogonal to $l$ that passes through $t$. Define, $r(t)\; =\; Vol(K\; \backslash cap\; H\_t)$; as discussed in the previous section, this function is concave. Now, let $K\text{'}\; =\; \backslash bigcup\_\; B(t,\; r(t))\; \backslash cap\; H\_t$. That is, $K\text{'}$ is obtained from $K$ by replacing each slice $H\_t\; \backslash cap\; K$ with a disc of the same $(n-1)$-dimensional volume centered $l$ inside of $H\_t$. The concavity of the radius function defined in the previous section implies that that $K\text{'}$ is convex. This construction is called the Brunn–Minkowski symmetrization.

Grunbaum's theorem

Theorem (Grunbaum's theorem):^[2] Consider a convex body $K\; \backslash subseteq\; \backslash mathbb^n$. Let $H$ be any half-space containing the center of mass of $K$; that is, the expected location of a uniform point sampled from $K.$ Then $\backslash mu(H\; \backslash cap\; K)\; \backslash geq\; (\backslash frac)^n\; \backslash mu(K)\; \backslash geq\; \backslash frac\; \backslash mu(K)$.

Grunbaum's theorem can be proven using Brunn–Minkowski inequality, specifically the convexity of the Brunn–Minkowski symmetrization.^[3]

Grunbaum's inequality has the following fair cake cutting interpretation. Suppose two players are playing a game of cutting up an $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$ 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$ respectively. Note, however, that in $n$ dimensions, calculating the centroid is $\backslash \#\; P$ hard,^[4] 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.^[5]

Isoperimetric inequality

Let $B\; =\; B(0,1)\; =\; \backslash$ denote the unit ball. For a convex body, K, let $S(K)\; =\; \backslash lim\_\; \backslash frac$ define its surface area. This agrees with the usual meaning of surface area by the Minkowski-Steiner formula. Consider the function $c(X)\; =\; \backslash frac$. The isoperimetric inequality states that this is maximized on Euclidean balls.

First, observe that Brunn–Minkowski implies $\backslash mu(K\; +\; \backslash epsilon\; B)\; \backslash geq\; (\backslash mu(K)^\; +\; \backslash epsilon\; V(B)^)^n\; =\; \backslash mu(K)\; (1\; +\; \backslash epsilon\; (\backslash frac)^)^n\; \backslash geq\; \backslash mu(K)\; (1\; +\; n\; \backslash epsilon\; (\backslash frac)^),$ where in the last inequality we used that $(1\; +\; x)^n\; \backslash geq\; 1\; +\; nx$ for $x\; \backslash geq\; 0$. We use this calculation to lower bound the surface area of $K$ via $S(K)\; =\; \backslash lim\_\; \backslash frac\; \backslash geq\; n\; \backslash mu(K)\; (\backslash frac)^.$ Next, we use the fact that $S(B)\; =\; n\; \backslash mu(B)$, which follows from the Minkowski-Steiner formula, to calculate $\backslash frac\; =\; \backslash frac\; \backslash geq\; \backslash frac\; =\; \backslash mu(K)^\; \backslash mu(B)^.$ Rearranging this yields the isoperimetric inequality: $\backslash frac\; \backslash geq\; \backslash frac.$

Applications to inequalities between mixed volumes

The Brunn–Minkowski inequality can be used to deduce the following inequality $V(K,\; \backslash ldots,\; K,\; L)^n\; \backslash geq\; V(K)^\; V(L)$, where the $V(K,\; \backslash 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.)

We recall the following facts about mixed volumes : $\backslash mu\; (\backslash lambda\_1\; K\_1\; +\; \backslash lambda\_2\; K\_2)\; =\; \backslash sum\_^r\; V(K\_,\; \backslash ldots,\; V(K\_)\; \backslash lambda\_\; \backslash ldots\; \backslash lambda\_$, so that in particular if $g(t)\; =\; \backslash mu\; (K\; +\; tL)\; =\; \backslash mu(V)\; +\; n\; V(K,\; \backslash ldots,\; K,\; L)\; t\; +\; \backslash ldots$, then $g\text{'}(0)\; =\; n\; V(K,\; \backslash ldots,\; K,\; L)$.

Let $f(t)\; :=\; \backslash mu(K\; +\; tL)^$. Brunn's theorem implies that this is concave for $t\; \backslash in\; [0,1]$. Thus, $f^+(0)\; \backslash geq\; f(1)\; -\; f(0)\; =\; \backslash mu(K\; +\; L)^\; -\; V(K)^$, where $f^+(0)$ denotes the right derivative. We also have that $f^+(0)\; =\; \backslash frac\; \backslash mu(K)^\; n\; V(K,\backslash ldots,\; K,L)$. From this we get $\backslash mu(K)^\; V(K,\; \backslash ldots,\; K,L)\; \backslash geq\; \backslash mu(K\; +\; L)^\; -\; V(K)^\; \backslash geq\; V(L)^$, where we applied BM in the last inequality.

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$ be the unit sphere in $\backslash mathbb^n$. Let $X\; \backslash subseteq\; S$. Define $X\_\; =\; \backslash$, where d refers to the Euclidean distance in $\backslash mathbb^n$. Let $\backslash nu$ denote the surface area on the sphere. Then, for any $\backslash epsilon\; \backslash in\; (0,1\; ]$ we have that $\backslash frac\; \backslash geq\; 1\; -\; \backslash frac\; e^$.

Proof: Let $\backslash delta\; =\; \backslash epsilon^2\; /\; 8$, and let $Y\; =\; S\; \backslash setminus\; X\_$. Then, for $x\; \backslash in\; X,\; y\; \backslash in\; Y$ one can show, using $\backslash frac\; ||x\; +\; y||^2\; =\; ||x||^2\; +\; ||y||^2\; -\; \backslash frac||x\; -\; y||^2$ and $\backslash sqrt\; \backslash leq\; 1\; -\; x/2$ for $x\; \backslash leq\; 1$, that $||\; \backslash frac\; ||\; \backslash leq\; 1\; -\; \backslash delta$. In particular, $\backslash frac\; \backslash in\; (1\; -\; \backslash delta)\; B(0,1)$.

We let $\backslash overline\; =\; \backslash text(X,\; \backslash ),\; \backslash overline\; =\; \backslash text(Y,\; \backslash )$, and aim to show that $\backslash frac\; \backslash subseteq\; (1\; -\; \backslash delta)\; B(0,1)$. Let $x\; \backslash in\; X,\; y\; \backslash in\; Y,\; \backslash alpha,\; \backslash beta\; \backslash in\; [0,1],\; \backslash bar\; =\; \backslash alpha\; x,\; \backslash bar\; =\; \backslash alpha\; y$. The argument below will be symmetric in $\backslash bar,\; \backslash bar$, so we assume without loss of generality that $\backslash alpha\; \backslash geq\; \backslash beta$ and set $\backslash gamma\; =\; \backslash beta\; /\; \backslash alpha\; \backslash leq\; 1$. Then,

(\bar{x)/(+) \bar{y}}{ 2 } = (\alpha x + \beta y)/(2) = \alpha (x + \gamma y)/(2) = \alpha ( \gamma (x + y)/(2) + ( 1 - \gamma) (x)/(2) ) = \alpha \gamma (x + y)/(2) + \alpha ( 1 - \gamma) (x)/(2) .

This implies that $\backslash frac\; \backslash in\; \backslash alpha\; \backslash gamma\; (1\; -\; \backslash delta)\; B\; +\; \backslash alpha\; (1\; -\; \backslash gamma)\; (1\; -\; \backslash delta)\; B\; =\; \backslash alpha\; (1\; -\; \backslash delta)\; B\; \backslash subseteq\; (1\; -\; \backslash delta)\; B$. (Using that for any convex body K and $\backslash gamma\; \backslash in\; [0,1]$, $\backslash gamma\; K\; +\; (1\; -\; \backslash gamma)\; K\; =\; K$.)

Thus, we know that $\backslash frac\; \backslash subseteq\; (1\; -\; \backslash delta)\; B(0,1)$, so $\backslash mu\; (\backslash frac)\; \backslash leq\; (1\; -\; \backslash delta)^n\; \backslash mu(B(0,1))$. We apply the multiplicative form of the Brunn–Minkowski inequality to lower bound the first term by $\backslash sqrt$, giving us $(1\; -\; \backslash delta)^n\; \backslash mu(B)\; \backslash geq\; \backslash mu(\backslash bar)^\; \backslash mu(\backslash bar)^$.

1 - (\nu(X _{\epsilon} ))/(\nu(S)) = (\nu(Y))/(\nu(S)) = (\mu( \bar{Y)/()}{\mu() B)} \leq ( 1 - \delta) ^{2n} (\mu(B))/(\mu(\bar{X) )} \leq ( 1 - \delta) ^{2n} (\nu(S))/(\nu(X)) \leq e (\nu(S))/(\nu(X)) = e ^{- n \epsilon ^{2} / 4} (\nu(S))/(\nu(X)) . QEDVersion 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ⁿ and every 0 ≤ t ≤ 1,

\left[ \mu (t A + ( 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 strictfor 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$ an $l\; \backslash times\; l$ square in the plane, and $B$ a ball of radius $\backslash epsilon$. In this case, $A\; +\; B$ is a rounded square, and its volume can be accounted for as the four rounded quarter circles of radius $\backslash epsilon$, the four rectangles of dimensions $l\; \backslash times\; \backslash epsilon$ along the sides, and the original square. Thus, $\backslash mu(A\; +\; B)\; =\; l^2\; +\; 4\; \backslash epsilon\; l\; +\; \backslash frac\; \backslash pi\; \backslash epsilon^2\; =\; \backslash mu(A)\; +\; 4\; \backslash epsilon\; l\; +\; \backslash mu(B)\; \backslash geq\; \backslash mu(A)\; +\; 2\; \backslash sqrt\; \backslash epsilon\; l\; +\; \backslash mu(B)\; =\; \backslash mu(A)\; +\; 2\; \backslash sqrt\; +\; \backslash mu(B)\; =\; (\backslash mu(A)^\; +\; \backslash mu(B)^)^2$.

This example also hints at the theory of mixed-volumes, since the terms that appear in the expansion of the volume of $A\; +\; B$ correspond to the differently dimensional pieces of A. In particular, if we rewrite Brunn–Minkowski as $\backslash mu(A\; +\; B)\; \backslash geq\; (\backslash mu(A)^\; +\; \backslash mu(B)^)^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 $\backslash mu(A\; +\; B)\; =\; V(A,\; \backslash ldots,\; A)\; +\; n\; V(B,\; A,\; \backslash ldots,\; A)\; +\; \backslash ldots\; +\; V(B,\backslash ldots,\; B,\; A,\backslash ldots,A)\; +\; \backslash ldots\; n\; V(B,\backslash ldots,\; B,A)\; +\; \backslash mu(B)$. This same phenomenon can also be seen for the sum of an n-dimensional $l\; \backslash times\; l$ box and a ball of radius $\backslash epsilon$, where the cross terms in $(\backslash mu(A)^\; +\; \backslash mu(B)^)^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$ denotes the middle third Cantor set, then it is an exercise in analysis to show that $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,^{[6] [7]} and combinatorial versions about counting sets of points inside the integer lattice.^[8]

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

• Book: Brunn, H. . Hermann Brunn . Über Ovale und Eiflächen . 1887 . Inaugural Dissertation, München.
• Book: Fenchel , Werner . Werner Fenchel . Bonnesen, Tommy . Theorie der konvexen Körper . Ergebnisse der Mathematik und ihrer Grenzgebiete . 3 . 1. Verlag von Julius Springer . Berlin . 1934.
• Book: Fenchel , Werner . Werner Fenchel . Bonnesen, Tommy . Theory of convex bodies . registration . L. Boron, C. Christenson and B. Smith. BCS Associates . Moscow, Idaho . 1987. 9780914351023 .
• Book: Dacorogna, Bernard . Introduction to the Calculus of Variations . Imperial College Press . London . 2004 . 1-86094-508-2.
• Heinrich Guggenheimer (1977) Applicable Geometry, page 146, Krieger, Huntington .
• Lyusternik . Lazar A. . Lazar Lyusternik . Die Brunn–Minkowskische Ungleichnung für beliebige messbare Mengen . Comptes Rendus de l'Académie des Sciences de l'URSS . Nouvelle Série . III . 1935 . 55 - 58.
• Book: Minkowski, Hermann . Hermann Minkowski

. Hermann Minkowski . Geometrie der Zahlen . Leipzig . Teubner . 1896.

• Ruzsa. Imre Z.. Imre Z. Ruzsa. The Brunn–Minkowski inequality and nonconvex sets. Geometriae Dedicata. 67. 10.1023/A:1004958110076. 1997. 3. 337–348. 1475877. 117749981 .
• Rolf Schneider, Convex bodies: the Brunn–Minkowski theory, Cambridge University Press, Cambridge, 1993.

Notes and References

1. 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. .
2. Grünbaum . B. . Branko Grünbaum . 1960 . Partitions of mass-distributions and of convex bodies by hyperplanes . Pacific Journal of Mathematics . 10 . 1257–1261 . 124818.
3. See these lecture notes for a proof sketch.
4. Rademacher . Luis . Erickson . Jeff . Approximating the centroid is hard . 10.1145/1247069.1247123 . 302–305 . Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, South Korea, June 6–8, 2007 . 2007.
5. See theorem 2.1 in these notes.
6. Book: GROMOV, M. . Advances in Differential Geometry and Topology . CONVEX SETS AND KÄHLER MANIFOLDS . WORLD SCIENTIFIC . 1990 . 978-981-02-0494-5 . 10.1142/9789814439381_0001 . 1–38.
7. Neeb . Karl-Hermann . Kaehler Geometry, Momentum Maps and Convex Sets . 2015-10-12 . math.SG . 1510.03289v1.
8. Hernández Cifre . María A. . Iglesias . David . Nicolás . Jesús Yepes . On a Discrete Brunn--Minkowski Type Inequality . SIAM Journal on Discrete Mathematics . Society for Industrial & Applied Mathematics (SIAM) . 32 . 3 . 2018 . 0895-4801 . 10.1137/18m1166067 . 1840–1856.