Andrew Granville's Home Page

2008 Publications

Irreducibility and Greatest Common Divisor Algorithms for Sparse Polynomials (with Mike Filaseta and Andrzej Schinzel)
Number Theory and Polynomials, London Math. Soc lecture notes, 352 (2008), 155--176.

We give an algorithm to determine whether a non-reciprocal polynomial of degree \( n\) is irreducible over the integers, that runs in time \( O(\log n (\log\log n)^2 \log\log\log n) \).


Prime number patterns
American Mathematical Monthly, 115 (2008), 279--296.

We develop various consequences of the Green-Tao theorem, for example showing that there exist polynomials of any given degree whose first \( k\) values are prime, and proving that there are magic squares of primes of arbitrary size.


Running time predictions for factoring algorithms (with Ernie Croot, Robin Pemantle and Prasad Tetali)
Algorithmic Number Theory, ANTS VIII, Banff, Springer LNCS, 5011 (2008), 1-36.

We discuss our belief that factoring algorithms almost always run in a time \( \sim J_0(n)\) to factor a given integer \( n\). Our work allows us to make very precise comparisons of the running times of the variants of the quadratic sieve, particularly the large prime variations.


Poisson statistics via the Chinese Remainder Theorem (with Par Kurlberg)
Advances in Mathematics, 218 (2008), 2013-2042.

We given conditions on subsets of the residues modulo coprime integers \( m\) and \( n\), which guarantee that the spacings between the residues mod \( mn\), constructed by the Chinese Remainder Theorem, are Poisson. This implies the results already extant in the literature.

Pretentious multiplicative functions and an inequality for the zeta-function (with K. Soundararajan)
Anatomy of Integers, CRM Proceedings, 46 (2008), 1191--198.

We note how several central results in multiplicative number theory may be rephrased naturally in terms of multiplicative functions \( f\) that pretend to be another multiplicative function \( g\). We formalize a `distance' which gives a measure of such pretentiousness, and as one consequence obtain a curious inequality for the zeta-function.


The number of possibilities for random dating (with Aaron Abrams and Rod Canfield)
Journal of Combinatorial Theory, Series A, 115 (2008), 1265--1271.

Let \( G\) be a regular graph and \( H\) a subgraph on the same vertex set. We give surprisingly compact formulas for the number of copies of \( H\) one expects to find in a random subgraph of \( G\).


Analytic Number Theory
Princeton Companion to Mathematics (eds. T. Gowers et al) PU press, 2008, 322-348

An introduction to analytic number theory for Gowers' interesting mathematical writing project


Smooth numbers: Computational number theory and beyond
Algorithmic number theory, MSRI Proceedings, 44 (2008), 267--323.

The analysis of many number theoretic algorithms turns on the role played by integers which have only small prime factors; such integers are known as "smooth numbers". To be able to determine which algorithm is faster than which, it has turned out to be important to have accurate estimates for the number of smooth numbers in various sequences. In this chapter, we will first survey the important estimates for application to computational number theory questions, results as well as conjectures, before moving on to give sketches of the proofs of many of the most important results. After this, we will describe applications of smooth numbers to various problems in different areas of number theory. More complete surveys, with many more references, though with a different focus, were given by Norton in 1971, and by Hildebrand and Tenenbaum in 1993.


The Fundamental Theorem of Arithmetic
La matematica, Problemi e teoremi, Einaudi, 2 (2008), 131-166.

An essay on the fundamental theorem, and subsequent developments, for an Italian mathematics encyclopaedia

In Italian: Article