Andrew Granville's Home Page

Recent research

In this Monthly note, we use Van der Waerden's Theorem and Fermat's Theorem on four squares in an arithmetic progression to prove that there are infinitely many primes.

We study the small scale distribution of the L^2-mass of eigenfunctions of the Laplacian on the the two-dimensional flat torus. Given an orthonormal basis of eigenfunctions, Lester and Rudnick showed the existence of a density one subsequence whose L^2-mass equidistributes more-or-less down to the Planck scale. We give a more precise version of their result showing equidistribution holds down to a small power of log above Planck scale, and also showing that the L^2-mass fails to equidistribute at a slightly smaller power of log above the Planck scale. This article rests on a number of results about the proximity of lattice points on circles, much of it based on foundational work of Javier Cilleruelo.

We discuss the mean values of multiplicative functions over function fields. In particular, we adapt the authors' new proof of Halasz's theorem on mean values to this simpler setting. Several of the technical difficulties that arise over the integers disappear in the function field setting, which helps bring out more clearly the main ideas of the proofs over number fields. We also obtain Lipschitz estimates showing the slow variation of mean values of multiplicative functions over function fields, which display some features that are not present in the integer situation.


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.


On ranks of quadratic twists of elliptic curves
(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 and Journal Link
We give bounds on the number of distinct differences \( N_a-a\) as \( a\) varies over all elements of a given finite set \( A \subset (\mathbb R/\mathbb Z)^d,\ d\geq 1\) and \( Na\) is a nearest neighbour to \( a\) .

Article and Journal Link

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

Let \( M(\chi)\) denote the maximum of \( |\sum_{n\le N}\chi(n)|\) for a given non-principal Dirichlet character \( \chi \pmod q\), and let \( N_\chi\) denote a point at which the maximum is attained. In this article we study the distribution of \( M(\chi)/\sqrt{q}\) as one varies over characters \( \pmod q\), where \( q\) is prime, and investigate the location of \( N_\chi\). We show that the distribution of \( M(\chi)/\sqrt{q}\) converges weakly to a universal distribution \( \Phi\), uniformly throughout most of the possible range, and get (doubly exponential decay) estimates for \( \Phi\)'s tail. Almost all \( \chi\) for which \( M(\chi)\) is large are odd characters that are \( 1\)-pretentious. Now, \( M(\chi)\ge |\sum_{n\le q/2}\chi(n)| = \frac{|2-\chi(2)|}\pi \sqrt{q} |L(1,\chi)|\), and one knows how often the latter expression is large, which has been how earlier lower bounds on \( \Phi\) were mostly proved. We show, though, that for most \( \chi\) with \( M(\chi)\) large, \( N_\chi\) is bounded away from \( q/2\), and the value of \( M(\chi)\) is little bit larger than \( \frac{\sqrt{q}}{\pi} |L(1,\chi)|\).


When the sieve works
(with Dimitris Koukoulopoulos 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.


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.


Selected expository articles