Xavier Dahan and Jean-Pierre Tillich’s Octonion-based Ramanujan Graphs with High Girth.
Update (February 2012): Non associative computations can be trickier than we expect. Unfortunately, the paper by Dahan and Tillich turned out to be incorrect.
Update: There is more to be told about the background of the new exciting paper. In particular, I would like to tell you more about regular graphs with high girth. (I started below.) The Ramanujan graphs story is, of course, also fascinating so at the very least I should give good links.
Michael Atiyah‘s lecture at IAS physics last Friday was entertaining, educational and quite provocative.
The talk started with the following thesis: There are four fundamental forces of nature and there are four division rings over the reals. The real numbers, complex numbers, Quaternions and the Octonions. Atiyah expects that the Octonions will play a major role in physics and will allow a theory which accounts for gravitation. He described some specific steps in this direction and related ideas and connections. At the end of the talk, Atiyah’s thesis looked more plausible than in the beginning. His concluding line was: “you can regard what I say as nonsense, or you can claim that you know it already, but you cannot make these two claims together.” In any case, it looks that the people in the audience were rather impressed by and sympathetic to the Octonionic ideas of this wise energetic scientific tycoon.
The same day I received an email from Nati Linial. The subject was: “a good topic for your blog” and the email contained just a single link.
Nati is my older academic brother and often I regard our relations as similar to typical relations between older and younger (biological) brothers. When he tells me what to do I often rebel, but usually at the end I do as he says and most of the times he is right.
So I waited a couple of hours before looking at the link. Indeed, 1011.2642v1.pdf is a great paper. It uses Octonions in place of Quaternions for the construction of Ramanujan graphs and describes a wonderful breakthrough in creating small graphs with large girth. Peter Sarnak’s initial reaction to the new paper was: “wow”.
Here is a link to a paper entitled “Octonions” by John Baez, that appeared in Bull. AMS.
Let be a -regular graph with girth where is an odd integer. Continue reading