Erdős Problem #455

Erdős Problem 455 --- 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/455.tex.

REUSED SOURCE 1

FORMAL RESTATEMENT

Let $q_1<q_2<\cdots$ be an infinite sequence of primes. Define gaps $g_n:=q_n-q_{n-1}$ for $n\ge 2$. Assume the gaps are nondecreasing: \[ \forall n\ge 2:\quad g_{n+1}\ge g_n\quad\text{equivalently}\quad q_{n+1}-q_n\ge q_n-q_{n-1}. \] The question is whether necessarily \[ \lim_{n\to\infty}\frac{q_n}{n^2}=\infty. \]

QUICK LITERATURE/CONTEXT CHECK

Only what is stated in the problem text is used: Richter $1976$ proved $\liminf_n \frac{q_n}{n^2}>0.352\dots$. No other external results are imported here.

ATTACK PLAN

• Prove elementary structural constraints forced by monotone gaps (e.g. gaps must be unbounded; basic growth inequalities).
• FAST REALITY CHECK: build an explicit example sequence by a greedy algorithm (always pick the smallest next prime respecting the nondecreasing-gap rule) and look at $q_n/n^2$ numerically.
• Identify the precise missing ingredient: one would need a lower bound on how fast prime gaps can be forced to grow in such a subsequence.

WORK

Fast reality check (one explicit admissible sequence). Define greedily: $q_1=2$, $q_2=3$, and for $n\ge 2$ choose $q_{n+1}$ to be the smallest prime $>q_n$ with $q_{n+1}-q_n\ge q_n-q_{n-1}$. The first terms are \[ 2,3,5,7,11,17,23,29,37,47,59,71,83,97,113,131,149,167,191,223,\dots \] and the ratios along this sequence are (exact computation) \[ \frac{q_{10}}{10^2}=0.47,\quad \frac{q_{20}}{20^2}\approx 0.5575,\quad \frac{q_{50}}{50^2}\approx 1.3964,\quad \frac{q_{100}}{100^2}\approx 2.1313,\quad \frac{q_{500}}{500^2}\approx 3.7713. \] This suggests $q_n/n^2$ may grow along at least this example, but this is not a proof and does not address worst-case sequences.

Lemma 455.1 (gaps must be unbounded). In any infinite prime sequence $(q_n)$ with nondecreasing gaps $g_n=q_n-q_{n-1}$, the gaps are unbounded; in fact $g_n\to\infty$.

Proof. Assume for contradiction that $(g_n)$ is bounded above by some integer $G$. Since $(g_n)$ is a nondecreasing sequence of integers, boundedness implies that $g_n$ is eventually constant: there exists $N$ and an integer $d$ such that $g_n=d$ for all $n\ge N$. Then for all $n\ge N$, \[ q_{n}=q_N+(n-N)d, \] so the tail of the sequence lies in the arithmetic progression $q_N+d\mathbb N$.

Choose a prime $r$ with $r\nmid d$ (there are infinitely many primes, and only finitely many divide $d$). Because $\gcd(d,r)=1$, the congruence $(q_N+(n-N)d)\equiv 0\pmod r$ has a solution $n\equiv n_0\pmod r$, and hence infinitely many solutions with $n\ge N$. For such an $n$ we have $r\mid q_n$. Since $q_n$ is prime, this forces $q_n=r$. But there are infinitely many such $n$, so we would get infinitely many indices with $q_n=r$, contradicting the strict increase $q_n<q_{n+1}$. Therefore $(g_n)$ is unbounded.

Finally, since $(g_n)$ is nondecreasing and unbounded, it must satisfy $g_n\to\infty$. $\square$

Lemma 455.2 (growth inequality from monotone gaps). For any $m<n$, \[ q_n\ge q_m+(n-m)\,(q_{m+1}-q_m). \] In particular $q_n\ge q_1+(n-1)(q_2-q_1)$ for all $n\ge 1$.

Proof. Write \[ q_n-q_m=\sum_{j=m+1}^n (q_j-q_{j-1})=\sum_{j=m+1}^n g_j. \] Since the gaps are nondecreasing, for every $j\ge m+1$ we have $g_j\ge g_{m+1}=q_{m+1}-q_m$. Thus \[ q_n-q_m=\sum_{j=m+1}^n g_j\ge \sum_{j=m+1}^n (q_{m+1}-q_m)=(n-m)(q_{m+1}-q_m), \] which is the claimed inequality. $\square$

VERIFICATION

• Lemma 455.1 uses only (a) integer-valued monotone bounded $\Rightarrow$ eventually constant, and (b) a modular argument to show an infinite arithmetic progression cannot consist entirely of distinct primes. The modular argument is checked carefully by selecting a prime $r\nmid d$.
• Lemma 455.2 is a direct telescoping sum + monotonicity lower bound.
• The greedy sequence sanity check indeed respects $g_{n+1}\ge g_n$ by construction.

FINAL. UNRESOLVED

(i) Strongest proved partial result. Any such sequence has $g_n\to\infty$ (Lemma 455.1) and satisfies the general growth lower bound $q_n\ge q_m+(n-m)(q_{m+1}-q_m)$ (Lemma 455.2). Computations for one explicit greedy sequence show $q_n/n^2$ increases at least up to $n=500$.

(ii) First gap (crisp). Prove that in every such prime sequence, the gaps grow at least linearly in $n$ (e.g. $g_n\gg n$), which would imply $q_n\gg n^2$ with a diverging constant, or else explicitly construct an infinite prime sequence with $g_n=o(n)$ (which would refute the claim).

(iii) Top 3 next moves.

1. Try a disproof-by-construction track: can one choose primes near $C n^2$ with increasing gaps $\asymp n$ indefinitely (this is a prime-distribution-in-short-intervals question)?
2. Try a proof track: use modular obstructions stronger than Lemma 455.1 to show that too-slowly-growing gaps force congruence repetitions that create composites.
3. Computation: search algorithmically for "slow-growth" admissible sequences (not just greedy) and track the smallest possible $q_n$ for each $n$ under the constraint.

(iv) Minimal counterexample structure. A minimal counterexample to $q_n/n^2\to\infty$ would be an infinite sequence of primes with nondecreasing gaps and a constant $C$ such that $q_n\le C n^2$ for infinitely many $n$; such a sequence would force $g_n=O(n)$ along an infinite subsequence while still threading primality constraints.

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.

FORMAL RESTATEMENT

Let $q_1<q_2<\cdots$ be an infinite sequence of primes. Define gaps $g_n:=q_n-q_{n-1}$ for $n\ge 2$. Assume the gaps are nondecreasing: \[ \forall n\ge 2:\quad g_{n+1}\ge g_n\quad\text{equivalently}\quad q_{n+1}-q_n\ge q_n-q_{n-1}. \] The question is whether necessarily \[ \lim_{n\to\infty}\frac{q_n}{n^2}=\infty. \]

QUICK LITERATURE/CONTEXT CHECK

Only what is stated in the problem text is used: Richter $1976$ proved $\liminf_n \frac{q_n}{n^2}>0.352\dots$. No other external results are imported here.

ATTACK PLAN

• Prove elementary structural constraints forced by monotone gaps (e.g. gaps must be unbounded; basic growth inequalities).
• FAST REALITY CHECK: build an explicit example sequence by a greedy algorithm (always pick the smallest next prime respecting the nondecreasing-gap rule) and look at $q_n/n^2$ numerically.
• Identify the precise missing ingredient: one would need a lower bound on how fast prime gaps can be forced to grow in such a subsequence.

WORK

Fast reality check (one explicit admissible sequence). Define greedily: $q_1=2$, $q_2=3$, and for $n\ge 2$ choose $q_{n+1}$ to be the smallest prime $>q_n$ with $q_{n+1}-q_n\ge q_n-q_{n-1}$. The first terms are \[ 2,3,5,7,11,17,23,29,37,47,59,71,83,97,113,131,149,167,191,223,\dots \] and the ratios along this sequence are (exact computation) \[ \frac{q_{10}}{10^2}=0.47,\quad \frac{q_{20}}{20^2}\approx 0.5575,\quad \frac{q_{50}}{50^2}\approx 1.3964,\quad \frac{q_{100}}{100^2}\approx 2.1313,\quad \frac{q_{500}}{500^2}\approx 3.7713. \] This suggests $q_n/n^2$ may grow along at least this example, but this is not a proof and does not address worst-case sequences.

Lemma 455.1 (gaps must be unbounded). In any infinite prime sequence $(q_n)$ with nondecreasing gaps $g_n=q_n-q_{n-1}$, the gaps are unbounded; in fact $g_n\to\infty$.

Proof. Assume for contradiction that $(g_n)$ is bounded above by some integer $G$. Since $(g_n)$ is a nondecreasing sequence of integers, boundedness implies that $g_n$ is eventually constant: there exists $N$ and an integer $d$ such that $g_n=d$ for all $n\ge N$. Then for all $n\ge N$, \[ q_{n}=q_N+(n-N)d, \] so the tail of the sequence lies in the arithmetic progression $q_N+d\mathbb N$.

Choose a prime $r$ with $r\nmid d$ (there are infinitely many primes, and only finitely many divide $d$). Because $\gcd(d,r)=1$, the congruence $(q_N+(n-N)d)\equiv 0\pmod r$ has a solution $n\equiv n_0\pmod r$, and hence infinitely many solutions with $n\ge N$. For such an $n$ we have $r\mid q_n$. Since $q_n$ is prime, this forces $q_n=r$. But there are infinitely many such $n$, so we would get infinitely many indices with $q_n=r$, contradicting the strict increase $q_n<q_{n+1}$. Therefore $(g_n)$ is unbounded.

Finally, since $(g_n)$ is nondecreasing and unbounded, it must satisfy $g_n\to\infty$. $\square$

Lemma 455.2 (growth inequality from monotone gaps). For any $m<n$, \[ q_n\ge q_m+(n-m)\,(q_{m+1}-q_m). \] In particular $q_n\ge q_1+(n-1)(q_2-q_1)$ for all $n\ge 1$.

Proof. Write \[ q_n-q_m=\sum_{j=m+1}^n (q_j-q_{j-1})=\sum_{j=m+1}^n g_j. \] Since the gaps are nondecreasing, for every $j\ge m+1$ we have $g_j\ge g_{m+1}=q_{m+1}-q_m$. Thus \[ q_n-q_m=\sum_{j=m+1}^n g_j\ge \sum_{j=m+1}^n (q_{m+1}-q_m)=(n-m)(q_{m+1}-q_m), \] which is the claimed inequality. $\square$

VERIFICATION

• Lemma 455.1 uses only (a) integer-valued monotone bounded $\Rightarrow$ eventually constant, and (b) a modular argument to show an infinite arithmetic progression cannot consist entirely of distinct primes. The modular argument is checked carefully by selecting a prime $r\nmid d$.
• Lemma 455.2 is a direct telescoping sum + monotonicity lower bound.
• The greedy sequence sanity check indeed respects $g_{n+1}\ge g_n$ by construction.

FINAL. UNRESOLVED

(i) Strongest proved partial result. Any such sequence has $g_n\to\infty$ (Lemma 455.1) and satisfies the general growth lower bound $q_n\ge q_m+(n-m)(q_{m+1}-q_m)$ (Lemma 455.2). Computations for one explicit greedy sequence show $q_n/n^2$ increases at least up to $n=500$.

(ii) First gap (crisp). Prove that in every such prime sequence, the gaps grow at least linearly in $n$ (e.g. $g_n\gg n$), which would imply $q_n\gg n^2$ with a diverging constant, or else explicitly construct an infinite prime sequence with $g_n=o(n)$ (which would refute the claim).

(iii) Top 3 next moves.

1. Try a disproof-by-construction track: can one choose primes near $C n^2$ with increasing gaps $\asymp n$ indefinitely (this is a prime-distribution-in-short-intervals question)?
2. Try a proof track: use modular obstructions stronger than Lemma 455.1 to show that too-slowly-growing gaps force congruence repetitions that create composites.
3. Computation: search algorithmically for "slow-growth" admissible sequences (not just greedy) and track the smallest possible $q_n$ for each $n$ under the constraint.

(iv) Minimal counterexample structure. A minimal counterexample to $q_n/n^2\to\infty$ would be an infinite sequence of primes with nondecreasing gaps and a constant $C$ such that $q_n\le C n^2$ for infinitely many $n$; such a sequence would force $g_n=O(n)$ along an infinite subsequence while still threading primality constraints.