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) \).Article

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.Article

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. Article

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.
Article

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.Article

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\).Article

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

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.Article