The cost of knowledge

A few days ago, inspired by this recent post of Tim Gowers, a web page entitled “the cost of knowledge” has been set up as a location for mathematicians and other academics to declare a protest against the academic publishing practices of Reed Elsevier, in particular with regard to their exceptionally high journal prices, their policy of “bundling” journals together so that libraries are forced to purchase subscriptions to large numbers of low-quality journals in order to gain access to a handful of high-quality journals, and their opposition to the open access movement (as manifested, for instance, in their lobbying in support of legislation such as the Stop Online Piracy Act (SOPA) and the Research Works Act (RWA)).   [These practices have been documented in a number of places; this wiki page, which was set up in response to Tim's post, collects several relevant links for this purpose.  Some of the other commercial publishers have  exhibited similar behaviour, though usually not to the extent that Elsevier has, which is why this particular publisher is the focus of this protest.]  At the protest site, one can publicly declare a refusal to either publish at an Elsevier journal, referee for an Elsevier journal, or join the board of an Elsevier journal.

(In the past, the editorial boards of several Elsevier journals have resigned over the pricing policies of the journal, most famously the board of Topology in 2006, but also the Journal of Algorithms in 2003, and a number of journals in other sciences as well.  Several libraries, such as those of Harvard and Cornell, have also managed to negotiate an unbundling of Elsevier journals, but most libraries are still unable to subscribe to such journals individually.)

For a more thorough discussion as to why such a protest is warranted, please see Tim’s post on the matter (and the 100+ comments to that post).   Many of the issues regarding Elsevier were already known to some extent to many mathematicians (particularly those who have served on departmental library committees), several of whom had already privately made the decision to boycott Elsevier; but nevertheless it is important to bring these issues out into the open, to make them commonly known as opposed to merely mutually known.  (Amusingly, this distinction is also of crucial importance in my favorite logic puzzle, but that’s another story.)   One can also see Elsevier’s side of the story in this response to Tim’s post by David Clark (the Senior Vice President for Physical Sciences at Elsevier).

For my own part, though I have sent about 9% of my papers in the past to Elsevier journals (with one or two still in press), I have now elected not to submit any further papers to these journals, nor to serve on their editorial boards, though I will continue refereeing some papers from these journals.  As of this time of writing, over five hundred mathematicians and other academics have also signed on to the protest in the four days that the site has been active.

Admittedly, I am fortunate enough to be at a stage of career in which I am not pressured to publish in a very specific set of journals, and as such, I am not making a recommendation as to what anyone else should do or not do regarding this protest.  However, I do feel that it is worth spreading awareness, at least, of the fact that such protests exist (and some additional petitions on related issues can be found at the previously mentioned wiki page).

Random matrices: Sharp concentration of eigenvalues

Van Vu and I have just uploaded to the arXiv our paper Random matrices: Sharp concentration of eigenvalues, submitted to the Electronic Journal of Probability. As with many of our previous papers, this paper is concerned with the distribution of the eigenvalues of a random Wigner matrix (such as a matrix drawn from the Gaussian Unitary Ensemble (GUE) or Gaussian Orthogonal Ensemble (GOE)). To simplify the discussion we shall mostly restrict attention to the bulk of the spectrum, i.e. to eigenvalues with for some fixed , although analogues of most of the results below have also been obtained at the edge of the spectrum.

If we normalise the entries of the matrix to have mean zero and variance , then in the asymptotic limit , we have the Wigner semicircle law, which asserts that the eigenvalues are asymptotically distributed according to the semicircular distribution , where

An essentially equivalent way of saying this is that for large , we expect the eigenvalue of to stay close to the classical location , defined by the formula

In particular, from the Wigner semicircle law it can be shown that asymptotically almost surely, one has

for all .

In the modern study of the spectrum of Wigner matrices (and in particular as a key tool in establishing universality results), it has become of interest to improve the error term in (1) as much as possible. A typical early result in this direction was by Bai, who used the Stieltjes transform method to obtain polynomial convergence rates of the shape for some absolute constant ; see also the subsequent papers of Alon-Krivelevich-Vu and of of Meckes, who were able to obtain such convergence rates (with exponentially high probability) by using concentration of measure tools, such as Talagrand’s inequality. On the other hand, in the case of the GUE ensemble it is known (by this paper of Gustavsson) that has variance comparable to in the bulk, so that the optimal error term in (1) should be about . (One may think that if one wanted bounds on (1) that were uniform in , one would need to enlarge the error term further, but this does not appear to be the case, due to strong correlations between the ; note for instance this recent result of Ben Arous and Bourgarde that the largest gap between eigenvalues in the bulk is typically of order .)

A significant advance in this direction was achieved by Erdos, Schlein, and Yau in a series of http://www.ams.org/mathscinet-getitem?mr=2587574{papers} where they used a combination of Stieltjes transform and concentration of measure methods to obtain local semicircle laws which showed, among other things, that one had asymptotics of the form

with exponentially high probability for intervals in the bulk that were as short as for some , where is the number of eigenvalues. These asymptotics are consistent with a good error term in (1), and are already sufficient for many applications, but do not quite imply a strong concentration result for individual eigenvalues (basically because they do not preclude long-range or “secular” shifts in the spectrum that involve large blocks of eigenvalues at mesoscopic scales). Nevertheless, this was rectified in a subsequent paper of Erdos, Yau, and Yin, which roughly speaking obtained a bound of the form

in the bulk with exponentially high probability, for Wigner matrices obeying some exponential decay conditions on the entries. This was achieved by a rather delicate high moment calculation, in which the contribution of the diagonal entries of the resolvent (whose average forms the Stieltjes transform) was shown to mostly cancel each other out.

As the GUE computations show, this concentration result is sharp up to the quasilogarithmic factor . The main result of this paper is to improve the concentration result to one more in line with the GUE case, namely

with exponentially high probability (see the paper for a more precise statement of results). The one catch is that an additional hypothesis is required, namely that the entries of the Wigner matrix have vanishing third moment. We also obtain similar results for the edge of the spectrum (but with a different scaling).

Our arguments are rather different from those of Erdos, Yau, and Yin, and thus provide an alternate approach to establishing eigenvalue concentration. The main tool is the Lindeberg exchange strategy, which is also used to prove the Four Moment Theorem (although we do not directly invoke the Four Moment Theorem in our analysis). The main novelty is that this exchange strategy is now used to establish large deviation estimates (i.e. exponentially small tail probabilities) rather than universality of the limiting distribution. Roughly speaking, the basic point is as follows. The Lindeberg exchange strategy seeks to compare a function of many independent random variables with the same function of a different set of random variables (which match moments with the original set of variables to some order, such as to second or fourth order) by exchanging the random variables one at a time. Typically, one tries to upper bound expressions such as

for various smooth test functions , by performing a Taylor expansion in the variable being swapped and taking advantage of the matching moment hypotheses. In previous implementations of this strategy, was a bounded test function, which allowed one to get control of the bulk of the distribution of , and in particular in controlling probabilities such as

for various thresholds and , but did not give good control on the tail as the error terms tended to be polynomially decaying in rather than exponentially decaying. However, it turns out that one can modify the exchange strategy to deal with moments such as

for various moderately large (e.g. of size comparable to ), obtaining results such as

after performing all the relevant exchanges. As such, one can then use large deviation estimates on to deduce large deviation estimates on .

In this paper we also take advantage of a simplification, first noted by Erdos, Yau, and Yin, that Four Moment Theorems become somewhat easier to prove if one works with resolvents (and the closely related Stieltjes transform ) rather than with individual eigenvalues, as the Taylor expansion of resolvents are very simple (essentially being a Neumann series). The relationship between the Stieltjes transform and the location of individual eigenvalues can be seen by taking advantage of the identity

for any energy level , which can be verified from elementary calculus. (In practice, we would truncate near zero and near infinity to avoid some divergences, but this is a minor technicality.) As such, a concentration result for the Stieltjes transform can be used to establish an analogous concentration result for the eigenvalue counting functions , which in turn can be used to deduce concentration results for individual eigenvalues by some basic combinatorial manipulations.

254B, Notes 4: The Bourgain-Gamburd expansion machine

We have now seen two ways to construct expander Cayley graphs . The first, discussed in Notes 2, is to use Cayley graphs that are projections of an infinite Cayley graph on a group with Kazhdan’s property (T). The second, discussed in Notes 3, is to combine a quasirandomness property of the group with a flattening hypothesis for the random walk.

We now pursue the second approach more thoroughly. The main difficulty here is to figure out how to ensure flattening of the random walk, as it is then an easy matter to use quasirandomness to show that the random walk becomes mixing soon after it becomes flat. In the case of Selberg’s theorem, we achieved this through an explicit formula for the heat kernel on the hyperbolic plane (which is a proxy for the random walk). However, in most situations such an explicit formula is not available, and one must develop some other tool for forcing flattening, and specifically an estimate of the form

for some , where is the uniform probability measure on the generating set .

In 2006, Bourgain and Gamburd introduced a general method for achieving this goal. The intuition here is that the main obstruction that prevents a random walk from spreading out to become flat over the entire group is if the random walk gets trapped in some proper subgroup of (or perhaps in some coset of such a subgroup), so that remains large for some moderately large . Note that

since , , and is symmetric. By iterating this observation, we seethat if is too large (e.g. of size for some comparable to ), then it is not possible for the random walk to converge to the uniform distribution in time , and so expansion does not occur.

A potentially more general obstruction of this type would be if the random walk gets trapped in (a coset of) an approximate group . Recall that a -approximate group is a subset of a group which is symmetric, contains the identity, and is such that can be covered by at most left-translates (or equivalently, right-translates) of . Such approximate groups were studied extensively in last quarter’s course. A similar argument to the one given previously shows (roughly speaking) that expansion cannot occur if is too large for some coset of an approximate group.

It turns out that this latter observation has a converse: if a measure does not concentrate in cosets of approximate groups, then some flattening occurs. More precisely, one has the following combinatorial lemma:

Lemma 1 (Weighted Balog-Szemerédi-Gowers lemma) Let be a group, let be a finitely supported probability measure on which is symmetric (thus for all ), and let . Then one of the following statements hold:

• (i) (Flattening) One has .
• (ii) (Concentration in an approximate group) There exists an -approximate group in with and an element such that .

This lemma is a variant of the more well-known Balog-Szemerédi-Gowers lemma in additive combinatorics due to Gowers (which roughly speaking corresponds to the case when is the uniform distribution on some set ), which in turn is a polynomially quantitative version of an earlier lemma of Balog and Szemerédi. We will prove it below the fold.

The lemma is particularly useful when the group in question enjoys a product theorem, which roughly speaking says that the only medium-sized approximate subgroups of are trapped inside genuine proper subgroups of (or, contrapositively, medium-sized sets that generate the entire group cannot be approximate groups). The fact that some finite groups (and specifically, the bounded rank finite simple groups of Lie type) enjoy product theorems is a non-trivial fact, and will be discussed in later notes. For now, we simply observe that the presence of the product theorem, together with quasirandomness and a non-concentration hypothesis, can be used to demonstrate expansion:

Theorem 2 (Bourgain-Gamburd expansion machine) Suppose that is a finite group, that is a symmetric set of generators, and that there are constants with the following properties.

1. (Quasirandomness). The smallest dimension of a nontrivial representation of is at least ;
2. (Product theorem). For all there is some such that the following is true. If is a -approximate subgroup with then generates a proper subgroup of ;
3. (Non-concentration estimate). There is some even number such that

   

   where the supremum is over all proper subgroups .

Then is a two-sided -expander for some depending only on , and the function (and this constant is in principle computable in terms of these constants).

This criterion for expansion is implicitly contained in this paper of Bourgain and Gamburd, who used it to establish the expansion of various Cayley graphs in for prime . This criterion has since been applied (or modified) to obtain expansion results in many other groups, as will be discussed in later notes.

Continued fractions, Bohr sets, and the Littlewood conjecture

Let be an element of the unit circle, let , and let . We define the (rank one) Bohr set to be the set

where is the distance to the origin in the unit circle (or equivalently, the distance to the nearest integer, after lifting up to ). These sets play an important role in additive combinatorics and in additive number theory. For instance, they arise naturally when applying the circle method, because Bohr sets describe the oscillation of exponential phases such as .

Observe that Bohr sets enjoy the doubling property

thus doubling the Bohr set doubles both the length parameter and the radius parameter . As such, these Bohr sets resemble two-dimensional balls (or boxes). Indeed, one can view as the preimage of the two-dimensional box under the homomorphism .

Another class of finite set with two-dimensional behaviour is the class of (rank two) generalised arithmetic progressions

with and Indeed, we have

and so we see, as with the Bohr set, that doubling the generalised arithmetic progressions doubles the two defining parameters of that progression.

More generally, there is an analogy between rank Bohr sets

and the rank generalised arithmetic progressions

One of the aims of additive combinatorics is to formalise analogies such as the one given above. By using some arguments from the geometry of numbers, for instance, one can show that for any rank Bohr set , there is a rank generalised arithmetic progression for which one has the containments

for some explicit depending only on (in fact one can take ); this is (a slight modification of) Lemma 4.22 of my book with Van Vu.

In the special case when , one can make a significantly more detailed description of the link between rank one Bohr sets and rank two generalised arithmetic progressions, by using the classical theory of continued fractions, which among other things gives a fairly precise formula for the generators and lengths of the generalised arithmetic progression associated to a rank one Bohr set . While this connection is already implicit in the continued fraction literature (for instance, in the classic text of Hardy and Wright), I thought it would be a good exercise to work it out explicitly and write it up, which I will do below the fold.

It is unfortunate that the theory of continued fractions is restricted to the rank one setting (it relies very heavily on the total ordering of one-dimensional sets such as or ). A higher rank version of the theory could potentially help with questions such as the Littlewood conjecture, which remains open despite a substantial amount of effort and partial progress on the problem. At the end of this post I discuss how one can use the rank one theory to rephrase the Littlewood conjecture as a conjecture about a doubly indexed family of rank four progressions, which can be used to heuristically justify why this conjecture should be true, but does not otherwise seem to shed much light on the problem.

Montgomery’s uncertainty principle

One of the most fundamental principles in Fourier analysis is the uncertainty principle. It does not have a single canonical formulation, but one typical informal description of the principle is that if a function is restricted to a narrow region of physical space, then its Fourier transform must be necessarily “smeared out” over a broad region of frequency space. Some versions of the uncertainty principle are discussed in this previous blog post.

In this post I would like to highlight a useful instance of the uncertainty principle, due to Hugh Montgomery, which is useful in analytic number theory contexts. Specifically, suppose we are given a complex-valued function on the integers. To avoid irrelevant issues at spatial infinity, we will assume that the support of this function is finite (in practice, we will only work with functions that are supported in an interval for some natural numbers ). Then we can define the Fourier transform by the formula

where . (In some literature, the sign in the exponential phase is reversed, but this will make no substantial difference to the arguments below.)

The classical uncertainty principle, in this context, asserts that if is localised in an interval of length , then must be “smeared out” at a scale of at least (and essentially constant at scales less than ). For instance, if is supported in , then we have the Plancherel identity

while from the Cauchy-Schwarz inequality we have

for each frequency , and in particular that

for any arc in the unit circle (with denoting the length of ). In particular, an interval of length significantly less than can only capture a fraction of the energy of the Fourier transform of , which is consistent with the above informal statement of the uncertainty principle.

Another manifestation of the classical uncertainty principle is the large sieve inequality. A particularly nice formulation of this inequality is due independently to Montgomery and Vaughan and Selberg: if is supported in , and are frequencies in that are -separated for some , thus for all (where denotes the distance of to the origin in ), then

The reader is encouraged to see how this inequality is consistent with the Plancherel identity (1) and the intuition that is essentially constant at scales less than . The factor can in fact be amplified a little bit to , which is essentially optimal, by using a neat dilation trick of Paul Cohen, in which one dilates to (and replaces each frequency by their roots), and then sending (cf. the tensor product trick); see this survey of Montgomery for details. But we will not need this refinement here.

In the above instances of the uncertainty principle, the concept of narrow support in physical space was formalised in the Archimedean sense, using the standard Archimedean metric on the integers (in particular, the parameter is essentially the Archimedean diameter of the support of ). However, in number theory, the Archimedean metric is not the only metric of importance on the integers; the -adic metrics play an equally important role; indeed, it is common to unify the Archimedean and -adic perspectives together into a unified adelic perspective. In the -adic world, the metric balls are no longer intervals, but are instead residue classes modulo some power of . Intersecting these balls from different -adic metrics together, we obtain residue classes with respect to various moduli (which may be either prime or composite). As such, another natural manifestation of the concept of “narrow support in physical space” is “vanishes on many residue classes modulo “. This notion of narrowness is particularly common in sieve theory, when one deals with functions supported on thin sets such as the primes, which naturally tend to avoid many residue classes (particularly if one throws away the first few primes).

In this context, the uncertainty principle is this: the more residue classes modulo that avoids, the more the Fourier transform must spread out along multiples of . To illustrate a very simple example of this principle, let us take , and suppose that is supported only on odd numbers (thus it completely avoids the residue class ). We write out the formulae for and :

If is supported on the odd numbers, then is always equal to on the support of , and so we have . Thus, whenever has a significant presence at a frequency , it also must have an equally significant presence at the frequency ; there is a spreading out across multiples of . Note that one has a similar effect if was supported instead on the even integers instead of the odd integers.

A little more generally, suppose now that avoids a single residue class modulo a prime ; for sake of argument let us say that it avoids the zero residue class , although the situation for the other residue classes is similar. For any frequency and any , one has

From basic Fourier analysis, we know that the phases sum to zero as ranges from to whenever is not a multiple of . We thus have

In particular, if is large, then one of the other has to be somewhat large as well; using the Cauchy-Schwarz inequality, we can quantify this assertion in an sense via the inequality

Let us continue this analysis a bit further. Now suppose that avoids residue classes modulo a prime , for some . (We exclude the case as it is clearly degenerates by forcing to be identically zero.) Let be the function that equals on these residue classes and zero away from these residue classes, then

Using the periodic Fourier transform, we can write

for some coefficients , thus

Some Fourier-analytic computations reveal that

and

and so after some routine algebra and the Cauchy-Schwarz inequality, we obtain a generalisation of (3):

Thus we see that the more residue classes mod we exclude, the more Fourier energy has to disperse along multiples of . It is also instructive to consider the extreme case , in which is supported on just a single residue class ; in this case, one clearly has , and so spreads its energy completely evenly along multiples of .

In 1968, Montgomery observed the following useful generalisation of the above calculation to arbitrary modulus:

Proposition 1 (Montgomery’s uncertainty principle) Let be a finitely supported function which, for each prime , avoids residue classes modulo for some . Then for each natural number , one has

where is the quantity

where is the Möbius function.

We give a proof of this proposition below the fold.

Following the “adelic” philosophy, it is natural to combine this uncertainty principle with the large sieve inequality to take simultaneous advantage of localisation both in the Archimedean sense and in the -adic senses. This leads to the following corollary:

Corollary 2 (Arithmetic large sieve inequality) Let be a function supported on an interval which, for each prime , avoids residue classes modulo for some . Let , and let be a finite set of natural numbers. Suppose that the frequencies with , , and are -separated. Then one has

where was defined in (4).

Indeed, from the large sieve inequality one has

while from Proposition 1 one has

whence the claim.

There is a great deal of flexibility in the above inequality, due to the ability to select the set , the frequencies , the omitted classes , and the separation parameter . Here is a typical application concerning the original motivation for the large sieve inequality, namely in bounding the size of sets which avoid many residue classes:

Corollary 3 (Large sieve) Let be a set of integers contained in which avoids residue classes modulo for each prime , and let . Then

where

Proof: We apply Corollary 2 with , , , , and . The key point is that the Farey sequence of fractions with and is -separated, since

whenever are distinct fractions in this sequence.

If, for instance, is the set of all primes in larger than , then one can set for all , which makes , where is the Euler totient function. It is a classical estimate that

Using this fact and optimising in , we obtain (a special case of) the Brun-Titchmarsh inequality

where is the prime counting function; a variant of the same argument gives the more general Brun-Titchmarsh inequality

for any primitive residue class , where is the number of primes less than or equal to that are congruent to . By performing a more careful optimisation using a slightly sharper version of the large sieve inequality (2) that exploits the irregular spacing of the Farey sequence, Montgomery and Vaughan were able to delete the error term in the Brun-Titchmarsh inequality, thus establishing the very nice inequality

for any natural numbers with . This is a particularly useful inequality in non-asymptotic analytic number theory (when one wishes to study number theory at explicit orders of magnitude, rather than the number theory of sufficiently large numbers), due to the absence of asymptotic notation.

I recently realised that Corollary 2 also establishes a stronger version of the “restriction theorem for the Selberg sieve” that Ben Green and I proved some years ago (indeed, one can view Corollary 2 as a “restriction theorem for the large sieve”). I’m placing the details below the fold.

A variant of Kemperman’s theorem

In 1964, Kemperman established the following result:

Theorem 1 Let be a compact connected group, with a Haar probability measure . Let be compact subsets of . Then

Remark 1 The estimate is sharp, as can be seen by considering the case when is a unit circle, and are arcs; similarly if is any compact connected group that projects onto the circle. The connectedness hypothesis is essential, as can be seen by considering what happens if and are a non-trivial open subgroup of . For locally compact connected groups which are unimodular but not compact, there is an analogous statement, but with now a Haar measure instead of a Haar probability measure, and the right-hand side replaced simply by . The case when is a torus is due to Macbeath, and the case when is a circle is due to Raikov. The theorem is closely related to the Cauchy-Davenport inequality; indeed, it is not difficult to use that inequality to establish the circle case, and the circle case can be used to deduce the torus case by considering increasingly dense circle subgroups of the torus (alternatively, one can also use Kneser’s theorem).

By inner regularity, the hypothesis that are compact can be replaced with Borel measurability, so long as one then adds the additional hypothesis that is also Borel measurable.

A short proof of Kemperman’s theorem was given by Ruzsa. In this post I wanted to record how this argument can be used to establish the following more “robust” version of Kemperman’s theorem, which not only lower bounds , but gives many elements of some multiplicity:

Theorem 2 Let be a compact connected group, with a Haar probability measure . Let be compact subsets of . Then for any , one has

Indeed, Theorem 1 can be deduced from Theorem 2 by dividing (1) by and then taking limits as . The bound in (1) is sharp, as can again be seen by considering the case when are arcs in a circle. The analogous claim for cyclic groups for prime order was established by Pollard, and for general abelian groups by Green and Ruzsa.

Let us now prove Theorem 2. It uses a submodularity argument related to one discussed in this previous post. We fix and with , and define the quantity

for any compact set . Our task is to establish that whenever .

We first verify the extreme cases. If , then , and so in this case. At the other extreme, if , then from the inclusion-exclusion principle we see that , and so again in this case (since ).

To handle the intermediate regime when lies between and , we rely on the submodularity inequality

for arbitrary compact . This inequality comes from the obvious pointwise identity

whence

and thus (noting that the quantities on the left are closer to each other than the quantities on the right)

at which point (2) follows by integrating over and then using the inclusion-exclusion principle.

Now introduce the function

for . From the preceding discussion vanishes at the endpoints ; our task is to show that is non-negative in the interior region . Suppose for contradiction that this was not the case. It is easy to see that is continuous (indeed, it is even Lipschitz continuous), so there must be at which is a local minimum and not locally constant. In particular, . But for any with , we have the translation-invariance

for any , and hence by (2)

Note that depends continuously on , equals when is the identity, and has an average value of . As is connected, we thus see from the intermediate value theorem that for any , we can find such that , and thus by inclusion-exclusion . By definition of , we thus have

Taking infima in (and noting that the hypotheses on are independent of ) we conclude that

for all . As is a local minimum and is arbitrarily small, this implies that is locally constant, a contradiction. This establishes Theorem 2.

We observe the following corollary:

Corollary 3 Let be a compact connected group, with a Haar probability measure . Let be compact subsets of , and let . Then one has the pointwise estimate

if , and

if .

Once again, the bounds are completely sharp, as can be seen by computing when are arcs of a circle. For quasirandom , one can do much better than these bounds, as discussed in this recent blog post; thus, the abelian case is morally the worst case here, although it seems difficult to convert this intuition into a rigorous reduction.

Proof: By cyclic permutation we may take . For any

we can bound

where we used Theorem 2 to obtain the third line. Optimising in , we obtain the claim.

A nilpotent Freiman dimension lemma

Emmanuel Breuillard, Ben Green and I have just uploaded to the arXiv the short paper “A nilpotent Freiman dimension lemma“, submitted to the special volume of the European Journal of Combinatorics in honour of Yahya Ould Hamidoune.  This paper is a nonabelian (or more precisely, nilpotent) variant of the following additive combinatorics lemma of Freiman:

Freiman’s lemma.  Let A be a finite subset of a Euclidean space with .  Then A is contained in an affine subspace of dimension at most .

This can be viewed as a “cheap” version of the more well known theorem of Freiman that places sets of small doubling in a torsion-free abelian group inside a generalised arithmetic progression.  The advantage here is that the bound on the dimension is extremely explicit.

Our main result is

Theorem.  Let A be a finite subset of a simply-connected nilpotent Lie group G which is a K-approximate group (i.e. A is symmetric, contains the identity, and can be covered by up to K left translates of A.  Then A can be covered by at most left-translates of a closed connected Lie subgroup of dimension at most .

We remark that our previous paper established a similar result, in which the dimension bound was improved to , but at the cost of worsening the covering number to , and with a much more complicated proof  (91 pages instead of 8). Furthermore, the bound on is ineffective, due to the use of ultraproducts in the argument (though it is likely that some extremely lousy explicit bound could eventually be squeezed out of the argument by finitising everything).  Note that the step of the ambient nilpotent group G does not influence the final bounds in the theorem, although we do of course need this step to be finite.  A simple quotienting argument allows one to deduce a corollary of the above theorem in which the ambient group is assumed to be residually torsion-free nilpotent instead of being a simply connected nilpotent Lie group, but we omit the statement of this corollary here.

To motivate the proof of this theorem, let us first show a simple case of an argument of Gleason, which is very much in the spirit of Freiman’s lemma:

Gleason Lemma (special case).  Let be a finite symmetric subset of a Euclidean space, and let be a sequence of subspaces in this space, such that the sets are strictly increasing in i for .  Then , where .

Proof.    By hypothesis, for each , the projection of to is non-trivial, finite, and symmetric.   In particular, since the vector space is torsion-free, is strictly larger than .  Equivalently, one can find  in that does not lie in ; in particular, and is disjoint from .  As a consequence, the are disjoint and lie in 5A, whence the claim.

Note that by combining the contrapositive of this lemma with a greedy algorithm, one can show that any K-approximate group in a Euclidean space is contained in a subspace of dimension at most , which is a weak version of Freiman’s lemma.

To extend the argument to the nilpotent setting we use the following idea.  Observe that any non-trivial genuine subgroup H of a nilpotent group G will contain at least one non-trivial central element; indeed, by intersecting H with the lower central series of G, and considering the last intersection which is non-trivial, one obtains the claim.  It turns out that one can adapt this argument to approximate groups, so that any sufficiently large K-approximate subgroup A of G will contain a non-trivial element that centralises a large fraction of A.  Passing to this large fraction and quotienting out the central element, we obtain a new approximate group.    If, after a bounded number of steps, this procedure gives an approximate group of bounded size, we are basically done.  If, however, the process continues, then by using some Lie group theory, one can find a long sequence of connected Lie subgroups of G, such that the sets are strictly increasing in i.   Using some Lie group theory and the hypotheses on G, one can deduce that the group generated by is much larger than , in the sense that the latter group has infinite index in the former.   It then turns out that the Gleason argument mentioned above can be adapted to this setting.

The spectral theorem and its converses for unbounded symmetric operators

Let be a self-adjoint operator on a finite-dimensional Hilbert space . The behaviour of this operator can be completely described by the spectral theorem for finite-dimensional self-adjoint operators (i.e. Hermitian matrices, when viewed in coordinates), which provides a sequence of eigenvalues and an orthonormal basis of eigenfunctions such that for all . In particular, given any function on the spectrum of , one can then define the linear operator by the formula

which then gives a functional calculus, in the sense that the map is a -algebra isometric homomorphism from the algebra of bounded continuous functions from to , to the algebra of bounded linear operators on . Thus, for instance, one can define heat operators for , Schrödinger operators for , resolvents for , and (if is positive) wave operators for . These will be bounded operators (and, in the case of the Schrödinger and wave operators, unitary operators, and in the case of the heat operators with positive, they will be contractions). Among other things, this functional calculus can then be used to solve differential equations such as the heat equation

the Schrödinger equation

the wave equation

or the Helmholtz equation

The functional calculus can also be associated to a spectral measure. Indeed, for any vectors , there is a complex measure on with the property that

indeed, one can set to be the discrete measure on defined by the formula

One can also view this complex measure as a coefficient

of a projection-valued measure on , defined by setting

Finally, one can view as unitarily equivalent to a multiplication operator on , where is the real-valued function , and the intertwining map is given by

so that .

It is an important fact in analysis that many of these above assertions extend to operators on an infinite-dimensional Hilbert space , so long as one one is careful about what “self-adjoint operator” means; these facts are collectively referred to as the spectral theorem. For instance, it turns out that most of the above claims have analogues for bounded self-adjoint operators . However, in the theory of partial differential equations, one often needs to apply the spectral theorem to unbounded, densely defined linear operators , which (initially, at least), are only defined on a dense subspace of the Hilbert space . A very typical situation arises when is the square-integrable functions on some domain or manifold (which may have a boundary or be otherwise “incomplete”), and are the smooth compactly supported functions on , and is some linear differential operator. It is then of interest to obtain the spectral theorem for such operators, so that one build operators such as or to solve equations such as (1), (2), (3), (4).

In order to do this, some necessary conditions on the densely defined operator must be imposed. The most obvious is that of symmetry, which asserts that

for all . In some applications, one also wants to impose positiveness, which asserts that

for all . These hypotheses are sufficient in the case when is bounded, and in particular when is finite dimensional. However, as it turns out, for unbounded operators these conditions are not, by themselves, enough to obtain a good spectral theory. For instance, one consequence of the spectral theorem should be that the resolvents are well-defined for any strictly complex , which by duality implies that the image of should be dense in . However, this can fail if one just assumes symmetry, or symmetry and positive definiteness. A well-known example occurs when is the Hilbert space , is the space of test functions, and is the one-dimensional Laplacian . Then is symmetric and positive, but the operator does not have dense image for any complex , since

for all test functions , as can be seen from a routine integration by parts. As such, the resolvent map is not everywhere uniquely defined. There is also a lack of uniqueness for the wave, heat, and Schrödinger equations for this operator (note that there are no spatial boundary conditions specified in these equations).

Another example occurs when , , is the momentum operator . Then the resolvent can be uniquely defined for in the upper half-plane, but not in the lower half-plane, due to the obstruction

for all test functions (note that the function lies in when is in the lower half-plane). For related reasons, the translation operators have a problem with either uniqueness or existence (depending on whether is positive or negative), due to the unspecified boundary behaviour at the origin.

The key property that lets one avoid this bad behaviour is that of essential self-adjointness. Once is essentially self-adjoint, then spectral theorem becomes applicable again, leading to all the expected behaviour (e.g. existence and uniqueness for the various PDE given above).

Unfortunately, the concept of essential self-adjointness is defined rather abstractly, and is difficult to verify directly; unlike the symmetry condition (5) or the positive condition (6), it is not a “local” condition that can be easily verified just by testing on various inputs, but is instead a more “global” condition. In practice, to verify this property, one needs to invoke one of a number of a partial converses to the spectral theorem, which roughly speaking asserts that if at least one of the expected consequences of the spectral theorem is true for some symmetric densely defined operator , then is self-adjoint. Examples of “expected consequences” include:

• Existence of resolvents (or equivalently, dense image for );
• Existence of a contractive heat propagator semigroup (in the positive case);
• Existence of a unitary Schrödinger propagator group ;
• Existence of a unitary wave propagator group (in the positive case);
• Existence of a “reasonable” functional calculus.
• Unitary equivalence with a multiplication operator.

Thus, to actually verify essential self-adjointness of a differential operator, one typically has to first solve a PDE (such as the wave, Schrödinger, heat, or Helmholtz equation) by some non-spectral method (e.g. by a contraction mapping argument, or a perturbation argument based on an operator already known to be essentially self-adjoint). Once one can solve one of the PDEs, then one can apply one of the known converse spectral theorems to obtain essential self-adjointness, and then by the forward spectral theorem one can then solve all the other PDEs as well. But there is no getting out of that first step, which requires some input (typically of an ODE, PDE, or geometric nature) that is external to what abstract spectral theory can provide. For instance, if one wants to establish essential self-adjointness of the Laplace-Beltrami operator on a smooth Riemannian manifold (using as the domain space), it turns out (under reasonable regularity hypotheses) that essential self-adjointness is equivalent to geodesic completeness of the manifold, which is a global ODE condition rather than a local one: one needs geodesics to continue indefinitely in order to be able to (unitarily) solve PDEs such as the wave equation, which in turn leads to essential self-adjointness. (Note that the domains and in the previous examples were not geodesically complete.) For this reason, essential self-adjointness of a differential operator is sometimes referred to as quantum completeness (with the completeness of the associated Hamilton-Jacobi flow then being the analogous classical completeness).

In these notes, I wanted to record (mostly for my own benefit) the forward and converse spectral theorems, and to verify essential self-adjointness of the Laplace-Beltrami operator on geodesically complete manifolds. This is extremely standard analysis (covered, for instance, in the texts of Reed and Simon), but I wanted to write it down myself to make sure that I really understood this foundational material properly.

254B, Notes 3: Quasirandom groups, expansion, and Selberg’s 3/16 theorem

In the previous set of notes we saw how a representation-theoretic property of groups, namely Kazhdan’s property (T), could be used to demonstrate expansion in Cayley graphs. In this set of notes we discuss a different representation-theoretic property of groups, namely quasirandomness, which is also useful for demonstrating expansion in Cayley graphs, though in a somewhat different way to property (T). For instance, whereas property (T), being qualitative in nature, is only interesting for infinite groups such as or , and only creates Cayley graphs after passing to a finite quotient, quasirandomness is a quantitative property which is directly applicable to finite groups, and is able to deduce expansion in a Cayley graph, provided that random walks in that graph are known to become sufficiently “flat” in a certain sense.

The definition of quasirandomness is easy enough to state:

Definition 1 (Quasirandom groups) Let be a finite group, and let . We say that is -quasirandom if all non-trivial unitary representations of have dimension at least . (Recall a representation is trivial if is the identity for all .)

Exercise 1 Let be a finite group, and let . A unitary representation is said to be irreducible if has no -invariant subspaces other than and . Show that is -quasirandom if and only if every non-trivial irreducible representation of has dimension at least .

Remark 1 The terminology “quasirandom group” was introduced explicitly (though with slightly different notational conventions) by Gowers in 2008 in his detailed study of the concept; the name arises because dense Cayley graphs in quasirandom groups are quasirandom graphs in the sense of Chung, Graham, and Wilson, as we shall see below. This property had already been used implicitly to construct expander graphs by Sarnak and Xue in 1991, and more recently by Gamburd in 2002 and by Bourgain and Gamburd in 2008. One can of course define quasirandomness for more general locally compact groups than the finite ones, but we will only need this concept in the finite case. (A paper of Kunze and Stein from 1960, for instance, exploits the quasirandomness properties of the locally compact group to obtain mixing estimates in that group.)

Quasirandomness behaves fairly well with respect to quotients and short exact sequences:

Exercise 2 Let be a short exact sequence of finite groups .

• (i) If is -quasirandom, show that is -quasirandom also. (Equivalently: any quotient of a -quasirandom finite group is again a -quasirandom finite group.)
• (ii) Conversely, if and are both -quasirandom, show that is -quasirandom also. (In particular, the direct or semidirect product of two -quasirandom finite groups is again a -quasirandom finite group.)

Informally, we will call quasirandom if it is -quasirandom for some “large” , though the precise meaning of “large” will depend on context. For applications to expansion in Cayley graphs, “large” will mean “ for some constant independent of the size of “, but other regimes of are certainly of interest.

The way we have set things up, the trivial group is infinitely quasirandom (i.e. it is -quasirandom for every ). This is however a degenerate case and will not be discussed further here. In the non-trivial case, a finite group can only be quasirandom if it is large and has no large subgroups:

Exercise 3 Let , and let be a finite -quasirandom group.

• (i) Show that if is non-trivial, then . (Hint: use the mean zero component of the regular representation .) In particular, non-trivial finite groups cannot be infinitely quasirandom.
• (ii) Show that any proper subgroup of has index . (Hint: use the mean zero component of the quasiregular representation.)

The following exercise shows that quasirandom groups have to be quite non-abelian, and in particular perfect:

Exercise 4 (Quasirandomness, abelianness, and perfection) Let be a finite group.

• (i) If is abelian and non-trivial, show that is not -quasirandom. (Hint: use Fourier analysis or the classification of finite abelian groups.)
• (ii) Show that is -quasirandom if and only if it is not perfect, i.e. the commutator group is a proper subgroup of . (Equivalently, is -quasirandom if and only if it has no non-trivial abelian quotients.)

Later on we shall see that there is a converse to the above two exercises; any non-trivial perfect finite group with no large subgroups will be quasirandom.

Exercise 5 Let be a finite -quasirandom group. Show that for any subgroup of , is -quasirandom, where is the index of in . (Hint: use induced representations.)

Now we give an example of a more quasirandom group.

Lemma 2 (Frobenius lemma) If is a field of some prime order , then is -quasirandom.

This should be compared with the cardinality of the special linear group, which is easily computed to be .

Proof: We may of course take to be odd. Suppose for contradiction that we have be a non-trivial representation on a unitary group of some dimension with . Set to be the group element

and suppose first that is non-trivial. Since , we have ; thus all the eigenvalues of are roots of unity. On the other hand, by conjugating by diagonal matrices in , we see that is conjugate to (and hence conjugate to ) whenever is a quadratic residue mod . As such, the eigenvalues of must be permuted by the operation for any quadratic residue mod . Since has at least one non-trivial eigenvalue, and there are distinct quadratic residues, we conclude that has at least distinct eigenvalues. But is a matrix with , a contradiction. Thus lies in the kernel of . By conjugation, we then see that this kernel contains all unipotent matrices. But these matrices generate (see exercise below), and so is trivial, a contradiction.

Exercise 6 Show that for any prime , the unipotent matrices

for any generate as a group.

Exercise 7 Let be a finite group, and let . If is generated by a collection of -quasirandom subgroups, show that is itself -quasirandom.

Exercise 8 Show that is -quasirandom for any and any prime . (This is not sharp; the optimal bound here is , which follows from the results of Landazuri and Seitz.)

As a corollary of the above results and Exercise 2, we see that the projective special linear group is also -quasirandom.

Remark 2 One can ask whether the bound in Lemma 2 is sharp, assuming of course that is odd. Noting that acts linearly on the plane , we see that it also acts projectively on the projective line , which has elements. Thus acts via the quasiregular representation on the -dimensional space , and also on the -dimensional subspace ; this latter representation (known as the Steinberg representation) is irreducible. This shows that the bound cannot be improved beyond . More generally, given any character , acts on the -dimensional space of functions that obey the twisted dilation invariance for all and ; these are known as the principal series representations. When is the trivial character, this is the quasiregular representation discussed earlier. For most other characters, this is an irreducible representation, but it turns out that when is the quadratic representation (thus taking values in while being non-trivial), the principal series representation splits into the direct sum of two -dimensional representations, which comes very close to matching the bound in Lemma 2. There is a parallel series of representations to the principal series (known as the discrete series) which is more complicated to describe (roughly speaking, one has to embed in a quadratic extension and then use a rotated version of the above construction, to change a split torus into a non-split torus), but can generate irreducible representations of dimension , showing that the bound in Lemma 2 is in fact exactly sharp. These constructions can be generalised to arbitrary finite groups of Lie type using Deligne-Luzstig theory, but this is beyond the scope of this course (and of my own knowledge in the subject).

Exercise 9 Let be an odd prime. Show that for any , the alternating group is -quasirandom. (Hint: show that all cycles of order in are conjugate to each other in (and not just in ); in particular, a cycle is conjugate to its power for all . Also, as , is simple, and so the cycles of order generate the entire group.)

Remark 3 By using more precise information on the representations of the alternating group (using the theory of Specht modules and Young tableaux), one can show the slightly sharper statement that is -quasirandom for (but is only -quasirandom for due to isocahedral symmetry, and -quasirandom for due to lack of perfectness). Using Exercise 3 with the index subgroup , we see that the bound cannot be improved. Thus, (for large ) is not as quasirandom as the special linear groups (for large and bounded), because in the latter case the quasirandomness is as strong as a power of the size of the group, whereas in the former case it is only logarithmic in size.

If one replaces the alternating group with the slightly larger symmetric group , then quasirandomness is destroyed (since , having the abelian quotient , is not perfect); indeed, is -quasirandom and no better.

Remark 4 Thanks to the monumental achievement of the classification of finite simple groups, we know that apart from a finite number (26, to be precise) of sporadic exceptions, all finite simple groups (up to isomorphism) are either a cyclic group , an alternating group , or is a finite simple group of Lie type such as . (We will define the concept of a finite simple group of Lie type more precisely in later notes, but suffice to say for now that such groups are constructed from reductive algebraic groups, for instance is constructed from in characteristic .) In the case of finite simple groups of Lie type with bounded rank , it is known from the work of Landazuri and Seitz that such groups are -quasirandom for some depending only on the rank. On the other hand, by the previous remark, the large alternating groups do not have this property, and one can show that the finite simple groups of Lie type with large rank also do not have this property. Thus, we see using the classification that if a finite simple group is -quasirandom for some and is sufficiently large depending on , then is a finite simple group of Lie type with rank . It would be of interest to see if there was an alternate way to establish this fact that did not rely on the classification, as it may lead to an alternate approach to proving the classification (or perhaps a weakened version thereof).

A key reason why quasirandomness is desirable for the purposes of demonstrating expansion is that quasirandom groups happen to be rapidly mixing at large scales, as we shall see below the fold. As such, quasirandomness is an important tool for demonstrating expansion in Cayley graphs, though because expansion is a phenomenon that must hold at all scales, one needs to supplement quasirandomness with some additional input that creates mixing at small or medium scales also before one can deduce expansion. As an example of this technique of combining quasirandomness with mixing at small and medium scales, we present a proof (due to Sarnak-Xue, and simplified by Gamburd) of a weak version of the famous “3/16 theorem” of Selberg on the least non-trivial eigenvalue of the Laplacian on a modular curve, which among other things can be used to construct a family of expander Cayley graphs in (compare this with the property (T)-based methods in the previous notes, which could construct expander Cayley graphs in for any fixed ).

Random matrices: The Four Moment Theorem for Wigner ensembles

Van Vu and I have just uploaded to the arXiv our short survey article, “Random matrices: The Four Moment Theorem for Wigner ensembles“, submitted to the MSRI book series, as part of the proceedings on the MSRI semester program on random matrix theory from last year.  This is a highly condensed version (at 17 pages) of a much longer survey (currently at about 48 pages, though not completely finished) that we are currently working on, devoted to the recent advances in understanding the universality phenomenon for spectral statistics of Wigner matrices.  In this abridged version of the survey, we focus on a key tool in the subject, namely the Four Moment Theorem which roughly speaking asserts that the statistics of a Wigner matrix depend only on the first four moments of the entries.  We give a sketch of proof of this theorem, and two sample applications: a central limit theorem for individual eigenvalues of a Wigner matrix (extending a result of Gustavsson in the case of GUE), and the verification of a conjecture of Wigner, Dyson, and Mehta on the universality of the asymptotic k-point correlation functions even for discrete ensembles (provided that we interpret convergence in the vague topology sense).

For reasons of space, this paper is very far from an exhaustive survey even of the narrow topic of universality for Wigner matrices, but should hopefully be an accessible entry point into the subject nevertheless.