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!
3 comments:
10 25 06
Matti:
Heh this is interesting. My next post will have something to do with Mersenne primes. Thanks for the inspiration!
Dear Sir,
your findings about Mersennes and Gaussian Mersennes are very amusing.
I would like to pose two questions to you:
1) It would be interesting to extend the notion of Mersenne primes
to quaternions and octonions: perhaps also in these fields
one can find correspondences to meaningful physical hierarchies.
2) Joël Sternheimer, French physicist, claims that
sound waves can influence the protein synthesis in living organisms.
(As a former musician, he was surprised to find that the distribution
of the mass of particles appear commensurate with frequencies (notes)
of the musical "tempered scale". citation from http://www.trufax.org/leonline.html)
Two references:
http://www.bekkoame.ne.jp/~dr.fuk/InterNonlocF.html
http://www.bekkoame.ne.jp/~dr.fuk/IndexE.html
For the little I've read,
it is my feeling that TGD could give
to this interesting phenomenon
an original theoretical framework.
Thank you and best regards,
Fabrizio Vassallo,
Pisa
Dear Fabrizio,
I am very sorry for a delayed response: I was at conference in Hungary. Thank you for questions and links. I hope I could find time to look the references to consider explanation. I learned in the conference that also radio waves from space affect the distribution of molecular weights of DNAs so that mere noise cannot be in question and there must be a mechanism in which radio waves affect this distribution.
The biological Gaussian Mersennes are really fascinating and I would hope to discover more concrete ideas about their role.
The extension of notion of Mersenne prime to quaternions and octonions seems plausible. Gaussian Mersennes are certainly excellent candidates since the norm squared is prime. One should find whether they remain primes in quaternionic context or decompose to a product of more elementary units.
With Best Regards,
Matti Pitkanen
Post a Comment