TY - JOUR

T1 - Prime Chains and Pratt Trees

AU - Ford, Kevin

AU - Konyagin, Sergei V.

AU - Luca, Florian

N1 - Funding Information:
Keywords and phrases: Prime chains, Pratt trees, branching random walks 2010 Mathematics Subject Classification: Primary 11N05, 11N36; Secondary 60J80 The research of K.F. was supported in part by NSF grants DMS-0555367 and DMS-0901339, that of S.K. was supported in part by Grant 08-01-00208 from the Russian Foundation for Basic Research, and that of F. L. was supported in part by projects PAPIIT 100508 and SEP-CONACyT 79685. Some of this work was accomplished while the third author visited the University of Illinois at Urbana-Champaign in February 2007, supported by NSF grant DMS-0555367. The first and second authors enjoyed the hospitality of the Institute for Advanced Study, where some of this work was done in November 2007 and spring 2010, the first author being supported by The Ellentuck Fund and The Friends of the Institute for Advanced Study. The first author was also supported by the NSF sponsored Workshop in Linear Analysis and Probability at Texas A&M University, August 2008.

PY - 2010/11

Y1 - 2010/11

N2 - Prime chains are sequences p1,...,pκ of primes for which pj+1≡1(mod pj) for each j. We introduce three new methods for counting long prime chains. The first is used to show that N(x;p)= O(x1+), where N(x; p) is the number of chains with p1 = p and pκ≤px. 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κ = p, valid for almost all p. As a consequence, we also settle a conjecture of Erdo{double acute}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, H(p) stays very close to e log log x.

AB - Prime chains are sequences p1,...,pκ of primes for which pj+1≡1(mod pj) for each j. We introduce three new methods for counting long prime chains. The first is used to show that N(x;p)= O(x1+), where N(x; p) is the number of chains with p1 = p and pκ≤px. 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κ = p, valid for almost all p. As a consequence, we also settle a conjecture of Erdo{double acute}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, H(p) stays very close to e log log x.

KW - Pratt trees

KW - Prime chains

KW - branching random walks

UR - http://www.scopus.com/inward/record.url?scp=78649319398&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78649319398&partnerID=8YFLogxK

U2 - 10.1007/s00039-010-0089-0

DO - 10.1007/s00039-010-0089-0

M3 - Article

AN - SCOPUS:78649319398

SN - 1016-443X

VL - 20

SP - 1231

EP - 1258

JO - Geometric and Functional Analysis

JF - Geometric and Functional Analysis

IS - 5

ER -