Ball - An Elementary Introduction to Modern Convex Geometry.pdf - Topologia i Geometria - renvox

Flavors of Geometry

MSRI Publications

Volume 31 , 1997

An Elementary Introduction

to Modern Convex Geometry

KEITH BALL

Contents

Preface

Lecture 1. Basic Notions

Lecture 2. Spherical Sections of the Cube

Lecture 3. Fritz John's Theorem

Lecture 4. Volume Ratios and Spherical Sections of the Octahedron

Lecture 5. The Brunn{Minkowski Inequality and Its Extensions

Lecture 6. Convolutions and Volume Ratios: The Reverse Isoperimetric

Problem 32

Lecture 7. The Central Limit Theorem and Large Deviation Inequalities 37

Lecture 8. Concentration of Measure in Geometry

Lecture 9. Dvoretzky's Theorem

Acknowledgements

References

Index

Preface

These notes are based, somewhat loosely, on three series of lectures given by

myself, J. Lindenstrauss and G. Schechtman, during the Introductory Workshop

in Convex Geometry held at the Mathematical Sciences Research Institute in

Berkeley, early in 1996. A fourth series was given by B. Bollobas, on rapid

mixing and random volume algorithms; they are found elsewhere in this book.

The material discussed in these notes is not, for the most part, very new, but

the presentation has been strongly inﬂuenced by recent developments: among

other things, it has been possible to simplify many of the arguments in the light

of later discoveries. Instead of giving a comprehensive description of the state of

the art, I have tried to describe two or three of the more important ideas that

have shaped the modern view of convex geometry, and to make them as accessible

KEITH BALL

as possible to a broad audience. In most places, I have adopted an informal style

that I hope retains some of the spontaneity of the original lectures. Needless to

say, my fellow lecturers cannot be held responsible for any shortcomings of this

presentation.

I should mention that there are large areas of research that fall under the

very general name of convex geometry, but that will barely be touched upon in

these notes. The most obvious such area is the classical or \Brunn{Minkowski"

theory, which is well covered in [Schneider 1993]. Another noticeable omission is

the combinatorial theory of polytopes: a standard reference here is [Brndsted

1983].

Lecture 1. Basic Notions

The topic of these notes is convex geometry. The objects of study are con-

vex bodies: compact, convex subsets of Euclidean spaces, that have nonempty

interior. Convex sets occur naturally in many areas of mathematics: linear pro-

gramming, probability theory, functional analysis, partial dierential equations,

information theory, and the geometry of numbers, to name a few.

Although convexity is a simple property to formulate, convex bodies possess

a surprisingly rich structure. There are several themes running through these

notes: perhaps the most obvious one can be summed up in the sentence: \All

convex bodies behave a bit like Euclidean balls." Before we look at some ways in

which this is true it is a good idea to point out ways in which it denitely is not.

This lecture will be devoted to the introduction of a few basic examples that we

need to keep at the backs of our minds, and one or two well known principles.

The only notational conventions that are worth specifying at this point are

the following. We will use

for which ( x ) < ( y )

whenever x

L .

The simplest example of a convex body in R n is the cube, [

K and y

1 ; 1] n . This does

not look much like the Euclidean ball. The largest ball inside the cube has radius

1, while the smallest ball containing it has radius p n , since the corners of the

cube are this far from the origin. So, as the dimension grows, the cube resembles

a ball less and less.

The second example to which we shall refer is the n -dimensional regular solid

simplex: the convex hull of n + 1 equally spaced points. For this body, the ratio

of the radii of inscribed and circumscribed balls is n : even worse than for the

cube. The two-dimensional case is shown in Figure 1. In Lecture 3 we shall see

−

to denote the standard Euclidean norm on R n .For

abody K ,vol( K ) will mean the volume measure of the appropriate dimension.

The most fundamental principle in convexity is the Hahn{Banach separation

theorem , which guarantees that each convex body is an intersection of half-spaces,

and that at each point of the boundary of a convex body, there is at least one

supporting hyperplane. More generally, if K and L are disjoint, compact, convex

subsets of R n , then there is a linear functional : R n

AN ELEMENTARY INTRODUCTION TO MODERN CONVEX GEOMETRY 3

Figure 1.

Inscribed and circumscribed spheres for an n -simplex.

that these ratios are extremal in a certain well-dened sense.

Solid simplices are particular examples of cones. By a cone in R n we just mean

the convex hull of a single point and some convex body of dimension n

−

1 (Figure

2). In R n , the volume of a cone of height h over a base of ( n

−

1)-dimensional

volume B is Bh=n .

The third example, which we shall investigate more closely in Lecture 4, is the

n -dimensional \octahedron", or cross-polytope: the convex hull of the 2 n points

(

1 ; 0 ; 0 ;:::; 0), (0 ;

1 ; 0 ;:::; 0), ..., (0 ; 0 ;:::; 0 ;

1). Since this is the unit ball

has radius 1, the inscribed sphere has radius 1 = p n ; so, as for the cube, the ratio

is p n : see Figure 3, left.

B n

. The circumscribing sphere of B n

is made up of 2 n pieces similar to the piece whose points have nonnegative

coordinates, illustrated in Figure 3, right. This piece is a cone of height 1 over

a base, which is the analogous piece in R n− 1 . By induction, its volume is

1= 1

n ! ;

−

and hence the volume of B n

is 2 n =n !.

Figure 2.

Acone.

of the ` 1 norm on R n , we shall denote it B n

KEITH BALL

(0 ; 0 ; 1)

( n ;:::; n

)

(1 ; 0 ;:::; 0)

(0 ; 1 ; 0)

(1 ; 0 ; 0)

Figure 3.

The cross-polytope (left) and one orthant thereof (right).

The nal example is the Euclidean ball itself,

= x 2

1 :

B n

n :

x i

very easily in terms of v n : the argument goes back to the

ancients. We think of the ball as being built of thin cones of height 1: see Figure

4, left. Since the volume of each of these cones is 1 =n times its base area, the

surface of the ball has area nv n . The sphere of radius 1, which is the surface of

the ball, we shall denote S n− 1 .

To calculate v n , we use integration in spherical polar coordinates. To specify

apoint x we use two coordinates: r , its distance from 0, and , a point on the

sphere, which species the direction of x . The point plays the role of n

1real

coordinates. Clearly, in this representation, x = r : see Figure 4, right. We can

−

Figure 4.

Computing the volume of the Euclidean ball.

We shall need to know the volume of the ball: call it v n . We can calculate the

surface \area" of B n

AN ELEMENTARY INTRODUCTION TO MODERN CONVEX GEOMETRY 5

write the integral of a function on R n

f = Z 1

r =0

f ( r )\ d " r n− 1 dr:

(1.1)

S n − 1

The factor r n− 1 appears because the sphere of radius r has area r n− 1 times that

of S n− 1 . The notation \ d " stands for \area" measure on the sphere: its total

mass is the surface area nv n . The most important feature of this measure is

its rotational invariance: if A is a subset of the sphere and U is an orthogonal

transformation of R n ,then UA has the same measure as A . Throughout these

lectures we shall normalise integrals like that in (1.1) by pulling out the factor

nv n , and write

f = nv n Z 1

f ( r ) r n− 1 d ( ) dr

S n − 1

where = n− 1 is the rotation-invariant measure on S n− 1 of total mass 1. To

nd v n , we integrate the function

exp

x i

− 2

both ways. This function is at once invariant under rotations and a product of

functions depending upon separate coordinates; this is what makes the method

work. The integral is

f = Z

Z 1

e −x i = 2 dx i = p 2 n :

e −x i = 2 dx =

−1

But this equals

nv n Z 1

e −r 2 = 2 r n− 1 ddr = nv n Z 1

e −r 2 = 2 r n− 1 dr = v n 2 n= 2 n

2 +1 :

S n − 1

Hence

n= 2

+1 :

This is extremely small if n is large. From Stirling's formula we know that

v n =

p 2 e −n= 2 n

( n +1) = 2 ;

so that v n is roughly

r 2 e

To put it another way, the Euclidean ball of volume 1has radius about

r n

2 e ;

which is pretty big.

Ball - An Elementary Introduction to Modern Convex Geometry.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: