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)

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

from Blecksmith--Erdős--Selfridge, and

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,

Cluster Primes, 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,

On cluster primes, Acta Arithmetica 109 (2003), 281--284, DOI 10.4064/aa109-3-6. 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 (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

with \(\rho(n)=+\infty\) if the set is empty, and put

Frontier lemma. A prime \(p>2\) is a cluster prime if and only if

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<p\) be primes and suppose \(C\) is already a cluster prime.

Transition lemma. The prime \(p\) is a cluster prime if and only if, for every odd composite integer

there is an odd prime \(r\leq t\) such that

Proof. All even differences through \(C-3\) are already represented using primes at most \(C\). The only new differences to check are

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

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<p-C\leq6\) is another 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)

2.3 Exact local-density obstruction

If \(p\) is a cluster prime and \(3\leq T\leq p-2\), then

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<q\leq p\). There are at most \(\pi(T)\) choices 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

3. Exact finite computation

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)

1. a full enumeration using the transition lemma; (d)
2. a separately written full enumeration in the original difference

variables, without calling the \(t\)-criterion routine; (d)

1. a third, literal global difference-set construction through \(10^5\),

adding every difference \(p-q\) whenever a new prime \(p\) arrives; (d)

1. 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)

3.1 Verified decade table

Here \(2\) is excluded, following the convention in the 1999 paper.

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)

3.2 Exact list fingerprint and extrema through \(10^8\)

• The ascending list of all 202,208 cluster primes through \(10^8\), encoded

as consecutive little-endian unsigned 64-bit integers, has SHA-256 41c46f29d4a26a62101597e6e9be03fca7bb3383017be871d9aac0053f6a6e9d. Both full enumerators independently produced this digest. (d)

• The last cluster prime at most \(10^8\) is \(99{,}999{,}551\). (d)
• Among consecutive cluster primes whose upper endpoint is at most \(10^8\),

the largest value gap is \(95{,}573{,}461-95{,}561{,}341=12{,}120\). Exactly 629 noncluster primes lie between these two cluster primes. (d)

3.3 First explicit failure certificates

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\).

These are finite exhaustive certificates, not probabilistic tests. (d)

3.4 Reproduction

The default dual enumeration through \(10^7\), plus the literal \(10^5\) audit, takes about 14 seconds on this VM:

python3 runs/erdos17_wave5e_verify.py

The exact \(10^8\) dual run used for the table and extrema was:

python3 runs/erdos17_wave5e_verify.py \
  --limit 100000000 \
  --cross-limit 100000000 \
  --brute-limit 100000

It completed with all_assertions_passed: true in 130.25 CPU-seconds and used 213,660 KiB maximum resident memory on this VM. (d)

The core transition check is:

def 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

The full source contains the independent enumerators, hashes, published-row regressions, primality audit, witness exhaustion, and command-line interface.

4. What remains, and the exact wall

4.1 Two hard consequences of a positive answer

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. (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)

4.2 The precise missing extension lemma

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.