An exponential sum of Conrey and Iwaniec

In their remarkable paper on the third moment of special values of twisted L-functions of modular forms, Conrey and Iwaniec require (among many ingredients!) a best-possible estimate (square-root cancellation) for the exponential sums
where \chi and \eta are non-trivial multiplicative characters modulo a prime p. Using a combination of the formalism of such exponential sums (including the consequences of the rationality of the corresponding L-functions over finite fields and of the Riemann Hypothesis of Deligne) together with some elementary averaging arguments inspired by ideas of Bombieri, and special treatment of the case \chi=\eta, they succeed in proving that
S(\chi,\eta)\ll p,
which is the expected estimate.

I looked at this sum recently because I wondered if (like the other sum of Friedlander and Iwaniec mentioned at the end of my previous post) it would turn out to be a special case of the correlation sums that feature in my recent paper with Fouvry and Michel. As far as I can see, it isn’t of this type, but this led me to attempt to find a proof of the estimate of Conrey and Iwaniec based on the philosophy of reducing a character sum in more than one variable to a one-parameter sum which involves more complicated summands than character values.

This does indeed work. I’ve written a short note explaining this (it is not intended for publication, so rather terse at some points). The outline is rather straightforward: we write
is a character and
which is a more “complicated” summand, but still a one-variable character sum.

It turns out that R(u) and -T(u) are both among these nice algebraic trace functions that occur in the paper with Fouvry and Michel. In particular they have the crucial irreducibility property that make such functions quasi-orthogonal, which means here that we get
\sum_u R(u)T(u)\ll q
unless \overline{R(u)} and T(u) are proportional for all u. (The size q on the left-hand side comes from the fact that T(u) is of weight 1, i.e., a sum of a bounded numbers of algebraic numbers of modulus \sqrt{q}; the one-variable sum over u gives square-root cancellation — by the Riemann Hypothesis — for the bounded summands q^{-1/2}R(u)T(u).)

One should feel that it is unlikely that \overline{R(u)} and T(u) are proportional, and indeed it is easy to show during the construction that they are not (the algebraic reason is that one is the trace of a representation of degree 1, whereas the other is a trace of a representation of degree 2…). To finish the proof, one must still be careful to control the implied constant in the estimate above, since it is a priori dependent on the characteristic of the finite field involved. A true dependency like this would be catastrophic, but one can show (in different ways) that this constant is in fact bounded uniformly (the basic reason is that the invariants measuring the complexity of the functions R(u) and T(u) are bounded independently of p).

This argument is quite clean in outline (and requires no special consideration of special cases like \chi=\eta) but it uses rather deep tools. In addition to three applications of the Riemann Hypothesis (one to understand the summand T(u), another to perform the sum over u, and the last as explained in a second), there is a fair amount of deep formalism involved in checking that T(u) has the desired properties for a nice algebraic function. There is one last nice ingredient: in order to ensure quasi-orthogonality, one needs to know that T(u) is irreducible in some precise sense. This requirement turns out to translate (using a last time the Riemann Hypothesis) to a nice diophantine property of these sums, namely that
\lim_{|k|\rightarrow +\infty}\frac{1}{|k|^2}\sum_{u}{|T_k(u)|^2}=1,
where k runs over finite extensions of \mathbf{F}_q and, denoting by N the form from k to \mathbf{F}_q, the sum
T_k(u)=\sum_{v\in k}{\chi(N(v(v+1)))\eta(N(uv-1))},
is the natural companion of T to such extensions. The proof of this limit formula is a nice exercise in manipulating finite sums in the tradition of analytic number theory…

A bijective challenge

Étienne Fouvry, Philippe Michel and myself have just finished a new paper, which is available on my web page and will soon be also on arXiv. This was quite an extensive project, which also opens many new questions. I will discuss the general problem we consider, and the techniques we use, in other posts, but today I want to discuss a by-product that we found particularly nice (and amusing). It can be phrased as a rather elementary-looking challenge: given a prime number p, and an element t of \mathbf{Z}/p\mathbf{Z} which is neither 0, 4 or -4 modulo p, let N_p(t) be the number of solutions (x,y)\in (\mathbf{Z}/p\mathbf{Z}-\{0\})^2 of the congruence


The challenge is to prove, bijectively if possible, that


and that


if p\equiv 1\pmod{4}.

This sounds simple and elegant enough that an elementary proof should exist, but our argument is a bit involved. First, the number N_p(t) is the number of points modulo p of the curve with equation above, whose projective (smooth) model is an elliptic curve, say E_t, over \mathbf{F}_p. Then we checked using Magma that E_t and E_{16/t} are isogenous over \mathbf{F}_p, and this is well-known to imply that the two curves have the same nunmber of points modulo p. The other two cases are similar, except that for

\gamma(t)=\frac{4t-16}{t+4}\text{ or } \frac{4t+16}{t-4},

the relevant isogenies are between E_t and \tilde{E}_{\gamma(t)}, where \tilde{E}_t denotes the quadratic twist of E_t by -1. Hence the number of points are the same when -1 is a square modulo p.

In the first case, the isogeny is of degree 4, and the others are of degree 8, so the formulas which define them are rather unwieldy, at least in the equivalent Weierstrass model.

The best explanation of this has probably to do with the relation between the family of elliptic curves and the modular curve Y_0(8) (a relation whose existence follows from Beauville’s classification of stable families of elliptic curves over \mathbf{P}^1 with four singular fibers, as C. Hall pointed out), but we didn’t succeed in getting a proof of all our statements using that link. In fact, we almost expected to find the identities above already spelled out in some corner or other of the literature on modular curves and universal families of elliptic curvers thereon, but we did not find anything.

In the next post, I’ll come back to this to explain the link with our paper, which ostensibly is about estimates for sums of Fourier coefficients of modular forms multiplied with functions “of algebraic origin”. Kloosterman sums will enter the picture to make the connection (in more ways than one!), and we’ll see a rather elegant formula of Beltrami…

P.S. Here is a link to a transcript of a Magma session proving the existence of the isogenies which imply our formulas, and ending with the formula of the 4-isogeny, written in terms of the original curve.

Explicit growth for generating subsets of SL_2 over finite fields

I have one more lecture next week in my expander class, but today I finished the proof of Helfgott’s growth theorem for \mathrm{SL}_2(\mathbf{F}_p). 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 p\geq 7 is prime, and if H\subset \mathrm{SL}_2(\mathbf{F}_p) is a symmetric generating set, containing 1 for simplicity, then either the triple product
H^{(3)}=\{xyz\,\mid\, x,y,z\in H\}
is all of \mathrm{SL}_2(\mathbf{F}_p), or otherwise we have
|H^{(3)}|\geq \frac{1}{2}|H|^{1+\delta}

(Of course, the factor 1/2 can be incorporated into a slightly-smaller exponent, but that introduces an ugly-looking dependency on the size of H, which one must recover using an uglier trivial bound for |H| 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 H with a regular-semisimple conjugacy class C, of the type
|C\cap H|\leq c|H^{(k)}|^{2/3}
for some fixed k and absolute constant c. 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
(x_1,x_2,x_3)\mapsto (x_1x_2,x_1x_3)
where the three arguments x_i are all in C (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 C 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 U is the subgroup of upper-triangular unipotent matrices, then
|U\cap H|\leq 1+|H^{(5)}|^{1/3}\leq 2|H^{(5)}|^{1/3},
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 \mathrm{SL}_2(\mathbf{Z}), generated by
u=\begin{pmatrix} 1& 3\\ 0&1\end{pmatrix},\quad\quad v=\begin{pmatrix} 1&0\\3&1\end{pmatrix},
modulo primes, namely (drumroll) for p large enough (drumroll; but I won’t tell you how large today), we have (drumroll)
\lambda_1(\Gamma_p)\geq 2^{-2^{34}}.

(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…)

Action graphs

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 (V,E,e), with vertex set V, edge set E, and
e\,:\, E\rightarrow \{\text{subsets of } V\text{ with } 1 \text{ or } 2\text{ elements}\}
is the “endpoints” map.)

What I knew about the Schreier graph of a group G with respect to a subgroup H and a (symmetric) generating set S is that it should be |S|-regular, and the combinatorial Laplace operator \Delta should be given by
\Delta\varphi(x)=\varphi(x)-\frac{1}{|S|}\sum_{s\in S}{\varphi(sx)},
for any function \varphi on G/H. 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 G on a set X, one takes X as vertices, and moves along edges (set up properly) from x to s\cdot x for s in the given subset S of G. 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 X, but that doesn’t make it less natural.)

In any case, here is an illustration of the action graph for the symmetric group S_5, with generators S=\{(1\ 2), (1\ 2\ 3\ 4\ 5), (1\ 5\ 4\ 3\ 2)\}, acting on X=\{1,2,3,4,5\} by evaluation:

Action graph

Equivalently, this is the Schreier graph of G/H with respect to S, where H is the stabilizer of 1.

As it should be, this graph is 3-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 5) would remain regular after removing loops and multiple edges, but the interested reader will have no problem checking that if S is replaced by
S'=S\cup\{(1\ 2\ 3), (1\ 3\ 2)\},
removing loops and multiple edges from the corresponding action graph leads to a non-regular graph. (The vertex 1 has three neighbors then, namely \{2, 3, 5\}, while the others have only 2.)

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

Another exercise on compact groups

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 \rho of G on H=L^2(G) (with respect to Haar measure) is faithful, and gives a continuous injection
G\rightarrow U(H)
where the unitary group U(H) is given the strong operator topology (if G 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 G). What we gain from seeing G 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 U(H), any open neighborhood U of 1 contains a finite intersection of sets of the type
U_{f,\epsilon}=\{g\in G\,\mid\, \|\rho(g)f-f\|\text{\textless} \epsilon\}
where f\in H has norm 1 and \epsilon\text{\textgreater} 0. It is then easy to see, using unitarity, that the conjugacy-invariant subset
V_{f,\epsilon}=\bigcap_{x\in G}{x^{-1}U_{f,\epsilon}x}\subset U_{f,\epsilon}
is equal to
V_{f,\epsilon}=\{g\in G\,\mid\, \|\rho(g)\varphi-\varphi\|\text{\textless} \epsilon\text{ for all }\varphi\in A_f\}
A_f=\{\rho(x)f\,\mid\, x\in G\}\subset H
is the orbit of f under G. But the strong continuity of \rho implies that the orbit map g\mapsto \rho(g)f is continuous for fixed f, so that A_f is compact in H (as image of a compact set under a continuous map; here H has the usual norm topology).
It is then a quick application of a standard compactness argument and splitting of epsilons to check that V_{f,\epsilon} is a neighborhood of 1 contained in U_{f,\epsilon}, and intersecting finitely many of these, we see that U 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 G has a faithful finite-dimensional representation, this can be used instead of \rho, but the purely topological argument becomes also much simpler.)