13 ms·

Sphere packings are quite a deep and fascinating area of pure mathemaics. It has close relations to coding theory, lattice theory, number theory, modular forms.

Sphere packings are quite a deep and fascinating area of pure mathemaics. It has close relations to coding theory, lattice theory, number theory, modular forms. John Conway [1] (who recently passed away due to COVID) wrote a famous book about it: Sphere Packings, Lattices and Groups -- which summarizes the subject concisely. A recent (2017) break through, was the proof that the Leech Lattice [2] yields the optimal sphere packing in dimension 24 [3]. The error correcting code constructed from this lattice is the Binary Golay Error Correcting Code [4]. It is able to correct 3 bits for every 24 bits, and maximally efficient in doing so. It was used to communicate with the Voyager probes. [1] https://en.wikipedia.org/wiki/John_Horton_Conway https://en.wikipedia.org/wiki/John_Horton_Conway [2] https://en.wikipedia.org/wiki/Leech_lattice https://en.wikipedia.org/wiki/Leech_lattice [3] https://arxiv.org/pdf/1603.06518.pdf https://arxiv.org/pdf/1603.06518.pdf [4] https://en.wikipedia.org/wiki/Binary_Golay_code https://en.wikipedia.org/wiki/Binary_Golay_code

jedimastert 6y ago
I didn't realize he died from COVID complications. That just makes it all the worse.
- jon_elbrook 6y ago
  He was 82.
  - taylorlunt 6y ago
    He was also a human being and he died.
- beefman 6y ago
  How does it make it worse?
jmcomets 6y ago
Sphere packing was my 3rd year internship project (summer of 2013), so happy to see what is quite the fascinating topic mentioned on HN! I'm a bit sad I don't have a lot to show for it, other than an old undocumented GitHub repo[1]... Glad to hear there were breakthroughs in the field, thanks for the heap of links for me to delve into. :) [1]: https://github.com/dcoeurjo/ThicknessDiag https://github.com/dcoeurjo/ThicknessDiag
haneefmubarak 6y ago
Our of curiosity and as a noob to coding theory, what makes a Binary Golay code more useful than say a RS Code or something else more common? The linked wiki article said that given 12 bits, the BG code can encode them as 24 bits with the ability to correct up to 3 bit errors and detect up to 7. If I'm understanding RS codes correctly, an RS code with 12 data and 12 parity bits would be able to correct up to 6 bit errors and detect up to 12. So what is the advantage of a BG code in that case?
- heinrichhartman 6y ago
  I am no expert either, but I just checked Wikipedia on Reed-Solomon codes [1]: > By adding t check symbols to the data, a Reed–Solomon code can detect (but not correct) any combination of up to and including t erroneous symbols, OR locate and correct up to and including ⌊t/2⌋ erroneous symbols at unknown locations So it looks like you would have to choose between, either: A) correcting 6 bits OR B) detecting 12 bit errors. No? [1] https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_cor...
  - wtallis 6y ago
    The correct interpretation there is that for any given R-S code, the tolerance for correctable errors is half as many bits as the tolerance for uncorrectable but still detectable errors. If you have an R-S code constructed to correct 6 bits or detect 12-bit errors, then for a given message: if the number of corrupted bits is no more than six, you can reconstruct the original message if the number of corrupted bits is between 6 and 12, you will detect the corruption if the number of corrupted bits is larger than 12, you may or may not detect the corruption.
- omazurov 6y ago
  The binary Golay code works on bits. Reed-Solomon code works on symbols that are comprised of many bits. A RS code with 12 data and 12 parity symbols (not bits!) must have symbol representation of at least 5 bits to cover 12 + 12 = 24 possible code locations. Bit-wise such code will reliably correct only 6 bit errors out of 24 * 5 = 120 bits (assuming t/2 error correction algorithm). If the errors come in bursts, however, that code can correct up to 6 * 5 = 30 bits.
tuesday20 6y ago
Can you suggest some books to learn interesting math topics for someone with just high school understanding of math?
86____ 6y ago
There is a great Numerphile video that links sphere packing to mathematics. https://youtu.be/CROeIGfr3gs https://youtu.be/CROeIGfr3gs
WhitneyLand 6y ago
One reason it’s fascinating for me is there are many unsolved problems that you can explain to lay people easily. Sometimes it feels like it’s kind of trying to bait you into thinking: Hmm, that doesn’t seem that hard to prove, maybe I should spend some spare time on it. edit: in case it’s not obvious I’m not trying to be presumptive The fart of trying some of these doesn’t last long . I may fantasize for a minute after reading one, then remember there have been many “simple”problems that went unproven for hundreds of year or longer. something like trisecting an angle with a protractor I would guess drove a few people to near insanity.

jedimastert 6y ago

I didn't realize he died from COVID complications. That just makes it all the worse.

jon_elbrook 6y ago
He was 82.
- taylorlunt 6y ago
  He was also a human being and he died.
beefman 6y ago
How does it make it worse?

jmcomets 6y ago

Sphere packing was my 3rd year internship project (summer of 2013), so happy to see what is quite the fascinating topic mentioned on HN! I'm a bit sad I don't have a lot to show for it, other than an old undocumented GitHub repo[1]... Glad to hear there were breakthroughs in the field, thanks for the heap of links for me to delve into. :) [1]: https://github.com/dcoeurjo/ThicknessDiag https://github.com/dcoeurjo/ThicknessDiag

haneefmubarak 6y ago

Our of curiosity and as a noob to coding theory, what makes a Binary Golay code more useful than say a RS Code or something else more common? The linked wiki article said that given 12 bits, the BG code can encode them as 24 bits with the ability to correct up to 3 bit errors and detect up to 7. If I'm understanding RS codes correctly, an RS code with 12 data and 12 parity bits would be able to correct up to 6 bit errors and detect up to 12. So what is the advantage of a BG code in that case?

heinrichhartman 6y ago
I am no expert either, but I just checked Wikipedia on Reed-Solomon codes [1]: > By adding t check symbols to the data, a Reed–Solomon code can detect (but not correct) any combination of up to and including t erroneous symbols, OR locate and correct up to and including ⌊t/2⌋ erroneous symbols at unknown locations So it looks like you would have to choose between, either: A) correcting 6 bits OR B) detecting 12 bit errors. No? [1] https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_cor...
- wtallis 6y ago
  The correct interpretation there is that for any given R-S code, the tolerance for correctable errors is half as many bits as the tolerance for uncorrectable but still detectable errors. If you have an R-S code constructed to correct 6 bits or detect 12-bit errors, then for a given message: if the number of corrupted bits is no more than six, you can reconstruct the original message if the number of corrupted bits is between 6 and 12, you will detect the corruption if the number of corrupted bits is larger than 12, you may or may not detect the corruption.
omazurov 6y ago
The binary Golay code works on bits. Reed-Solomon code works on symbols that are comprised of many bits. A RS code with 12 data and 12 parity symbols (not bits!) must have symbol representation of at least 5 bits to cover 12 + 12 = 24 possible code locations. Bit-wise such code will reliably correct only 6 bit errors out of 24 * 5 = 120 bits (assuming t/2 error correction algorithm). If the errors come in bursts, however, that code can correct up to 6 * 5 = 30 bits.

tuesday20 6y ago

Can you suggest some books to learn interesting math topics for someone with just high school understanding of math?

86____ 6y ago

There is a great Numerphile video that links sphere packing to mathematics. https://youtu.be/CROeIGfr3gs https://youtu.be/CROeIGfr3gs

WhitneyLand 6y ago

One reason it’s fascinating for me is there are many unsolved problems that you can explain to lay people easily. Sometimes it feels like it’s kind of trying to bait you into thinking: Hmm, that doesn’t seem that hard to prove, maybe I should spend some spare time on it. edit: in case it’s not obvious I’m not trying to be presumptive The fart of trying some of these doesn’t last long . I may fantasize for a minute after reading one, then remember there have been many “simple”problems that went unproven for hundreds of year or longer. something like trisecting an angle with a protractor I would guess drove a few people to near insanity.