Andrew Granville's Home Page

Recent research

Big biases amongst products of two primes
(with David Dummit and Hershy Kisilevsky)

David Dummit and Hershy Kisilevsky observed from calculation that the Legendre symbols \( (p/q) \) and \( (q/p) \) are unequal for rather more than a quarter of the pairs of odd primes \(p\) and \(q\) with \(pq\leq x\), during some calculations. In fact almost \( 30 \% \) of the \(pq\)'s up to a million satisfy \( p\equiv q\equiv 3 \pmod 4\). Together we found that this is no accident and that the bias up to \(x\) is roughly \( 1 +1/3(\log\log x-1)\). This is a much stronger bias than the traditional "prime race" problem. When doing the math one finds that this problems about \(pq\)'s is equivalent to the prime race problem, for primes \(=3 \pmod 4\) versus those \(=1 \pmod 4\), in which we weight each prime by its reciprocal.

Article

On ranks of quadratic twists of elliptic curve
(with Mark Watkins, Steve Donnelly, Noam Elkies, Tom Fisher and Nick Rogers)

Some years ago I presented a heuristic that, in the family of quadratic twists of a given elliptic curve, the rank is absolutely bounded, the proposed bound depending only on the number of rational 2-torsion points. At the time this contradicted the popular belief. Mark Watkins took it upon himself to do a massive calculation of ranks of quadratic twists of the congruent number curve, to test out my "conjecture". This paper is the record of an enormous calculation, performed under Mark's leadership, involving the incredibly sophisticated algorithms and ideas of the other co-authors (Stephen Donnelly, Noam Elkies, Tom Fisher,and Nick Rogers). The evidence is as compelling as we have any right to hope for, suggesting that the quadratic twists all have rank less than or equal to 7.

Article
****

Article

The frequency and the structure of large character sums
(with Jonathan Bober, Leo Goldmakher and Dimitris Koukoulopoulos)

****

Article

When the sieve works
(with Dimitris Koukoulopoulo and Kaisa Matomäki)

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 Matomäki and I show that there exists a constant \( \kappa >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 \( > \kappa\), then the number of integers left unsieved is roughly as one might guess. Moreover we conjecture that one can take any \( \kappa>1\), and speculate that an analogous result may be true when sieving any interval. The proof revolves around a quantitative estimate for additive combinatorics for sumsets.

Article

An accurate running time estimate for the quadratic sieve
(with Ernie Croot, Robin Pemantle and Prasad Tetali)

In 1994, Pomerance noted that part of the analysis of the running time of many of the key factoring algorithms amounted to the following question: "Randomly" select integers from \( 1,2,..,x \) until the product of some subset of these integers equals a square. Each different factoring algorithm gives rise to a different notion of "random", but Pomerance proposed investigating the problem when "random" means each integer occurs with equal probability. Schroeppel's practical method is to look for such "square products" only among those integers whose prime factors are all \( \leq y(x)\) (chosen optimally). His algorithm will find a square product after one has selected \( f(x)\) integers for a certain function \( f\), with probability tending to \( 1\). In joint work with Ernie Croot, Robin Pemantle and Prasad Tetali, we conjecture that in Pomerance's problem there is a "sharp transition", in that, with probability tending to \( 1\), there is no square product after one has selected \( (e^{-\gamma}-\epsilon) f(x) \) integers but there is a square product after one has selected \( (e^{-\gamma}+\epsilon) f(x) \) integers. Moreover we prove the second statement, unconditionally, using random graph theory.

Article

Selected expository articles