Kloostermania turns 1.0

Since the Pocket Kloostermania has remained unchanged for almost five years, an update is probably welcome! This is now available, in time to honor N. Katz on the occasion of this 71st birthday (which I will help celebrate in China next week).

Important changes in the new version:

(1) It was recompiled — hence a new modern look instead of a style reminiscent of the dark ages –, and the resulting binary should work on any Android system with version 4.0.3 or later;

(2) To keep up with recent progress, the program now displays Kloosterman sums and/or Birch sums, instead of Kloosterman and/or Salié sums. On the other hand, the moduli used are now restricted to primes, to simplify things a bit, and only one parameter is used: the sums displayed are
$latex \sum_{x\in\mathbf{F}_p^{\times}}e\Bigl(\frac{ax+\bar{x}}{p}\Bigr)$
and
$latex \sum_{x\in\mathbf{F}_p}e\Bigl(\frac{ax+x^3}{p}\Bigr)$

(3) In addition to being able to change the modulus by swiping horizontally, a vertical swipe on the screen scrolls among the values of the parameter $latex a$. As was the case in the previous version (and even more because phones are faster now), the scrolling is usually too fast for a single step, so tapping once close to one of the edges of the window displaying the sum will perform just one step of the corresponding move (e.g., tapping close to the right of the screen goes to the next prime modulus). The value of the sum and its parameters and then displayed quickly.

(4) The plots are presented in orthonormal configurations, to give a more faithful representation of the paths in the plane;

Kloostermania
Kloostermania

(5) In the “About” dialog, a single click will display (if a PDF viewer is installed) the paper of W. Sawin and myself that explains the limiting distribution of Kloosterman (and Birch) paths…

(6) It is possible to save (or rather to “share” in the usual Android way) a picture of the sums currently displayed, as a PNG file.

(6) And the launcher icon is better.

Icon
Icon

The installation file is available right now on the updated Kloostermania page!

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 $latex 10^{11}$ neurons and $latex 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…

Kummer extensions, Hilbert’s Theorem 90 and judicious expansion

This semester, I am teaching “Algebra II” for the first time. After “Algebra I” which covers standard “Groups, rings and fields”, this follow-up is largely Galois theory. In particular, I have to classify cyclic extensions.

In the simplest case where $latex L/K$ is a cyclic extension of degree $latex n\geq 1$ and $latex K$ contains all $latex n$-th roots of unity (and $latex n$ is coprime to the characteristic of $latex K$), this essentially means proving that if $latex L/K$ has cyclic Galois group of order $latex n$, then there is some $latex b\in L$ with $latex L=K(b)$ and $latex b^n=a$ belongs to $latex K^{\times}$.

Indeed, the converse is relatively simple (in the technical sense that I can do it on paper or on the blackboard without having to think about it in advance, by just following the general principles that I remember).

I had however the memory that the second step is trickier, and didn’t remember exactly how it was done. The texts I use (the notes of M. Reid, Lang’s “Algebra” and Chambert-Loir’s delightful “Algèbre corporelle”, or rather its English translation) all give “the formula” for the element $latex b$ but they do not really motivate it. This is certainly rather quick, but since I can’t remember it, and yet I would like to motivate as much as possible all steps in this construction, I looked at the question a bit more carefully.

As it turns out, a judicious expansion and lengthening of the argument makes it (to me) more memorable and understandable.

The first step (which is standard and motivated by the converse) is to recognize that it is enough to find some element $latex x$ in $latex L^{\times}$ such that $latex \sigma(x)=\xi x$, where $latex \sigma$ is a generator of the Galois group $latex G=\mathrm{Gal}(L/K)$ and $latex \xi $ is a primitive $latex n$-th root of unity in $latex L$. This is a statement about the $latex K$-linear action of $latex G$ on $latex L$, or in other words about the representation of $latex G$ on the $latex K$-vector space $latex L$. So, as usual, the first question is to see what we know about this representation.

And we know quite a bit! Indeed, the normal basis theorem states that $latex L$ is isomorphic to the left-regular representation of $latex G$ on the vector space $latex V$ of $latex K$-valued functions $latex \varphi\,:\, G\longrightarrow K$, which is given by
$latex (\sigma\cdot \varphi)(\tau)=\varphi(\sigma^{-1}\tau)$.
(It is more usual to use the group algebra $latex K[G]$, but both are isomorphic).

The desired equation implies (because $latex G$ is generated by $latex \sigma$) that $latex Kx$ is a sub-representation of $latex L$. In $latex V$, we have an explicit decomposition in direct sum
$latex V=\bigoplus_{\chi} K\chi,$
where $latex \chi$ runs over all characters $latex \chi\,:\, G\longrightarrow K$ (these really run over all characters of $latex G$ over an algebraic closure of $latex K$, because $latex K$ contains all $latex n$-th roots of unity and $latex G$ has exponent $latex n$). So $latex x$ (if it is to exist) must correspond to some character. The only thing to check now is whether we can find one with the right $latex \sigma$ eigenvalue.

So we just see what happens (or we remember that it works). For a character $latex \chi\in V$ such that $latex \chi(\sigma) = \omega$, and $latex x\in L^{\times}$ the element corresponding to $latex \chi$ under the $latex G$-isomorphism $latex L\simeq V$, we obtain $latex \sigma(x)=\omega^{-1}x$. But by easy character theory (recall that $latex G$ is cyclic of order $latex n$) we can find $latex \chi$ with $latex \chi(\sigma)=\xi^{-1}$, and we are done.

I noticed that Lang hides the formula in Hilbert’s Theorem 90: an element of norm $latex 1$ in a cyclic extension, with $latex \sigma$ a generator of the Galois group, is of the form $latex \sigma(x)/x$ for some non-zero $latex x$; this is applied to the $latex n$-th root of unity in $latex L$. The proof of Hilbert’s Theorem 90 uses something with the same flavor as the representation theory argument: Artin’s Lemma to the effect that the elements of $latex G$ are linearly independent as linear maps on $latex L$. I haven’t completely elucidated the parallel however.

(P.S. Chambert-Loir’s blog has some recent very interesting posts on elementary Galois theory, which are highly recommended.)

A parity lemma of A. Irving

In his recent work on the divisor function in arithmetic progressions to smooth moduli, A. Irving proves the following rather amusing lemma (see Lemma 4.5 in his paper):

Lemma Let $latex p$ be an odd prime number, let $latex k\geq 1$ be an integer and let $latex h=(h_1,\ldots,h_k)$ be a $latex k$-tuple of elements of $latex \mathbf{F}_p$. For any subset $latex I$ of $latex \{1,\ldots, k\}$, denote
$latex h_I=\sum_{i\in I}{h_i},$
and for any $latex x\in\mathbf{F}_p$, let
$latex \nu_h(x)=|\{I\subset \{1,\ldots, k\}\,\mid\, h_I=x\}|$
denote the multiplicity of $latex x$ among the $latex (h_I)$.
Then if none of the $latex h_i$ is zero, there exists some $latex x$ for which $latex \nu_h(x)$ is odd.

I will explain two proofs of this result, first Irving’s, and then one that I came up with. I’m tempted to guess that there is also a proof using some graph theory, but I didn’t succeed in crafting one yet.

Irving’s proof. This is very elegant. Let $latex \xi$ be a primitive $latex p$-th root of unity. We proceed by contraposition, hence assume that all multiplicities $latex \nu_h(x)$ are even. Now consider the element
$latex N=\prod_{i=1}^k(1+\xi^{h_i})$
of the cyclotomic field $latex K_p=\mathbf{Q}(\xi)$. By expanding and using the assumption we see that
$latex N=\sum_{x\in\mathbf{F}_p} \nu_h(x)\xi^{x}\in 2\mathbf{Z}[\xi].$
In particular, the norm (from $latex K_p$ to $latex \mathbf{Q}$) of $latex N$ is an even integer, but because $latex p$ is odd, the norm of $latex 1+\xi^{h_i}$ is known to be odd for all $latex h_i\not=0$. Hence some factor must have $latex h_i=0$, as desired.

A second proof. When I heard of Irving’s Lemma, I didn’t have his paper at hand (or internet), so I tried to come up with a proof. Here’s the one I found, which is a bit longer but maybe easier to find by trial and error.

First we note that
$latex \sum_{x\in \mathbf{F}_p} \nu_h(x)=2^k$
is even. In particular, since $latex p$ is odd, there is at least some $latex x$ with $latex \nu_h(x)$ even.

Now we argue by induction on $latex k\geq 1$. For $latex k=1$, the result is immediate: there are two potential sums $latex 0$ and $latex h_1$, and so if $latex h_1\not=0$, there is some odd multiplicity.

Now assume that $latex k\geq 2$ and that the result holds for all $latex (k-1)$-tuples. Let $latex h$ be a $latex k$-tuple, with no $latex h_i$ equal to zero, and which has all multiplicities $latex \nu_h(x)$ even. We wish to derive a contradiction. For this, let $latex j=(h_1,\ldots,h_{k-1})$. For any $latex x\in\mathbf{F}_p$, we have
$latex \nu_h(x)=\nu_j(x)+\nu_j(x-h_k),$
by counting separately those $latex I$ with sum $latex x$ which contain $latex k$ or not.

Now take $latex x$ such that $latex \nu_j(x)$ is odd, which exists by induction. Our assumptions imply that $latex \nu_j(x-h_k)$ is also odd. Then, iterating, we deduce that $latex \nu_j(x-nh_k)$ is odd for all integers $latex n\geq 0$. But the map $latex n\mapsto x-nh_k$ is surjective onto $latex \mathbf{F}_p$, since $latex h_k$ is non-zero. Hence our assumption would imply that all multiplicities $latex \nu_j(y)$ are odd, which we have seen is not the case… Hence we have a contradiction.