Hacker News Reader

Comment by heinrichhartman | Hacker News Reader

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 [2] https://en.wikipedia.org/wiki/Leech_lattice [3] https://arxiv.org/pdf/1603.06518.pdf [4] https://en.wikipedia.org/wiki/Binary_Golay_code

View on HN

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

He was 82.

He was also a human being and he died.

How does it make it worse?

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.

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

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?

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_cor...

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.

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.

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

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

Reply on news.ycombinator.com