[HN Gopher] Mathematicians discover new way for spheres to 'kiss'
___________________________________________________________________
Mathematicians discover new way for spheres to 'kiss'
Author : isaacfrond
Score : 136 points
Date : 2025-01-16 09:57 UTC (13 hours ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| danwills wrote:
| 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 would be!
| terminalbraid wrote:
| > Is it all on computers now?
|
| Most modern math is certainly not "all on computers" and in
| general not even "mostly on computers". There are definitely
| proofs for things like testing large spaces exhaustively which
| are sped up by computers (see the
| https://en.wikipedia.org/wiki/Four_color_theorem) and
| definitely for things like visualization (probably one of the
| oldest uses of computers for math), but usually the real work
| goes into how math has always been done: identifying patterns
| and abusing symmetries.
|
| For this one explicitly, if you read through the paper you'll
| find the statement that the main theorem presented here "does
| not depend on any computer calculations. However, we have made
| available files with explicit coordinates for our kissing
| configurations"
| viccis wrote:
| It really depends though. Even in something like knot theory,
| that one might consider to be a very "pure" area, there's
| still a lot of computation involved that can be automated by
| computers.
| davethedevguy wrote:
| 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.
| bux93 wrote:
| I have a hard time visualizing even 3 dimension, but 4
| dimensions and up, I just think of it as a spreadsheet where
| each thing has 4 or more columns of data rather than 3.
| Whether a 4th column is time, spin, color, smell or yet
| another coordinate.
| nejsjsjsbsb wrote:
| It sort of like the visualizable 3D "kissing spheres" is
| the story that makes it interesting, captivating and
| accessible and therefore competitive/social which makes it
| interesting even more, but basically at higher dims it's a
| bunch of equations as it is impossible to visualise on
| human wetware.
|
| You could do kissing starfish but no one cares as there is
| no lore. A bit like 125m world record doesn't matter. 100m
| is the thing.
|
| This is not a knock ... it is interesting how social /
| tradition based maths is.
|
| Another example is Fermat's Last Theorem. It had legendary
| status.
| ndsipa_pomu wrote:
| However, the use of spheres means that it is applicable
| to error correcting codes, whereas "kissing starfish"
| wouldn't be useful.
| aleph_minus_one wrote:
| > 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?
|
| For such discrete geometry problems, high-dimensional spaces
| often behave "weirdly" - your geometric intuition from R^3
| will often barely help you.
|
| You thus typically rather rely on ideas such as symmetry, or
| calculations whether "there is still space inbetween that you
| can fill", or sometimes stochastic/averaging arguments to
| show the existence of some configuration.
| jstanley wrote:
| > 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 sphere, you get a
| circle. If you slice a line through a circle, you get 2
| points. If you slice a 3d space through a hypersphere in 4d
| space, do you get a normal sphere? Probably.
| close04 wrote:
| > 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 in much
| higher dimensions, like 24 (!). They all "visualized" the
| equations but in ways that gave them much more insight than
| you or I might imagine just by looking at the text.
| neom wrote:
| I have dyscalculia so I'm always studying how people who
| have "math minds" work, especially because I have an
| strong spacial visual thinking style, i thought i should
| be good at thinking about physical math. When I found out
| they're not visualizing the stuff but instead "visualized
| the equations together and imaging them into new ones" -
| I gave up my journey into math.
| semi-extrinsic wrote:
| My two cents on this: I've done a lot of math, up to
| graduate courses in weird stuff like operator algebra.
| I've also read quite a bit of maths pedagogy.
|
| I've come to understand that the key thing that
| determines success in math is _ability to compress
| concepts_.
|
| When young children learn arithmetic, some are able to
| _compress_ addition such that it takes almost zero
| effort, and then they can play around with the concept in
| their minds. For them, taking the next step to
| multiplication is almost trivial.
|
| When a college math student learns the triangle
| inequality, >99.99% understand it on a superficial level.
| But <0.01% _compress_ it and play around with it in their
| minds, and can subsequently wield it like an elegant tool
| in surprising contexts. These are the people with "math
| minds".
| neom wrote:
| wow.
|
| I have been posting on hackernews "I have dyscalculia"
| for years in hopes for a comment like this, basically
| praying someone like you would reply with the right
| "thinking framework" for me - THANK YOU! This is the
| first time I've heard this, thought about this, and I
| sort of understand what you mean, if you're able to
| expand on it in any way, that concept, maybe I can think
| how I do it in other areas I can map it? I also have
| dyslexia, and have not found a good strategy for phonics
| yet, and I'm now 40, so I'm not sure I ever will hehe :))
|
| I even struggle with times tables because the lifting is
| really hard for me for some reason, it always amazes me
| people can do 8x12 in their heads.
| semi-extrinsic wrote:
| You're welcome :)
|
| The foundations for these concepts were laid by Piaget
| and Brissiaud, but most of their work is in french. In
| English, "Young children reinvent arithmetic" by Kamii is
| an excellent and practically oriented book based on
| Piaget's theories, that you may find useful. Although it
| is 250 pages.
|
| This approach has become mainstream in maths teaching
| today, but unfortunately often misunderstood by teachers.
| The point of using different strategies to arrive at the
| same answer in arithmetics is NOT that children should
| memorize different strategies, but that they should be
| given as many tools as possible to increase the chance
| that they are able to play around with and compress the
| concept being learned.
|
| The clearest expression of the concept of compression is
| maybe in this paper, I don't know if it helps or if it's
| too academic.
|
| https://files.eric.ed.gov/fulltext/EJ780177.pdf
| neom wrote:
| I should be able to chat with an llm about this paper,
| but my gut says you've given me the glimmer of where I
| need to go. This is something I've been deeply deeply
| frustrated about for 30 years now, I had really given up
| hope of ever being able to process mathematics (whatever
| they are) properly, it's a real task to figure out how to
| get someone to see how your brain work and then have them
| understand how to provide you with some framework to
| grasp what they know.
|
| Once again I wanted to thank you for slowing down and
| taking the time to leave this thoughtful comment, if
| everyone took 5 minutes to try to understand what the
| other person is saying to see if they can help, the world
| would be a considerably better place. Thank you.
| eszed wrote:
| Calculating 8x12 in my head relies on a trick / technique
| - they call it "chunking", I believe, in the Common Core
| maths curriculum that US parents get so angry about -
| that (I'm also in my 40s) was never demonstrated in
| schools when we were kids. (They tried to make me
| memorize the 12x table, which I couldn't, so I calculated
| it my way instead; took a little longer, but not so much
| that anyone caught on that I wasn't doing what the
| teacher said.) I'd like to think I was smart enough to
| work it out for myself, but I suspect my dad showed it to
| me.
|
| I'll show it to you, but first: are you able to add 80 +
| 16 in your head? (There's another trick to learn for
| that.)
| neom wrote:
| 96, easy. Lets go, real time math tutoring in the
| hackernews comments, 2025 baby! :D
| Cyber_Mobius wrote:
| Just a tangent, but there's a nice trick for 8 x 12.
|
| In algebra, you learn that (a - b)(a + b) = a^2 - b^2.
| It's not too hard to spot this when it's all variables
| with a little practice but it's easy to overlook that you
| can apply this to arithmetic too anywhere that you can
| rewrite a problem as (a-b)(a+b). This happens when the
| difference between the two numbers you're trying to
| multiply is even.
|
| For a, take the halfway point between the two numbers,
| and for b, take half the difference between the numbers.
| So a = (8 + 12) / 2 = 10. b = (12 - 8) / 2 = 2.
|
| Here, 8 = 10 - 2 and 12 = 10 + 2. So you can do something
| like (10 - 2)(10 + 2) = 10^2 - 2^2 = 100 - 4 = 96.
|
| It's kind of a tossup if it's more useful on these
| smaller problems but it can be pretty fun to apply it to
| something like 17 x 23 which looks daunting on its own
| but 17 x 23 = (20-3)(20+3) = 20^2 - 3^2 = 400 - 9 = 391
| neodimium wrote:
| Shortly after graduating as an engineer, I remember
| receiving much help regarding mathematical thinking from
| a book by Keith Devlin titled "The Language of
| Mathematics: Making the Invisible Visible".
|
| What stuck with me (written from memory, so might differ
| somewhat from the text):
|
| In the introductory chapter, he describes mathematics as
| the science of patterns. E.g. number theory deals with
| patterns of numbers, calculus with patterns of change,
| statistics with patterns of uncertainty, and geometry
| with patterns of shapes and spaces..
|
| Mathematical thinking involves abstraction: you identify
| the salient structures & quantities and describe their
| relationships, discarding irrelevant details. This is
| kind of like how, when playing chess, you can play with
| physical pieces or with a board on a computer screen -
| the pieces themselves don't matter, it's what each piece
| represents and the rules of the game that matters.
|
| Now, these relationships and quantities need to be
| represented somehow: this could be a diagram or formulas
| using some notation. There are usually different options
| here. Different notations can highlight or obscure
| structures and relationships by emphasizing certain
| properties and de-emphasizing others. With a good
| notation, certain proofs that would otherwise be
| cumbersome might be very short. (Note also that notations
| typically have rules associated with them that govern how
| expressions can be manipulated - these rules typically
| correspond in some way to the things being represented
| and their properties.)
|
| Now, roughly speaking, mathematicians may study various
| abstract structures and relationships without caring
| about how these correspond to the real world. They
| develop frameworks, notations and tools useful in dealing
| with these kinds of patterns. Physicists care about which
| patterns describe the world we live in, using the above
| mathematical tools to express theories that can make
| predictions that correspond to things we observe in the
| real world. As an engineer, I take a real-world problem
| and identify the salient features and physical theories
| that apply. I then convert the problem into an abstract
| representation, apply the mathematical tools (informed by
| the relevant physical theories), and develop a solution.
| I then translate the mathematical solution back into
| real-world terms.
|
| One example of the above in action is how Riemann
| geometry, the geometry of curved surfaces, was created by
| developing a geometry where parallel lines can cross.
| Later, this geometry became integral in expressing the
| ideas of relativity.
|
| This maps back to the idea of "making the invisible
| visible": Using the language of mathematics we can
| describe the invisible forces of aerodynamics that cause
| a 400 ton aircraft suspended in the air. For the latter,
| we can "run the numbers" on computers to visualize
| airflow and the subsequent forces acting on the airframe.
| At various stages of design, the level of abstraction
| might be very course (napkin calculations, discarding a
| lot of detail) or very fine (taking into account many
| different effects).
|
| Lastly, regarding your post of 'When I found out they're
| not visualizing the stuff but instead "visualized the
| equations together and imaging them into new ones"':
|
| Sometimes when studying relationships between physical
| things you notice that there are recurring patterns in
| the relationships themselves. For example, the same
| equations crop up in certain mechanical systems than does
| in certain electrical ones. (In the past there were
| mechanical computers that have now been replaced with the
| familiar electronic ones). With these higher order
| patterns, you don't necessarily care about physical
| things in the real world anymore. You apply the
| abstraction recursively: what are the salient parts of
| the relationships and how do they relate. This is roughly
| how you can generalize things from 2 dimensions to 3 and
| eventually n. Like learning a language, you begin to
| "see" the patterns as you immerse yourself in them.
| Majromax wrote:
| 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."
| david-gpu wrote:
| My sister is a mathematican and she used to say that if
| you want to understand a 24-dimensional space, you start
| from a generalized n-dimensional space and then set n=24.
|
| This wasn't atypical of her. She would also say that if
| your house is on fire then you call the firefighters, but
| if it is _not_ on fire then you set it on fire, thereby
| reducing the problem to something that you have already
| solved.
| mindcrime wrote:
| > 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."
|
| He did. You can see / hear that line in this video from
| his old Coursera course.
|
| https://youtu.be/TNhgCkYDc8M?list=PLLssT5z_DsK_gyrQ_biidw
| vPY...
|
| Exactly how seriously he intended this to be taken is a
| matter of debate, but he definitely said it.
| zmgsabst wrote:
| > 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.
| JJMcJ wrote:
| Note that the solid set, all points within a certain
| distance of the center, is called a ball:
| https://en.wikipedia.org/wiki/Ball_(mathematics)
|
| If the boundary is included, it's a closed ball, otherwise
| it's an open ball.
|
| So the sphere is the "skin", the ball is the whole thing.
|
| A bit different than common usage.
| tomrod wrote:
| 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.
| evandrofisico wrote:
| In my PhD I did study systems in higher dimensions (including
| fractal dimensions) and it is not a metaphor and no, I did
| not visualize them, it was more like defining a mathematical
| representation of the system geometry and working on top of
| it.
| bell-cot wrote:
| I suspect that you have plenty of company...but from a
| journalism PoV, those kind of things are where it gets tricky.
| Explaining in detail, and at length, is a lot more work than
| this short article. Then there are the decisions - "just how
| much detail?", "just how long?", (worse) "how much mathematical
| background should we assume, in our readers?", and (worst) "how
| willing will our readers be, to slog through serious
| mathematics?".
|
| (I'm assuming you've already searched for math bloggers, and
| similar "labor of love" coverage of the topic.)
| scythe wrote:
| In many cases you are "translating" the higher-dimensional
| geometry into something that is not geometric or which is much
| lower dimensional. You don't generally visualize 24 dimensions.
| You can get a decent intuition for 4 with practice but at some
| point this breaks down.
|
| For example, the 24-dimensional packing corresponds to the
| Leech lattice which itself corresponds to the Golay code:
|
| https://en.wikipedia.org/wiki/Leech_lattice
|
| https://en.wikipedia.org/wiki/Binary_Golay_code
| iNic wrote:
| 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).
| david-gpu wrote:
| _> For example high dimensional spheres are "pointy" and
| most of their volume are near their surface_
|
| I had a visceral reaction to this. In what sense can a sphere
| be considered pointy? Almost by definition, it is the volume
| that minimizes surface area, in any number of dimensions.
|
| I can see how in higher dimensions e.g. a hypersphere has
| much lower volume than a hypercube. But that's not because
| the hypersphere became pointy, it's because the corners of
| the hypercube are increasingly more voluminous relative to
| the volume of the hypersphere, right?
| btown wrote:
| https://news.ycombinator.com/item?id=3995615 (both article
| and comments) describe various ways of looking at this -
| and there are many implications for machine learning e.g.
| https://news.ycombinator.com/item?id=3995964 !
| iNic wrote:
| There is a standard thought experiment where you start with
| a hypercube of side-length 2, centered at the origin. You
| then place a radius 1 sphere on each vertex of this
| hypercube. The question then becomes: what is the largest
| sphere you can place at the origin so that it is
| "contained" by the other spheres. As it turns out in like
| dimension 6 or so the radius of the center sphere exceeds
| 1. It will actually poke out arbitrarily far (while still
| being restricted by the corner spheres).
| Sharlin wrote:
| Yes, but that can be better understood as the _hypercube_
| becoming more pointy, not the sphere. And it 's true; the
| cube's vertices get arbitrarily far from the origin,
| while the centers of its faces stay at +-1.
|
| There are other ways in which a hypersphere can be
| considered "pointy", though; for example, consider a
| point lying on the surface being moved some epsilon
| distance to a random direction. As the dimension
| increases, the probability that the point ends up inside
| the sphere approaches zero - the sphere spans a smaller
| and smaller fraction of the "sky".
| senderista wrote:
| Specifically, of course, d = sqrt(N), where N is
| dimension and d is distance of a vertex of the unit
| hypercube from the origin.
| carltg_ wrote:
| I hear this point parroted all of the time, but I think
| it is a misunderstanding and a poor visualization.
| Consider the same situation, but instead of focusing on
| the radius of the center sphere, focus on the distance
| between the spheres on the corners to the origin. For
| 1-dimension, these 'spheres' are unit intervals and so
| the distance is 1 (Central radius is 0). For
| 2-dimensions, these are circles at a distance of root(3)
| (Central radius is root(2)-1). 3-D: root(3) (Central
| radius is root(3)-1). Etc. So, it isn't the central
| circle getting more 'pointy' allowing the central radius
| to increase, but rather that the corner circles are
| getting further from the origin, allowing larger
| N-spheres (increasing proportional to the root of N).
| Thus, pointy is not the right way to conceptualize these
| spheres. For the more visual folk, I would recommend
| drawing this out and you can see this in action. More
| clearly, if a sphere became 'spikey' then the distance on
| the surface of the spike should be further than a
| neighboring point, which is NOT the case. Not trying to
| attack you, I just see this same point over and over and
| think that this warrants more thought
| jochi427 wrote:
| I remember learning about the probability of returning to the
| origin in a 2D random walk versus a 3D random walk when I
| took stochastic processes. After we proved with probability 1
| you return to the origin in a 2D walk (and with probability 0
| you return in 3D) my professor said "that's why you hand a
| drunk man the keys to a car and not an airplane when he
| leaves the bar". After checking wikipedia it looks like he
| riffed off this quote from Shizuo Kakutani: "A drunk man will
| find his way home, but a drunk bird may get lost forever".
| CamperBob2 wrote:
| That's interesting, about the probability being zero in 3D.
| Is this on an integer lattice? The source that cannot be
| cited on HN without loss of karma says that the probability
| of returning to the origin in Z^3 is approximately 0.34.
|
| I don't see how it could possibly be zero, even for reals,
| unless you're relying on the idea that the probability of
| any given real emerging from a uniform RNG is zero. That
| would seem to apply in 2D as well.
| jochi427 wrote:
| I'm sure I am just misremembering -- it was definitely on
| Z^3 so I guess its actually 34%. Thanks for letting me
| know
| dxuh wrote:
| > "There may be structures without any symmetry at all," said
| Gabriele Nebe (opens a new tab) of RWTH Aachen University in
| Germany. "And no good way to find them."
|
| She taught Lineare Algebra II when I took it! It was one of the
| toughest lectures I took during university. I remember looking to
| the person next to me and one of us asked "do you understand
| anything?" and the other said "no! I haven't understood anything
| for like 20 minutes" and we burst out laughing and couldn't get
| it together until we were asked to quiet down. Wadim if you hang
| out here, send me a mail or something!
| nejsjsjsbsb wrote:
| The interesting ta for me:
|
| > Had she been one of his graduate students, he would have tried
| harder to convince her to work on something else. "If they work
| on something hopeless, it'll be bad for their career," he said.
| anarchonurzox wrote:
| A small anecdote: my dad is a mathematician. For a significant
| portion of his postdoc/early career (in the 80's/90's) he
| worked on proving a particular conjecture. Eventually he
| abandoned it and went to be much more successful in other
| areas.
|
| A few years ago someone found a counterexample. He was quite
| depressed for a few weeks at the thought of how much of his
| strongest research years had been devoted to something
| impossible.
|
| Choosing a "good first problem" in math is quite difficult. It
| needs to be "novel," somewhat accessible, and possible to solve
| (which is an unknown when you're starting out)!
| senderista wrote:
| At least he didn't "prove" a theorem that turned out to be
| false!
| nejsjsjsbsb wrote:
| Thanks that is a good anecdote. Did he get over it and how?
|
| To me such a career is useful for (a) the greater good: you
| can't make discoveries without dead ends and (b) the maths
| created along the way! Or if not shares then the skills
| developed.
| matsemann wrote:
| > _In two dimensions, the answer is clearly six: Put a penny on a
| table, and you'll find that when you arrange another six pennies
| around it, they fit snugly into a daisylike pattern._
|
| Is there an intuitive reason for why 6 fits so perfectly? Like,
| it could be a small gap somewhere, like in 3d when it's 12, but
| it isn't. Something to do with tessellation and hexagons,
| perhaps?
|
| > _They look for ways to arrange spheres as symmetrically as
| possible. But there's still a possibility that the best
| arrangements might look a lot weirder._
|
| Like square packing for 11 looks just crazy (not same problem,
| but similar): https://en.wikipedia.org/wiki/Square_packing
| jansan wrote:
| It would be fun to make that square packing for 11 from wood
| and give it to puzzle enthusiasts with this task: Rearrange the
| squares so you can add an additional 12th square. And then
| watch them struggle putting even those 11 squares back in.
| JKCalhoun wrote:
| Three pennies form an equilateral triangle with (of course) 60
| degree angles.
|
| Six of those equilateral triangles will perfectly add to 360
| degrees. Intuitive enough? (I'm being a little hand-wavey by
| skipping over the part where each penny triangle shares two
| pennies with a neighbor -- why the answer is not 18 for
| example.)
|
| For my mind though, the intuitiveness ends in dimension 2
| though. ;-)
| zython wrote:
| two best spheres in a room; they might kiss :^)
| TaurenHunter wrote:
| https://knowyourmeme.com/memes/now-kiss
| rpigab wrote:
| > 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/
| quuxplusone wrote:
| > 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."
| rpigab wrote:
| This helped a lot, thanks! I now see a similiarity where I
| was missing the bridges between geometry and lossy
| information channels. It's really interesting, though it's a
| really complex problem.
| sohkamyung wrote:
| 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...
| crazygringo wrote:
| 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.
| quuxplusone wrote:
| 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."
| awanderingmind wrote:
| Here is an example of that sort of thing, using gradient
| descent as a starting point:
| https://arxiv.org/abs/math/0611451. It is technically about
| spherical codes rather than the kissing problem specifically,
| but they are closely related:
| https://en.wikipedia.org/wiki/Spherical_code
| gosub100 wrote:
| Sort of a tangent, but here's a 20m video explaining how to
| invert a sphere without tearing it:
|
| https://youtu.be/wO61D9x6lNY?si=ecBgnOemKAbYZCrP
| NooneAtAll3 wrote:
| if we believe the article, Li did all the work
|
| and yet Cohn is first on the author list :(
| ratmice wrote:
| Alphabetical order is normal.
|
| http://www.ams.org/learning-careers/leaders/CultureStatement...
| dekhn wrote:
| I took a class taught by David Huffman (of Huffman coding) called
| Cybernetics (IIUC it was the UCSC equivalent of a class Wiener
| taught at MIT.
|
| The very first day, he started out by talking about kissing
| spheres and concluded the lecture with "and that's why kissing
| spheres are easy in 7 dimensions" (or something like that).
|
| Every lecture of his was like being placed in front of a window
| looking upon a wonderful new world, incomprehensible at first,
| but slowly becoming more and more clear as he explained.
| Sometimes I wish I could play in the garden of math.
| 2-3-7-43-1807 wrote:
| what kind of kiss is that? certainly not a french kiss.
| Jun8 wrote:
| If you are wondering what sort of idiot would dispute a math
| problem with Newton, it was not a dispute at all; it's not even
| clear that they had a discussion at all:
| https://hsm.stackexchange.com/questions/5148/how-did-newton-...
___________________________________________________________________
(page generated 2025-01-16 23:00 UTC)