'Sieving' Prime Numbers From Thin Ore

Like prospectors, mathematicians who study prime numbers would like to know how these unusual numbers are scattered through the ore of other integers. Now they have a new prospecting tool. Researchers report in a paper to appear in the Annals of Mathematics that they have developed a powerful new "sieve" for estimating the abundance of primes in sparse sequences of integers, which have been difficult or impossible to assay until now.

To find these cherished numbers, John Friedlander of the University of Toronto and Henryk Iwaniec of Rutgers University in New Jersey have refined a tool known as the asymptotic sieve, developed in the 1970s by Enrico Bombieri of the Institute for Advanced Study in Princeton. Roughly speaking, a mathematical sieve determines the abundance of primes in a long list of numbers by estimating how many numbers remain when multiples of small primes are removed--a procedure that sifts out most composite numbers. But errors can creep into the procedure. The errors are easiest to estimate for "dense" sequences such as 1, 5, 9, 13--a progression that contains roughly one-fourth of all numbers up to a given size.

Friedlander and Iwaniec, however, set out to analyze a sequence consisting of numbers of the form a2 + b4, which contains a tiny fraction of the integers up to any particular number. This "thinness" puts the sequence, and others like it, out of reach of previous sieve techniques. But with their new sieve, the two mathematicians proved that the sequence includes infinitely many primes. "Nobody dreamed you could analyze such sequences," says Bombieri.

The sieve relies on the special algebraic properties of the formula a2 + b4. In a number system known as the Gaussian integers, which enlarges the ordinary integers by including i, the square root of -1, such sums can always be factored as (a + b2i)(a - b2i). By putting the numbers in their sequence into this form, Friedlander and Iwaniec found that they had far more control over the errors when they applied their sieve.

Because the technique relies on properties found in only a small fraction of sequences, it won't solve many of sieve theory's dearest problems--proving, for example, that each interval between consecutive squares contains at least one prime. "The answer to most of these questions is, we don't know," says Andrew Granville, a number theorist at the University of Georgia.

Follow News from Science

A 3D plot from a model of the Ebola risk faced at different West African regions over time.
dancing shoes