# Brunn–Minkowski theorem

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).

Inhalt 1 Aussage 1.1 Multiplicative version 2 On the hypothesis 2.1 Measurability 2.2 Non-emptiness 3 Beweise 4 Important corollaries 4.1 Concavity of the radius function (Brunn's theorem) 4.2 Brunn–Minkowski symmetrization of a convex body 4.3 Grunbaum's theorem 4.4 Isoperimetrische Ungleichung 4.5 Applications to inequalities between mixed volumes 4.6 Concentration of measure on the sphere and other strictly convex surfaces 5 Bemerkungen 6 Beispiele 6.1 Rounded cubes 6.2 Examples where the lower bound is loose 7 Connections to other parts of mathematics 8 Siehe auch 9 Verweise 10 References Statement Let n ≥ 1 and let μ denote the Lebesgue measure on Rn. Let A and B be two nonempty compact subsets of Rn. Then the following inequality holds: {Anzeigestil [in (A+B)]^{1/n}geq [in (EIN)]^{1/n}+[in (B)]^{1/n},} wo ein + B denotes the Minkowski sum: {displaystyle A+B:={,a+bin mathbb {R} ^{n}mid ain A, bin B,}.} The theorem is also true in the setting where {textstyle 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 {textstyle mu (lambda A+(1-Lambda )B)geq mu (EIN)^{Lambda }in (B)^{1-Lambda }} für alle {textstyle lambda in [0,1]} .

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

In one direction, use the inequality {textstyle lambda x+(1-Lambda )ygeq x^{Lambda }y^{1-Lambda }} (Young's inequality for products), which holds for {textstyle x,ygeq 0,lambda in [0,1]} . Im Speziellen, {textstyle mu (lambda A+(1-Lambda )B)geq (lambda mu (EIN)^{1/n}+(1-Lambda )in (B)^{1/n})^{n}geq mu (EIN)^{Lambda }in (B)^{1-Lambda }} .

Umgekehrt, using the multiplicative form, wir finden {textstyle mu (A+B)= ein (Lambda {frac {EIN}{Lambda }}+(1-Lambda ){frac {B}{1-Lambda }})geq {frac {in (EIN)^{Lambda }in (B)^{1-Lambda }}{Lambda ^{nlambda }(1-Lambda )^{n(1-Lambda )}}}} The right side is maximized at {displaystyle lambda =1-{frac {1}{1+e^{C}}},C={frac {1}{n}}ln {frac {in (B)}{in (EIN)}}} , which gives {textstyle mu (A+B)geq (in (EIN)^{1/n}+in (B)^{1/n})^{n}} .

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

On the hypothesis Measurability It is possible for {textstyle A,B} to be Lebesgue measurable and {textstyle A+B} to not be; a counter example can be found in "Measure zero sets with non-measurable sum." Auf der anderen Seite, wenn {textstyle A,B} are Borel measurable, dann {textstyle A+B} is the continuous image of the Borel set {textstyle Atimes 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.

We note that in the case that A and B are compact, so is A + B, being the image of the compact set {textstyle Atimes B} under the continuous addition map : {textstyle +:mathbb {R} ^{n}mal mathbb {R} ^{n}zu mathbb {R} ^{n}} , so the measurability conditions are easy to verify.

Non-emptiness The condition that {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.

show Geometric proof via cuboids and measure theory show Proof as a corollary of the Prékopa–Leindler inequality 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 {textstyle Ksubseteq mathbb {R} ^{n}} . Lassen {textstyle K(x)=Kcap {x_{1}=x}} be vertical slices of K. Definieren {textstyle r(x)= ein (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). We note that 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, wir haben das {textstyle K(lambda x+(1-Lambda )j)supseteq lambda K(x)+(1-Lambda )K(j)} . Applying the Brunn–Minkowski inequality gives {textstyle r(K(lambda x+(1-Lambda )j))geq lambda r(K(x))+(1-Lambda )r(K(j))} , bereitgestellt {textstyle K(x)not =emptyset ,K(j)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 {textstyle K} . Fix some line {textstyle l} and for each {textstyle tin l} Lassen {textstyle H_{t}} denote the affine hyperplane orthogonal to {textstyle l} das durchgeht {textstyle t} . Definieren, {textstyle r(t)=Vol(Kcap H_{t})} ; as discussed in the previous section, this function is concave. Jetzt, Lassen {textstyle K'=bigcup _{tin l,Kcap H_{t}not =emptyset }B(t,r(t))cap H_{t}} . Das ist, {textstyle K'} is obtained from {textstyle K} by replacing each slice {textstyle H_{t}cap K} with a disc of the same {textstyle (n-1)} -dimensional volume centered {textstyle l} inside of {textstyle H_{t}} . The concavity of the radius function defined in the previous section implies that that {textstyle K'} ist konvex. This construction is called the Brunn–Minkowski symmetrization.

Grunbaum's theorem Theorem (Grunbaum's theorem[Zitat benötigt]): Consider a convex body {textstyle Ksubseteq mathbb {R} ^{n}} . Lassen {textstyle H} be any half-space containing the center of mass of {textstyle K} ; das ist, the expected location of a uniform point sampled from {textstyle K.} Dann {textstyle mu (Hcap K)geq ({frac {n}{n+1}})^{n}in (K)geq {frac {1}{e}}in (K)} .

Grunbaum's theorem can be proven using Brunn–Minkowski inequality, specifically the convexity of the Brunn–Minkowski symmetrization[Zitat benötigt]. See these lecture notes for a proof sketch.

Grunbaum's inequality has the following fair cake cutting interpretation. Suppose two players are playing a game of cutting up an {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 {textstyle 1/e} fraction of the total. In dimensions 2 und 3, the most common dimensions for cakes, the bounds given by the theorem are approximately {textstyle .444,.42} beziehungsweise. Notiz, jedoch, that in {textstyle n} Maße, calculating the centroid is {textstyle #P} hard[Zitat benötigt], 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. Siehe Satz 2.1 in these notes.

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

show Proof of isoperimetric inequality via Brunn–Minkowski Applications to inequalities between mixed volumes The Brunn–Minkowski inequality can be used to deduce the following inequality {textstyle V(K,Punkte ,K,L)^{n}geq V(K)^{n-1}v(L)} , bei dem die {textstyle V(K,Punkte ,K,L)} term is a mixed-volume. Equality holds iff K,L are homothetic. (Siehe Satz 3.4.3 in Hug and Weil's course on convex geometry.) show Proof 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.

Satz: Lassen {textstyle S} be the unit sphere in {textstyle mathbb {R} ^{n}} . Lassen {textstyle Xsubseteq S} . Definieren {textstyle X_{Epsilon }={zin S:d(z,X)leq epsilon }} , where d refers to the Euclidean distance in {textstyle mathbb {R} ^{n}} . Lassen {textstyle nu } denote the surface area on the sphere. Dann, für alle {textstyle epsilon in (0,1]} wir haben das {textstyle {frac {nicht (X_{Epsilon })}{nicht (S)}}geq 1-{frac {nicht (S)}{nicht (X)}}e^{-{frac {nepsilon ^{2}}{4}}}} .

show Proof Version of this result hold also for so-called strictly convex surfaces, where the result depends on the modulus of convexity. Jedoch, the notion of surface area requires modification, sehen: the aforementioned notes on concentration of measure from Barvinok.