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 -