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 project

Article

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

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

Article
In Italian: Article