Octonions to the Rescue

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 G be a k-regular graph with girth g where g 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 G must have. Put m=(g-1)/2. Let’s look at one vertex v. It has k neighbors, let V_1 be the set of neighbors. Every neighbor in V_1 has k-1 “new” neighbors lets V_2 be the set of all those. We can continue this way and if there are no cycles of length smaller than g all these vertices are different for k=1,2,\dots, m. 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…)

About these ads
This entry was posted in Algebra and Number Theory, Combinatorics, Computer Science and Optimization, Open problems, Physics and tagged , , , . Bookmark the permalink.

11 Responses to Octonions to the Rescue

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

  2. Greg Friedman says:

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

  3. Kea says:

    Wow, 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 Kalai says:

      Well, 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.

  4. Alejandro Rivero says:

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

  5. Unfortunately the paper has just been withdrawn. See at

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s