E. Kowalski’s blog

I have one more lecture next week in my expander class, but today I finished the proof of Helfgott’s growth theorem for . As I had hoped, I did this in my notes with explicit constants (I didn’t try to follow those constants on the blackboard).

Taking into account some grains de sel, since there may well be minor computational mistakes lurking around (though I have already corrected a few), the result I obtain is the following: if is prime, and if is a symmetric generating set, containing for simplicity, then either the triple product

is all of , or otherwise we have

where

(Of course, the factor can be incorporated into a slightly-smaller exponent, but that introduces an ugly-looking dependency on the size of , which one must recover using an uglier trivial bound for small, so I preferred this version…)

The current version of the notes contains the argument, though it is a bit rough (I will soon rearrange some of it, to attempt to provide more motivation — at least the way I understand how it goes…)

For the proof, I followed the clear outline in the first sections of the paper of Pyber and Szabó. This reduces the problem, rather quickly and cleanly, to a “non-concentration” estimate for the intersection of with a regular-semisimple conjugacy class , of the type

for some fixed and absolute constant . This inequality is now commonly called a (generalized) Larsen-Pink inequality (the prototype going back to the late 90′s preprint — now published — of Larsen and Pink for the non-concentration of finite subgroups of algebraic groups in subvarieties). Though the general case is quite tricky, there is here an easy enough argument, based on studying the fibers of the map

where the three arguments are all in (this is the basic idea already presented by Larsen and Pink to explain their result, in another case).

It turns out that, if one imposes that is not the conjugacy class of elements of trace 0, which can be ensured (using bare hands) by “escape from subvarieties”, the cases where this map has positive-dimensional fibers are rather simple to analyze (I owe this computation to R. Pink…)

Moreover, only one case requires another instance of Larsen-Pink-type inequalities (those readers who have looked at the paper of Larsen and Pink, or the one of Breuillard-Green-Tao which has a general “approximate” version, will know that there is a rather complicated induction involved in general), and it is a very easy one: if is the subgroup of upper-triangular unipotent matrices, then

which is an instructive exercise. (In fact, in rearranging this section of my notes, I will use this as a motivating example…)

With this final ingredient, I can now produce (with the same amount of salt…) an effective spectral gap for the Cayley graphs of the Lubotzky subgroup of , generated by

modulo primes, namely (drumroll) for large enough (drumroll; but I won’t tell you how large today), we have (drumroll)

(Actually, I already know various points of inefficiency in my treatment of the Bourgain-Gamburd expansion argument which should lead to some improvements, and I hope to find other avenues to explore and stones to turn to do better…)

The beginning of my lecture notes on expander graphs is now available. These first sections are really elementary. If it were not grossly insulting to the noble brotherhood (and sisterhood) of bookkeepers, I would say that I deal here mostly with bookkeeping: setting up a rigorous “coding” of the class of graphs I want to consider (which are unoriented graphs where multiple edges are allowed as well as loops), defining maps between such graphs, and setting up the basic examples of Cayley graphs and Schreier graphs.

But still, I managed to trip once on the last point, and my first definition turned out to be rather bad. Of course, it is not that I don’t know what a Schreier graph is supposed to be, but rather that I stumbled when expressing properly this intuition in the specific “category” I am using (where a graph is a triple , with vertex set , edge set , and

is the “endpoints” map.)

What I knew about the Schreier graph of a group with respect to a subgroup and a (symmetric) generating set is that it should be -regular, and the combinatorial Laplace operator should be given by

for any function on . This I managed to ensure on the second try, though the definition is a bit more complicated than I would like.

I actually wrote things down for more general “action graphs”, which are pretty much the obvious thing: given an action of the group on a set , one takes as vertices, and moves along edges (set up properly) from to for in the given subset of . Here is a query concerning this: do these general graphs have a standard name? I have not seem the definition in this generality before, but it seems very natural and should be something well-known, hence named. (Of course, using decomposition in orbits, such a graph is a disjoint union of Schreier graphs modulo stabilizers of certain points of , but that doesn’t make it less natural.)

In any case, here is an illustration of the action graph for the symmetric group , with generators , acting on by evaluation:

Equivalently, this is the Schreier graph of with respect to , where is the stabilizer of .

As it should be, this graph is -regular, and this property would fail if loops and multiple edges were not permitted. It is true that, in that case, the resulting graph (a cycle of length ) would remain regular after removing loops and multiple edges, but the interested reader will have no problem checking that if is replaced by

removing loops and multiple edges from the corresponding action graph leads to a non-regular graph. (The vertex 1 has three neighbors then, namely , while the others have only 2.)

(The typesetting of the graph is done using the tkz-graph package already mentioned in my previous post.)

While writing the chapters about compact groups in my notes, I had a few times the impression that it would be useful to use the fact that there is a basis of conjugacy-invariant neighborhoods of 1 in such a group. This thought would then fork in two subthreads, one in which I noticed that I didn’t really see how to prove this, and the second in which I realized I didn’t need it anyway.
This happened again during the last week-end, with the difference that I thought of trying to prove this property using representation theory. I failed at first, and finally tried to look it up online to make sure the property was actually true. Indeed, it is, and I found this book, which has three proofs (of a slightly more general statement). But I have to admit to having an inferiority complex with respect to general topology: any argument that goes on for more than a few lines without being transparent tends to make me uneasy and confuse me, and this is what happened with these arguments.

So I tried again to use representations, and indeed it works! Here’s the idea: the regular representation of on (with respect to Haar measure) is faithful, and gives a continuous injection

where the unitary group is given the strong operator topology (if is infinite, it is not continuous for the operator norm topology). Hence this map is a homeomorphism onto its image (we use here the compactness of ). What we gain from seeing in this way as a subgroup of the unitary group of a (typically) infinite-dimensional space, and with a “strange” topology to boot, is a concrete description of a basis of open neighborhoods of 1, which is open to further manipulations.

Indeed, from the definition of the strong topology on , any open neighborhood of 1 contains a finite intersection of sets of the type

where has norm 1 and . It is then easy to see, using unitarity, that the conjugacy-invariant subset

is equal to

where

is the orbit of under . But the strong continuity of implies that the orbit map is continuous for fixed , so that is compact in (as image of a compact set under a continuous map; here has the usual norm topology).
It is then a quick application of a standard compactness argument and splitting of epsilons to check that is a neighborhood of 1 contained in , and intersecting finitely many of these, we see that contains indeed a conjugacy invariant neighborhood of 1…

I really can’t say that it is simpler than the purely topological argument (mostly because one needs to know about Haar measure!), but I find this rather nice as an exercise. It illustrates how representation theory can be useful to study a general compact group, at a very basic level, and also shows that it may be useful to embed (or project, with the orbit map) a compact group into complicated-looking infinite-dimensional beasts… (Of course, if has a faithful finite-dimensional representation, this can be used instead of , but the purely topological argument becomes also much simpler.)

I have just added to my notes on representation theory the very cute formula of Frobenius that gives, in terms of irreducible characters, the number of representations of a given element as a commutator in a finite group :

where runs over the irreducible (complex) characters of (this is Proposition 4.4.3 on page 118 of the last version of the notes).

I wanted to mention some applications, and had a vague memory that this was used to show that most or all elements in various simple groups are actual commutators. By searching around a bit, I found out easily that, indeed, there was a conjecture of Ore from 1951 to the effect that the set of commutators is equal to for any non-abelian finite simple group , and that (after various earlier works) this has recently been proved by Liebeck, O’Brien, Shalev and Tiep.

I mentioned this of course, but then I also wanted to give some example of non-commutator, and decided to look for this using Magma (the fact that I am recovering from a dental operation played a role in inciting me to find something distracting to do). Here’s what I found out.

First, a natural place to look for interesting examples is the class of perfect groups, of course not simple. This is also easy enough to implement since Magma has a database of perfect groups of “small” order. Either by brute force enumeration of all commutators or by implementing the Frobenius formula, I got the first case of a perfect group , of order , which contains only distinct commutators.

Then I wanted to know “what” this group really was. Magma gave it to me as a permutation group acting on letters, with an explicit set of generators, and with a list of relations, which was not very enlightening. However, looking at a composition series, it emerged that fits in an exact sequence

This was much better, since after a while it reminded me of one of my favorite types of groups: the Weyl groups of the symplectic groups (equivalently, the “generic” Galois group for the splitting field of a palindromic rational polynomial of degree ), which fit in an relatively similar exact sequence

From there, one gets a strong suspicion that must be the commutator subgroup of , and this was easy to check (again with Magma, though this is certainly well-known; the drop of the rank of the kernel comes from looking at the determinant in the signed-permutation -dimensional representation, and the drop from to is of course from the signature.)

This identification is quite nice, obviously. In particular, it’s now possible to identify concretely which elements of are not commutators. It turns out that a single conjugacy class, of order , is the full set of missing elements. As a signed permutation matrix, it is the conjugacy class of

and the reason it is not a commutator is that Magma tells us that all commutators in have trace in (always in the signed-permutation representation). Thus the trace doesn’t fit…

At least, this is the numerical reason. I feel I should be able to give a theoretical explanation of this, but I haven’t succeeded for the moment. Part of the puzzlement is that this behavior seems to be special to , the Weyl group of the root system . Indeed, for , the corresponding derived subgroup is not perfect, so the question does not arise (at least in the same way). And when , the derived subgroup of is indeed perfect, but — experimentally! — it seems that all elements of are then commutators.

I haven’t found references to a study of this Ore-type question for those groups, so I don’t know if these “experimental” facts are in fact known to be true. Another question seems natural: does this special fact have any observable consequence, for instance in Galois theory? I don’t see how, but readers might have better insights…

(P.S. I presume that GAP or Sage would be equally capable of making the computations described here; I used Magma mostly because I know its language better.

P.P.S And the computer also tells us that even for the group above, all elements are the product of at most two commutators, which a commenter points out is also a simple consequence of the fact that there are more than commutators….

P.P.P.S To expand one of my own comments: the element above is a commutator in the group itself. For instance with

and

where .)

Searching on Numdam for the papers of É. Cartan, I noticed one from 1927 entitled “Sur certains cycles arithmétiques”. Although this was not the one I was looking for, natural curiosity immediately had the better of me, and I downloaded the article, wondering what marvels could be there: an anticipation of Heegner cycles? special subvarieties of Shimura varieties?

As usual, the truth was even more surprising than such exalted expectations. Indeed, Cartan, considering “le problème de Mathématiques élémentaires proposé au dernier concours d’agrégation”, raises and solves the following question:

Classify, for any base , the integers such that, when is written in base , the integers obtained by all cyclic permutation of the digits are in arithmetic progression.

This is rather surprising, since I had no idea that É. Cartan had any interest in elementary number theory; considering that he was 58 years old in 1927, I find this quite whimsical and refreshing…

Here is an example: for base 10, take ; the cyclic permutations yield the additional integers and ; and — lo and behold — we have indeed

exhibiting the desired arithmetic progression. (One also allows a leading digit being , wich can be permuted with the others, so that, for instance, , with companions and , is also a solution.)
More impressively consider ; with — in order — the progression

with common difference equal to (which is also the smallest of the 6 integers.)

Cartan finds two distinct sources of such cycles, which he calls “de première [resp. de seconde] catégorie”, and classifies them, for any base . The original problème d’agrégation asked for cycles of lengths 3 and 6 in base 10 and Cartan finds 3 cycles of length 6 and 6 of length 3. I wonder how many students managed to solve this question…

I won’t write down the solutions here — for the moment at least –, so that those readers who are interested can try their own skill…