Erdős problem #17: verified partial progress
Access/check date: 2026-07-26 UTC.
Claim labels used throughout:
- (a) elementary-rigorous: proved below from definitions.
- (b) rigorous-modulo-named-theorem/source: depends only on the named,
linked theorem or on a directly inspected primary source.
- (c) plausible/structural-unverified: heuristic, search miss, or cost
projection; never used as a theorem.
- (d) computational-only: exact finite computation, reproducible with the
standalone checker.
0. Mandatory live-page gate
I fetched the rendered live problem page
and its discussion thread
through the Bright Data browser path, not datacenter curl. (b)
The live page's verbatim statement is:
> Are there infinitely many primes \(p\) such that every even number \(n\leq > p-3\) can be written as a difference of primes \(n=q_1-q_2\) where
> \(q_1,q_2\leq p\)?
The gate did not trigger. The rendered page showed the following. (b)
| Live-page field | Rendered value |
|---|---|
| Status | OPEN |
| Comments | 1 comment on this problem |
| Claimed proofs | 0 claimed proofs for this problem |
| Interested in collaborating | None |
| Currently working on this problem | None |
| Likes this problem | Dogmachine, holyterror |
| This problem looks difficult | TerenceTao |
| This problem looks tractable | None |
| Results could be formalisable | None |
| Working on formalising the results | None |
| Formalised statement | Yes |
| Related OEIS sequence | A038133 |
| Last page edit | 28 December 2025 |
The only comment, by Dogmachine on 2025-08-09, points to the general
prime-difference question and reports Ribenboim's observation that “it has
never been proved that every even number can be written as difference of
primes.” It contains no proposed proof, counterexample, or worker. (b)
The page also states that the first prime without the property is \(97\);
that these property-holding primes are called cluster primes; and that
A038133 lists the odd primes which are not
cluster primes. (This resolves the grammatical antecedent of “such primes”
on the page.) (b)
The cited known bounds for the cluster-prime counting function
\(\pi_C(x)\) are
\[ \pi_C(x)\ll_A \frac{x}{(\log x)^A}\quad(A>0) \]from Blecksmith--Erdős--Selfridge, and
\[ \pi_C(x)\ll x\exp\!\bigl(-c(\log\log x)^2\bigr)\quad(c<1/8) \]from Elsholtz. (b)
1. Primary-source literature audit
Direct literature
- The original problem also appears as a “good prime” problem in the
1994 Oberwolfach report, problem 4 on page 23 of the PDF.
That source additionally asks for unusually prime-rich terminal intervals.
(b)
- Richard Blecksmith, Paul Erdős, and J. L. Selfridge,
American Mathematical Monthly 106 (1999), 43--48,
DOI 10.1080/00029890.1999.12005005.
I inspected the full paper and verified its metadata through Crossref. It
proves the arbitrary-fixed-power logarithmic upper bound, proves convergence
of the sum of reciprocals of cluster primes, describes a forward algorithm,
and reports counts through \(10^{13}\). (b)
- Christian Elsholtz,
Acta Arithmetica 109 (2003), 281--284,
I inspected the full paper and verified the DOI through Crossref. Its
displayed theorem gives constant \(1/60\); its final refinement gives every
constant below \(1/8\), exactly supporting the live page's formulation.
(b)
Exact-title/phrase searches and cited-by trails found no later paper claiming
to prove or disprove the infinitude of cluster primes, and no later direct
improvement to Elsholtz's cluster-prime bound. This is a documented search
miss, not a proof that no such literature exists. (c)
Closely related prime-difference results that do not solve #17
- Huang and Wu,
On the set of the difference of primes,
arXiv:1505.00187, later Proc. AMS 145 (2017), 3787--3793,
DOI 10.1090/proc/13533, prove that the
set of even integers occurring infinitely often as prime differences is a
\(\Delta^*_{721}\)-set (hence, in particular, syndetic). This neither says
that every even integer occurs nor enforces the endpoint \(q_1\leq p\)
required here. (b)
- Goswami, Huang, and Wu,
On the set of Kronecker numbers,
arXiv:2303.05767, later Bull. Aust. Math. Soc. 110 (2024), 262--270,
DOI 10.1017/S0004972724000133,
explicitly describe “every even number is a prime difference infinitely
often” as beyond current methods and prove density/product/ratio results
instead. Those results do not provide the uniform bounded endpoint in #17.
(b)
- The only later exact-title hit using “cluster primes” was Somanath, Bindu,
and Das,
[*On the Exponential Diophantine Equation Related to the Powers of Cluster
Primes*](https://link.springer.com/chapter/10.1007/978-981-96-1505-6_16)
(2025), DOI 10.1007/978-981-96-1505-6_16. Its primary-source abstract is
about \(p^x+q^y=z^2\) with selected cluster primes, not their infinitude or
counting function. (b)
No arXiv identifier was found for the 1999 or 2003 direct papers; I have not
invented one. (b)
2. Exact reductions
2.1 A nonrecursive frontier formulation
For a positive even integer \(n\), define
\[ \rho(n)=\min\{r\geq 3:r\text{ and }n+r\text{ are prime}\}, \]with \(\rho(n)=+\infty\) if the set is empty, and put
\[ F(x)=\max_{\substack{2\leq n\leq x\\2\mid n}}\bigl(n+\rho(n)\bigr). \]Frontier lemma. A prime \(p>2\) is a cluster prime if and only if
\[ F(p-3)\leq p. \tag{1} \]Proof. A positive even difference cannot use the prime \(2\): if the
smaller prime were \(2\), the larger one would be an even integer greater than
\(2\). Thus a representation \(n=q_1-q_2\) is exactly a choice of an odd prime
\(r=q_2\) for which \(n+r=q_1\) is prime. The least possible upper prime is
therefore \(n+\rho(n)\). Requiring that least upper prime to be at most \(p\)
for every even \(n\leq p-3\) is exactly (1). \(\square\) (a)
This isolates the global obstacle: one needs infinitely many prime endpoints
\(p\) at which the running maximum \(F(p-3)\) has not crossed \(p\). (a)
2.2 A finite transition criterion
Let \(C
Transition lemma. The prime \(p\) is a cluster prime if and only if, for
every odd composite integer
\[ 9\leq t\leq p-C+1, \tag{2} \]there is an odd prime \(r\leq t\) such that
\[ p-t+r\quad\text{is prime}. \tag{3} \]Proof. All even differences through \(C-3\) are already represented using
primes at most \(C\). The only new differences to check are
\[ C-1,C+1,\ldots,p-3. \]Write any one of them uniquely as \(n=p-t\). Then \(t\) runs through the odd
integers \(3,5,\ldots,p-C+1\). A representation
\[ p-t=q_1-q_2,\qquad q_1,q_2\leq p, \]is equivalent, on setting \(r=q_2\), to \(r\) and \(p-t+r\) both being prime
and \(r\leq t\). Conversely, any such \(r\) gives the required representation.
If \(t\) itself is prime, take \(r=t\) and \(q_1=p\); hence only odd composite
\(t\), starting with \(9\), require work. \(\square\) (a)
One immediate corollary is that any prime \(p\) with \(0 cluster prime, because (2) is empty. (a) For \(C=89\) and \(p=97\), the sole new composite is \(t=9\). Its possible smaller odd primes \(r=3,5,7\) give \(p-t+r=91,93,95\), all composite. Therefore \(88=97-9\) has no allowed representation and \(97\) is not a cluster prime. This is a complete hand certificate. (a) If \(p\) is a cluster prime and \(3\leq T\leq p-2\), then2.3 Exact local-density obstruction
Indeed, there are \(\lfloor(T-1)/2\rfloor\) differences \(p-t\) with odd
\(3\leq t\leq T\). In any representation \(p-t=q-r\), one has
\(r\leq t\leq T\) and \(p-T for \(r\) per prime \(q\) in that terminal interval, so counting possible pairs proves (4). (a) By the prime number theorem, (4) forces at least \((\tfrac12+o(1))\log T\) primes in that terminal interval as \(T\to\infty\). This is the prime-clustering mechanism used by the cited upper-bound papers. (b), modulo the prime number theorem The complete standalone source is erdos17_wave5e_verify.py. It uses only the Python standard library. The verification layers are: 1. an Eratosthenes sieve, with every entry through \(20{,}000\) independently compared to trial division; (d) 2. a full enumeration using the transition lemma; (d) 3. a separately written full enumeration in the original difference variables, without calling the \(t\)-criterion routine; (d) 4. a third, literal global difference-set construction through \(10^5\), adding every difference \(p-q\) whenever a new prime \(p\) arrives; (d) 5. direct exhaustion of every possible smaller prime for each of the first thirty noncluster witness certificates. (d) The two full enumerators agreed at every prime through \(10^8\), and the literal global method agreed at every prime through \(10^5\). (d) Here \(2\) is excluded, following the convention in the 1999 paper. | \(x\) | cluster primes \(\leq x\) | noncluster odd primes \(\leq x\) | |---:|---:|---:| | \(10^2\) | 23 | 1 | | \(10^3\) | 99 | 68 | | \(10^4\) | 420 | 808 | | \(10^5\) | 1,807 | 7,784 | | \(10^6\) | 8,287 | 70,210 | | \(10^7\) | 40,017 | 624,561 | | \(10^8\) | 202,208 | 5,559,246 | Every entry is recomputed from scratch, not read from OEIS. They reproduce the corresponding Blecksmith--Erdős--Selfridge table rows; this run does not claim a range record beyond their published \(10^{13}\) computation. (d) as consecutive little-endian unsigned 64-bit integers, has SHA-256 Both full enumerators independently produced this digest. (d) the largest value gap is \(95{,}573{,}461-95{,}561{,}341=12{,}120\). Exactly 629 noncluster primes lie between these two cluster primes. (d) The second column is an even \(n\leq p-3\) which the direct checker proves is not \(q_1-q_2\) for any primes \(q_1,q_2\leq p\). | noncluster \(p\) | missing difference \(n\) | |---:|---:| | 97 | 88 | | 127 | 118 | | 149 | 140 | | 191 | 182 | | 211 | 202 | | 223 | 214 | | 227 | 202 | | 229 | 202 | | 251 | 242 | | 257 | 242 | These are finite exhaustive certificates, not probabilistic tests. (d) The default dual enumeration through \(10^7\), plus the literal \(10^5\) audit, takes about 14 seconds on this VM: The exact \(10^8\) dual run used for the table and extrema was: It completed with used 213,660 KiB maximum resident memory on this VM. (d) The core transition check is: The full source contains the independent enumerators, hashes, published-row regressions, primality audit, witness exhaustion, and command-line interface. If infinitely many cluster primes exist, then every positive even integer is a difference of two primes: given even \(n\), choose a cluster prime \(p\geq n+3\). Thus #17 implies Maillet's still-open conjecture. (a) For any sufficiently large cluster prime \(p\), apply the definition to \(p-9\). The smaller prime in a representation can only be \(3,5,\) or \(7\); therefore at least one of \(p-6,p-4,p-2\) is prime. Consequently infinitely many cluster primes would imply infinitely many prime gaps of size at most \(6\), i.e. \(H_1\leq6\). (a) The current unconditional bounded-gap theorem only gives \(H_1\leq246\); Polymath8b gives \(H_1\leq6\) only under generalized Elliott--Halberstam. See [*Variants of the Selberg sieve, and bounded intervals containing many primes*](https://arxiv.org/abs/1407.4897). (b) Even the conditional \(H_1\leq6\) handles only the first transition constraint \(t=9\); it supplies none of the simultaneously growing constraints for \(t=15,21,25,\ldots\). (a) By the transition lemma, infinitude is equivalent to the following extension statement: > For every cluster prime \(C\), there is a prime \(p>C\) such that, for every > odd composite \(t\leq p-C+1\), some prime \(r\leq t\) makes \(p-t+r\) > prime. One direction recursively produces infinitely many cluster primes; the other chooses the next larger cluster prime and invokes the transition lemma. (a) No searched theorem gives this extension. The obstruction already begins at \(t=9\), where a lower bound would imply \(H_1\leq6\); the full statement then requires a growing family of correlated prime-pair alternatives. The Brun and large-sieve machinery in the two direct papers is one-sided here: it proves strong upper bounds on how often the required clustering can occur, but does not give a positive lower bound. (b) The \(\Delta^*_{721}\)/syndetic prime-difference results do not bridge the gap: they guarantee that some differences occur frequently in every bounded combinatorial configuration, whereas #17 requires all even differences up to a moving endpoint, with their representing primes also below that same endpoint. (a), using the cited theorem's statement A finite computation, regardless of range, cannot supply the missing uniform infinitude step. The present result is therefore an exact reduction plus a reproducible finite audit, not a solution or a claimed closure. (a) PARTIAL: proved an exact transition/frontier reduction and independently verified all cluster primes through 10^8 (202,208 total), but infinitude remains blocked already by the unproved H_1<=6/Maillet-level lower-bound barrier and the growing transition constraints.
3. Exact finite computation
3.1 Verified decade table
3.2 Exact list fingerprint and extrema through \(10^8\)
41c46f29d4a26a62101597e6e9be03fca7bb3383017be871d9aac0053f6a6e9d.
3.3 First explicit failure certificates
3.4 Reproduction
python3 runs/erdos17_wave5e_verify.py
python3 runs/erdos17_wave5e_verify.py \
--limit 100000000 \
--cross-limit 100000000 \
--brute-limit 100000
all_assertions_passed: true in 130.25 CPU-seconds anddef transition_failure_t(previous_cluster, candidate, is_prime):
largest_t = candidate - previous_cluster + 1
for t in range(9, largest_t + 1, 2):
if is_prime[t]:
continue
for r in range(3, t + 1, 2):
if is_prime[r] and is_prime[candidate - t + r]:
break
else:
return t
return None
4. What remains, and the exact wall
4.1 Two hard consequences of a positive answer
4.2 The precise missing extension lemma