WEBVTT 00:00:00.046 --> 00:00:01.159 Take a sphere. 00:00:01.242 --> 00:00:04.877 Not the one in front of you, but its cousin in a thousand dimensions. 00:00:04.981 --> 00:00:08.450 Almost everything you know about the round one quietly fails up there, 00:00:08.533 --> 00:00:11.112 and it fails in a useful direction: 00:00:11.308 --> 00:00:15.325 by the end of this lecture, one fact about where a sphere keeps its area will hand us 00:00:15.325 --> 00:00:18.158 a theorem about every normed space there is. 00:00:19.555 --> 00:00:22.656 So start in three dimensions, where we can look. 00:00:22.968 --> 00:00:27.961 Here is the unit sphere, and there, drawn around its middle, is its equator. 00:00:28.158 --> 00:00:31.932 Let it turn once, so you can see it is a ball and not a disc. 00:00:32.635 --> 00:00:37.279 Now mark off a band around that equator: every point within zero point two radians 00:00:37.279 --> 00:00:40.601 of it, about twelve degrees of latitude either way. 00:00:40.797 --> 00:00:44.477 On this sphere the band is nothing special. It holds about twenty percent 00:00:44.477 --> 00:00:49.320 of the area, and you can see that: most of the surface is out in the two caps. 00:00:50.116 --> 00:00:52.938 Keep that picture, and raise the dimension. 00:00:53.135 --> 00:00:57.326 I cannot draw the sphere in dimension one thousand, but I can tell you what happens 00:00:57.326 --> 00:00:59.057 to this same band up there: 00:00:59.253 --> 00:01:02.468 it swallows essentially all of the area, and the two caps, 00:01:02.551 --> 00:01:06.592 which look like most of the sphere here, hold almost nothing at all. 00:01:07.895 --> 00:01:10.100 The reason is a picture we can draw. 00:01:10.183 --> 00:01:14.548 Slice the sphere by latitude, and ask how much area sits at each one. 00:01:14.745 --> 00:01:18.667 In dimension n the answer is proportional to sine of theta, 00:01:18.750 --> 00:01:21.154 raised to the power n minus one. 00:01:21.258 --> 00:01:26.704 For our sphere that exponent is just one, and the profile is this gentle mound. 00:01:27.408 --> 00:01:29.243 Now raise the exponent. 00:01:29.347 --> 00:01:32.320 At n equals eleven the mound sharpens. 00:01:32.516 --> 00:01:36.801 At n around fifty it is a spike, standing on the equator. 00:01:37.114 --> 00:01:42.002 The area has nowhere else to go: any latitude away from the equator has sine 00:01:42.002 --> 00:01:47.227 less than one, and a number below one, raised to the fiftieth power, is nothing. 00:01:48.624 --> 00:01:51.817 Here are the guarantees, for the very same band. 00:01:52.269 --> 00:01:56.415 On our sphere, dimension two, it holds about twenty percent. 00:01:56.867 --> 00:02:01.164 By dimension one hundred it already holds at least seventy two percent. 00:02:02.076 --> 00:02:03.746 By dimension one thousand, 00:02:03.829 --> 00:02:06.916 at least ninety nine point nine nine nine nine nine percent. 00:02:06.999 --> 00:02:11.945 And by ten thousand, everything except one part in ten to the eighty six. 00:02:12.142 --> 00:02:16.520 A band you would barely notice on a globe is, up there, the whole sphere. 00:02:17.317 --> 00:02:21.184 That is concentration of measure, and two questions come with it. 00:02:21.380 --> 00:02:25.131 Why the equator, of all places, and what guarantees those numbers? 00:02:25.328 --> 00:02:27.627 Keep one eye on where this is heading: 00:02:27.731 --> 00:02:32.028 the same phenomenon will, at the end, buy Dvoretzky's theorem. 00:02:32.224 --> 00:02:35.905 But first the why, and the why is an inequality about caps. 00:02:36.966 --> 00:02:39.217 A cap is the sphere's own disc. 00:02:39.300 --> 00:02:44.546 Pick a point x zero, and take everything within spherical distance R of it. 00:02:44.629 --> 00:02:47.135 There it is, poured around the pole. 00:02:47.218 --> 00:02:52.362 Let it turn, so you can see the cap lying on the surface, and there is its formula. 00:02:52.671 --> 00:02:54.155 Now grow it. 00:02:54.238 --> 00:03:00.242 Take any set A and fatten it by epsilon: everything within distance epsilon of A. 00:03:00.345 --> 00:03:02.282 That is the epsilon extension, 00:03:02.365 --> 00:03:07.544 written A sub epsilon, and for a cap it means the cap plus this collar. 00:03:07.741 --> 00:03:12.046 Growing a set costs area, and the bill is paid along the boundary: 00:03:12.129 --> 00:03:15.056 the longer the edge, the more the collar adds. 00:03:15.852 --> 00:03:17.885 So here is Levy's question. 00:03:18.197 --> 00:03:23.362 Among all sets of one fixed area, which shape, when you fatten it by epsilon, 00:03:23.445 --> 00:03:25.002 grows the least? 00:03:25.616 --> 00:03:28.241 Watch what happens to a bad candidate. 00:03:29.637 --> 00:03:35.617 Here is the same total area, split into two half-size caps, one at each pole. 00:03:35.930 --> 00:03:37.879 Nothing about the area changed. 00:03:37.962 --> 00:03:39.866 What changed is the edge: 00:03:40.063 --> 00:03:43.779 this set has two boundary circles where the single cap had one. 00:03:44.576 --> 00:03:47.850 Now fatten both sides by the same epsilon. 00:03:48.047 --> 00:03:50.579 The single cap grows one collar. 00:03:50.892 --> 00:03:52.596 The split set grows two, 00:03:52.679 --> 00:03:56.337 and two collars around two circles is more new area than one. 00:03:56.650 --> 00:04:00.958 Same area in, more area out: splitting was a bad trade. 00:04:02.010 --> 00:04:04.379 And that is the pattern in general. 00:04:04.483 --> 00:04:08.338 Wiggly sets, stretched sets, scattered sets: 00:04:08.791 --> 00:04:13.293 at a fixed area, every one of them carries at least as much boundary as the cap, 00:04:13.376 --> 00:04:15.360 and grows at least as fast. 00:04:15.443 --> 00:04:17.626 The cap is the minimizer. 00:04:19.023 --> 00:04:20.661 Say it precisely. 00:04:20.765 --> 00:04:25.536 If A and the cap C cover the same fraction of the sphere, then for every 00:04:25.536 --> 00:04:31.272 positive epsilon, the extension of A is at least as big as the extension of C. 00:04:31.724 --> 00:04:35.612 That is Levy's spherical isoperimetric inequality, 00:04:35.695 --> 00:04:39.074 and it is the engine under everything that follows. 00:04:39.870 --> 00:04:42.286 One more reading before we use it. 00:04:42.390 --> 00:04:45.708 The cap is solving the same problem the disc solves in the plane 00:04:45.791 --> 00:04:47.938 and the ball solves in space: 00:04:48.021 --> 00:04:50.541 least boundary for the area enclosed. 00:04:50.737 --> 00:04:54.744 On the sphere, least boundary becomes least growth. 00:04:54.940 --> 00:04:56.566 Now let us spend it. 00:04:57.690 --> 00:05:00.442 Here is the payoff move, and it is short. 00:05:00.639 --> 00:05:04.018 Take any set A covering exactly half the sphere: 00:05:04.214 --> 00:05:06.929 half is where a set and its complement balance, 00:05:07.012 --> 00:05:09.660 and it is the case that powers everything. 00:05:09.973 --> 00:05:12.215 Which cap has measure one half? 00:05:12.411 --> 00:05:14.897 The one of radius pi over two: 00:05:15.093 --> 00:05:16.464 a hemisphere. 00:05:16.916 --> 00:05:19.378 So the hemisphere is the shape to beat. 00:05:20.291 --> 00:05:21.462 Let it turn once, 00:05:21.545 --> 00:05:26.445 so that blue reads as half of a surface rather than as a lid laid across one. 00:05:27.241 --> 00:05:30.470 Fatten the hemisphere by epsilon and you get this: 00:05:30.666 --> 00:05:35.775 everything above the equator, plus a collar of angular width epsilon below it. 00:05:36.390 --> 00:05:39.560 By the isoperimetric inequality, whatever 00:05:39.560 --> 00:05:44.831 A actually was, its extension covers at least as much of the sphere as this does. 00:05:45.628 --> 00:05:48.252 So what does the grown hemisphere miss? 00:05:48.449 --> 00:05:54.626 Only this: the cap of radius pi over two minus epsilon, around the opposite pole. 00:05:54.823 --> 00:06:00.767 Call it B. The extension covers one minus the measure of B, and everything now rides 00:06:00.767 --> 00:06:02.567 on how small B is. 00:06:03.364 --> 00:06:06.801 And B is exactly the kind of region the spike killed. 00:06:06.998 --> 00:06:11.292 Every point of it sits at latitude at least epsilon away from the equator, 00:06:11.375 --> 00:06:15.625 where the sine to the n minus one profile has already collapsed. 00:06:16.240 --> 00:06:21.069 Integrate that profile and the measure of B comes out at most a constant times e 00:06:21.069 --> 00:06:24.031 to the minus c n epsilon squared. 00:06:24.943 --> 00:06:26.697 Put the chain together. 00:06:26.894 --> 00:06:28.912 Any set of measure one half, 00:06:28.995 --> 00:06:34.638 grown by epsilon, covers all of the sphere except an exponentially small remainder. 00:06:34.835 --> 00:06:37.959 The constants C and c are universal: 00:06:38.062 --> 00:06:43.647 they depend on nothing, not the dimension, not the set, not epsilon. 00:06:44.065 --> 00:06:46.887 That is the concentration inequality. 00:06:48.260 --> 00:06:50.780 How small is exponentially small? 00:06:51.348 --> 00:06:55.689 Let me plot the escaping mass, e to the minus n epsilon squared, 00:06:55.772 --> 00:06:57.375 against the dimension. 00:06:57.537 --> 00:07:02.864 Here it is for epsilon equal to zero point two, and above it, decaying slower, 00:07:02.947 --> 00:07:05.537 the thinner margin zero point one. 00:07:06.333 --> 00:07:08.285 Now ride the steep one. 00:07:08.481 --> 00:07:12.406 At n around fifty the escaping mass is already near a tenth. 00:07:12.603 --> 00:07:15.840 By one hundred and fifty it is a quarter of one percent, 00:07:15.923 --> 00:07:21.543 and off the right edge, in dimension one thousand, it is ten to the minus eighteen. 00:07:21.740 --> 00:07:23.537 And compare the two curves: 00:07:23.620 --> 00:07:29.008 halving epsilon quarters the exponent, so the thin margin decays four times slower. 00:07:29.205 --> 00:07:31.667 The square on epsilon is real. 00:07:32.092 --> 00:07:34.856 This behavior earned the spheres a title. 00:07:34.960 --> 00:07:40.043 A sequence of spaces satisfying exactly this bound, uniformly in n, 00:07:40.126 --> 00:07:44.898 is called a normal Levy family, and the spheres are the founding example. 00:07:45.095 --> 00:07:47.833 The name matters because the mechanism travels: 00:07:47.916 --> 00:07:51.412 any family with the bound inherits everything we do next. 00:07:52.572 --> 00:07:55.255 Concentration so far is about sets. 00:07:55.567 --> 00:07:58.320 The version that gets used is about functions. 00:07:58.516 --> 00:08:02.984 Take any real function f on the sphere that is Lipschitz with constant one, 00:08:03.067 --> 00:08:07.477 so it moves by at most the distance you moved, and let M be its median: 00:08:07.560 --> 00:08:10.359 half the sphere sits at or below M. 00:08:10.842 --> 00:08:12.422 Now grow that half. 00:08:12.618 --> 00:08:17.423 Every point of the extension is within epsilon of somewhere f was at most M, 00:08:17.506 --> 00:08:21.002 and a Lipschitz function cannot climb faster than distance. 00:08:21.198 --> 00:08:25.063 So on the whole extension, f is at most M plus epsilon, 00:08:25.146 --> 00:08:27.608 and the extension is nearly everything. 00:08:28.149 --> 00:08:32.187 Run the same argument from above, with the set where f is at least M, 00:08:32.270 --> 00:08:34.338 and the mirror bound comes out. 00:08:34.534 --> 00:08:36.056 Put the two together: 00:08:36.160 --> 00:08:39.513 apart from an exception of size at most twice the old one, 00:08:39.596 --> 00:08:43.416 every point of the sphere has f within epsilon of the median. 00:08:43.613 --> 00:08:48.385 There it is: essentially the entire sphere lands in this little window. 00:08:48.996 --> 00:08:51.598 Read that slowly, because it is strange. 00:08:51.794 --> 00:08:55.207 A Lipschitz function on a high-dimensional sphere is, 00:08:55.207 --> 00:08:58.238 for every practical purpose, a constant. 00:08:58.342 --> 00:09:03.033 You may design f as cleverly as you like; the geometry flattens it. 00:09:03.230 --> 00:09:07.259 Milman's insight was that this is not a curiosity but a tool. 00:09:08.656 --> 00:09:11.908 Here is the tool at work, first where we can see it. 00:09:12.104 --> 00:09:13.741 This is the cube, and everything 00:09:13.741 --> 00:09:18.154 that follows is one flat cut through its centre, taken two different ways. 00:09:18.467 --> 00:09:21.579 Let it turn first, so you know where its corners are. 00:09:22.375 --> 00:09:25.406 Cut it straight across, parallel to a face. 00:09:25.603 --> 00:09:30.515 The knife goes in flat, like this, and the face it leaves behind is a square. 00:09:30.967 --> 00:09:33.382 That much you would have guessed without me. 00:09:34.179 --> 00:09:38.670 Now tilt the knife, until it stands square to the long diagonal of the cube, 00:09:38.753 --> 00:09:42.142 the line joining one corner to the corner furthest away from it. 00:09:42.225 --> 00:09:45.697 Same cube, same centre, different angle. 00:09:46.494 --> 00:09:49.083 And the face it leaves is a hexagon. 00:09:49.280 --> 00:09:54.784 A regular one, with six equal sides, cut out of a body built entirely from squares. 00:09:54.981 --> 00:09:58.105 This is the step nobody believes until they watch it. 00:09:59.017 --> 00:10:01.851 So turn it again, and follow the rim. 00:10:01.955 --> 00:10:04.693 It crosses six of the cube's twelve edges, 00:10:04.776 --> 00:10:07.772 and it crosses every one of them at its midpoint. 00:10:07.969 --> 00:10:10.814 Six midpoints, six equal sides. 00:10:12.327 --> 00:10:15.311 Now lay the two sections flat and measure them. 00:10:15.508 --> 00:10:18.408 Draw the biggest circle that fits inside each one, 00:10:18.491 --> 00:10:20.802 and the smallest that wraps around it. 00:10:21.115 --> 00:10:25.028 For the square, the inner circle has radius one and the outer reaches 00:10:25.028 --> 00:10:29.881 the corners at root two, so the outer is forty one percent bigger than the inner. 00:10:30.678 --> 00:10:33.070 The hexagon is measurably rounder. 00:10:33.174 --> 00:10:36.831 Its inner circle is the larger of the two, while its outer circle 00:10:36.831 --> 00:10:42.149 is the same root two, because its corners are still edge midpoints of the same cube. 00:10:42.346 --> 00:10:47.246 The ratio drops to two over root three, about one point one five. 00:10:47.442 --> 00:10:49.414 Same cube, better direction, 00:10:49.497 --> 00:10:52.819 and the section has forgotten most of the cube's corners. 00:10:53.615 --> 00:10:58.654 In dimension n the same cube has central sections round to within any tolerance you 00:10:58.654 --> 00:11:03.949 name, and, more surprisingly, you do not have to hunt for the direction. 00:11:04.146 --> 00:11:08.579 The norm of the cube, like any norm, is a Lipschitz function on the sphere, 00:11:08.662 --> 00:11:11.078 so it concentrates at its median. 00:11:11.274 --> 00:11:15.383 On a random subspace of the right dimension it is nearly constant, 00:11:15.466 --> 00:11:18.090 and nearly constant is nearly round. 00:11:19.487 --> 00:11:21.343 That is Dvoretzky's theorem, 00:11:21.426 --> 00:11:25.653 in the sharp form Milman proved with exactly this concentration. 00:11:25.756 --> 00:11:29.539 For every tolerance epsilon there is a constant c of epsilon, 00:11:29.622 --> 00:11:34.056 and every n-dimensional normed space, no matter how jagged its unit ball, 00:11:34.139 --> 00:11:36.925 contains a subspace of dimension at least c 00:11:36.925 --> 00:11:42.731 of epsilon times log n on which the norm is within one plus epsilon of Euclidean. 00:11:43.527 --> 00:11:46.337 And the proof is this lecture run in reverse. 00:11:46.534 --> 00:11:48.577 Caps grow slowest, so sets 00:11:48.577 --> 00:11:53.429 of half measure grow to everything, so Lipschitz functions sit at their medians, 00:11:53.512 --> 00:11:58.481 so norms are constant on random subspaces, so round sections exist. 00:11:58.678 --> 00:12:02.972 One inequality about the oldest shape on the sphere, pushed four steps, 00:12:03.055 --> 00:12:05.644 reaches every norm in every dimension. 00:12:06.859 --> 00:12:09.725 Log n is small, and that is honest: 00:12:09.808 --> 00:12:14.337 the cube itself shows you cannot do better than logarithmic in general. 00:12:14.440 --> 00:12:17.646 But it is not zero, and that is the miracle. 00:12:18.098 --> 00:12:21.605 In high dimension, roundness is not the exception. 00:12:21.801 --> 00:12:25.494 It is what is left when there is nowhere else for the measure to go.