Live data from Hacker News

Mathematicians discover new way for spheres to 'kiss'

quantamagazine.org

21–30 of 74 posts

Re: Mathematicians discover new way for spheres to 'kiss'

#21
> Mathematicians often visualize this problem in terms of spheres. You can think of each code word as a high-dimensional point at the center of a sphere. If an error-filled message (when represented as a high-dimensional point) lives inside a given sphere, you know that the code word at the sphere’s center was the intended message. You don’t want these spheres to overlap — otherwise, a received message might be interpreted in more than one way. But the spheres shouldn’t be too far apart, either. Packing the spheres tightly means you can communicate more efficiently.

I went to math prep school for 2 years, attended 12 hours of math class in agebra and analysis per week, which I think proves I've done more math than most people in the general population, and this makes no sense to me. It either lacks introduction required to understand the analogy, or I've become really dumb. I want to understand this based on what the article says, but I can't. I can't represent error-filled messages as high-dimensional points. It's easier for me to imagine what the intersection between 4D spheres would look like in geometry.

I found this for anyone interested in understanding 4D spheres without knowing too much math: https://baileysnyder.com/interactive-4d/4d-spheres/

Re: Mathematicians discover new way for spheres to 'kiss'

#22
post #14
post #7

Earlier quoted context omitted.

> just a visual metaphor It's not really a metaphor . An n-sphere is the set of all points that are the same distance away from the same centre, in (n+1)-dimensional space. That generalises perfectly well to any number of dimensions. In 1 dimension you get 2 points (0-sphere), in 2 dimensions you get a circle (1-sphere), in 3 dimensions you get a sphere (2-sphere), etc. EDIT: Also, if you slice a plane through a sphe…

> etc. That's handwaving the answer just as you were getting to the crux of the matter. "Are mathematicians really visualising spheres with physical space between them" in higher dimensions than 3 (or maybe 4)? From the experience of some of the bigger minds in mathematics I met during my PhD, they don't actually visualize a practical representation of the sphere in this case since that would be untenable especially…

Reportedly, Geoffrey Hinton said: “To deal with a 14-dimensional space, visualize a 3-D space and say 'fourteen' to yourself very loudly. Everyone does it.”

Re: Mathematicians discover new way for spheres to 'kiss'

#23
post #2

I'd really love to know what the mathematicians are actually doing when they work this stuff out? Is it all on computers now? Can they somehow visualize 24-dimensional-sphere-packings in their minds? Are they maybe rigorously checking results of a 'test function' that tells them they found a correct/optimal packing? I would love to know more about what the day-to-day work involved in this type of research actually wo…

The kind of intuition you gain for higher dimension tends not to be visual. It is more that you learn a bunch of tools and these in turn build intuition. For example high dimensional spheres are "pointy" and most of their volume are near their surface. These ideas can be defined rigorously and are important and useful. For medium dimension there are usually specific facts that you exploit. In my own work stuff like "How often do you expect random walks to intersect" is very important (and dependent on dimension).

Re: Mathematicians discover new way for spheres to 'kiss'

#24
post #2

I'd really love to know what the mathematicians are actually doing when they work this stuff out? Is it all on computers now? Can they somehow visualize 24-dimensional-sphere-packings in their minds? Are they maybe rigorously checking results of a 'test function' that tells them they found a correct/optimal packing? I would love to know more about what the day-to-day work involved in this type of research actually wo…

Likewise! In higher dimensions, are the spheres just a visual metaphor based on the 3-dimensional problem, or are mathematicians really visualising spheres with physical space between them? Is that even a valid question, or does it just betray my inability to perceive higher dimensions? This is fascinating and I'm in awe of the people that do this work.

A circle from a flat 2d manifold can be from a 3d sphere, cylinder, or other cross section.

Our mental models don't extend well beyond 3, possibly 4, dimensions, hence _all_ of our intuition starts to be doubtful after 3 dimensions.

Re: Mathematicians discover new way for spheres to 'kiss'

#25
It's strange the article doesn't even mention just trying to simulate the problem computationally.

Surely it's not too difficult to repeatedly place spheres around a central sphere in 17 dimensions, maximizing how many kiss for each new sphere added, until you get a number for how many fit? And add some randomness to the choices to get a range of answers Monte Carlo-style, to then get some idea of the lower bound? [Edit: I meant upper bound, whoops.]

Obviously ideally you want to discover a mathematically regular approach if you can. But surely computation must also play a role here in narrowing down reasonable bounds for the problem?

And computation will of course be essential if the answer turns out to be chaotic for certain numbers of dimensions, if the optimal solution is just a jumble without any kind of symmetry at all.

Re: Mathematicians discover new way for spheres to 'kiss'

#26
post #7

Earlier quoted context omitted.

Likewise! In higher dimensions, are the spheres just a visual metaphor based on the 3-dimensional problem, or are mathematicians really visualising spheres with physical space between them? Is that even a valid question, or does it just betray my inability to perceive higher dimensions? This is fascinating and I'm in awe of the people that do this work.

> just a visual metaphor It's not really a metaphor . An n-sphere is the set of all points that are the same distance away from the same centre, in (n+1)-dimensional space. That generalises perfectly well to any number of dimensions. In 1 dimension you get 2 points (0-sphere), in 2 dimensions you get a circle (1-sphere), in 3 dimensions you get a sphere (2-sphere), etc. EDIT: Also, if you slice a plane through a sphe…

> If you slice a 3d space through a hypersphere in 4d space, do you get a normal sphere? Probably.

Yep — and this will generally be the case, as the equation looks like: x1^2 + x2^2 + … + xn^2 = r^2. If you fix one dimension, you have a hyperplane perpendicular to that axis — and a sphere of one dimension lower in that hyperplane.

For four dimensions, you can sort of visualize that as x^2 + y^2 + z^2 + t^2 = r^2, where xyz are your normal 3D and t is time. From t=-r to t=r, you have it start as a point then spheres of growing size until you hit t=0, then the spheres shrink back to a point.

Re: Mathematicians discover new way for spheres to 'kiss'

#27
post #21

> Mathematicians often visualize this problem in terms of spheres. You can think of each code word as a high-dimensional point at the center of a sphere. If an error-filled message (when represented as a high-dimensional point) lives inside a given sphere, you know that the code word at the sphere’s center was the intended message. You don’t want these spheres to overlap — otherwise, a received message might be inter…

> I want to understand this based on what the article says, but I can't. I can't represent error-filled messages as high-dimensional points.

Well, start with an analogy. Let's say you and I want to communicate a message, which comes from a set of let's say 4 possible messages: "YES", "NO", "GOOD", and "BYE". Let's further suppose that the medium for this message (the "data channel") is going to be a single point selected from a 2D square. We'll agree beforehand on four points in the square that will represent our four possible messages. Then, you're going to position a dot at one of those points, and I'm going to observe that dot and infer your message from its position.

If the "data channel" is "error-free" (a.k.a. "lossless"), then it really doesn't matter which points we agree on: you could say that the exact center of the square is "YES", the point one millimeter to the left is "NO", the point two millimeters to the left is "GOOD", and so on. But if the data channel is "lossy," then the dot might get shaken around before I observe it. Or equivalently, I might observe its position slightly incorrectly. So we should choose our "code" so as to minimize the effect of this "error."

The best way to do that, on a square, is to place our four "code points" all the way at the four corners of the square, as far away from each other as possible. By "as far away from each other as possible," I mean in the sense of https://en.wikipedia.org/wiki/Pole_of_inaccessibility — I mean we want to maximize the minimum distance between any two points. A mathematician would notice that this is the same thing as maximizing the radius R such that we can draw a circle of radius R around each of our code points without any of the circles intersecting. (R in this case is half of the square's side length.)

If we add a fifth code point, this same reasoning would lead us to place that fifth point right smack in the center of the square. And the sixth point... well, I feel like that gets tricky.

BUT! In actual communications, we don't send messages encoded as real points in 2D squares. We send messages as discrete bit-strings, i.e., strings of zeros-and-ones of length N, which you can see as discrete points at the corners of an N-dimensional hypercube. Then, if we want to send K different messages robust against errors(+), we should pick as our code points some K corners of the hypercube so as to maximize the minimum Manhattan distance along the hypercube's edges between any two code points. This is the basic idea behind error-correcting codes.

A digital error-correcting code is "K code points in a bounded region of N-dimensional hyperspace (namely the discrete set of corners of a unit hypercube), selected so as to maximize the minimum distance between any two of them." The kissing-hyperspheres problem is "K sphere-centers in a bounded region of N-dimensional hyperspace (namely the continuous set of points at unit distance from the origin), selected so as to maximize the minimum distance between any two of them (and then, if that minimum distance is still >=1, increase K and try again)."

If all you meant is "Those two problem statements don't seem 100% equivalent," I think I agree with you. But if you meant you didn't see the similarity at all... well, I hope this helped.

https://en.wikipedia.org/wiki/Pole_of_inaccessibility

https://en.wikipedia.org/wiki/Error_correction_code

(+) — edited to add: Robust against the traditional model of error, i.e., our "threat model" is that any given bit has a constant small probability of getting flipped, so that our observed point may be some random Manhattan walk away from the code point you actually sent. You could instead use a different threat model — e.g. supposing that the bits sent in the actual digital message's "low-order" bits would flip more often than the high-order bits — in which case the optimal selection of code points wouldn't be as simple as "just maximize Manhattan distance."

Re: Mathematicians discover new way for spheres to 'kiss'

#28
post #21

> Mathematicians often visualize this problem in terms of spheres. You can think of each code word as a high-dimensional point at the center of a sphere. If an error-filled message (when represented as a high-dimensional point) lives inside a given sphere, you know that the code word at the sphere’s center was the intended message. You don’t want these spheres to overlap — otherwise, a received message might be inter…

I'm not sure if this helps makes things clearer, but see this diagram for symbols in Quadrature Amplitude Modulation [1]. The valid symbols are mapped to certain points in the vector space. Now, imagine non-overlapping circles around each symbol. If a received signal falls within a circle, it would be mapped to that symbol in the centre of the circle.

This can be extended to 3-D or higher dimension spaces.

[1] https://en.wikipedia.org/wiki/Quadrature_amplitude_modulatio...

Re: Mathematicians discover new way for spheres to 'kiss'

#29

It's strange the article doesn't even mention just trying to simulate the problem computationally. Surely it's not too difficult to repeatedly place spheres around a central sphere in 17 dimensions, maximizing how many kiss for each new sphere added, until you get a number for how many fit? And add some randomness to the choices to get a range of answers Monte Carlo-style, to then get some idea of the lower bound? [E…

Maybe the author thought it was so obvious that you could get some lower bounds that way, that it didn't seem worth mentioning! :) Wikipedia has a list, where I presume the lower bounds are mostly demonstrated constructively. Upper bounds must be demonstrated non-constructively, so I presume computers don't really help there.

https://en.wikipedia.org/wiki/Kissing_number#Some_known_boun...

Even in dimension 5, the kissing number is apparently known only as "42 plus or minus 2."

Re: Mathematicians discover new way for spheres to 'kiss'

#30

It's strange the article doesn't even mention just trying to simulate the problem computationally. Surely it's not too difficult to repeatedly place spheres around a central sphere in 17 dimensions, maximizing how many kiss for each new sphere added, until you get a number for how many fit? And add some randomness to the choices to get a range of answers Monte Carlo-style, to then get some idea of the lower bound? [E…

[deleted]
Post reply on HN