Spikey Spheres 


My latest posts can be found here: Previous blog posts:
Additionally, some earlier writings: 
The problem is that the usual visualisation of hillclimbing, or hilldescending, is that you're on a gently undulating vista, and that some directions are up, some are down, and it's easy to decide which is which. You write the code, set off, and somehow the system never finds a good solution. Part of the problem is that there is simply a lot of space to explore. If you discretise space and have 1000 places to be in each dimension, 2 dimensions gives you a million places to be. That's not so bad. 1800 dimensions gives you ${10}^{5400}$ places to be. That's not good. You definitely need to move in moderately large strides, and then hone your solution by using binary chop or similar techniques. But it's worse than that. The problem is that the error function may be "smooth," but your intuition of what this means is wrong. Let's give you a different intuition. This isn't complete, and it certainly isn't perfect, but it can help to understand the problem.
There's a small gap in the middle, and in it we can put a circle touching all four of the surrounding circles. How big is it? By Pythagoras, the distance from the centre of the bounding square (and hence of the central circle) to the centre of one of the other circles is $\sqrt{2}$ (Figure 2 at right) The big circles have radius 1, so the smaller circle has radius $\sqrt{2}1$ which is about 0.4142, a bit more than 0.4. If we go to three dimensions we get a 4x4x4 cube with 8 spheres in it. A sphere of size 0.4 fits between the spheres on a face, and pushing it into the centre means it can rattle around. Now we can grow it until it touches all eight spheres.. How big? The distance from the centre of the cube to the centre of a sphere is $\sqrt{3}.$ Subtracting off the radius of one of the corner spheres we get a radius for the internal sphere of $\sqrt{3}1,$ which is about 0.732. More generally, in "n" dimensions the distance from the centre of the hypercube to the centre of a hypersphere is $\sqrt{n},$ and so the radius of the central hypersphere is $\sqrt{n}1.$ (I'm already tired of writing "hyper"  I'll leave it out from now on)
That's odd, but it gets even more interesting. In 9 dimensions the central sphere is of size $\sqrt{9}1,$ which is 2. Remember, that's the radius of the central sphere, so the diameter is 4. That's the size of the containing box. The central sphere actually touches the sides of the containing box. But wait  it gets better. In 10 dimensions the central sphere is of size $\sqrt{10}1,$ which is about 2.162. The diameter is about 4.325. It pokes out the sides (and top and bottom, etc) of the "containing" box.
And in some ways, for some purposes, that's a good intuition. If that were the only oddity then we might get away with ignoring it, but it isn't. Picture cutting off a spherical cap of height $h.$ What is its volume in 2 dimensions? In three dimensions? In four dimensions? It's worth noting that the volume of a sphere gets smaller and smaller as the dimension goes up, but the volume of the cap as a ratio of the whole sphere gets smaller and smaller even faster. Somehow, a spherical cap in high dimensions has almost no volume, even when of moderate height/depth. What's that got to do with being spikey? Think of something which is as symmetrical as you can make it, but which when you chop it off, has almost no volume. The best thing to think of in our regular 3D world is a spike. It has very little volume, even if you take quite a lot of it. So one visualisation of a sphere in very high dimensions is not something smooth and round, but something that is somehow simultaneously very symmetrical, and yet also very spikey. A bit like a hedgehog. Well, actually, not like a hedgehog. One problem with this visualisation is that in truth, every point on the surface looks the same. If it really were like a spike then as you travel away from the extremity the nature of the surface would change. With a true highdimensional sphere, every point on the surface is "an extremity". Every point on the surface looks like every other point. So call your imagination into action. Imagine yourself at the tip of a spike on a very spikey object, like a hedgehog. Now start walking. You cover some distance, but you're still at the tip of a spike. Every direction looks the same, no matter how you move. So the surface of a highdimensional sphere is simultaneously smooth, spikey and symmetrical.
And let me just finish by saying that this isn't the whole story. The purpose of this item hasn't been to let you work, troublefree, with highdimensional spaces. The purpose has been to show that things aren't what you might expect, and that your regular, understandable, 3Dbased intuition can be completely inappropriate. 1800dimensional space is big. Really big. And sortof spikey.
My thanks to Rachel, Neil, Colin Percival, and Cedric StJean for their comments on early drafts.
CommentsI've decided no longer to include comments directly via the Disqus (or any other) system. Instead, I'd be more than delighted to get emails from people who wish to make comments or engage in discussion. Comments will then be integrated into the page as and when they are appropriate. If the number of emails/comments gets too large to handle then I might return to a semiautomated system. That's looking increasingly unlikely.

Quotation from Tim BernersLee 