254B, Notes 7: Sieving and expanders

In this final set of course notes, we discuss how (a generalisation of) the expansion results obtained in the preceding notes can be used for some number-theoretic applications, and in particular to locate almost primes inside orbits of thin groups, following the work of Bourgain, Gamburd, and Sarnak. We will not attempt here to obtain the sharpest or most general results in this direction, but instead focus on the simplest instances of these results which are still illustrative of the ideas involved.

One of the basic general problems in analytic number theory is to locate tuples of primes of a certain form; for instance, the famous (and still unsolved) twin prime conjecture asserts that there are infinitely many pairs in the line in which both entries are prime. In a similar spirit, one of the Landau conjectures (also still unsolved) asserts that there are infinitely many primes in the set . The Mersenne prime conjecture (also unsolved) asserts that there are infinitely many primes in the set , and so forth.

More generally, given some explicit subset in (or , if one wishes), such as an algebraic variety, one can ask the question of whether there are infinitely many integer lattice points in in which all the coefficients are simultaneously prime; let us refer to such points as prime points.

At this level of generality, this problem is impossibly difficult. Indeed, even the much simpler problem of deciding whether the set is non-empty (let alone containing prime points) when is a hypersurface cut out by a polynomial is essentially Hilbert’s tenth problem, which is known to be undecidable in general by Matiyasevich’s theorem. So one needs to restrict attention to a more special class of sets , in which the question of finding integer points is not so difficult. One model case is to consider orbits , where is a fixed lattice vector and is some discrete group that acts on somehow (e.g. might be embedded as a subgroup of the special linear group , or on the affine group ). In such a situation it is then quite easy to show that is large; for instance, will be infinite precisely when the stabiliser of in has infinite index in .

Even in this simpler setting, the question of determining whether an orbit contains infinitely prime points is still extremely difficult; indeed the three examples given above of the twin prime conjecture, Landau conjecture, and Mersenne prime conjecture are essentially of this form (possibly after some slight modification of the underlying ring , see this paper of Bourgain-Gamburd-Sarnak for details), and are all unsolved (and generally considered well out of reach of current technology). Indeed, the list of non-trivial orbits which are known to contain infinitely many prime points is quite slim; Euclid’s theorem on the infinitude of primes handles the case , Dirichlet’s theorem handles infinite arithmetic progressions , and a somewhat complicated result of Green, Tao, and Ziegler handles “non-degenerate” affine lattices in of rank two or more (such as the lattice of length arithmetic progressions), but there are few other positive results known that are not based on the above cases (though we will note the remarkable theorem of Friedlander and Iwaniec that there are infinitely many primes of the form , and the related result of Heath-Brown that there are infinitely many primes of the form , as being in a kindred spirit to the above results, though they are not explicitly associated to an orbit of a reasonable action as far as I know).

On the other hand, much more is known if one is willing to replace the primes by the larger set of almost primes – integers with a small number of prime factors (counting multiplicity). Specifically, for any , let us call an -almost prime an integer which is the product of at most primes, and possibly by the unit as well. Many of the above sorts of questions which are open for primes, are known for -almost primes for sufficiently large. For instance, with regards to the twin prime conjecture, it is a result of Chen that there are infinitely many pairs where is a prime and is a -almost prime; in a similar vein, it is a result of Iwaniec that there are infinitely many -almost primes of the form . On the other hand, it is still open for any fixed whether there are infinitely many Mersenne numbers which are -almost primes. (For the superficially similar situation with the numbers , it is in fact believed (but again unproven) that there are only finitely many -almost primes for any fixed (the Fermat prime conjecture).)

The main tool that allows one to count almost primes in orbits is sieve theory. The reason for this lies in the simple observation that in order to ensure that an integer of magnitude at most is an -almost prime, it suffices to guarantee that is not divisible by any prime less than . Thus, to create -almost primes, one can start with the integers up to some large threshold and remove (or “sieve out”) all the integers that are multiples of any prime less than . The difficulty is then to ensure that a sufficiently non-trivial quantity of integers remain after this process, for the purposes of finding points in the given set .

The most basic sieve of this form is the sieve of Eratosthenes, which when combined with the inclusion-exclusion principle gives the Legendre sieve (or exact sieve), which gives an exact formula for quantities such as the number of natural numbers less than or equal to that are not divisible by any prime less than or equal to a given threshold . Unfortunately, when one tries to evaluate this formula, one encounters error terms which grow exponentially in , rendering this sieve useful only for very small thresholds (of logarithmic size in ). To improve the sieve level up to a small power of such as , one has to replace the exact sieve by upper bound sieves and lower bound sieves which only seek to obtain upper or lower bounds on quantities such as , but contain a polynomial number of terms rather than an exponential number. There are a variety of such sieves, with the two most common such sieves being combinatorial sieves (such as the beta sieve), based on various combinatorial truncations of the inclusion-exclusion formula, and the Selberg upper bound sieve, based on upper bounds that are the square of a divisor sum. (There is also the large sieve, which is somewhat different in nature and based on almost orthogonality considerations, rather than on any actual sieving, to obtain upper bounds.) We will primarily work with a specific sieve in this notes, namely the beta sieve, and we will not attempt to optimise all the parameters of this sieve (which ultimately means that the almost primality parameter in our results will be somewhat large). For a more detailed study of sieve theory, see the classic text of Halberstam and Richert, or the more recent texts of Iwaniec-Kowalski or of Friedlander-Iwaniec.

Very roughly speaking, the end result of sieve theory is that excepting some degenerate and “exponentially thin” settings (such as those associated with the Mersenne primes), all the orbits which are expected to have a large number of primes, can be proven to at least have a large number of -almost primes for some finite . (Unfortunately, there is a major obstruction, known as the parity problem, which prevents sieve theory from lowering all the way to ; see this blog post for more discussion.) One formulation of this principle was established by Bourgain, Gamburd, and Sarnak:

Theorem 1 (Bourgain-Gamburd-Sarnak) Let be a subgroup of which is not virtually solvable. Let be a polynomial with integer coefficients obeying the following primitivity condition: for any positive integer , there exists such that is coprime to . Then there exists an such that there are infinitely many with non-zero and -almost prime.

This is not the strongest version of the Bourgain-Gamburd-Sarnak theorem, but it captures the general flavour of their results. Note that the theorem immediately implies an analogous result for orbits , in which is now a polynomial from to , and one uses instead of . It is in fact conjectured that one can set here, but this is well beyond current technology. For the purpose of reaching , it is very natural to impose the primitivity condition, but as long as one is content with larger values of , it is possible to relax the primitivity condition somewhat; see the paper of Bourgain, Gamburd, and Sarnak for more discussion.

By specialising to the polynomial , we conclude as a corollary that as long as is primitive in the sense that it contains matrices with all coefficients coprime to for any given , then contains infinitely many matrices whose elements are all -almost primes for some depending only on . For further applications of these sorts of results, for instance to Appolonian packings, see the paper of Bourgain, Gamburd, and Sarnak.

It turns out that to prove Theorem 1, the Cayley expansion results in from the previous set of notes are not quite enough; one needs a more general Cayley expansion result in where is square-free but not necessarily prime. The proof of this expansion result uses the same basic methods as in the case, but is significantly more complicated technically, and we will only discuss it briefly here. As such, we do not give a complete proof of Theorem 1, but hopefully the portion of the argument presented here is still sufficient to give an impression of the ideas involved.

Marker lecture IV: “Sieving for almost primes and expanders”

In this final lecture in the Marker lecture series, I discuss the recent work of Bourgain, Gamburd, and Sarnak on how arithmetic combinatorics and expander graphs were used to sieve for almost primes in various algebraic sets.

Marker lecture III: “Small gaps between primes”

In the third Marker lecture, I would like to discuss the recent progress, particularly by Goldston, Pintz, and Yıldırım, on finding small gaps between consecutive primes.  (See also the surveys by Goldston-Pintz-Yıldırım, by Green, and by Soundararajan on the subject; the material here is based to some extent on these prior surveys.)