Prime chains and Pratt trees

DOI10.1007/S00039-010-0089-0MaRDI QIDQ607663zbMATH OpenOpenAlexFDO

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

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

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.

Review text

A prime chain is a sequence \(p_1,\ldots,p_k\) of primes for which \(p_{j+1}\equiv 1\pmod {p_j}\) for each \(j\). Let \(N(x,p)\) be the number of prime chains with \(p_1=p\) and \(\frac{p_k}{p_1}\leq x\). The authors prove that for \(p\geq 2\) and \(x\geq 20\) \[ N(x;p)\leq x\exp\left(\frac{\log x (\log\log\log x+O(1))}{\log \log x}\right). \] Let \(f(p)\) be the number of prime chains with \(p_k=p\). Then we have \[ f(p)\geq 0.378\log p \] for almost all primes \(p\). For all \(x\geq 3\) and any positive integer \(h\), \[ |\{p\leq x:f(p)=h\}|\leq \left(\frac{6\log x}{h}\right)^h. \] Let \(H(p)\) be the length of the longest prime chain with \(p_k=p\). It holds that \[ H(p)\leq (\log p)^{0.9503} \] for almost all \(p\). They introduce a probabilistic model of \(H(p)\), based on the theory of branching random walks, which suggests that for most \(p\leq x\), \(H(p)\) stays very close to \(e\log\log x\).

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

• Chernoff's theorem in the branching random walk
• Coincidences in the values of the Euler and Carmichael functions
• Common values of the arithmetic functions and
• Every Prime Has a Succinct Certificate
• 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?)
• 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 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 Lucas-Pratt primality tree
• The primes contain arbitrarily long arithmetic progressions
• Very Short Primality Proofs

Cited in

(8)

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

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)