Prime Chains and Pratt Trees

Prime chains are sequences $p_{1}, \ldots , p_{k}Prime chains are sequences p₁, ?, p_kp_{1}, \ldots , p_{k} of primes for which p_j+1 o 1{p_{j+1} \equiv 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_e(x^1+e){N(x; p) = O_{\varepsilon}(x^{1+\varepsilon})}, where N(x; p) is the number of chains with p ₁ = p and p_k ￡ p_x{p_k \leq p_x}. The second method is used to show that the number of prime chains ending at p is ≍ 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 Erdős, 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{p \leq x}, H(p) stays very close to e log log x.