Prime Chains and Pratt Trees

Kevin Ford, Sergei V. Konyagin, Florian Luca

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1231-1258
Number of pages28
JournalGeometric and Functional Analysis
Volume20
Issue number5
DOIs
StatePublished - Nov 2010

Keywords

  • Pratt trees
  • Prime chains
  • branching random walks

ASJC Scopus subject areas

  • Analysis
  • Geometry and Topology

Fingerprint Dive into the research topics of 'Prime Chains and Pratt Trees'. Together they form a unique fingerprint.

Cite this