Prime-Detecting Sieves.

By Glyn Harman

Princeton University Press

Copyright © 2007 Princeton University Press
All right reserved.
ISBN: 978-0-691-12437-7

Chapter One

Introduction

1.1 THE BEGINNING

Many problems in number theory have the form: Prove that there exist infinitely many primes in a set A or prove that there is a prime in each set [A.sup.(n)] for all large n. Examples of the first include:

The twin-prime conjecture. Here one takes A = {p + 2: p a prime}.

Primes represented by polynomials. A typical problem here is whether the quadratic [n.sup.2] + 1 is infinitely often prime. So one takes A = {[n.sup.2] + 1: n [member of] Z}.

Examples of the second problem include:

Goldbach’s conjecture. In this case [A.sup.(n)] = {2n – p : p a prime,p [less than or equal to] n}.

Is there a prime between consecutive squares? For this problem we take [A.sup.(n)] = {m : [n.sup.2] [less than or equal to] m [less than or equal to] [(n + 1).sup.2]}.

I must stress that we will not be able to get as far as a proof of these results in this book! As is well known, the solution to these problems seems to be well beyond all our current methods. Nevertheless, the methods we present here have produced remarkable progress in our knowledge of the distribution of primes in “thin” sequences. It should be clear from reading this book just what information we lack to tackle the above problems.

If we write [pi](x) for the number of primes up to x, the prime number theorem tells us that [pi](x) ~ x/log x. Thus we might hope that if the integers in a set A are about x in size, and assuming that there are no obstacles preventing primes from belonging to A (like A consisting only of even numbers), then the number of primes in A is about [absolute value of A] log x (perhaps times some factor depending on the likelihood of small primes dividing integers in A). We shall discover that our hopes are realized so long as we have the two types of arithmetical information introduced in Section 1.6. We shall find that when the information available is strong, we can obtain an asymptotic formula for the number of primes in a given set. When the information is not quite so strong, we can often still obtain a non-trivial lower bound for this quantity. The common thread running through this book is the use of sieve methods: either identities or inequalities. Indeed our inequalities are simply identities where we bound below by zero sums that are in all probability positive. We shall see that the sieve method can be traced back to Eratosthenes in antiquity. Even modern formulations of sieve identities that apparently have no connection with the ancient Greek mathematician turn out to be intimately related through the ubiquitous identity (1.3.1), which underlies all our work. From another point of view, our work here could be regarded simply as the inclusion/exclusion principle pushed to the nth degree (with n [right arrow] [infinity]!).

There are four basic types of problem that we will consider and we introduce them now to whet the reader’s appetite.

1. Diophantine approximation. This is the easiest problem to deal with since much progress can be made with relatively elementary arithmetical information. We know that if [alpha] is irrational, then there are infinitely many pairs of coprime integers m, n with

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

See [57, Theorem 171], for example. Indeed, the right-hand side above can be improved by a factor up to [5.sup.-1/2]. Now what if we wanted to have fractions with prime denominator? This is the sort of question a number theorist naturally asks. We would hope to get infinitely many solutions to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and, as [theta] increases from 0 (trivial: there is a solution in m for every p) to 1, (the result is false for one: see note below), the problem presumably increases in difficulty. Indeed, no one has any idea how to increase [theta] above 1/3 unless one assumes very strong results on primes in arithmetic progressions (stronger than the Generalized Riemann Hypothesis, which gives the 1/3 exponent). Taking a different perspective on this problem, [alpha]n is dense (mod 1) if a is irrational, and one can consider Kronecker’s theorem [57, Theorem 440] in the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

One would then ask about obtaining infinitely many solutions to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Taking =0 we recover our original problem. It will be useful to write

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus the above problems correspond to small values of [parallel][alpha]p]parallel] or [parallel][alpha]p + [parallel].

Remark. In [61] it is shown that there are uncountably many a such that

[parallel][alpha]p]parallel] has only finitely many solutions in primes p.

2. Primes in short intervals. We would like to know that the interval [n, n + [n.sup.1/2]) contains primes for all large n. There is no method known at present that could tackle this problem (unless we assume an extraordinary hypothesis on the existence of Siegel zeros). If we knew the Riemann Hypothesis were true, then we would obtain the expected asymptotic formula for the number of primes in the interval [n, n + [n.sup.1/2+[epsilon]]). Here is a case where [epsilon] makes all the difference! To be more precise, Dirichlet series/polynomial methods only work when the intervals have this greater length. If we are unable to prove that there are primes in the interval [n, n + [n.sup.1/2+[epsilon]]) without the Riemann Hypothesis, how much larger do we have to make the interval to get an unconditional result? To keep with the convention of the first problem that increasing [theta] means increasing difficulty, how big can we make [theta] and the interval [[n, n + [n.sup.1-[theta]]) still contains primes for all large n? Can we get the expected asymptotic formula

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We can in fact obtain this formula for [theta] <5/12 (by Huxley’s work [97]) and obtain good upper and lower bounds for larger [theta]. For example, we can get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for [theta] [less than or equal to] 9/20, as will be demonstrated in Chapter 10.

Instead of making the intervals longer and asking for primes, we can keep the intervals short and look for “prime-like” numbers. There are two likely candidates for such numbers: almost-primes (with a limited number of prime factors) and numbers with a large prime factor. We shall consider the latter only since conventional sieve methods provide the best answers for almost-primes. We can ask for an integer m [member of] [n, n + [n.sup.1/2+[epsilon]]) to have a large prime factor, say >[n.sup.[theta]]. Again, increasing the value of [theta] increases the difficulty of the problem, but [theta] can be taken quite close to 1 (>25/26 ; see Chapter 5 here). For this problem one can reduce the size of the interval to [n, n + [n.sup.[alpha]]) with [alpha] [less than or equal to] 1/2, but the best exponent to date for [theta], even with [alpha] = 1/2 , is now substantially smaller (0.738 proved in, we give an improved result in Chapter 6 here).

Instead of considering all intervals, we can ask what happens almost always. That is, we consider intervals [x, x + y(x)) with x [less than or equal to] X but allow o(X) exceptions if x [member of] N. Equivalently, if x [member of] [1, [infinity]), we allow a set of exceptional x of measure o(X). Now the Riemann Hypothesis furnishes us with an almost perfect answer: One can take y(x) = [(log x).sup.2]. Even without this hypothesis one can still take y as quite a small power of x. Later in this work we shall require both the “all” and the “almost-all” results with primes restricted to arithmetic progressions with small modulus in order to apply the circle method to consider the distribution of Goldbach numbers (numbers represented as the sum of two primes) in short intervals. We shall also generalize our method to discuss Gaussian primes in small regions.

3. Primes in arithmetic progressions. Let a, q [member of] N, (a, q) = 1. By a famous result due to Dirichlet we know that there are infinitely many primes in the arithmetic progression a (mod q). The next natural questions to ask are: How big is the smallest such prime? How many such primes are there up to N? The smallest known value of ITLITL such that p <[q.sup.C],p [equivalent to] a (mod q) for all large q has become known as Linnik’s constant since Linnik was the first to show that such a ITLITL exists.

We would expect that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.1.1)

where [phi](q) is Euler’s totient function. The Generalized Riemann Hypothesis implies this result for N > [q.sup.2+[epsilon]]. Mention should also be made of recent work by Friedlander and Iwaniec assuming the existence of Siegel zeros. Unfortunately (1.1.1) is only known to be true unconditionally for N substantially larger than q. See for a thorough discussion of this question. However, it is possible to show that (1.1.1) is true on average for q [less than or equal to] [N.sup.1/2] [(log N).sup.-A] for some A (the Bombieri-Vinogradov theorem, which we prove in Chapter 2 here). As is well known, it is our ignorance concerning possible zeros of Dirichlet L-functions near the line Re s = 1 that causes a lot of trouble. We are able to replace (1.1.1) with upper and lower bounds over larger ranges of q with our methods. We can also show that for most q Linnik’s constant is not much larger than 2. Indeed, for almost all q we can show that it is actually less than 2. These results, although having importance in themeselves, have significance for other problems. For example, we can use average results on primes in arithmetic progressions to give good lower bounds for the greatest prime factor of p + a where p is a prime (see Chapter 8 here). Also, we can use results on primes in most arithmetic progressions to study Carmichael numbers. The techniques we use in this monograph do not appear capable of improving the best known value of Linnik’s constant (see [81]), however. The reader will see why later when we consider primes in individual arithmetic progressions subject to a certain condition.

4. Primes represented by additive forms. It is conjectured that if f(x) [member of] Z[x] is nonconstant with a positive leading term and irreducible, and if f(n) has no fixed prime divisor for n ? N, then f(n) will take on infinitely many prime values. Dirichlet’s theorem shows that this is true for linear polynomials, but there are no known results for higher degree. If one is allowed two variables, the case p = [m.sup.2] + [n.sup.2] is well understood, and the more general case of the sum of two quadratic polynomials has been studied. The first progress toward analogues for higher-degree forms came with the Friedlander and Iwaniec result that [m.sup.2] + [n.sup.4] takes on prime values infinitely often [37]. Indeed they were even able to furnish an asymptotic formula for the number of prime values taken as the region allowed for (m, n) expands. Further work was performed by Heath-Brown [82], who showed a similar result for [x.sup.3] + 2[y.sup.3]. We shall prove both of these results in this book, although we do not have the space to provide all the details.

1.2 THE SIEVE OF ERATOSTHENES

The ancient Greek mathematician and astronomer Eratosthenes is credited with being the first to observe that the primes up to a given number, say N, can be found simply as follows. We write down all the integers up to N and take 2 as the first prime; then we cross out all subsequent multiples of 2. In general, find the next uncrossed number as the next prime (so after 2 we find 3, of course) and cross out all of its multiples. This is easily demonstrated on a piece of paper or an overhead projector with the numbers up to 100, say, but I don’t know how to make it look exciting in print! (See Tables 1.1 and 1.2 below) The reader with an internet search should soon find a site that will give an animated version of the sieve, or one could quickly write one’s own program to do this task. By the 13th century A.D. it had been noticed that one needs only to cross out multiples of primes up to [square root of N] since all composite numbers up to N must have at least one prime factor not exceeding [square root of N]. The reader will note the problem with the number 1 – we must not cross out all its multiples, yet it is not a prime! Sometimes, even with quite sophisticated arguments it is still necessary to deal with the number 1 separately. Historically, 1 was originally considered to be a prime, of course.

Clearly the simple principle inherent in the sieve of Eratosthenes is not restricted just to finding the primes up to N. One can similarly “sieve” any given set of integers A by crossing out multiples of primes less than the square root of each number concerned. Nor need one only sieve to obtain primes. One could strike out all multiples of primes that divide some given integer q and thereby obtain the integers in a set coprime to q. As another example, one could cross out multiples of primes congruent to 3 (mod 4) to obtain those members of a set that are properly represented as a sum of two squares.

1.3 THE SIEVE OF ERATOSTHENES-LEGENDRE

In 1808 Legendre showed how the Sieve of Eratosthenes could be used to count the number of primes up to x. The crucial point is that one needs to distinguish between numbers that are crossed off once, twice, three times, and so on. If one estimates [pi](x) by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

one gets too small a number because many numbers are crossed off more than once. If one uses

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

one obtains too large a number because numbers crossed out three times, for example, are counted three times by the final sum. The formula Legendre produced needed a whole string of multiple sums that increase in number with x. Clearly this was in need of some notation to tidy up the expression. Some years later Mbius defined the function (n), which bears his name, by writing

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We take (1) = 1 since 1 has no prime factors and note that (n) is zero whenever n has a square factor exceeding 1. In other words, (n) is only nonzero for square-free n.

We then obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that the left-hand side of the Eratosthenes-Legendre formula is [pi](x)-[pi]([x.sup.1/2]+ 1 and not [pi](x) since we “sieve out” the primes up to [x.sup.1/2] and the number 1 is not sieved out at all on the right-hand side.

The formula can be proved directly by noting that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.3.1)

We shall find that this simple formula lies at the heart of much that follows throughout this book.

Clearly we can modify this formula in many ways. Say we want to determine whether an integer n is free of prime factors from some finite set P. Let Q be the product of the primes in P. We then have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(Continues…)

Excerpted from Prime-Detecting Sieves. by Glyn Harman Copyright © 2007 by Princeton University Press. Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.