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

http://arxiv.org/PS_cache/arxiv/pdf/1011/1011.2642v1.pdf

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.

### Some background:

Let be a -regular graph with girth where is an odd integer. Recall that the girth of a graph is the length of the smallest cycle. We can ask: what is the minimum number of vertices must have. Put . Let’s look at one vertex . It has neighbors, let be the set of neighbors. Every neighbor in has “new” neighbors lets be the set of all those. We can continue this way and if there are no cycles of length smaller than all these vertices are different for . So we identified $1+k+k(k-1)+\dots+k(k-1)^{m-1}$ different vertices. This gives a lower bound known as “Moore bound”.

How good is this bound? It is surprisingly good and the paper by Dahan and Tillish breaks the known records in this respect. (To be continued…)

Pingback: Tweets that mention Octanions to the Rescue | Combinatorics and more -- Topsy.com

Greg FriedmanHi Gil,

I think I much more often see “Octonion” than “Octanion”, so I’m curious if you have a conscious reason for preferring the latter.

Greg FriedmanPS. How does Atiyah say it?

Gil KalaiPost authorHi Greg, greetings. This was a mistake, I suppose.

KeaWow, I hope the Atiyah lecture makes it onto their great video website. As someone in the ‘knew it already’ camp, I am very interested to know what he is thinking.

Gil KalaiPost authorWell, I suppose the comment at the end referred to the entire talk: He described in the beginning another basic principle related to cutoffs and then a lot of other stuff including a new looks at protons and neutrons.

Alejandro RiveroDid Atiyah speak of CP2 vs S4 as something similar to covering spaces? It is a topic that very few people can claim to know.

Alejandro Riverohttp://arxiv.org/abs/math/0206135 is Atiyah’s take on CP2/S4, if someone is curious about.

Alejandro RiveroAnd here is Arnold’s take: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.50.6421&rep=rep1&type=pdf

Lior SilbermanUnfortunately the paper has just been withdrawn. See at

Lior SilbermanThe system at my hyperlink. It was http://arxiv.org/abs/1011.2642