Type: Article

Prime chains and Pratt trees

Kevin Ford; Sergei V. Konyagin; Florian Luca;

Abstract:

Prime chains are sequences p(1), ..., p(k) of primes for which p(j+1) equivalent to 1 (mod p(j)) for each j. We introduce three new methods for counting long prime chains. The first is used to show that N(x; p) = O(epsilon)(x(1+epsilon)), where N(x; p) is the number of chains with p(1) = p and p(k) <= px. The second method is used to show that the number of prime chains ending at p is asymptotic to log p for most p. The third method produces the first nontrivial upper bounds on H(p), the length of the longest chain with p(k) = p, valid for almost all p. As a consequence, we also settle a conjecture of Erdos, Granville, Pomerance and Spiro from 1990. A probabilistic model of H(p), based on the theory of branching random walks, is introduced and analyzed. The model suggests that for most p <= x, H(p) stays very close to e log log x.