254B, Lecture Notes 7: The transference principle, and linear equations in primes

In this, the final lecture notes of this course, we discuss one of the motivating applications of the theory developed thus far, namely to count solutions to linear equations in primes (or in dense subsets of primes ). Unfortunately, the most famous linear equations in primes: the twin prime equation and the even Goldbach equation – remain out of reach of this technology (because the relevant affine linear forms involved are commensurate, and thus have infinite complexity with respect to the Gowers norms), but most other systems of equations, in particular that of arithmetic progressions for (or equivalently, for ) , as well as the odd Goldbach equation , are tractable.

To illustrate the main ideas, we will focus on the following result of Green:

Theorem 1 (Roth’s theorem in the primes) Let be a subset of primes whose upper density is positive. Then contains infinitely many arithmetic progressions of length three.

This should be compared with Roth’s theorem in the integers (Notes 2), which is the same statement but with the primes replaced by the integers (or natural numbers ). Indeed, Roth’s theorem for the primes is proven by transferring Roth’s theorem for the integers to the prime setting; the latter theorem is used as a “black box”. The key difficulty here in performing this transference is that the primes have zero density inside the integers; indeed, from the prime number theorem we have .

There are a number of generalisations of this transference technique. In a paper of Green and myself, we extended the above theorem to progressions of longer length (thus transferring Szemerédi’s theorem to the primes). In a series of papers (culminating in a paper to appear shortly) of Green, myself, and also Ziegler, related methods are also used to obtain an asymptotic for the number of solutions in the primes to any system of linear equations of bounded complexity. This latter result uses the full power of higher order Fourier analysis, in particular relying heavily on the inverse conjecture for the Gowers norms; in contrast, Roth’s theorem and Szemerédi’s theorem in the primes are “softer” results that do not need this conjecture.

To transfer results from the integers to the primes, there are three basic steps:

• A general transference principle, that transfers certain types of additive combinatorial results from dense subsets of the integers to dense subsets of a suitably “pseudorandom set” of integers (or more precisely, to the integers weighted by a suitably “pseudorandom measure”);
• An application of sieve theory to show that the primes (or more precisely, an affine modification of the primes) lie inside a suitably pseudorandom set of integers (or more precisely, have significant mass with respect to a suitably pseudorandom measure).
• If one is seeking asymptotics for patterns in the primes, and not simply lower bounds, one also needs to control correlations between the primes (or proxies for the primes, such as the Möbius function) with various objects that arise from higher order Fourier analysis, such as nilsequences.

The former step can be accomplished in a number of ways. For progressions of length three (and more generally, for controlling linear patterns of complexity at most one), transference can be accomplished by Fourier-analytic methods. For more complicated patterns, one can use techniques inspired by ergodic theory; more recently, simplified and more efficient methods based on duality (the Hahn-Banach theorem) have also been used. No number theory is used in this step. (In the case of transference to genuinely random sets, rather than pseudorandom sets, similar ideas appeared earlier in the graph theory setting, see this paper of Kohayakawa, Luczak, and Rodl.

The second step is accomplished by fairly standard sieve theory methods (e.g. the Selberg sieve, or the slight variants of this sieve used by Goldston and Yildirim). Remarkably, very little of the formidable apparatus of modern analytic number theory is needed for this step; for instance, the only fact about the Riemann zeta function that is truly needed is that it has a simple pole at , and no knowledge of L-functions is needed.

The third step does draw more significantly on analytic number theory techniques and results (most notably, the method of Vinogradov to compute oscillatory sums over the primes, and also the Siegel-Walfisz theorem that gives a good error term on the prime number theorem in arithemtic progressions). As these techniques are somewhat orthogonal to the main topic of this course, we shall only touch briefly on this aspect of the transference strategy.

A remark on primality testing and the binary expansion

I’ve just uploaded to the arXiv the short note “A remark on primality testing and the binary expansion“, submitted to the Journal of the Australian Mathematical Society. In this note I establish the following result: for any sufficiently large integer n, there exists an n-bit prime p, such that the numbers for are all composite. In particular, if one flips any one of the bits in the binary expansion of the prime p, one obtains a composite number. As a consequence, one obtains the (rather plausible) consequence that in order to (deterministically) test whether an n-bit integer is prime or not, one needs (in the worst-case) to read all n bits of the prime. (This question was posed to me by my colleague here at UCLA, Yiannis Moschovakis.)

Primes p of the form mentioned in the above result are somewhat rare at first; the first some prime is . But in fact, the argument in my note shows that the set of such primes actually has positive relative density inside the set of all primes. (Amusingly, this means that one can apply a theorem of Ben Green and myself and conclude that there are arbitrarily long arithmetic progressions of such primes, although I doubt that there is any particular significance or application to this conclusion.)

The same remark applies to other bases; thus, for instance, there exist infinitely many prime numbers with the property that if one changes any one of the base 10 digits of that number, one obtains a composite number. (Presumably the first such number can be located by computer search, though I did not attempt to do so.) [Update, Feb 25: see comments.]