Analytic and Geometric Number Theory Seminar

A sequence of primes $p_1, \dotsc , p_k$ is a prime chain if $p_{j+1} \equiv 1 \pmod{p_j}$ for each $j$. For example: 3, 7, 29, 59. We describe new estimates for counts of prime chains satisfying various properties, e.g. the number of chains with $p_k \leq x$ and the number of chains with $p_1=p$ and $p_k \leq x$. We discuss some applications of these estimates, in particular the settling of a 50-year old conjecture of Erdős that $\phi(a) = \sigma(b)$ has infinitely many solutions ($\phi$ is Euler’s function, $\sigma$ is the sum of divisors function). We also focus on the distribution of $H(p)$, the length of the longest chain ending at a given prime p. $H(p)$ has another interpretation as the height of the Pratt tree for a prime $p$, defined recursively as the tree with root node $p$, and below $p$ are links to the prime factors $q$ of $p-1$, below each $q$ are links to the prime factors of $q-1$, and so on. In 1975, Pratt used this tree in conjunction with Lucas’s 1876 primality proving method to show that every prime has a short certificate (proof) of primality. We give new, nontrivial bounds for $H(p)$, valid for almost all $p$. The proof settles a conjecture of Erdős, Granville, Pomerance and Spiro. We describe a random model of the tree, based on branching random walks, which leads to some surprising conjectures about the distribution of $H(p)$. This is joint work with Sergei Konyagin and Florian Luca.