Whether there exist subexponential-size locally decodable codes, and sub-nε-communication private information retrieval (PIR) protocols, have been major open problems for a decade. A new preprint by Sergey Yekhanin reveals that both of these questions hinge on -- wait for this -- whether or not there are infinitely many Mersenne primes. By using the fact (discovered a month ago) that 232,582,657-1 is prime, Yekhanin can already give a 3-server PIR protocol with communication complexity O(n1/32,582,658), improving the previous bound of O(n1/5.25). Duuuuuude. If you've ever wondered what it is that motivates complexity theorists, roll this one up and smoke it.I do not pretend of understanding much about this statement but I have the dim gut feeling that the existence of infinite number of Mersenne primes would be wonderful for communications. In any case I can optimistically click the link and try to read the abstract.
- At the first line of abstract I make a head on collision with "Q-query Locally Decodable Code (LDC)". LDC codes n-bit message to an N-bit code word C(x) such that one can probabilistically recover any bit of the message by querying only q bits of the code words, even after some constant fraction of bits have been corrupted. Error correction seems to be in question. Knowledge of these q bits allow to save all bits. "Locally decodable" has only heuristic meaning for me.
- Authors assign to Mersenne primes Mt=2t-1 (t is also prime) 3-query codes satisfying N=exp(n-1/t) for all values of the bit number n. As Mersenne prime increases N approaches to unity. I guess that the equality is a shorthand for N=Pn(t)exp(n-1/t), Pn(t) a polynomial.
The original discovery was that the mass scale ratios for elementary particles seem to be near to ratios of Mersenne primes. Eventually this led to p-adic mass calculations where the prime p characterizing p-adic number field characterizes elementary particle mass scale. It turns out that quite many elementary particles correspond to Mersennes or Gaussian Mersennes (also primes p near 2k, k prime or even integer, are possible). In particular, Mersenne primes label bosons mediating fundamental interactions: electro-weak gauge bosons correspond to M89, M107 to gluons, and gravitons can be assigned to M127 defining the largest non-super-astronomical p-adic length scale of this kind.
Also Gaussian Mersennes are interesting. The length scale range between 10 nm (cell membrane thickness) and 2.5 micrometers (size of small cell) contains four(!) Gaussian Mersennes Gk = (1+i)k-1, k=151,157,163,167. All primes k in this range define Gaussian Mersennes. This number theoretic miracle suggests that also Gaussian Mersennes are crucial for communications and especially so in living matter!
The heuristics is that Mersenne primes and their Gaussian cousins are winners in the number theoretical fight for survival. Maybe the ability to communicate reliably with minimum number of "parity bits" is the key to the success. Mersennes and possibly Fermat primes (very few of latter are known or might even exist) would be preferred since they are so near to powers of two. If the number of Mersenne primes is infinite, TGD would predict infinite hierarchy of exotic bosons and maximally interesting Universe. TGD inspired theory of consciousness suggests that real fermionic partons and their p-adic counterparts form particle and its cognitive representation so that cognition, information processing, and communications would be present already at elementary particle level. Exciting!