Prime chains and Pratt trees

DOI10.1007/S00039-010-0089-0zbMATH Open1218.11085arXiv0904.0473OpenAlexW2026158180MaRDI QIDQ607663FDOQ607663

Authors: Kevin Ford, Sergei Konyagin, Florian Luca 

Publication date: 3 December 2010

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

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.

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

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

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)

Cites Work

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

Cited In (7)

• On a recursively defined sequence involving the prime counting function
• Sums of two squares in short intervals
• Pairing inversion for finding discrete logarithms
• Poisson-Dirichlet branching random walks
• Long Chains of Nearly Doubled Primes
• Two remarks on iterates of Euler's totient function
• Title not available (Why is that?)

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)