Erdős Problem #695

Erdős Problem 695 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/695.tex.

REUSED SOURCE 1

1) FORMAL RESTATEMENT

A prime chain is a strictly increasing sequence of primes $p_1<p_2<\cdots$ such that \[ p_{i+1}\equiv 1\pmod{p_i}\quad\text{for all }i\ge 1. \] Question (growth): Is it true that for every such infinite chain, \[ \lim_{k\to\infty} p_k^{1/k}=\infty\ ? \] Equivalently, is it necessary that $\log p_k / k \to \infty$?

Question (existence of slow chains): Does there exist a prime chain with \[ p_k\le \exp\big(k(\log k)^{1+o(1)}\big)\quad\text{as }k\to\infty? \]

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement notes that for the greedy chain (each step chooses the least prime $\equiv 1\pmod{p_i}$) one can use Linnik's theorem to obtain an upper bound of the form $p_k\le e^{e^{O(k)}}$, and that a conjectural bound on least primes in progressions would imply $p_k\le \exp(k(\log k)^{1+o(1)})$. I do not use any results beyond what is explicitly stated here.

3) ATTACK PLAN

Proof track (force superexponential growth): derive unavoidable lower bounds on multipliers $m_i=(p_{i+1}-1)/p_i$ and show their product must grow faster than $c^k$.

Disproof track (construct slow chain): attempt to build an infinite chain with bounded or slowly growing multipliers (e.g. always $m_i=2$ gives $p_{i+1}=2p_i+1$), but primality constraints are difficult.

I provide unconditional lower bounds and computational sanity checks; the main growth questions remain open here.

4) WORK

Lemma 695.1 (Parity forces doubling from the second step). Let $p_i$ be an odd prime. If $p_{i+1}\equiv 1\pmod{p_i}$ and $p_{i+1}>2$, then \[ p_{i+1}\ge 2p_i+1. \] Consequently, any prime chain satisfies $p_{i+1}\ge 2p_i+1$ for all $i\ge 2$.

Proof. Write $p_{i+1}=1+m p_i$ for some integer $m\ge 1$. If $p_i$ is odd then $m p_i$ has the same parity as $m$, hence $p_{i+1}=1+m p_i$ is even iff $m$ is odd.

For $p_{i+1}$ to be a prime strictly larger than $2$, it must be odd. Therefore $m$ must be even, so $m\ge 2$. Hence \[ p_{i+1}=1+m p_i\ge 1+2p_i. \] In any chain, $p_2$ is odd, so the conclusion applies for all $i\ge 2$. $\square$

Lemma 695.2 (Exponential lower bound on $p_k$). For any prime chain $(p_k)$, \[ p_k\ge 2^{k-2}p_2 + (2^{k-2}-1)\quad\text{for all }k\ge 2. \] In particular, if $p_1=2$ then $p_2\ge 3$ and thus $p_k\ge 3\cdot 2^{k-2}+ (2^{k-2}-1)=4\cdot 2^{k-2}-1=2^{k}-1$ for all $k\ge 2$.

Proof. For $i\ge 2$, Lemma 695.1 gives $p_{i+1}\ge 2p_i+1$. We prove by induction on $k\ge 2$ the stronger inequality \[ p_k\ge 2^{k-2}p_2 + (2^{k-2}-1). \] Base case $k=2$ is equality. Assume it holds for $k$. Then \[ p_{k+1}\ge 2p_k+1\ge 2\big(2^{k-2}p_2 + (2^{k-2}-1)\big)+1=2^{k-1}p_2+(2^{k-1}-1), \] which is the desired statement for $k+1$. This completes the induction.

If additionally $p_1=2$, then $p_2$ is an odd prime so $p_2\ge 3$. Plugging into the bound yields $p_k\ge 3\cdot 2^{k-2}+(2^{k-2}-1)=2^k-1$ for $k\ge 2$. $\square$

FAST REALITY CHECK (greedy chain computation). Taking the greedy chain starting at $p_1=2$ (each $p_{i+1}$ the smallest prime $\equiv 1\pmod{p_i}$), a local primality search gives the first terms: \[ ( p_1,\dots,p_{10})=(2,3,7,29,59,709,2837,22697,590123,1180247). \] For $k=10$ this gives $p_{10}^{1/10}\approx 4.0476$.

5) VERIFICATION

- Lemma 695.1 relies only on parity and the fact that primes $>2$ are odd.

- Lemma 695.2 is a straightforward induction using Lemma 695.1.

- The computed greedy-chain values were verified by direct congruence checks in the script (each $p_{i+1}=1+m p_i$ with integer $m$ and primality test).

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. Any prime chain grows at least exponentially: $p_{i+1}\ge 2p_i+1$ for $i\ge 2$ (Lemma 695.1) and hence $p_k\ge 2^k-1$ for $k\ge 2$ when $p_1=2$ (Lemma 695.2).

(ii) First gap (crisp). Decide whether every infinite prime chain must satisfy $\log p_k/k\to\infty$ (equivalently $p_k^{1/k}\to\infty$), or construct an infinite chain with $p_k^{1/k}$ bounded.

(iii) Top 3 next moves. 1. Study the special case $p_{i+1}=2p_i+1$ (all multipliers minimal) as a candidate for a slow-growing chain; prove (or disprove) existence of an infinite chain of this form. 2. Develop a lower-bound argument showing that multipliers $m_i=(p_{i+1}-1)/p_i$ must themselves grow without bound along any infinite chain. 3. Use computational search to explore long finite chains with small multipliers to guess the correct growth behavior and identify obstructions.

(iv) Minimal counterexample structure. A counterexample to “$p_k^{1/k}\to\infty$” would be an infinite chain where the multipliers $m_i=(p_{i+1}-1)/p_i$ stay bounded (or at most grow slowly), e.g. a Cunningham-type chain with $m_i=2$ for all $i$, which would force $p_k\asymp 2^k$ and hence keep $p_k^{1/k}$ bounded.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

1) FORMAL RESTATEMENT

A prime chain is a strictly increasing sequence of primes $p_1<p_2<\cdots$ such that \[ p_{i+1}\equiv 1\pmod{p_i}\quad\text{for all }i\ge 1. \] Question (growth): Is it true that for every such infinite chain, \[ \lim_{k\to\infty} p_k^{1/k}=\infty\ ? \] Equivalently, is it necessary that $\log p_k / k \to \infty$?

Question (existence of slow chains): Does there exist a prime chain with \[ p_k\le \exp\big(k(\log k)^{1+o(1)}\big)\quad\text{as }k\to\infty? \]

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement notes that for the greedy chain (each step chooses the least prime $\equiv 1\pmod{p_i}$) one can use Linnik's theorem to obtain an upper bound of the form $p_k\le e^{e^{O(k)}}$, and that a conjectural bound on least primes in progressions would imply $p_k\le \exp(k(\log k)^{1+o(1)})$. I do not use any results beyond what is explicitly stated here.

3) ATTACK PLAN

Proof track (force superexponential growth): derive unavoidable lower bounds on multipliers $m_i=(p_{i+1}-1)/p_i$ and show their product must grow faster than $c^k$.

Disproof track (construct slow chain): attempt to build an infinite chain with bounded or slowly growing multipliers (e.g. always $m_i=2$ gives $p_{i+1}=2p_i+1$), but primality constraints are difficult.

I provide unconditional lower bounds and computational sanity checks; the main growth questions remain open here.

4) WORK

Lemma 695.1 (Parity forces doubling from the second step). Let $p_i$ be an odd prime. If $p_{i+1}\equiv 1\pmod{p_i}$ and $p_{i+1}>2$, then \[ p_{i+1}\ge 2p_i+1. \] Consequently, any prime chain satisfies $p_{i+1}\ge 2p_i+1$ for all $i\ge 2$.

Proof. Write $p_{i+1}=1+m p_i$ for some integer $m\ge 1$. If $p_i$ is odd then $m p_i$ has the same parity as $m$, hence $p_{i+1}=1+m p_i$ is even iff $m$ is odd.

For $p_{i+1}$ to be a prime strictly larger than $2$, it must be odd. Therefore $m$ must be even, so $m\ge 2$. Hence \[ p_{i+1}=1+m p_i\ge 1+2p_i. \] In any chain, $p_2$ is odd, so the conclusion applies for all $i\ge 2$. $\square$

Lemma 695.2 (Exponential lower bound on $p_k$). For any prime chain $(p_k)$, \[ p_k\ge 2^{k-2}p_2 + (2^{k-2}-1)\quad\text{for all }k\ge 2. \] In particular, if $p_1=2$ then $p_2\ge 3$ and thus $p_k\ge 3\cdot 2^{k-2}+ (2^{k-2}-1)=4\cdot 2^{k-2}-1=2^{k}-1$ for all $k\ge 2$.

Proof. For $i\ge 2$, Lemma 695.1 gives $p_{i+1}\ge 2p_i+1$. We prove by induction on $k\ge 2$ the stronger inequality \[ p_k\ge 2^{k-2}p_2 + (2^{k-2}-1). \] Base case $k=2$ is equality. Assume it holds for $k$. Then \[ p_{k+1}\ge 2p_k+1\ge 2\big(2^{k-2}p_2 + (2^{k-2}-1)\big)+1=2^{k-1}p_2+(2^{k-1}-1), \] which is the desired statement for $k+1$. This completes the induction.

If additionally $p_1=2$, then $p_2$ is an odd prime so $p_2\ge 3$. Plugging into the bound yields $p_k\ge 3\cdot 2^{k-2}+(2^{k-2}-1)=2^k-1$ for $k\ge 2$. $\square$

FAST REALITY CHECK (greedy chain computation). Taking the greedy chain starting at $p_1=2$ (each $p_{i+1}$ the smallest prime $\equiv 1\pmod{p_i}$), a local primality search gives the first terms: \[ ( p_1,\dots,p_{10})=(2,3,7,29,59,709,2837,22697,590123,1180247). \] For $k=10$ this gives $p_{10}^{1/10}\approx 4.0476$.

5) VERIFICATION

- Lemma 695.1 relies only on parity and the fact that primes $>2$ are odd.

- Lemma 695.2 is a straightforward induction using Lemma 695.1.

- The computed greedy-chain values were verified by direct congruence checks in the script (each $p_{i+1}=1+m p_i$ with integer $m$ and primality test).

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. Any prime chain grows at least exponentially: $p_{i+1}\ge 2p_i+1$ for $i\ge 2$ (Lemma 695.1) and hence $p_k\ge 2^k-1$ for $k\ge 2$ when $p_1=2$ (Lemma 695.2).

(ii) First gap (crisp). Decide whether every infinite prime chain must satisfy $\log p_k/k\to\infty$ (equivalently $p_k^{1/k}\to\infty$), or construct an infinite chain with $p_k^{1/k}$ bounded.

(iii) Top 3 next moves. 1. Study the special case $p_{i+1}=2p_i+1$ (all multipliers minimal) as a candidate for a slow-growing chain; prove (or disprove) existence of an infinite chain of this form. 2. Develop a lower-bound argument showing that multipliers $m_i=(p_{i+1}-1)/p_i$ must themselves grow without bound along any infinite chain. 3. Use computational search to explore long finite chains with small multipliers to guess the correct growth behavior and identify obstructions.

(iv) Minimal counterexample structure. A counterexample to “$p_k^{1/k}\to\infty$” would be an infinite chain where the multipliers $m_i=(p_{i+1}-1)/p_i$ stay bounded (or at most grow slowly), e.g. a Cunningham-type chain with $m_i=2$ for all $i$, which would force $p_k\asymp 2^k$ and hence keep $p_k^{1/k}$ bounded.