Erdoes #455 - working report - Erdős Problem a Day

Erdős problem 455 — wave 9k

Date: 2026-07-28 UTC

Result in one paragraph

I did not solve the limit question. I did obtain two verifiable partial results. First, a one-unit refinement of Richter's arithmetic-progression capacity argument proves

\liminf_{n\to\infty}\frac{q_n}{n^2} \geq \frac{1}{S-1} >0.543448148339064,

where

S=\sum_{r\geq1} \frac{(p_{r+1}-1)^2}{p_2p_3\cdots p_{r+1}} =2.840101954632269\ldots

and $p_1=2,p_2=3,\ldots$. Richter's published constant is $1/S =0.352100035834621\ldots$. The refinement is rigorous modulo Bertrand's postulate, used only for elementary convergence/growth estimates; I make no claim that it is new to the literature. Second, an exact all-pairs dynamic program proves that among primes at most $100000$, the longest sequence with nondecreasing gaps has length exactly $250$. Equivalently, if $Q(k)$ is the least possible last term of a $k$-term finite sequence, then $Q(250)=99119$ and $Q(251)>100000$. A 250-term witness and the complete table $Q(1),\ldots,Q(250)$ are below.

Classification labels used throughout:

(a) elementary-rigorous;
(b) rigorous modulo a named theorem;
(c) plausible/structural-unverified;
(d) computational-only.

Step 0: live-page audit

I fetched the live page through the Bright Data browser path, not datacenter curl, and also fetched its LaTeX view. The page was last edited 07 October 2025. The observed state on 2026-07-28 was:

status: OPEN;
comments: 0;
claimed proofs: 0;
“Likes this problem”: Dogmachine, Prasannam;
“Interested in collaborating”: None;
“Currently working on this problem”: None;
“This problem looks difficult”: ebarschkis, Prasannam;
“This problem looks tractable”: None;
“Formalised statement?”: Yes;
“The results on this problem could be formalisable”: None;
“I am working on formalising the results on this problem”: None.

Thus none of the mandatory stop conditions applied. These are (d, live-page observations), not claims about the mathematical literature.

Verbatim current statement

Let $q_1<q_2<\cdots$ be a sequence of primes such that \[q_{n+1}-q_n\geq q_n-q_{n-1}.\] Must \[\lim_n \frac{q_n}{n^2}=\infty?\]

The only result listed on the live page is, verbatim:

Richter \cite{Ri76} proved that \[\liminf_n \frac{q_n}{n^2}>0.352\cdots.\]

Primary-source and literature audit

Bernd Richter, Über die Monotonie von Differenzenfolgen, Acta

Arithmetica 30 (1976), 225–227, DOI 10.4064/aa-30-3-225-227, publisher/EuDML scan. I downloaded and visually checked both scanned pages. The file SHA-256 was 95a94187c123c77560c5cbce9c9161449c7b1d3f27d7f0101488375a06a492e4. Richter actually proves the sharper displayed theorem $\liminf q_n/n^2\geq1/S$, with $S=2.84010\ldots$, and constructs the comparison gap sequence used in that proof. (b, Richter's theorem, with the prime number theorem used in his printed proof.)

P. Erdős and R. L. Graham, *Old and New Problems and Results in

Combinatorial Number Theory*, author-hosted scan, printed p. 91. The file SHA-256 was 0cbf0c32f0ab1e1c71db5121a88bac905bf976c4a6ab6bb6d7d9cf9ddd184ed3. The bottom of p. 90 defines the prime sequence and p. 91 says that Richter proved positive liminf, then asks whether the limit is infinite. This verifies that the cited source really contains this problem.

Exact-title, DOI, exact-phrase, formula, “convex primes,” and

“ascending wave primes” searches found no later paper addressing this prime-specific asymptotic. OpenAlex work W986587584 and Semantic Scholar paper 75962fad701bdb9e8578500c93ee1e0c9a22b31c each report one citing work, namely Erdős–Graham (1980). This is only a (c) search miss, not evidence that later literature cannot exist. Related “ascending wave” papers concern Ramsey/coloring questions and do not supply the needed prime-chain estimate.

No arXiv identifier is asserted for Richter or Erdős–Graham; both sources predate arXiv.

A refined Richter bound

Theorem

Let $q_1<q_2<\cdots$ be primes with nondecreasing gaps. With $S$ as above,

\boxed{\displaystyle \liminf_{n\to\infty}\frac{q_n}{n^2}\geq\frac1{S-1} =0.5434481483390644517\ldots .}

This is (b), rigorous modulo Bertrand's postulate. Every other step is elementary and is included below.

1. The local block bound and its off-by-one

Put

P(d)=\min\{p:p\text{ is prime and }p\nmid d\}.

After at most the first gap, every $q_i$ is odd and every gap is even. For an even gap $d$, let $r(d)$ be its multiplicity in the nondecreasing gap sequence. Its occurrences form one block, so this block contains $r(d)+1$ primes in an arithmetic progression of difference $d$.

Let $p=P(d)$. Because $p\nmid d$, any $p$ consecutive terms of that progression run through every residue modulo $p$. Hence:

r(d)\leq \begin{cases} p-1,&\text{if the block starts with }p,\\ p-2,&\text{otherwise.} \end{cases} \tag{1}

Indeed, absent the prime $p$ itself, at most $p-1$ progression terms, and therefore at most $p-2$ equal gaps, are possible. If a term divisible by $p$ is prime, it equals $p$. It must be the first term: $d$ is divisible by every prime below $p$, which gives $d\geq p-1$ (the small cases $p=3,5,7$ are immediate, and the primorial only grows thereafter), so no earlier positive prime can occur. This proves (1). (a)

Richter used the uniform $p-1$ bound on the number of equal gaps. The generic bound is one smaller.

2. Exceptional blocks are asymptotically negligible

Write $p_j$ for the $j$-th prime and

M_r=p_2p_3\cdots p_r,\qquad M_1=1.

If $d=2a$ and $P(2a)=p_{r+1}$, then $M_r\mid a$. In particular, for $a\leq x$, $M_r\leq x$. Since $M_r\geq3^{r-1}$, only $O(\log x)$ values of $r$, hence only $O(\log x)$ possible primes $P(2a)$, occur.

An exceptional block in (1) starts at the sequence term $q_i=P(2a)$. Strict increase of the $q_i$ makes these starting primes distinct. Consequently, among $a\leq x$ there are only $O(\log x)$ exceptional blocks. Their extra contribution to the count capacity is $O(\log x)=o(x)$, and their extra weighted gap contribution is at most $2xO(\log x)=o(x^2)$. (a)

3. Mean generic capacity

The condition $P(2a)=p_{r+1}$ is exactly

M_r\mid a,\qquad p_{r+1}\nmid a.

Its natural density is

\frac1{M_r}-\frac1{M_{r+1}} =\frac{p_{r+1}-1}{M_{r+1}}.

Therefore the mean of Richter's capacity $P(2a)-1$ is

S=\sum_{r\geq1} \frac{(p_{r+1}-1)^2}{M_{r+1}},

whereas the mean of the generic capacity $P(2a)-2$ is

c=S-1 =\sum_{r\geq1} \frac{(p_{r+1}-1)(p_{r+1}-2)}{M_{r+1}}. \tag{2}

The density calculation can be passed through the infinite sum uniformly. Bertrand gives $p_j<2^j$, while $M_r\geq(r+1)!/2$, so the tails are bounded by a convergent factorial majorant. Thus

\sum_{a\leq x}(P(2a)-2)=cx+o(x). \tag{3}

Partial summation then gives

\sum_{a\leq x}2a(P(2a)-2)=cx^2+o(x^2). \tag{4}

Equations (2)–(4) are (b), modulo Bertrand's postulate.

Adding the exceptional allowances from step 2 does not change either main term.

4. From capacities to $q_n$

For each $a$, give gap $2a$ exactly $P(2a)-2$ generic slots and, if the actual sequence has the exceptional block starting at $P(2a)$, one extra slot. Let

\gamma_1\leq\gamma_2\leq\cdots

be the sorted multiset of these slots. By (1), the $k$-th actual even gap is at least $\gamma_k$.

The number of slots through $2x$ is $cx+o(x)$, and their sum is $cx^2+o(x^2)$. If $x_N$ is the first threshold containing $N$ slots, then $x_N\sim N/c$. The last capacity jump is $o(x_N)$: from $M_r\leq x_N$, $M_r\geq3^{r-1}$, and Bertrand, $P(2x_N)=O(x_N^{\log_3 2})=o(x_N)$. It follows that

\sum_{k\leq N}\gamma_k =cx_N^2+o(x_N^2) =\frac{N^2}{c}+o(N^2).

Discarding the possible first, odd gap and shifting the index by one has no effect on a quadratic liminf. For the remaining even gaps, $q_{N+1}$ is an initial constant plus their first $N+O(1)$ terms, so

\liminf_{n\to\infty}\frac{q_n}{n^2}\geq\frac1c=\frac1{S-1}.

This completes the proof. (b)

Independently recomputed constants

The verifier sums 40 terms as exact rational numbers and bounds the remaining tail using Bertrand plus a geometric majorant. It obtains the rigorous intervals

\begin{aligned} 2.84010195463226942418512583422403893600545580 &<S\\ &< 2.84010195463226942418512583492840049453739256, \end{aligned}

and

\begin{aligned} 0.543448148339064451738083894344434431364113614 &<\frac1{S-1}\\ &< 0.543448148339064451738083894552457679087849175. \end{aligned}

These numerical enclosures are (d); the rational tail argument in the code makes them rigorous finite computations. As a separate direct check, for $x=10^6$ the script recomputes

\sum_{a\leq x}(P(2a)-2)=1\,840\,090

and

\sum_{a\leq x}2a(P(2a)-2)=1\,840\,095\,871\,172,

whose normalized values are $1.840090$ and $1.840095871172$, respectively. (d)

Exact finite computation

Define $Q(k)$ to be the least possible last prime in any $k$-term finite sequence with nondecreasing gaps.

Exhaustive recurrence

Let

2=p_0<p_1<\cdots<p_{m-1}\leq X

be all primes through $X$, and let $L(i,j)$, $i<j$, be the maximum length of a valid sequence ending in $p_i,p_j$. A predecessor $p_h$ is allowed exactly when

p_i-p_h\leq p_j-p_i \quad\Longleftrightarrow\quad p_h\geq2p_i-p_j.

Therefore

L(i,j)=\max\left(2,\, 1+\max_{\substack{h<i\\p_h\geq2p_i-p_j}}L(h,i)\right). \tag{5}

Induction on $j$ proves that (5) examines every possible predecessor and no invalid one. Suffix maxima down each already computed column make the algorithm $O(\pi(X)^2)$ time; triangular unsigned-16-bit rows use $\pi(X)(\pi(X)-1)$ bytes. The first endpoint at which the running maximum reaches $k$ is exactly $Q(k)$. This recurrence and its completeness proof are (a); the resulting table is (d).

For $X=100000$, $\pi(X)=9592$. The result is

\boxed{M(100000)=250,\quad Q(250)=99119,\quad Q(251)>100000.}

Here $M(X)$ is the maximum possible length with all terms at most $X$. (d)

Complete exact table $n:Q(n)$

  1- 10: 1:2 2:3 3:5 4:7 5:11 6:17 7:23 8:29 9:37 10:47
 11- 20: 11:59 12:71 13:83 14:97 15:113 16:131 17:149 18:167 19:191 20:223
 21- 30: 21:251 22:281 23:311 24:347 25:383 26:419 27:457 28:499 29:541 30:587
 31- 40: 31:641 32:691 33:743 34:797 35:853 36:911 37:971 38:1031 39:1091 40:1151
 41- 50: 41:1213 42:1277 43:1361 44:1433 45:1511 46:1583 47:1657 48:1733 49:1811 50:1889
 51- 60: 51:1973 52:2063 53:2153 54:2243 55:2333 56:2423 57:2521 58:2621 59:2729 60:2837
 61- 70: 61:2953 62:3079 63:3191 64:3307 65:3433 66:3559 67:3691 68:3823 69:3967 70:4111
 71- 80: 71:4259 72:4409 73:4561 74:4721 75:4889 76:5059 77:5231 78:5407 79:5581 80:5779
 81- 90: 81:5981 82:6163 83:6353 84:6547 85:6737 86:6947 87:7159 88:7369 89:7583 90:7817
 91-100: 91:8053 92:8291 93:8537 94:8779 95:9029 96:9277 97:9533 98:9787 99:10061 100:10331
101-110: 101:10589 102:10847 103:11113 104:11383 105:11657 106:11933 107:12211 108:12491 109:12781 110:13093
111-120: 111:13397 112:13691 113:13997 114:14303 115:14621 116:14939 117:15259 118:15581 119:15901 120:16223
121-130: 121:16547 122:16871 123:17203 124:17539 125:17881 126:18223 127:18583 128:18947 129:19309 130:19681
131-140: 131:20063 132:20431 133:20807 134:21187 135:21569 136:21961 137:22349 138:22739 139:23131 140:23531
141-150: 141:23957 142:24371 143:24793 144:25219 145:25657 146:26099 147:26539 148:26981 149:27427 150:27883
151-160: 151:28349 152:28807 153:29269 154:29741 155:30223 156:30707 157:31193 158:31687 159:32183 160:32687
161-170: 161:33191 162:33703 163:34217 164:34739 165:35267 166:35797 167:36341 168:36887 169:37441 170:37997
171-180: 171:38557 172:39119 173:39703 174:40289 175:40879 176:41479 177:42083 178:42677 179:43271 180:43867
181-190: 181:44483 182:45119 183:45737 184:46381 185:47017 186:47653 187:48299 188:48947 189:49597 190:50261
191-200: 191:50923 192:51577 193:52237 194:52901 195:53569 196:54251 197:54941 198:55631 199:56333 200:57037
201-210: 201:57751 202:58477 203:59183 204:59921 205:60647 206:61379 207:62119 208:62861 209:63607 210:64373
211-220: 211:65129 212:65899 213:66683 214:67477 215:68261 216:69061 217:69877 218:70687 219:71503 220:72337
221-230: 221:73181 222:74017 223:74857 224:75703 225:76561 226:77417 227:78277 228:79139 229:80021 230:80897
231-240: 231:81773 232:82651 233:83537 234:84431 235:85331 236:86239 237:87149 238:88069 239:88993 240:89917
241-250: 241:90841 242:91771 243:92707 244:93607 245:94513 246:95419 247:96329 248:97241 249:98179 250:99119

Some scale points are:

| $n$ | $Q(n)$ | $Q(n)/n^2$ | |---:|---:|---:| | 25 | 383 | 0.612800000 | | 50 | 1889 | 0.755600000 | | 75 | 4889 | 0.869155556 | | 100 | 10331 | 1.033100000 | | 150 | 27883 | 1.239244444 | | 200 | 57037 | 1.425925000 | | 250 | 99119 | 1.585904000 |

These ratios are finite data only; no asymptotic extrapolation is claimed. (d)

A 250-term witness

The DP reconstructs the following sequence ending at $99119$:

2, 3, 5, 7, 11, 17, 23, 29, 37, 47,
59, 71, 83, 97, 113, 131, 149, 173, 197, 223,
251, 281, 311, 347, 383, 419, 461, 503, 547, 593,
641, 691, 743, 797, 853, 911, 971, 1031, 1097, 1163,
1229, 1297, 1367, 1439, 1511, 1583, 1657, 1733, 1811, 1889,
1973, 2063, 2153, 2243, 2339, 2441, 2543, 2647, 2753, 2861,
2969, 3079, 3191, 3319, 3449, 3581, 3727, 3877, 4027, 4177,
4327, 4481, 4637, 4793, 4951, 5119, 5297, 5477, 5657, 5849,
6047, 6247, 6449, 6653, 6857, 7069, 7283, 7499, 7717, 7937,
8161, 8387, 8623, 8863, 9103, 9343, 9587, 9833, 10079, 10331,
10589, 10847, 11113, 11383, 11657, 11939, 12227, 12517, 12809, 13103,
13397, 13697, 14009, 14321, 14633, 14947, 15263, 15581, 15901, 16223,
16547, 16889, 17231, 17573, 17921, 18269, 18617, 18973, 19333, 19697,
20063, 20431, 20809, 21193, 21577, 21961, 22349, 22751, 23159, 23567,
23977, 24391, 24809, 25237, 25667, 26099, 26539, 26981, 27437, 27893,
28349, 28807, 29269, 29741, 30223, 30707, 31193, 31687, 32183, 32687,
33191, 33703, 34217, 34747, 35291, 35837, 36389, 36943, 37501, 38069,
38639, 39209, 39779, 40351, 40927, 41507, 42089, 42677, 43271, 43867,
44491, 45121, 45751, 46381, 47017, 47653, 48313, 48973, 49633, 50311,
50989, 51673, 52369, 53069, 53773, 54493, 55217, 55949, 56681, 57413,
58151, 58889, 59627, 60373, 61121, 61871, 62627, 63389, 64151, 64919,
65687, 66457, 67231, 68023, 68819, 69623, 70429, 71237, 72047, 72859,
73673, 74489, 75307, 76129, 76961, 77797, 78643, 79493, 80347, 81203,
82067, 82939, 83813, 84691, 85571, 86453, 87337, 88223, 89113, 90007,
90907, 91807, 92707, 93607, 94513, 95419, 96329, 97241, 98179, 99119

The standalone verifier checks every term by trial division and checks every adjacent gap inequality. This finite construction is (d). It is not a counterexample and says nothing by itself about extension to an infinite sequence.

Independent checks and reproducibility

The standalone script is runs/erdos455_wave9k_reverify.py.

Run:

python3 runs/erdos455_wave9k_reverify.py --limit 100000

It performs all of the following from scratch:

generates primes by an Eratosthenes sieve;
independently matches that sieve against trial-division primality

through 47;

enumerates all $2^{15}-1=32767$ nonempty subsets of the primes through

47 and confirms that their exhaustive $Q(k)$ table equals the DP table;

runs recurrence (5) on all $9592$ primes through $100000$;
reconstructs and trial-divides every term of the 250-term witness;
checks strict increase and every nondecreasing-gap inequality;
audits the $P(d)-2/P(d)-1$ block rule on every equal-gap block in the

witness;

recomputes the rigorous rational intervals for $S$, $1/S$, and

$1/(S-1)$;

directly sums the first $10^6$ generic capacities.

The final measured full run took 31.25 wall-seconds (31.13 user CPU-seconds) and 110032 KB peak resident memory on this VM. The SHA-256 of the canonical mathematical payload (limit, full $Q$-table, witness, and constant enclosures; excluding runtime metadata) was 449c21e9044c9f33b9e756b7b5399ddd00b4245807f90ce7b662fa8642247a9c. (d)

The calculation stores no probabilistic primality decisions, SAT/SMT assumptions, floating-point comparisons, or unverified external tables. Floating point is used only to format already exact integers/rationals.

Exact reduction and remaining wall

Let $d_n=q_{n+1}-q_n$. For every nondecreasing positive gap sequence,

\frac{q_n}{n^2}\to\infty \quad\Longleftrightarrow\quad \frac{d_n}{n}\to\infty. \tag{6}

The forward direction follows from $q_n\leq q_1+n d_n$; the reverse direction follows from

q_n\geq\sum_{j=\lfloor n/2\rfloor}^{n-1}d_j \geq\frac n2\,d_{\lfloor n/2\rfloor}.

This is (a).

Equivalently, in terms of the equal-gap block multiplicities,

\boxed{\displaystyle \sum_{a\leq x}r(2a)=o(x).} \tag{7}

Indeed, the left side is the generalized inverse counting how many gaps are at most $2x$. This equivalence is (a).

Richter's local argument gives a linear capacity with constant $S$; the refinement above gives the still-linear capacity

\sum_{a\leq x}r(2a)\leq(S-1)x+o(x).

Thus it improves the quadratic constant but cannot prove (7). The exact missing ingredient is a global linked-block sparsity lemma showing that a single chain of adjacent prime arithmetic-progression blocks uses only $o(x)$ of the available generic slots through gap $2x$. Bounds on each block separately cannot do this: the tuple of $P(d)-1$ progression terms is locally admissible in the generic case, so fixed-dimensional prime-tuple heuristics do not predict a further local loss. What must be controlled is compatibility between the endpoint of one block and the start of every later block. No theorem located in the literature search provides such growing-dimensional, linked prime-pattern uniformity. This diagnosis is (c); equation (7), the precise target it identifies, is (a).

For scale, extending the same exact DP to $X=10^6$ would create about $\binom{78498}{2}=3.08\times10^9$ states, need at least 6.2 GB just for the triangular uint16 cells, and cost roughly 0.6–2 core-hours after memory/cache overhead. At $X=10^7$, it would need about $2.2\times10^{11}$ states, over 440 GB, and roughly 40+ core-hours. I did not run either.

PROVED: $\liminf q_n/n^2\ge1/(S-1)>0.543448148339064$, and exactly $M(100000)=250$; the required limit remains open and reduces to linked-block sparsity (7).

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger