3 ms·

Lenstra-Lenstra-Lovasz: http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm http://en.wikipedia.org/wiki

Lenstra-Lenstra-Lovasz: http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%9... High dimensional work is bloody hard, and this algorithm works amazingly well. I've spoken with Lenstra (one of them) and he's amazingly insightful on these things. He helped to crystalise my understanding of why high-dimensional spheres should be thought of as "spikey," rather than "round."

jules 16y ago
Why are high dimensional spheres spikey?
- RiderOfGiraffes 16y ago
  Ah. I really should write that up. Far too long to explain in a comment here, far to interesting (to me!) to forget or ignore. I'll write it up and submit it. Anyone who cares to email me can get an early version to read, and your feedback would be useful. Please. Thanks.
  - orangecat 16y ago
    Please do. My guess would be similar to Zaak's: the n-dimensional volume of an n-dimensional hypersphere approaches 0 as n approaches infinity. (http://www.mathreference.com/ca-int,hsp.html http://www.mathreference.com/ca-int,hsp.html). A hypersphere with radius 1 centered at the origin has to get out to 1 along each axis (e.g. x=1, y=z=0 for a 3 dimensional sphere), and in order for that not to contribute much volume, it has to be a narrow spike rather than a gradual curve.
  - deleted 16y ago
    [deleted]
- Zaak 16y ago
  I believe it's because in high dimensions, most of the "volume" is near the center, whereas in low dimensions, most of the volume is near the surface.
  - cperciva 16y ago
    Not at all. The expected distance between the center of an n-ball and a random point in the ball is n/(n+1) times the radius. Now, if you look at an n-sphere with respect to orthogonal axes, you find that moving along an axis you get out as far as (1, 0, ... 0) and moving "away" from the axes you only get to (1/sqrt(n), 1/sqrt(n), ... 1/sqrt(n)); but this isn't due to the sphere being spiky -- rather, it's because orthogonal axes are spiky.
- deleted 16y ago
  [deleted]
- RiderOfGiraffes 16y ago
  Now written up here: http://news.ycombinator.com/item?id=1846682 http://news.ycombinator.com/item?id=1846682
- RiderOfGiraffes 16y ago
  In response to requests, the write-up is now available here: http://news.ycombinator.com/item?id=1846682 http://news.ycombinator.com/item?id=1846682

jules 16y ago

Why are high dimensional spheres spikey?

RiderOfGiraffes 16y ago
Ah. I really should write that up. Far too long to explain in a comment here, far to interesting (to me!) to forget or ignore. I'll write it up and submit it. Anyone who cares to email me can get an early version to read, and your feedback would be useful. Please. Thanks.
- orangecat 16y ago
  Please do. My guess would be similar to Zaak's: the n-dimensional volume of an n-dimensional hypersphere approaches 0 as n approaches infinity. (http://www.mathreference.com/ca-int,hsp.html http://www.mathreference.com/ca-int,hsp.html). A hypersphere with radius 1 centered at the origin has to get out to 1 along each axis (e.g. x=1, y=z=0 for a 3 dimensional sphere), and in order for that not to contribute much volume, it has to be a narrow spike rather than a gradual curve.
- deleted 16y ago
  [deleted]
Zaak 16y ago
I believe it's because in high dimensions, most of the "volume" is near the center, whereas in low dimensions, most of the volume is near the surface.
- cperciva 16y ago
  Not at all. The expected distance between the center of an n-ball and a random point in the ball is n/(n+1) times the radius. Now, if you look at an n-sphere with respect to orthogonal axes, you find that moving along an axis you get out as far as (1, 0, ... 0) and moving "away" from the axes you only get to (1/sqrt(n), 1/sqrt(n), ... 1/sqrt(n)); but this isn't due to the sphere being spiky -- rather, it's because orthogonal axes are spiky.
deleted 16y ago
[deleted]
RiderOfGiraffes 16y ago
Now written up here: http://news.ycombinator.com/item?id=1846682 http://news.ycombinator.com/item?id=1846682
RiderOfGiraffes 16y ago
In response to requests, the write-up is now available here: http://news.ycombinator.com/item?id=1846682 http://news.ycombinator.com/item?id=1846682