Growth of prime chains $p_{i+1}\equiv 1\pmod{p_i}$: is $\lim_k p_k^{1/k}=\infty$? (Erdős #695)
Statement
Let $p_1<p_2<\cdots$ be a sequence of primes with $p_{i+1}\equiv 1\pmod{p_i}$ for every $i$ (a prime chain). Is it true that $$\lim_{k\to\infty} p_k^{1/k}=\infty?$$ Does there exist such a sequence with $$p_k\leq \exp\!\big(k(\log k)^{1+o(1)}\big)?$$
Acceptance. FULLY RESOLVES (proof-shaped): a complete rigorous proof — a Lean/Coq formalisation preferred, otherwise a full written proof — that establishes $\lim_k p_k^{1/k}=\infty$ for every prime chain (or exhibits a chain violating it), and/or constructs a prime chain with $p_k\leq \exp(k(\log k)^{1+o(1)})$. ADVANCES: an unconditional construction of a prime chain growing strictly slower than the greedy Linnik bound stated in the background ($p_k\leq e^{e^{O(k)}}$); a proof of a nontrivial lower bound on the growth of every prime chain; or a reproducible computation extending OEIS A061092 or the record shortest prime chains, with the search code. Deliver the proof, the explicit construction, or the search program plus attained chains.
Background
Posed by Erdős [Er79e] and listed as open on erdosproblems.com/695 (fetched 2026-07-21, status 'open'). A sequence of primes in which each divides one less than the next is called a prime chain. The greedy chain ($p_1=2$, $p_{i+1}$ the smallest prime $\equiv 1\pmod{p_i}$) grows at most like $p_k\leq e^{e^{O(k)}}$ by Linnik's theorem on the least prime in an arithmetic progression. It is conjectured that for every prime $p$ there is a prime $p'\leq p(\log p)^{O(1)}$ with $p'\equiv 1\pmod p$, which would yield a chain with $p_k\leq \exp(k(\log k)^{1+o(1)})$. The growth of finite prime chains was studied in depth by Ford, Konyagin, and Luca [FKL10]. A Lean formalisation exists. Related OEIS sequence A061092; see also Erdős #696 (erdosproblems.com/696). Attacker's tool: sieve / analytic bounds on least primes in arithmetic progressions (Linnik-type), together with large-scale computation constructing short prime chains to extend A061092 and empirically test the conjectured growth rate.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #695 (T. F. Bloom) | website |
| REF-02 | OEIS A061092 | website |
| REF-03 | Lean formalisation (DeepMind formal-conjectures) #695 | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.