Bounding short exponential sums on smooth moduli via Weyl differencing

As in previous posts, we use the following asymptotic notation: is a parameter going off to infinity, and all quantities may depend on unless explicitly declared to be “fixed”. The asymptotic notation is then defined relative to this parameter. A quantity is said to be of polynomial size if one has , and said to be bounded if . Another convenient notation: we write for . Thus for instance the divisor bound asserts that if has polynomial size, then the number of divisors of is .

This post is intended to highlight a phenomenon unearthed in the ongoing polymath8 project (and is in fact a key component of Zhang’s proof that there are bounded gaps between primes infinitely often), namely that one can get quite good bounds on relatively short exponential sums when the modulus is smooth, through the basic technique of Weyl differencing (ultimately based on the Cauchy-Schwarz inequality, and also related to the van der Corput lemma in equidistribution theory). Improvements in the case of smooth moduli have appeared before in the literature (e.g. in this paper of Heath-Brown, paper of Graham and Ringrose, this later paper of Heath-Brown, this paper of Chang, or this paper of Goldmakher); the arguments here are particularly close to that of the first paper of Heath-Brown. It now also appears that further optimisation of this Weyl differencing trick could lead to noticeable improvements in the numerology for the polymath8 project, so I am devoting this post to explaining this trick further.

To illustrate the method, let us begin with the classical problem in analytic number theory of estimating an incomplete character sum

where is a primitive Dirichlet character of some conductor , is an integer, and is some quantity between and . Clearly we have the trivial bound

we also have the classical Pólya-Vinogradov inequality

This latter inequality gives improvements over the trivial bound when is much larger than , but not for much smaller than . The Pólya-Vinogradov inequality can be deduced via a little Fourier analysis from the completed exponential sum bound

for any , where . (In fact, from the classical theory of Gauss sums, this exponential sum is equal to for some complex number of norm .)

In the case when is a prime, improving upon the above two inequalities is an important but difficult problem, with only partially satisfactory results so far. To give just one indication of the difficulty, the seemingly modest improvement

to the Pólya-Vinogradov inequality when was a prime required a 14-page paper in Inventiones by Montgomery and Vaughan to prove, and even then it was only conditional on the generalised Riemann hypothesis! See also this more recent paper of Granville and Soundararajan for an unconditional variant of this result in the case that has odd order.

Another important improvement is the Burgess bound, which in our notation asserts that

for any fixed integer , assuming that is square-free (for simplicity) and of polynomial size; see this previous post for a discussion of the Burgess argument. This is non-trivial for as small as .

In the case when is prime, there has been very little improvement to the Burgess bound (or its Fourier dual, which can give bounds for as large as ) in the last fifty years; an improvement to the exponents in (3) in this case (particularly anything that gave a power saving for below ) would in fact be rather significant news in analytic number theory.

However, in the opposite case when is smooth – that is to say, all of its factors are much smaller than – then one can do better than the Burgess bound in some regimes. This fact has been observed in several places in the literature (in particular, in the papers of Heath-Brown, Graham-Ringrose, Chang, and Goldmakher mentioned previously), but also turns out to (implicitly) be a key insight in Zhang’s paper on bounded prime gaps. In the case of character sums, one such improved estimate (closely related to Theorem 2 of the Heath-Brown paper) is as follows:

Proposition 1 Let be square-free with a factorisation and of polynomial size, and let be integers with . Then for any primitive character with conductor , one has

This proposition is particularly powerful when is smooth, as this gives many factorisations with the ability to specify with a fair amount of accuracy. For instance, if is -smooth (i.e. all prime factors are at most ), then by the greedy algorithm one can find a divisor of with ; if we set , then , and the above proposition then gives

which can improve upon the Burgess bound when is small. For instance, if , then this bound becomes ; in contrast the Burgess bound only gives for this value of (using the optimal choice for ), which is inferior for .

The hypothesis that be squarefree may be relaxed, but for applications to the Polymath8 project, it is only the squarefree moduli that are relevant.

Proof: If then the claim follows from the trivial bound (1), while for the claim follows from (2). Hence we may assume that

We use the method of Weyl differencing, the key point being to difference in multiples of .

Let , thus . For any , we have

and thus on averaging

By the Chinese remainder theorem, we may factor

where are primitive characters of conductor respectively. As is periodic of period , we thus have

and so we can take out of the inner summation of the right-hand side of (4) to obtain

and hence by the triangle inequality

Note how the characters on the right-hand side only have period rather than . This reduction in the period is ultimately the source of the saving over the Pólya-Vinogradov inequality.

Note that the inner sum vanishes unless , which is an interval of length by choice of . Thus by Cauchy-Schwarz one has

We expand the right-hand side as

We first consider the diagonal contribution . In this case we use the trivial bound for the inner summation, and we soon see that the total contribution here is .

Now we consider the off-diagonal case; by symmetry we can take . Then the indicator functions restrict to the interval . On the other hand, as a consequence of the Weil conjectures for curves one can show that

for any ; indeed one can use the Chinese remainder theorem and the square-free nature of to reduce to the case when is prime, in which case one can apply (for instance) the original paper of Weil to establish this bound, noting also that and are coprime since is squarefree. Applying the method of completion of sums (or the Parseval formula), this shows that

Summing in (using Lemma 5 from this previous post) we see that the total contribution to the off-diagonal case is

which simplifies to . The claim follows.

A modification of the above argument (using more complicated versions of the Weil conjectures) allows one to replace the summand by more complicated summands such as for some polynomials or rational functions of bounded degree and obeying a suitable non-degeneracy condition (after restricting of course to those for which the arguments are well-defined). We will not detail this here, but instead turn to the question of estimating slightly longer exponential sums, such as

where should be thought of as a little bit larger than .

A Fourier-analytic proof of Frobenius’ theorem

A finite group is said to be a Frobenius group if there is a non-trivial subgroup of (known as the Frobenius complement of ) such that the conjugates of are “disjoint as possible” in the sense that whenever . This gives a decomposition

where the Frobenius kernel of is defined as the identity element together with all the non-identity elements that are not conjugate to any element of . Taking cardinalities, we conclude that

and hence

A remarkable theorem of Frobenius gives an unexpected amount of structure on and hence on :

Theorem 1 (Frobenius’ theorem) Let be a Frobenius group with Frobenius complement and Frobenius kernel . Then is a normal subgroup of , and hence (by (2) and the disjointness of and outside the identity) is the semidirect product of and .

I discussed Frobenius’ theorem and its proof in this recent blog post. This proof uses the theory of characters on a finite group , in particular relying on the fact that a character on a subgroup can induce a character on , which can then be decomposed into irreducible characters with natural number coefficients. Remarkably, even though a century has passed since Frobenius’ original argument, there is no proof known of this theorem which avoids character theory entirely; there are elementary proofs known when the complement has even order or when is solvable (we review both of these cases below the fold), which by the Feit-Thompson theorem does cover all the cases, but the proof of the Feit-Thompson theorem involves plenty of character theory (and also relies on Theorem 1). (The answers to this MathOverflow question give a good overview of the current state of affairs.)

I have been playing around recently with the problem of finding a character-free proof of Frobenius’ theorem. I didn’t succeed in obtaining a completely elementary proof, but I did find an argument which replaces character theory (which can be viewed as coming from the representation theory of the non-commutative group algebra ) with the Fourier analysis of class functions (i.e. the representation theory of the centre of the group algebra), thus replacing non-commutative representation theory by commutative representation theory. This is not a particularly radical depature from the existing proofs of Frobenius’ theorem, but it did seem to be a new proof which was technically “character-free” (even if it was not all that far from character-based in spirit), so I thought I would record it here.

The main ideas are as follows. The space of class functions can be viewed as a commutative algebra with respect to the convolution operation ; as the regular representation is unitary and faithful, this algebra contains no nilpotent elements. As such, (Gelfand-style) Fourier analysis suggests that one can analyse this algebra through the idempotents: class functions such that . In terms of characters, idempotents are nothing more than sums of the form for various collections of characters, but we can perform a fair amount of analysis on idempotents directly without recourse to characters. In particular, it turns out that idempotents enjoy some important integrality properties that can be established without invoking characters: for instance, by taking traces one can check that is a natural number, and more generally we will show that is a natural number whenever is a subgroup of (see Corollary 4 below). For instance, the quantity

is a natural number which we will call the rank of (as it is also the linear rank of the transformation on ).

In the case that is a Frobenius group with kernel , the above integrality properties can be used after some elementary manipulations to establish that for any idempotent , the quantity

is an integer. On the other hand, one can also show by elementary means that this quantity lies between and . These two facts are not strong enough on their own to impose much further structure on , unless one restricts attention to minimal idempotents . In this case spectral theory (or Gelfand theory, or the fundamental theorem of algebra) tells us that has rank one, and then the integrality gap comes into play and forces the quantity (3) to always be either zero or one. This can be used to imply that the convolution action of every minimal idempotent either preserves or annihilates it, which makes itself an idempotent, which makes normal.

Quasirandom groups and a cheap version of the Brauer-Fowler theorem

Suppose that is a finite group of even order, thus is a multiple of two. By Cauchy’s theorem, this implies that contains an involution: an element in of order two. (Indeed, if no such involution existed, then would be partitioned into doubletons together with the identity, so that would be odd, a contradiction.) Of course, groups of odd order have no involutions , thanks to Lagrange’s theorem (since cannot split into doubletons ).

The classical Brauer-Fowler theorem asserts that if a group has many involutions, then it must have a large non-trivial subgroup:

Theorem 1 (Brauer-Fowler theorem) Let be a finite group with at least involutions for some . Then contains a proper subgroup of index at most .

This theorem (which is Theorem 2F in the original paper of Brauer and Fowler, who in fact manage to sharpen slightly to ) has a number of quick corollaries which are also referred to as “the” Brauer-Fowler theorem. For instance, if is a an involution of a group , and the centraliser has order , then clearly (as contains and ) and the conjugacy class has order (since the map has preimages that are cosets of ). Every conjugate of an involution is again an involution, so by the Brauer-Fowler theorem contains a subgroup of order at least . In particular, we can conclude that every group of even order contains a proper subgroup of order at least .

Another corollary is that the size of a simple group of even order can be controlled by the size of a centraliser of one of its involutions:

Corollary 2 (Brauer-Fowler theorem) Let be a finite simple group with an involution , and suppose that has order . Then has order at most .

Indeed, by the previous discussion has a proper subgroup of index less than , which then gives a non-trivial permutation action of on the coset space . The kernel of this action is a proper normal subgroup of and is thus trivial, so the action is faithful, and the claim follows.

If one assumes the Feit-Thompson theorem that all groups of odd order are solvable, then Corollary 2 suggests a strategy (first proposed by Brauer himself in 1954) to prove the classification of finite simple groups (CFSG) by induction on the order of the group. Namely, assume for contradiction that the CFSG failed, so that there is a counterexample of minimal order to the classification. This is a non-abelian finite simple group; by the Feit-Thompson theorem, it has even order and thus has at least one involution . Take such an involution and consider its centraliser ; this is a proper subgroup of of some order . As is a minimal counterexample to the classification, one can in principle describe in terms of the CFSG by factoring the group into simple components (via a composition series) and applying the CFSG to each such component. Now, the “only” thing left to do is to verify, for each isomorphism class of , that all the possible simple groups that could have this type of group as a centraliser of an involution obey the CFSG; Corollary 2 tells us that for each such isomorphism class for , there are only finitely many that could generate this class for one of its centralisers, so this task should be doable in principle for any given isomorphism class for . That’s all one needs to do to prove the classification of finite simple groups!

Needless to say, this program turns out to be far more difficult than the above summary suggests, and the actual proof of the CFSG does not quite proceed along these lines. However, a significant portion of the argument is based on a generalisation of this strategy, in which the concept of a centraliser of an involution is replaced by the more general notion of a normaliser of a -group, and one studies not just a single normaliser but rather the entire family of such normalisers and how they interact with each other (and in particular, which normalisers of -groups commute with each other), motivated in part by the theory of Tits buildings for Lie groups which dictates a very specific type of interaction structure between these -groups in the key case when is a (sufficiently high rank) finite simple group of Lie type over a field of characteristic . See the text of Aschbacher, Lyons, Smith, and Solomon for a more detailed description of this strategy.

The Brauer-Fowler theorem can be proven by a nice application of character theory, of the type discussed in this recent blog post, ultimately based on analysing the alternating tensor power of representations; I reproduce a version of this argument (taken from this text of Isaacs) below the fold. (The original argument of Brauer and Fowler is more combinatorial in nature.) However, I wanted to record a variant of the argument that relies not on the fine properties of characters, but on the cruder theory of quasirandomness for groups, the modern study of which was initiated by Gowers, and is discussed for instance in this previous post. It gives the following slightly weaker version of Corollary 2:

Corollary 3 (Weak Brauer-Fowler theorem) Let be a finite simple group with an involution , and suppose that has order . Then can be identified with a subgroup of the unitary group .

One can get an upper bound on from this corollary using Jordan’s theorem, but the resulting bound is a bit weaker than that in Corollary 2 (and the best bounds on Jordan’s theorem require the CFSG!).

Proof: Let be the set of all involutions in , then as discussed above . We may assume that has no non-trivial unitary representation of dimension less than (since such representations are automatically faithful by the simplicity of ); thus, in the language of quasirandomness, is -quasirandom, and is also non-abelian. We have the basic convolution estimate

(see Exercise 10 from this previous blog post). In particular,

and so there are at least pairs such that , i.e. involutions whose product is also an involution. But any such involutions necessarily commute, since

Thus there are at least pairs of non-identity elements that commute, so by the pigeonhole principle there is a non-identity whose centraliser has order at least . This centraliser cannot be all of since this would make central which contradicts the non-abelian simple nature of . But then the quasiregular representation of on has dimension at most , contradicting the quasirandomness.

The theorems of Frobenius and Suzuki on finite groups

The classification of finite simple groups (CFSG), first announced in 1983 but only fully completed in 2004, is one of the monumental achievements of twentieth century mathematics. Spanning hundreds of papers and tens of thousands of pages, it has been called the “enormous theorem”. A “second generation” proof of the theorem is nearly completed which is a little shorter (estimated at about five thousand pages in length), but currently there is no reasonably sized proof of the classification.

An important precursor of the CFSG is the Feit-Thompson theorem from 1962-1963, which asserts that every finite group of odd order is solvable, or equivalently that every non-abelian finite simple group has even order. This is an immediate consequence of CFSG, and conversely the Feit-Thompson theorem is an essential starting point in the proof of the classification, since it allows one to reduce matters to groups of even order for which key additional tools (such as the Brauer-Fowler theorem) become available. The original proof of the Feit-Thompson theorem is 255 pages long, which is significantly shorter than the proof of the CFSG, but still far from short. While parts of the proof of the Feit-Thompson theorem have been simplified (and it has recently been converted, after six years of effort, into an argument that has been verified by the proof assistant Coq), the available proofs of this theorem are still extremely lengthy by any reasonable standard.

However, there is a significantly simpler special case of the Feit-Thompson theorem that was established previously by Suzuki in 1957, which was influential in the proof of the more general Feit-Thompson theorem (and thus indirectly to the proof of CFSG). Define a CA-group to be a group with the property that the centraliser of any non-identity element is abelian; equivalently, the commuting relation (defined as the relation that holds when commutes with , thus ) is an equivalence relation on the non-identity elements of . Trivially, every abelian group is CA. A non-abelian example of a CA-group is the group of invertible affine transformations on a field . A little less obviously, the special linear group over a finite field is a CA-group when is a power of two. The finite simple groups of Lie type are not, in general, CA-groups, but when the rank is bounded they tend to behave as if they were “almost CA”; the centraliser of a generic element in , for instance, when is bounded and is large), is typically a maximal torus (because most elements in are regular semisimple) which is certainly abelian. In view of the CFSG, we thus see that CA or nearly CA groups form an important subclass of the simple groups, and it is thus of interest to study them separately. To this end, we have

Theorem 1 (Suzuki’s theorem on CA-groups) Every finite CA-group of odd order is solvable.

Of course, this theorem is superceded by the more general Feit-Thompson theorem, but Suzuki’s proof is substantially shorter (the original proof is nine pages) and will be given in this post. (See this survey of Solomon for some discussion of the link between Suzuki’s argument and the Feit-Thompson argument.) Suzuki’s analysis can be pushed further to give an essentially complete classification of all the finite CA-groups (of either odd or even order), but we will not pursue these matters here.

Moving even further down the ladder of simple precursors of CSFG is the following theorem of Frobenius from 1901. Define a Frobenius group to be a finite group which has a subgroup (called the Frobenius complement) with the property that all the non-trivial conjugates of for , intersect only at the origin. For instance the group is also a Frobenius group (take to be the affine transformations that fix a specified point , e.g. the origin). This example suggests that there is some overlap between the notions of a Frobenius group and a CA group. Indeed, note that if is a CA-group and is a maximal abelian subgroup of , then any conjugate of that is not identical to will intersect only at the origin (because and each of its conjugates consist of equivalence classes under the commuting relation , together with the identity). So if a maximal abelian subgroup of a CA-group is its own normaliser (thus is equal to ), then the group is a Frobenius group.

Frobenius’ theorem places an unexpectedly strong amount of structure on a Frobenius group:

Theorem 2 (Frobenius’ theorem) Let be a Frobenius group with Frobenius complement . Then there exists a normal subgroup of (called the Frobenius kernel of ) such that is the semi-direct product of and .

Roughly speaking, this theorem indicates that all Frobenius groups “behave” like the example (which is a quintessential example of a semi-direct product).

Note that if every CA-group of odd order was either Frobenius or abelian, then Theorem 2 would imply Theorem 1 by an induction on the order of , since any subgroup of a CA-group is clearly again a CA-group. Indeed, the proof of Suzuki’s theorem does basically proceed by this route (Suzuki’s arguments do indeed imply that CA-groups of odd order are Frobenius or abelian, although we will not quite establish that fact here).

Frobenius’ theorem can be reformulated in the following concrete combinatorial form:

Theorem 3 (Frobenius’ theorem, equivalent version) Let be a group of permutations acting transitively on a finite set , with the property that any non-identity permutation in fixes at most one point in . Then the set of permutations in that fix no points in , together with the identity, is closed under composition.

Again, a good example to keep in mind for this theorem is when is the group of affine permutations on a field (i.e. the group for that field), and is the set of points on that field. In that case, the set of permutations in that do not fix any points are the non-trivial translations.

To deduce Theorem 3 from Theorem 2, one applies Theorem 2 to the stabiliser of a single point in . Conversely, to deduce Theorem 2 from Theorem 3, set to be the space of left-cosets of , with the obvious left -action; one easily verifies that this action is faithful, transitive, and each non-identity element of fixes at most one left-coset of (basically because it lies in at most one conjugate of ). If we let be the elements of that do not fix any point in , plus the identity, then by Theorem 3 is closed under composition; it is also clearly closed under inverse and conjugation, and is hence a normal subgroup of . From construction is the identity plus the complement of all the conjugates of , which are all disjoint except at the identity, so by counting elements we see that

As normalises and is disjoint from , we thus see that is all of , giving Theorem 2.

Despite the appealingly concrete and elementary form of Theorem 3, the only known proofs of that theorem (or equivalently, Theorem 2) in its full generality proceed via the machinery of group characters (which one can think of as a version of Fourier analysis for nonabelian groups). On the other hand, once one establishes the basic theory of these characters (reviewed below the fold), the proof of Frobenius’ theorem is very short, which gives quite a striking example of the power of character theory. The proof of Suzuki’s theorem also proceeds via character theory, and is basically a more involved version of the Frobenius argument; again, no character-free proof of Suzuki’s theorem is currently known. (The proofs of Feit-Thompson and CFSG also involve characters, but those proofs also contain many other arguments of much greater complexity than the character-based portions of the proof.)

It seems to me that the above four theorems (Frobenius, Suzuki, Feit-Thompson, and CFSG) provide a ladder of sorts (with exponentially increasing complexity at each step) to the full classification, and that any new approach to the classification might first begin by revisiting the earlier theorems on this ladder and finding new proofs of these results first (in particular, if one had a “robust” proof of Suzuki’s theorem that also gave non-trivial control on “almost CA-groups” – whatever that means – then this might lead to a new route to classifying the finite simple groups of Lie type and bounded rank). But even for the simplest two results on this ladder – Frobenius and Suzuki – it seems remarkably difficult to find any proof that is not essentially the character-based proof. (Even trying to replace character theory by its close cousin, representation theory, doesn’t seem to work unless one gives in to the temptation to take traces everywhere and put the characters back in; it seems that rather than abandon characters altogether, one needs to find some sort of “robust” generalisation of existing character-based methods.) In any case, I am recording here the standard character-based proofs of the theorems of Frobenius and Suzuki below the fold. There is nothing particularly novel here, but I wanted to collect all the relevant material in one place, largely for my own benefit.

245C, Notes 2: The Fourier transform

In these notes we lay out the basic theory of the Fourier transform, which is of course the most fundamental tool in harmonic analysis and also of major importance in related fields (functional analysis, complex analysis, PDE, number theory, additive combinatorics, representation theory, signal processing, etc.). The Fourier transform, in conjunction with the Fourier inversion formula, allows one to take essentially arbitrary (complex-valued) functions on a group (or more generally, a space that acts on, e.g. a homogeneous space ), and decompose them as a (discrete or continuous) superposition of much more symmetric functions on the domain, such as characters ; the precise superposition is given by Fourier coefficients , which take values in some dual object such as the Pontryagin dual of . Characters behave in a very simple manner with respect to translation (indeed, they are eigenfunctions of the translation action), and so the Fourier transform tends to simplify any mathematical problem which enjoys a translation invariance symmetry (or an approximation to such a symmetry), and is somehow “linear” (i.e. it interacts nicely with superpositions). In particular, Fourier analytic methods are particularly useful for studying operations such as convolution and set-theoretic addition , or the closely related problem of counting solutions to additive problems such as or , where are constrained to lie in specific sets . The Fourier transform is also a particularly powerful tool for solving constant-coefficient linear ODE and PDE (because of the translation invariance), and can also approximately solve some variable-coefficient (or slightly non-linear) equations if the coefficients vary smoothly enough and the nonlinear terms are sufficiently tame.

The Fourier transform also provides an important new way of looking at a function , as it highlights the distribution of in frequency space (the domain of the frequency variable ) rather than physical space (the domain of the physical variable ). A given property of in the physical domain may be transformed to a rather different-looking property of in the frequency domain. For instance:

• Smoothness of in the physical domain corresponds to decay of in the Fourier domain, and conversely. (More generally, fine scale properties of tend to manifest themselves as coarse scale properties of , and conversely.)
• Convolution in the physical domain corresponds to pointwise multiplication in the Fourier domain, and conversely.
• Constant coefficient differential operators such as in the physical domain corresponds to multiplication by polynomials such as in the Fourier domain, and conversely.
• More generally, translation invariant operators in the physical domain correspond to multiplication by symbols in the Fourier domain, and conversely.
• Rescaling in the physical domain by an invertible linear transformation corresponds to an inverse (adjoint) rescaling in the Fourier domain.
• Restriction to a subspace (or subgroup) in the physical domain corresponds to projection to the dual quotient space (or quotient group) in the Fourier domain, and conversely.
• Frequency modulation in the physical domain corresponds to translation in the frequency domain, and conversely.

(We will make these statements more precise below.)

On the other hand, some operations in the physical domain remain essentially unchanged in the Fourier domain. Most importantly, the norm (or energy) of a function is the same as that of its Fourier transform, and more generally the inner product of two functions is the same as that of their Fourier transforms. Indeed, the Fourier transform is a unitary operator on (a fact which is variously known as the Plancherel theorem or the Parseval identity). This makes it easier to pass back and forth between the physical domain and frequency domain, so that one can combine techniques that are easy to execute in the physical domain with other techniques that are easy to execute in the frequency domain. (In fact, one can combine the physical and frequency domains together into a product domain known as phase space, and there are entire fields of mathematics (e.g. microlocal analysis, geometric quantisation, time-frequency analysis) devoted to performing analysis on these sorts of spaces directly, but this is beyond the scope of this course.)

In these notes, we briefly discuss the general theory of the Fourier transform, but will mainly focus on the two classical domains for Fourier analysis: the torus , and the Euclidean space . For these domains one has the advantage of being able to perform very explicit algebraic calculations, involving concrete functions such as plane waves or Gaussians .