Lecture 13: Brunn-Minkowski Inequality (Cont.), Brunn’s Theorem, Isoperimetric Inequality, Grunbaum’s Theorem

18.409 An Algorithmist’s Toolkit October 27, 2009 Lecture 13 Lecturer: Jonathan Kelner 1 Scribe: Jonathan Pines (2009) Outline Last time, we proved the Brunn-Minkowski inequality for boxes. Today we’ll go over the general version of the Brunn-Minkowski inequality and then move on to applications, including the Isoperimetric inequality and Grunbaum’s theorem. 2 The Brunn-Minkowski inequality Theorem 1 Let A, B ⊆ Rn be compact measurable sets. Then (Vol(A ⊕ B))1/n ≥ (Vol(A))1/n + (Vol(B))1/n . (1) The equality holds when A is a translation of a dilation of B (up to zero-measure sets). Proof An equivalent version of Brunn-Minkowski inquality is given by � �1/n Vol(λA ⊕ (1 − λ)B) ≥ λ(Vol(A))1/n + (1 − λ)(Vol(B))1/n , ∀λ ∈ [0, 1]. (2) The equivalence of (1) and (2) follows from the fact that Vol(λA) = λn Vol(A): � �1/n Vol(λA ⊕ (1 − λ)B) � �1/n + Vol((1 − λ)B) � �1/n � �1/n = λn Vol(A) + (1 − λ)n Vol(B) � �1/n � �1/n = λ Vol(A) + (1 − λ) Vol(B) . ≥ � Vol(λA) �1/n (3) The inequality (2) implies that the nth root of the volume function is concave with respect to the Minkowski sum. Here, we sketch the proof for Theorem 1 by proving (1) for any set constructed from a finite collection of boxes. The proof can be generalized to any measurable set by approximating the set with a sequence of finite collections of boxes and taking the limit. We omit the analysis details here. Let A and B be finite collections of boxes in Rn . We prove (1) by induction on the number of boxes in A ∪ B. Define the following subsets of Rn : A+ = A ∩ {x ∈ Rn |xn ≥ 0} , A− B + = B ∩ {x ∈ Rn |xn ≥ 0} , B − = A ∩ {x ∈ Rn |xn ≤ 0}, = B ∩ {x ∈ Rn |xn ≤ 0}. (4) Translate A and B such that the following conditions hold: 1. A has some pair of boxes separated by the hyperplane {x ∈ Rn |x1 = 0}. i.e. there exists a box that lies completely in the halfspace {x ∈ Rn |x1 ≥ 0} and there is some other box that lies in its complement half-space (see figure 1). (If there’s no such box in that direction we can change coordinates.) 2. It holds that Vol(A+ ) Vol(B + ) = . Vol(A) Vol(B) 13-1 (5) Note that translation of A or B just translates A ⊕ B, so any statement about the translated sets holds for the original ones. Since A+ and A− are strict subsets of A, we know that A+ ∪ B + and A− ∪ B − have fewer boxes than A ∪ B. Therefore, (1) is true for them by the induction hypothesis. Moreover, A+ ⊕ B + and A− ⊕ B − are disjoint because they differ in sign of the x1 coordinate. Hence, we have Vol(A ⊕ B) ≥ Vol(A+ ⊕ B + ) + Vol(A− ⊕ B − ) �n � �n � ≥ Vol(A+ )1/n + Vol(B + )1/n + Vol(A− )1/n + Vol(B − )1/n � � � � �1/n �n �1/n �n Vol(B + ) Vol(B − ) + − + Vol(A ) 1 + = Vol(A ) 1 + Vol(A+ ) Vol(A− ) � � n � �1/n � � Vol(B) = Vol(A+ ) + Vol(A− ) 1 + Vol(A) � � n = Vol(A)1/n + Vol(B)1/n , (6) where the second inequality follows from the induction hypothesis, and the second equality is implied by (5). Figure 1: A+ and B + as defined in the proof of Theorem 1. 3 Applications of Brunn-Minkowski Inequality In this section, we demonstrate the power of Brunn-Minkowski inequality by using it to prove some important theorems in convex geometry. 3.1 Volumes of Parallel Slices Let K ∈ Rn be a convex body. A parallel slice, denoted by Kt , is defined as an intersection of the body with a hyperplane, i.e. (7) Kt = K ∩ {x ∈ Rn |x1 = t}. 13-2 Define the volume of the parallel slice Kt , denoted by vK (t), to be its (n − 1)-dimensional volume. vK (t) = Voln−1 (Kt ). (8) We are interested in the behavior of the function vK (t), and in particular, in whether it is concave. Consider the Euclidean ball in Rn . The following plots of vK (t) for different n suggest that except for n = 2, the function vK (t) is not concave in t. As another example, consider a circular cone in R3 . The volume of a parallel slice is proportional to t2 , so vK (t) is not concave. More generally, vK (t) is proportional to tn−1 for a circular cone in Rn . This suggests that the (n − 1)th root of vK is a concave function. This guess is verified by Brunn’s theorem. Theorem 2 (Brunn’s Theorem) Let K be a convex body, and let vK (t) be defined as in (8). Then the 1 function vK (t) n−1 is concave. Proof Let s, r, t ∈ R with s = (1 − λ)r + λt for some λ ∈ [0, 1]. Define the (n − 1)-dimensional slices Kr , Ks , Kt as in (7). First, we claim that (1 − λ)Ar ⊕ λAt ⊆ As . (9) We show this by proving that for any x ∈ Ar , y ∈ At , we have z = (1 − λ)x ⊕ λy ∈ As , as follows. Connect the points (r, x) and (t, y) with a straight line (see figure 2). By convexity of K, the line lies completely in the body. In particular, the point (s, z), which is a convex combination of (r, x) and (t, y), lies in As . Therefore, z ∈ As and the claim in (9) is true. Now, by applying the version of Brunn-Minkowski inequality in (2), we have 1 ≥ (1 − λ)Vol(Ar ) n−1 + λVol(At ) n−1 1 ≥ (1 − λ)vK (r) n−1 + λvK (t) n−1 Vol(As ) n−1 ⇒ vK (s) n−1 1 1 1 1 (10) Figure by MIT OpenCourseWare. Figure 2: n-dimensional convex body K in Theorem 2. 3.2 Isoperimetric Inequality A few lectures ago, we asked the question of finding the body of a given volume with the smallest surface area. The answer, namely the Euclidean ball, is a direct consequence of the Isoperimetric inequality. Before stating the theorem, let us define the surface area of a body using the Minkowski sum. Definition 3 Let K be a body. The surface area of K is defined as the differential rate of volume increase as we add a small Euclidean ball to the body, i.e., Vol(K ⊕ B2n ) − Vol(K) . e→0  S(K) = Vol(∂K) = lim 13-3 (11) Now we state the theorem: Theorem 4 (Isoperimetric inequality) For any convex body K, with n-dimensional volume V (K) and sur­ face area S(K), � � 1 �1/n � S(K) n−1 V (K) ≤ (12) V (B2n S(B2n ) Proof By applying the Brunn-Minkowski inequality, we have the following: �n � V (K ⊕ B2n ) ≥ V (K)1/n + V (B2n )1/n � � �1/n � V (B2n ) = V (K) 1 +  V (K) � � �� V (B2n ) ≥ V (K) 1 + n V (K) (13) where the second inequality is obtained by keeping the first two terms of the Taylor expansion of (1 + x)n . Now, the definition of surface area in (11) implies: � S(K) = V (∂K) ≥ V (K) + nV (K) � = nV (K) = nV (K) (B2n ) V V (K) n−1 n V (B2n ) V (K ) �1/n − V (K)  �1/n V (B2n )1/n . (14) For an n-dimensional unit ball, we have S(B2n ) = nV (B2n ). Therefore, S(K) S(B2n ) � � 1 S(K) n−1 ⇒ S(B2n ) 3.3 ≥ nV (K) � n−1 n V (B2n )1/n n−1 nV (K) n V (B2n )1/n ≥ nV (B2n ) � �1/n V (K) = V (B2n ) 1 � n−1 (15) Grunbaum’s Theorem Given a high-dimensional convex body, we would like to pick a point x such that for any cut of the body by a hyperplane, the piece containing x is big. A reasonable choice for x is the centroid, i.e. � 1 x= ydy. Vol(K) y∈K This choice guarantees to get at least half of the volume for any origin symmetric body, such as a cube or a ball. The question is how much we are guaranteed to get for a general convex body, and in particular, what body gives the worst case. Do we get a constant fraction of the body, or does the guarantee depend on dimension? 13-4 Let us first consider the simple example of a circular n-dimensional cone (figure 3). Suppose we cut the cone C by the hyperplane {x1 = x̄1 } at its centroid, where � �n−1 � h tR 1 n (16) t · Voln−1 dt = h. x̄1 = Vol(C) t=0 h n+1 Grunbaum’s theorem states that the circular cone is indeed the worst case if we choose the centroid. Figure 3: n-dimensional circular cone. First we’ll need the following lemma: Lemma 5 Let L = C ∩ {x1 ≤ x̄1 } by the left side of the cone (which is x1 -aligned with vertex at the origin). (L) ≥ 1e . Then 12 ≥ VV (C) Proof � �n n V ( n+1 C) n V (L) = = V (C) V (C) n+1 � �n n 1 1 ≤ ≤ 2 n+1 e Theorem 6 (Grunbaum’s Theorem) Let K be a convex body, and divide it into K1 and K2 using a hyper­ plane. If K1 contains the centroid of K, then 1 Vol(K1 ) ≥ . e Vol(K) (17) In particular, the hyperplane through the centroid divides the volume into almost equal pieces, and the worst case ratio is approximately 0.37 : 0.63. Proof WLOG, change coordinates with an affine transformation so that the centroid is the origin and the hyperplane H used to cut is x1 = 0. Then perform the following operations: 1. Replace every (n − 1)-dimensional slice Kt with an (n − 1)-dimensional ball with the same volume to get K  , which is convex per Lemma 7 below. 2. Turn K’ into a cone, such that the ratio gets smaller per Lemma 8 below. Lemma 7 K’ is convex. Proof Let Kt = K  ∩ {x1 = t} be a parallel slice in the modified body. The radius of Kt is proportional 1 1 to V (Kt ) n−1 . By applying Brunn-Minkowski inequality, we get that V (Kt ) n−1 is a concave function in t.  Thus K is convex. 13-5 Lemma 8 We can turn K  into a cone while decreasing the ratio.   Proof Let K+ = K  ∩ {x1 ≥ 0}, K− = K  ∩ {x1 ≤ 0}. Make a cone yQ̄0 by picking y having x1 coordinate  . Extend the code in the {x1 ≤ 0} region, so that the volume positive on the x1 -axis, and V (yQ̄0 ) = V (K+  ); name this code C  . Now by Lemma 5, the centroid of C  must lie in of the extended part equals V (K− yQ̄0 . Let H  be the translation of H along the x1 -axis so that it contains the centroid of C  . Then r(K, H) = r(C  , H) ≥ r(C  , H  ) ≥ 1/e. This completes the proof of Grunbaum’s theorem. 4 Next Time Next time, we will discuss approximating the volume of a convex body. 13-6