Erdős Problem #17

Erdős Problem 17: Cluster Primes --- Round 3 Continuation

We continue strictly from the Round-2 state of the investigation. The original question remains: \[ \text{Are there infinitely many cluster primes?} \] Here a prime $p$ is cluster if every even integer $n$ with $2\le n\le p-3$ can be written as \[ n=q_1-q_2 \] with primes $q_1,q_2\le p$.

1) ROUND-3 OBJECTIVE

Path (C): obstruction / structural correction.

Round-2 proved a single-offset obstruction theorem: for every fixed odd composite $m\ge 9$, there are infinitely many primes $p$ for which the even number $n=p-m$ fails the cluster condition. The natural next gap is whether these obstructions can be synchronized. That is the direction pursued here.

The new Round-3 goal is to prove a genuinely stronger statement:

for any finite set of odd composite offsets $m$, there are infinitely many primes $p$ for which all corresponding even numbers $p-m$ fail simultaneously.

2) Round-2 FOUNDATION USED

We use the following previously established results.

1. Round-1 Lemma 17.1 (prime-pair formulation). A prime $p$ is cluster if and only if for every even $n$ with $2\le n\le p-3$ there exists a prime $q\le p-n$ such that both $q$ and $q+n$ are prime.

2. Round-2 Lemma 17.3 (finite reduction for $n=p-m$). If $p$ is an odd prime, $3\le m\le p-2$, and $n:=p-m$, then any representation $n=q_1-q_2$ with primes $q_1,q_2\le p$ forces $q_2\le m$. Consequently, \[ n=p-m \] fails at $p$ if and only if \[ \forall\ \text{primes }q\le m,\qquad p-(m-q)\ \text{is not prime}. \]

3. Round-2 Lemma 17.4 (CRT--Dirichlet forcing). Given finitely many positive integers $d_1,\dots,d_k$, and pairwise distinct primes $r_i$ such that $r_i\nmid d_i$, one can choose a residue class $a\pmod{R}$, where $R=\prod_i r_i$, such that infinitely many primes $p\equiv a\pmod R$ satisfy that every $p-d_i$ is composite.

4. Round-2 Theorem 17.5 (single-offset obstruction). For every fixed odd composite $m\ge 9$, there are infinitely many primes $p$ such that $p-m$ fails the cluster condition at $p$.

No Round-2 proofs are repeated here; they are only invoked and extended.

3) NEW INSIGHT / TOOL (ROUND-3)

New insight: simultaneous obstruction forcing.

Round-2 killed one prescribed near-$p$ gap at a time. The new idea is that the CRT--Dirichlet construction can be run simultaneously for every pair $(m,q)$ with $m$ in a fixed finite set of odd composite offsets and $q\le m$ prime. Thus finitely many candidate witness systems can all be destroyed at once.

This has two concrete consequences.

1. The obstructions $p-m$ for different odd composite $m$ are not mutually incompatible; any finite family of them can occur simultaneously for infinitely many primes $p$.
2. The single-offset theorem of Round-2 upgrades to an arbitrarily-many-offset theorem, showing that non-cluster behavior can be forced in a highly structured way.

A second new consequence is a complete classification of fixed odd offsets: if $m$ is a fixed odd prime, then $p-m$ is always trivially representable for every prime $p>m$; if $m$ is a fixed odd composite, then $p-m$ fails for infinitely many primes $p$.

4) ATTACK PLAN (ROUND-3)

The exact gap left after Round-2 was this:

Round-2 produced infinitely many primes with one prescribed failing gap $p-m$, but did not address whether several such prescribed failures can be forced simultaneously, nor whether fixed odd offsets can be classified completely.

The plan is therefore:

1. Extend the Round-2 CRT--Dirichlet argument from one offset $m$ to a finite family $M$ of odd composite offsets.
2. Deduce that for every $K\ge 1$ there are infinitely many primes with at least $K$ distinct failing even integers.
3. Combine the new theorem with the trivial representation $p-m=p-m$ when $m$ is prime to classify fixed odd offsets.
4. Extract a concrete local corollary for cluster primes, namely that every cluster prime $p>7$ must be preceded by a prime gap at most $6$.

This overcomes the previous obstacle because it shows that a whole finite obstruction pattern can be enforced with one global arithmetic progression.

5) WORK (ROUND-3)

5.1 Simultaneous finite-pattern obstruction theorem

Theorem 17.7. Let $M$ be a finite nonempty set of odd composite integers, each at least $9$. Then there exist infinitely many primes $p$ such that for every $m\in M$, the even integer \[ n_m:=p-m \] fails the cluster condition at $p$. In particular, for such primes $p$, the prime $p$ is non-cluster and has at least $|M|$ distinct failing even integers.

Proof. Let \[ B:=\max M. \] For each pair $(m,q)$ with $m\in M$ and $q\le m$ prime, define \[ d_{m,q}:=m-q. \] Because every $m\in M$ is composite, we never have $q=m$, so each $d_{m,q}$ is a positive integer.

Choose pairwise distinct primes \[ r_{m,q}>B \] for all such pairs $(m,q)$. Since $0<d_{m,q}<m\le B<r_{m,q}$, we have \[ r_{m,q}\nmid d_{m,q} \] for every pair.

Now apply the Round-2 CRT--Dirichlet lemma simultaneously to the full finite family of integers $d_{m,q}$. We obtain a modulus \[ R:=\prod_{m\in M}\ \prod_{\substack{q\le m \\ q\ \mathrm{prime}}} r_{m,q} \] and a residue class $a\pmod R$ with $\gcd(a,R)=1$ such that there are infinitely many primes \[ p\equiv a\pmod R \] and, for every sufficiently large such prime $p$, \[ p-d_{m,q}=p-(m-q) \] is composite for every pair $(m,q)$.

Fix such a prime $p$, large enough that $p\ge B+3$. Then for each $m\in M$, the integer \[ n_m=p-m \] is even because both $p$ and $m$ are odd, and it lies in the cluster range since \[ 2\le p-m\le p-3. \] Moreover, for every prime $q\le m$, the number \[ p-(m-q) \] is composite. By Round-2 Lemma 17.3, this means exactly that $n_m=p-m$ fails the cluster condition at $p$.

Since this holds for every $m\in M$, all these failures occur simultaneously. The numbers $p-m$ are distinct because the elements of $M$ are distinct, so $p$ has at least $|M|$ distinct failing even integers. In particular, $p$ is non-cluster. Since infinitely many such primes $p$ exist, the theorem follows. $\square$

5.2 Corollary: arbitrarily many prescribed failures

Corollary 17.8. For every integer $K\ge 1$, there exist infinitely many primes $p$ for which at least $K$ distinct even integers $n$ with $2\le n\le p-3$ fail the cluster condition.

Proof. Choose any set $M$ consisting of $K$ distinct odd composite integers at least $9$; for example, the first $K$ odd composite integers at least $9$. Apply Theorem 17.7. Then for infinitely many primes $p$, every number $p-m$ with $m\in M$ fails, giving at least $K$ distinct failures. $\square$

This strictly strengthens Round-2, where only one prescribed failure gap was forced at a time.

5.3 Corollary: classification of fixed odd offsets

Corollary 17.9. Let $m\ge 3$ be a fixed odd integer.

1. If $m$ is prime, then for every prime $p>m$ the even integer $p-m$ is represented as a difference of two primes $\le p$, namely \[ p-m=p-m, \] with $q_1=p$ and $q_2=m$. Thus the fixed offset $m$ never causes failure.

2. If $m$ is composite, then $m\ge 9$, and there exist infinitely many primes $p$ such that $p-m$ fails the cluster condition at $p$.

Thus, among fixed odd offsets, the prime offsets are always trivially covered, while every odd composite offset fails for infinitely many primes.

Proof. Part $1$ is immediate from the representation $p-m=q_1-q_2$ with $q_1=p$ and $q_2=m$.

For part $2$, every odd composite integer at least $3$ is at least $9$, so the conclusion follows from the Round-2 single-offset obstruction theorem (equivalently from Theorem 17.7 with $M=\{m\}$). $\square$

5.4 Corollary: a necessary local condition for cluster primes

Corollary 17.10. If $p>7$ is a cluster prime, then the preceding prime gap is at most $6$; equivalently, at least one of \[ p-2,\qquad p-4,\qquad p-6 \] is prime.

Proof. If $p=11$, the preceding prime is $7$, so the gap is $4\le 6$. It therefore remains to treat the case $p>11$.

Because $9$ is an odd composite, the even number $p-9$ lies in the cluster range for every prime $p>11$. If $p$ is cluster, then $p-9$ must be representable.

Apply Round-2 Lemma 17.3 with $m=9$. The possible upper primes are \[ p-(9-q),\qquad q\in\{2,3,5,7\}, \] namely \[ p-7,\qquad p-6,\qquad p-4,\qquad p-2. \] Now $p-7$ is even and greater than $2$ for $p>9$, hence composite. Therefore at least one of \[ p-6,\quad p-4,\quad p-2 \] must be prime. This means there is a prime in the interval $(p-8,p)$, so the preceding prime gap is at most $6$. $\square$

This recovers a sharp and very concrete necessary condition on any cluster prime.

6) ADVERSARIAL VERIFICATION

We now test the Round-3 argument for hidden flaws.

1. Do simultaneous congruences conflict across different offsets $m$? No. Each pair $(m,q)$ is assigned its own distinct modulus prime $r_{m,q}$. CRT handles all congruences simultaneously because the moduli are pairwise coprime.

2. Could some $d_{m,q}$ equal $0$? No. Since every $m\in M$ is composite and $q$ is prime, $q=m$ cannot happen. Hence $d_{m,q}=m-q\ge 1$.

3. Could the forced divisor $r_{m,q}$ equal the number $p-(m-q)$, making it prime rather than composite? This can happen for at most one value of $p$ per pair $(m,q)$. Excluding finitely many such exceptional primes still leaves infinitely many primes in the arithmetic progression.

4. Are the claimed failing numbers distinct? Yes. If $m_1\neq m_2$, then $p-m_1\neq p-m_2$. Thus Theorem 17.7 really gives at least $|M|$ distinct failures.

5. Does every $p-m$ lie in the required cluster range? Yes. Once $p\ge \max(M)+3$, we have $2\le p-m\le p-3$ for every $m\in M$.

6. Does Corollary 17.9 miss any odd offsets? The only odd integer below $3$ is $1$, but then $p-1>p-3$ and it lies outside the cluster range. So the classification of fixed odd offsets naturally begins at $m=3$.

No contradiction with earlier rounds arises: Theorem 17.7 genuinely strengthens the Round-2 one-offset theorem, and Corollaries 17.8--17.10 are proper new consequences.

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED)

The original question --- whether there are infinitely many cluster primes --- remains open.

However, Round-3 proves a theorem strictly stronger than the Round-2 result:

For any finite set $M$ of odd composite integers at least $9$, there are infinitely many primes $p$ such that every prescribed near-$p$ gap $p-m$ with $m\in M$ fails simultaneously.

This yields the following new unconditional advances.

1. For every $K\ge 1$, there are infinitely many primes with at least $K$ distinct failing even integers.
2. Fixed odd offsets are completely classified: prime offsets are always trivially represented, while odd composite offsets fail infinitely often.
3. Any attempted proof strategy based on the idea that different near-$p$ obstructions are mutually incompatible is ruled out: finitely many such obstructions can coexist on an infinite set of primes.
4. Every cluster prime $p>7$ must be preceded by a prime gap at most $6$.

These results do not settle infinitude of cluster primes, but they sharpen the obstruction side substantially and isolate a stronger structural barrier than in Round-2.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 49%

9) REFERENCES

1. R. Blecksmith, P. Erdős, and J. L. Selfridge, Cluster Primes, American Mathematical Monthly 106 $1999$, 43--48.
2. C. Elsholtz, On cluster primes, Acta Arithmetica 109 $2003$, 281--284.
3. Chinese Remainder Theorem (standard elementary number theory).
4. Dirichlet's theorem on primes in arithmetic progressions (standard analytic number theory).

10) OUTPUT FORMAT

This is a drop-in LaTeX fragment with no preamble and no \begin{document}, as requested.

Erdős Problem #17: independent continuation

1) TARGET AND SOURCE AUDIT

All supplied versions considered: 17.tex. The source proves simultaneous CRT obstructions for any fixed finite set of composite offsets and a necessary preceding gap of at most six. I do not promote these obstructions to a proof about all sufficiently large primes.

2) WORK

An exact moving-offset hitting condition.

For $p>17$, the first two conditions in $1$ require \[ D_p\cap\{2,4,6\}\ne\varnothing,\quad D_p\cap\{2,4,8,10,12\}\ne\varnothing. \] The omitted $q=2$ choices give even upper numbers greater than two. Thus if neither $p-2$ nor $p-4$ is prime, cluster forces $p-6$ prime and at least one of $p-8,p-10,p-12$ prime. This is a two-offset constraint stronger than the source's single necessary gap test.

A reproducible exhaustive check, verification/batch_2_checks.py, uses trial division and all pair differences for every prime at most 500. It finds 65 cluster primes, with largest 491, and checks the preceding-gap necessity for each. This is finite evidence only.

3) ADVERSARIAL VERIFICATION

4) FINAL

5) SOURCES CHECKED

6) COMPLETION ESTIMATE

1) FORMAL RESTATEMENT

Let $p$ be a prime. Let $\mathcal P(p):=\{q\text{ prime}: 2\le q\le p\}$.

Define: $p$ is a cluster prime if \[ \forall n\in\mathbb Z\;\Big( n\ \text{even and }2\le n\le p-3\ \Rightarrow\ \exists q_1,q_2\in\mathcal P(p)\text{ with }n=q_1-q_2\Big). \] (For $p\le 3$ the condition is vacuous because there is no even $n$ with $2\le n\le p-3$.)

Question: Are there infinitely many cluster primes?

2) QUICK LITERATURE/CONTEXT CHECK

The provided problem statement already records the main known global information: Blecksmith--Erdős--Selfridge $1999$ and Elsholtz $2003$ proved strong upper bounds on the counting function of cluster primes (in particular, that they have density $0$ in the primes). I do not use (or claim) any further literature beyond what is explicitly stated in the problem file.

3) ATTACK PLAN

Proof track (ambitious): - Try to show infinitely many $p$ satisfy the required "prime-pair covering" condition by a probabilistic/heuristic model for prime gaps, possibly reducing to simultaneously finding at least one prime pair of each even gap $n\le p-3$.

Disproof track (ambitious): - Try to force failures by exhibiting, for infinitely many primes $p$, an even $n\le p-3$ such that no prime pair $\le p$ has gap $n$. For a fixed $p$, this is equivalent to showing no prime in $[2,p-n]$ forms a prime pair with gap $n$.

What I can actually deliver here is a clean reformulation, a combinatorial necessary condition, and verified small cases.

4) WORK

FAST REALITY CHECK (explicit small cases)

For a fixed prime $p$, define $D(p):=\{q_1-q_2: q_1,q_2\in\mathcal P(p)\}$. Then $p$ is cluster iff every even $n\in[2,p-3]$ lies in $D(p)$.

I ran an exact brute-force check (enumerating primes $\le p$ and checking all even $n\le p-3$) for $p\le 300$.

Result (exact): the cluster primes $\le 300$ are \[ \begin{aligned} &2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,\\ &101,103,107,109,113,131,137,139,151,157,163,167,173,179,181,193,197,199,233,239,241,271,277,281,283. \end{aligned} \] The non-cluster primes $\le 300$ are \[ (97,\,88),\ (127,\,112),\ (149,\,140),\ (191,\,182),\ (211,\,202),\ (223,\,202),\ (227,\,202),\ (229,\,202),\ (251,\,242),\ (257,\,242),\ (263,\,242),\ (269,\,242),\ (293,\,284), \] where $(p,\,n_\text{fail})$ records the smallest even $n\le p-3$ that fails.

Example verification of the first failure $p=97$ (no computation needed): - The claimed failing even number is $n=88\le 97-3$. - If $q_1-q_2=88$ with primes $q_1,q_2\le 97$, then $q_2=q_1-88\le 97-88=9$. - The only primes $\le 9$ are $2,3,5,7$, giving $q_1\in\{90,91,93,95\}$, none of which is prime. So $97$ is not cluster.

Lemma 17.1 (equivalent prime-pair formulation). For any prime $p$, the following are equivalent:

(a) $p$ is a cluster prime.

(b) For every even integer $n$ with $2\le n\le p-3$ there exists a prime $q\le p-n$ such that $q$ and $q+n$ are both primes (hence both $\le p$).

Proof. (a)$\Rightarrow$(b): Fix even $n\le p-3$. By (a), there exist primes $q_1,q_2\le p$ with $q_1-q_2=n$. Put $q=q_2$. Then $q\le p-n$ because $q+n=q_1\le p$. Also $q$ and $q+n=q_1$ are prime.

(b)$\Rightarrow$(a): Fix even $n\le p-3$. By (b) there is a prime $q\le p-n$ with $q$ and $q+n$ prime. Set $q_2=q$ and $q_1=q+n$. Then $q_1,q_2\le p$ and $q_1-q_2=n$. This is exactly (a). $\square$

Lemma 17.2 (a combinatorial lower bound on $\pi(p)$ from the cluster property). Let $p$ be a cluster prime and let $\pi(p)=|\mathcal P(p)|$. Then \[ \binom{\pi(p)}{2}\ \ge\ \frac{p-3}{2}. \] Equivalently, $\pi(p)$ must satisfy \[ \pi(p)\ge \left\lceil\frac{1+\sqrt{1+4(p-3)}}{2}\right\rceil. \]

Proof. Because $p>2$ implies $p$ is odd, every even $n$ with $2\le n\le p-3$ is an even positive integer. Since $p$ is cluster, for each such even $n$ there exist primes $q_1>q_2$ in $\mathcal P(p)$ with $q_1-q_2=n$. In particular, each such $n$ occurs as a positive difference between two distinct primes $\le p$.

There are exactly $(p-3)/2$ even integers in the interval $[2,p-3]$.

On the other hand, the number of ordered pairs $(q_1,q_2)$ of distinct primes with $q_1>q_2$ is exactly $\binom{\pi(p)}{2}$. Each such ordered pair contributes at most one positive difference $q_1-q_2$, so the set of attainable positive differences has size at most $\binom{\pi(p)}{2}$. Therefore, to cover all $(p-3)/2$ required even differences, we must have $\binom{\pi(p)}{2}\ge (p-3)/2$.

Solving $\pi(p)(\pi(p)-1)/2\ge (p-3)/2$ gives $\pi(p)(\pi(p)-1)\ge p-3$, and the quadratic formula yields the stated lower bound on $\pi(p)$. $\square$

5) VERIFICATION

- Quantifiers: Lemma 17.1 checks the same $n$-range $2\le n\le p-3$ and keeps the constraint $q_1,q_2\le p$; the equivalence is exact. - Edge cases: For $p\le 3$ the definition is vacuous; Lemma 17.1 still holds because the quantified set of $n$ is empty. - Lemma 17.2: The only nontrivial step is the counting bound "distinct positive differences $\le$ number of ordered pairs"; this is correct because the map $(q_1,q_2)\mapsto q_1-q_2$ may collide, so counting pairs is an upper bound on distinct differences. - Sanity check: for $p=5$, $\pi(5)=3$ and $\binom{3}{2}=3\ge (5-3)/2=1$, consistent.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: - Exact reformulation (Lemma 17.1). - A necessary combinatorial constraint $\binom{\pi(p)}{2}\ge (p-3)/2$ for any cluster prime $p$ (Lemma 17.2). - Verified exact small cases: all cluster primes $\le 300$ listed above, and explicit failure at $p=97$ via $n=88$.

(ii) First gap (crisp): Prove or disprove \[ \text{there exist infinitely many primes }p\text{ such that }\forall\text{ even }n\le p-3\ \exists\text{ primes }q,q+n\le p. \]

(iii) Top 3 next moves (concrete): 1. For each non-cluster prime $p$ observed computationally, the first failing $n$ is close to $p$ (e.g., $97\mapsto 88$). Prove a structural lemma of the form: if $p$ is large and a specific short list of prime gaps up to some bound occurs below $p$, then $p$ is cluster. 2. Attempt to show that if $p$ is cluster then the prime set $\mathcal P(p)$ must contain a prime in each residue class modulo many small moduli (because each even gap imposes a pair constraint); formalize and see whether this is plausible/impossible. 3. Computationally extend the verified range (e.g., to $p\le 10^5$) and tabulate the distribution of the first failing $n$; look for a pattern that could be proved (e.g., failures coming from $n=p-q$ where $q$ is the smallest prime not producing a prime $p-q+q$).

(iv) Minimal counterexample structure (if the answer is "finitely many"): A minimal obstruction prime $p$ would come with a smallest even $n\le p-3$ such that the prime-pair system $\{q\le p-n: q,q+n\text{ prime}\}$ is empty; empirically in small data $n$ is large (close to $p$), forcing $q$ to lie among the very small primes. Proving infinitely many obstructions would amount to constructing infinitely many primes $p$ for which some large even $n$ forces $q$ into a finite set that yields no valid $q+n$.