Worms, brains and “graphes expanseurs”

Two days ago, I was in Paris and visited the École Polytechnique there (for the first time, as it turns out), in order to give the traditional introductory lecture presenting various aspects of mathematics that is given each year to the incoming class of students. (Many people would wonder how a new class can be incoming in April; this is because the students of École Polytechnique, which is a military school, begin their studies with a military/civil service from September to April).

I had selected expander graphs as the topic of my talk, as being simultaneously a very modern subject, that can be presented with very basic definitions (most students, coming from the French “Classes préparatoires” have had two very solid years of mathematical studies, but of a rather traditional kind), and that has links to many different areas, including more applied ones.

The slides of my presentation can be found here, in French, and I prepared an English translation there (up to the handwritten bits of information on certain pictures, which will remain in French…) Actually, the slides by themselves are not particularly interesting, since there are many remarks and details that I only described during the talk.

The talk begins with a discussion of graphs, continues with basic notions of expansion, and then defines expander graphs, with a bit of the history (especially the paper of Barzdin and Kolmogorov that I like very much), and concludes with two applications (among many…): Apollonian circle packings, and the Gromov-Guth knot-distorsion theorem. If this looks like a lot of ground to cover, this is because the talk was 1h30 long…

While preparing the first part of the talk, I researched some examples of graphs with more care than I had done before. Some of the things I found are extremely interesting, and since they might not be so well-known among my readers, I will present them quickly.

(1) The worm is Caenorhabditis elegans, more chummily known as C. elegans, one of the stars of neurosciences, as being the only animal whose entire nervous system has been mapped at the level of all individual neurons and connections between them. This was done in 1986 by White, Southgate, Thomson and Brenner, with minor corrections since then, and an important update and representation in 2011 by Varshney, Chen, Paniagua and Chklovskii. The resulting graph has 302 neurons (this number is apparently constant over all individuals), and about 8000 edges. (Interestingly, it is naturally a mix of directed and un-directed edges, depending on the type of biological connection). The paper of Varshney, Chen, Paniagua and Chklovskii is quite fascinating, as it investigates many mathematical invariants of the graph, and for instance compares the number of small subgraphs of various types with the expected number for random graphs with comparable parameters (certain subgraphs arise with higher frequency…)

Much more about C. elegans is found on dedicated websites, including Openworm, which seems to have as a goal to recreate the animal virtually…

(2) The brain is the humain brain; it can’t be mapped at the level of C. elegans (there are about 10^{11} neurons and 10^{15} synapses, from what I’ve seen), but I read a very interesting survey by Valiant about attempts to understand the computational model underpinning the reasoning capacities of the brain. He presents four basic tasks that must be among those that the brain performs, and explains how he succeeded in earlier work (from 1994 to 2005) in finding realistic algorithms and models for these problems. He comments:

In [5,14] it is shown that algorithms for the four random
access tasks described above can be performed on the
neuroidal model with realistic values of the numerical
parameters. The algorithms used are all of the vicinal
style. Their basic steps are all local in that they only
change synaptic strengths between pairs of neurons that
are directly connected. Yet they need to achieve the more
global objectives of random access. In order that they be
able to do this certain graph theoretic connectivity prop-
erties are required of the network. The property of
expansion [15], that any set of a certain number of
neurons have between them substantially more neighbors
than their own number, is an archetypal such property.
(This property, widely studied in computer science, was
apparently first discussed in a neuroscience setting [16].)
The vicinal algorithms for the four tasks considered here
need some such connectivity properties. In each case
random graphs with appropriate realistic parameters have
it, but pure randomness is not necessarily essential.

Here reference [16] is to the Barzdin-Kolmogorov paper.

(3) Lastly, I was wondering what is the size (number of vertices) of the largest graphs for which the first non-zero Laplace eigenvalue has been computed, approximately. The best I found is a paper of Kang, Breed, Papalexakis, and Faloutsos, which describes an algorithm that they have applied successfully to real-world graphs with about a billion vertices. This is rather impressive…

0.00023814967230605090687395214144185337601

Yesterday my younger son was playing dice; the game involved throwing 6 dices simultaneously, and he threw a complete set 1, 2, 3, 4, 5, 6, twice in a row!

Is that a millenial-style coincidence worth cosmic pronouncements? Actually, not that much: since the dices are indistinguishable, the probability of a single throw of this type is

\frac{6!}{6^6}\simeq  0.015432098765432098765432098765432098765,

so about one and a half percent. And for two, assuming independence, we get a probability

\frac{(6!)^2}{6^{12}}\simeq 0.00023814967230605090687395214144185337601,

or a bit more than one chance in five throusand. This is small, but not extraordinarily so.

(The dices are thrown from a cup, so the independence assumption is quite reliable here.)

Trace functions, a survey

At last count, my series of works with Étienne Fouvry and Philippe Michel on trace functions and their applications consists of seven research papers or preprints, amounting to a bit more than 200 pages. To these are added a number of works-in-progress or partial notes (some with results we did not need or use and so took out of earlier drafts of our papers, some with worked-out examples or remarks, etc). We have a relatively firm project of writing a monograph account of the whole theory and applications, which we view in part as a way of making accessible some of the deep consequences of the Riemann Hypothesis over finite fields of Deligne, but this is clearly a long-term project. In the meantime, we have written a first short survey, the first draft of which can be found on my web page. This is in fact the written (and slightly expanded) account of a Colloquio de Giorgi that I gave at the

[Scuola Normale Superiore]
Scuola Normale Superiore

Scuola Normale Superiore in Pisa earlier this year, and we have included an unusual representation of the fundamental domain of the modular group acting on the upper half-plane as an homage and acknowledgement of this occasion.

[Pisa]
Pisa

Fouvry 60

We are currently enjoying in Marseille the warmth and delights of a French Mediterranean Bouillabaisse while celebrating analytic number theory and the achievements of É. Fouvry, on the occasion of his 60th birthday.

I think everyone who has been in contact with any of his papers has immense respect for his scientific work. All those of us who have been fortunate enough to talk with him beyond purely scientific matters will also attest to his exemplary intellectual honesty, rectitude, generosity and — also important to my mind — to his sense of humor.

In analytic number theory, we play day to day in a wild down-to-earth jungle. We also all know that somewhere there is a Garden of Eden, where the Riemann Hypothesis roams free, and we hope to go there one day. Fewer know that there is a place even beyond, a Nirvana where even the Riemann Hypothesis is but a shadow of a deeper truth. And fewer still are those who have set foot in this special place. É. Fouvry did, and he was among the very first ones, if not the very first; and more people have walked on the moon than been there.

A few years ago, I wrote a nominating letter for Étienne’s application to the Institut Universitaire de France. There is one sentence that I wrote which still seems to me to summarize best my feelings about this part of his work: Rarely in history was so much owed by so many arithmeticians to so few. This is even truer today than it was then. Reader, if you care at all about prime numbers, recall that without É. Fouvry and very few others (two of whom are with us in Marseille), you might well never have known that the gaps between successive primes do not grow to infinity.