# Patterns in the Primes

Questions abound in the realm of prime numbers: How many primes are there? How many primes fall within certain patterns? How are primes spaced? Is there a way to tell quickly whether a number is prime?

Versions of such questions are among the most difficult open problems in mathematics, number theorist Andrew Granville recently told a large audience at the MAA's Carriage House Conference Center. "Primes," he noted, "are the building blocks from which the integers are made, and so it is of interest to understand how they are distributed."

Granville, who holds the Canadian Research Chair in number theory at the University of Montreal, addressed a variety of issues concerning primes, noting spectacular recent progress on several of the questions, despite their apparent difficulty. Granville's talk, "Patterns in the Primes," was the latest presentation in the MAA's Distinguished Lecture Series, sponsored by the National Security Agency.

Granville started with Euclid's proof that there are infinitely many primes. He then presented a new, quite different way of proving the infinitude of primes—indeed, one that offers infinitely many proofs—using dynamical systems.

Granville then moved on to the question of whether there are formulas that take on only prime values, starting with Fermat's conjecture that 22^n + 1 is prime for all n greater than or equal to 0. He went on to discuss polynomials that have lots of prime values, such as 6n + 5 and n2 + n + 41, and showed that no polynomial can ever take only prime values. On the other hand, the question of whether a polynomial of degree greater than 1 can take prime values infinitely often, even when every value is not a prime, remains open.

Granville then examined various attempts to find easy ways to identify primes, including an ingenious method proposed by Y.V. Matijasevic in 1971 and another invented by John Conway. He illustrated Conway's method using an entertaining animation by Anthony Doran called "Conway's Prime-Producing Machine."

Granville's presentation of how to identify primes quickly included a discussion of Fermat's Little Theorem (1640) and the extraordinary 2002 discovery by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena of a method that recognizes primes in polynomial time.

Granville delved into various historical efforts to try to understand the distribution of prime numbers, including Carl Friedrich Gauss's early estimate of the density of primes and the Riemann Hypothesis.

In returning to the topic of polynomials with prime values, Granville looked at several special cases: Are there polynomials whose first m values are all prime? Can one have arbitrarily many consecutive prime values? A.G. Van der Corput, for example, proved in 1939 that there are infinitely many linear polynomials whose first three values are prime. Antal Balog demonstrated in 1990 that there are infinitely many degree-d polynomials whose first 2d + 1 values are prime. In a recent breakthrough, Ben Green and Terrence Tao proved that there are infinitely many k-term arithmetic progressions of primes.

As an application of the powerful Green-Tao theorem, Granville proved the existence of n x n magic squares of primes, where the sum of each row, column, and diagonal is identical. The same theorem can be used to prove a variety of other questions concerning primes, he pointed out.

Granville's final topic was the size of gaps between consecutive primes, including the still-open conjecture that there are infinitely many twin primes and recent work by Green and Tao to tackle additional longstanding questions related to the distribution of primes.

Granville's lecture provided illuminating glimpses of exciting contemporary efforts to understand and elucidate patterns in the primes. —H. Waldman

An Interview with Andrew Granville

This MAA Distinguished Lecture was funded by the National Security Agency.