Andrew Granville's Home Page


Montreal Number Theory webpage (including Quebec-Vermont seminar, and analytic number theory seminar)

Number Theory, special year at the CRM, 2014-15: From Arithmetic Statistics to Zeta elements

Other Seminars


Course Notes

Useful references

Number theory journals

My Recent Research

When the sieve works

We are sieving a set of size X (perhaps the integers in an interval) with the primes for a given set P. The "probability" that a given element of our set is divisible by p, from P, is about 1/p. In order to use some sort of inclusion-exclusion argument, we will need to know the "probability" that a given element of our set is divisible by pq, with p,q from P. We expect this to be 1/pq, but if pq>X then this will have to rather inaccurate. So the many wonderful results of sieve theory typically work under the assumption the primes in P are less than X^(1/2).

But what if we allow some of the primes in P to be greater than X^(1/2) ? We know many examples where the number of integers left unsieved is far less than one might guess, in this case. In this article Dimitris Koukoulopoulos, Kaisa Matomaki and I show that there exists a constant k>1 such that if we are sieving the interval [1,X], and the sum of the reciprocals of the primes up to X that are not in P, is >k, then the number of integers left unsieved is roughly as one might guess. Moreover we conjecture that one can take any k>1, and speculate that an analogous result may be true when sieving any interval.

The proof revolves around a quantative estimate for additive combinatorics for sumsets.

The number of sumsets in a finite field

An accurate running time estimate for the quadratic sieve

The central limit theorem and the Chinese Remainder Theorem

Selected expository articles

  • Don't be seduced by the zeros!
  • Different approaches to the distribution of primes
  • The Princeton Companion to Mathematics: Analytic number theory
  • Prime number patterns (2009 Ford Prize)
  • It is easy to determine whether a given integer is prime (2008 Chauvenet Prize)
  • Prime number races (2007 Ford Prize)
  • It's as easy as abc
  • Zaphod Beeblebrox's brain and the fifty-ninth row of Pascal's triangle (1995 Hasse Prize)
  • Publications

    Short resumé

    Upcoming Travel Calendar

    Mar 28-30, 2014: Yale math morning and colloquium
    Apr 26, 2014: MSRI Math Lovers forum
    May 29-30, 2014: Number fields and function fields, Royal Society, Chicheley Hall, Bucks
    June 23-July 4, 2014: Summer school on Counting Arithmetic Objects, CRM, Montreal
    July 9-25, 2014: Summer School on Analytic Number Theory, IHES, Paris
    Sept 15-19, 2014: Statistics and number theory, CRM, Montreal
    Sept 22-26, 2014: LMS-CMI Research school on Bounded Gaps Between Primes, Oxford
    Sept 29-Oct 3, 2014: CMI workshop, Analytic number theory, Oxford
    Oct 6-10, 2104: Additive Combinatorics and expanders, CRM, Montreal
    Nov 10-14, 2014: Counting arithmetic objects, CRM, Montreal
    Dec 8-12, 2014: Probabilistic and multiplicative number theory, CRM Montreal

    Contact Information

    Need a reference?

    Public lectures

    Primes, including an animation

    MSI: Anatomy of Integers and Permutations

    Of general interest

    Many of the papers of Paul Erdos

    CRM-ISM Postdoctoral Fellowships

    Best Professions in 2010?

    Thanking our sponsors

    Differences in pure and applied math and stats?