Prime chains and Pratt trees

DOI10.1007/S00039-010-0089-0MaRDI QIDQ607663zbMATHOpenAlexFDO

Authors Kevin Ford, Sergei Konyagin, Florian Luca

Publication date 3 December 2010

Published in Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0904.0473

zbMATH Keywords

prime chains

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Distribution of primes (11N05) Applications of sieve methods (11N36)

Abstract: We study the distribution of prime chains, which are sequences p_1,...,p_k of primes for which p_{j+1}equiv 1pmod{p_j} for each j. We give estimates for the number of chains with p_kle x (k variable), and the number of chains with p_1=p and p_k le px. The majority of the paper concerns the distribution of H(p), the length of the longest chain with p_k=p, which is also the height of the Pratt tree for p. We show H(p)ge cloglog p and H(p)le (log p)^{1-c'} for almost all p, with c,c' explicit positive constants. We can take, for any epsilon>0, c=e-epsilon assuming the Elliott-Halberstam conjecture. A stochastic model of the Pratt tree, based on a branching random walk, is introduced and analyzed. The model suggests that for most p, H(p) stays very close to e loglog p.

Recommendations

• Long Chains of Nearly Doubled Primes
• Chains of Large Gaps Between Primes
• scientific article; zbMATH DE number 1643954
• scientific article; zbMATH DE number 572155
• Sieving Very Thin Sets of Primes, and Pratt Trees with Missing Primes

Cites work

• scientific article; zbMATH DE number 3467229 (Why is no real title available?)
• scientific article; zbMATH DE number 1542664 (Why is no real title available?)
• scientific article; zbMATH DE number 2206373 (Why is no real title available?)
• scientific article; zbMATH DE number 3018543 (Why is no real title available?)
• Chernoff's theorem in the branching random walk
• Coincidences in the values of the Euler and Carmichael functions
• Common values of the arithmetic functions \(\varphi\) and \(\sigma\)
• Every Prime Has a Succinct Certificate
• Integers without large prime factors
• Irreducible radical extensions and Euler-function chains
• Limit theorems for the minimal position in a branching random walk with independent logconcave displacements
• Minima in branching random walks
• Minimal positions in a branching random walk
• Number of prime divisors of \(\varphi_ k(n)\), where \(\varphi_ k\) is the \(k\)-fold iterative of \(\varphi\)
• On the Asymptotic Distribution of Large Prime Factors
• On the distribution of large prime divisors
• On the normal number of prime factors of \(\phi(n)\)
• On values taken by the largest prime factor of shifted primes
• Poisson-Dirichlet branching random walks
• Shifted primes without large prime factors
• Smooth Values of the Iterates of the Euler Phi-Function
• Some problems on the iteration of multiplicative number-theoretical functions
• The Lucas-Pratt primality tree
• The first- and last-birth problems for a multitype age-dependent branching process
• The iterated Carmichael λ-function and the number of cycles of the power generator
• The primes contain arbitrarily long arithmetic progressions
• Very Short Primality Proofs

Cited in

(7)

• Pairing inversion for finding discrete logarithms
• Sums of two squares in short intervals
• Poisson-Dirichlet branching random walks
• On a recursively defined sequence involving the prime counting function
• Two remarks on iterates of Euler's totient function
• Long Chains of Nearly Doubled Primes
• scientific article; zbMATH DE number 1643954 (Why is no real title available?)

This page was built for publication: Prime chains and Pratt trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q607663)