Andrew Granville's Home Page

Preprints submitted for publication

Sieve weights and their smoothings
(with Dimitris Koukoulopoulos and James Maynard)

We obtain asymptotic formulas for the \( 2k\)th moments of partially smoothed divisor sums of the M\"obius function. When \( 2k\) is small compared with \( A\), the level of smoothing, then the main contribution to the moments come from integers with only large prime factors, as one would hope for in sieve weights. However if \( 2k\) is any larger, compared with \( A\), then the main contribution to the moments come from integers with quite a few prime factors, which is not the intention when designing sieve weights. The threshold for ``small'' occurs when \( A=\frac 1{2k} \binom{2k}{k}-1\). One can ask analogous questions for polynomials over finite fields and for permutations, and in these cases the moments behave rather differently, with even less cancellation in the divisor sums. We give, we hope, a plausible explanation for this phenomenon, by studying the analogous sums for Dirichlet characters, and obtaining each type of behaviour depending on whether or not the character is ``exceptional''.

Part-and-parcel of the study of ``multiplicative number theory'' is the study of the distribution of multiplicative functions \( f\) in arithmetic progressions. Although appropriate analogies to the Bombieri-Vingradov Theorem have been proved for particular examples of multiplicative functions, there has not previously been headway on a general theory; seemingly none of the different proofs of the Bombieri-Vingradov Theorem for primes adapt well to this situation. In this article we prove that such a result has been so elusive because \( f \) can be ``pretentious'' in two different ways. Firstly it might correlate with a character of small conductor, which can be ruled out by assuming a ``Siegel-Walfisz'' type criterion for \( f\). Secondly \( f\) might be particularly awkward on large primes, and this can be avoided by restricting our attention to smoothly supported \( f\). Under these assumptions we recover a Bombieri-Vingradov Theorem for multiplicative \( f\). For a fixed residue class \( a\) we extend such averages out to moduli \( \leq x^{\frac {20}{39}-\delta}\) .

Let \( f\) and \( g\) be \( 1\)-bounded multiplicative functions for which \( f*g=1_{.=1}\). The Bombieri-Vinogradov Theorem holds for both \( f\) and \( g\) if and only if the Siegel-Walfisz criterion holds for both \( f\) and \( g\), and the Bombieri-Vinogradov Theorem holds for \( f\) restricted to the primes.


A new proof of Halasz's Theorem, and its consequences
(with Adam Harper and K. Soundararajan)

Halasz's Theorem gives an upper bound for the mean value of a multiplicative function \( f\). The bound is sharp for general such \( f\), and, in particular, it implies that a multiplicative function with \( |f(n)|\le 1\) has either mean value \( 0\), or is ``close to" \( n^{it}\) for some fixed \( t\). The proofs in the current literature have certain features that are difficult to motivate and which are not particularly flexible. In this article we supply a different, more flexible, proof, which indicates how one might obtain asymptotics, and can be modified to short intervals and to arithmetic progressions. We use these results to obtain new, arguably simpler, proofs that there are always primes in short intervals (Hoheisel's Theorem), and that there are always primes near to the start of an arithmetic progression (Linnik's Theorem).


Natural exact covering systems and the reversion of the M\"obius series
(with Ian Goulden, L. Bruce Richmond and Jeffrey Shallit)

Let \( a_n\) denote the number of natural exact covering systems of cardinality \( n \) and let \( A(x)=\sum_{n\geq 1} a_nx^n.\) If \( M(x)=\sum_{n\geq 1} \mu(n)x^n\) then \( A(M(x))=M(A(x))=x.\) Using this result, we deduce an asymptotic expression for \( a_n\) .