A sequence of primes $p_1,ldots,p_k$ is a prime chain if $p_{j+1}equiv 1 pmod{p_j}$ for each $j$. For example: 3, 7, 29, 59. Wedescribe new estimates for counts of prime chains satisfying variousproperties, e.g. the number of chains with $p_kle x$ and the number ofchains with $p_1=p$ and $p_kle x$. We discuss some applications of theseestimates, in particular the settling of a 50-year old conjecture of ErdHos that $phi(a)=sigma(b)$ has infinitely many solutions ($phi$ isEuler's function, $sigma$ is the sum of divisors function). We also focuson the distribution of $H(p)$, the length of the longest chain ending at agiven prime $p$. $H(p)$ has another interpretation as the height of thePratt 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, Prattused this tree in conjunction with Lucas' 1876 primality proving method toshow that every prime has a short certificate (proof) of primality. Wegive new, nontrivial bounds for $H(p)$, valid for almost all $p$. Theproof settles a conjectue of Erdos, Granville, Pomerance and Spiro. Wedescribe 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.
Penn Mathematics Colloquium
Wednesday, February 24, 2010 - 4:30pm
Kevin Ford
University of Illinois at Urbana-Champaign & IAS