Erdős Problem #238

Erdős Problem #238 (Round 2)

1) ROUND-2 OBJECTIVE

Path (C): obstruction/correction. Round 1 already proved a weak Erdős-type theorem: for each fixed $c_2>0$, one can force a block of more than $c_1^*(c_2)\log x$ consecutive primes whose internal gaps all exceed $c_2$. The exact gap was quantitative: no explicit dependence on $c_2$ was obtained, and there was no explanation of why the simple counting strategy stops short of the full conjecture.

In this round I will do two things.

• First, sharpen the partial theorem to an explicit bound \[ L_{c_2}(x)\gg \frac{\log x}{1+\lfloor c_2\rfloor}, \] where $L_{c_2}(x)$ is the maximal length of such a block.
• Second, prove that the Round-1 pigeonhole strategy is combinatorially sharp: global control of the number of small gaps cannot by itself yield anything stronger than a constant multiple of $\log x/c_2$.

2) Round-1 FOUNDATION USED

I use the following Round-1 ingredients.

• Round-1 Theorem 238.2: for each fixed $c_2>0$ there exists some $c_1^*(c_2)>0$ such that $L_{c_2}(x)>c_1^*(c_2)\log x$ for all large $x$.
• The block-decomposition inequality from Round 1: if $m=\pi(x)$ and $B(x)$ is the number of indices $i<m$ with $p_{i+1}-p_i\le c_2$, then \[ L_{c_2}(x)\ge \frac{m}{B(x)+1}. \]

3) NEW INSIGHT / TOOL (ROUND-2)

The new ingredient is the same divisor-sum averaging device from Problem #234: \[ \sum_{h\le H}\frac{h}{\phi(h)}\ll H. \] When combined with the Selberg-sieve prime-pair upper bound, this yields an explicit estimate \[ B(x)\ll H\,\frac{x}{(\log x)^2}, \qquad H:=\lfloor c_2\rfloor. \] The second new ingredient is a purely combinatorial sharpness lemma showing that the bound $L\ge m/(B+1)$ cannot be improved using only the single scalar datum "there are at most $B$ bad gaps".

4) ATTACK PLAN (ROUND-2)

The exact unresolved issue after Round 1 was: why does the elementary sieve-plus-pigeonhole method only give some unspecified $c_1^*(c_2)$, and how close is that method to optimal? I now prove two precise claims.

Claim 238-R2(a). For every fixed $c_2>0$, \[ L_{c_2}(x)\gg \frac{\log x}{1+\lfloor c_2\rfloor} \qquad (x\to\infty). \]

Claim 238-R2(b). Any method using only the numerical inequality $B(x)\le B$ and the path decomposition into good blocks is combinatorially sharp up to constants; in particular, such a method can never force a block much longer than $m/(B+1)$ without extra information on how the bad gaps are distributed.

This isolates the real missing ingredient for the full conjecture: one needs nontrivial information about the spacing pattern of the small gaps, not merely their total number.

5) WORK (ROUND-2)

Let $p_1<p_2<\cdots<p_{\pi(x)}\le x$ be the primes up to $x$, and let \[ L_{c_2}(x):=\max\left\{\ell:\ \text{there exists a block of }\ell\text{ consecutive primes }\le x\text{ with all pairwise differences }>c_2\right\}. \] Because adjacent gaps are positive integers, the condition "all pairwise differences exceed $c_2$" is equivalent to saying that every adjacent gap inside the block is at least $H+1$, where \[ H:=\lfloor c_2\rfloor. \] If $H=0$, then every gap between odd primes already exceeds $c_2$, so apart from the initial pair $(2,3)$ one may take essentially all primes up to $x$. Thus the interesting case is $H\ge 1$.

As before, call a gap bad if \[ p_{i+1}-p_i\le H. \] Let $B_H(x)$ be the number of bad indices $i<\pi(x)$. Removing bad edges partitions the path of primes into blocks, each of which has all adjacent gaps $>c_2$. Therefore \[ L_{c_2}(x)\ge \frac{\pi(x)}{B_H(x)+1}. \] So it remains to bound $B_H(x)$.

Theorem 238.2.1 (explicit quantitative partial theorem). For every fixed $c_2>0$, \[ L_{c_2}(x)\gg \frac{\log x}{1+\lfloor c_2\rfloor} \qquad (x\to\infty). \]

Proof. If $H=0$, then as noted above the conclusion is trivial, so assume $H\ge 1$.

Every bad gap of size $h\ge 2$ produces a prime pair $(p,p+h)$ with both entries prime. The gap $1$ occurs only once, namely between $2$ and $3$. Hence \[ B_H(x) \le 1+\sum_{2\le h\le H}\Pi(x;h), \] where $\Pi(x;h)$ counts prime pairs $p,p+h\le x$.

By the prime-pair Selberg-sieve estimate, \[ \Pi(x;h)\ll \frac{h}{\phi(h)}\frac{x}{(\log x)^2}. \] Therefore \[ B_H(x) \ll 1+\frac{x}{(\log x)^2}\sum_{2\le h\le H}\frac{h}{\phi(h)}. \] By the divisor-sum lemma proved in Problem #234, \[ \sum_{h\le H}\frac{h}{\phi(h)}\ll H. \] Thus \[ B_H(x)\ll 1+H\frac{x}{(\log x)^2}. \] On the other hand, the prime number theorem gives \[ \pi(x)\asymp \frac{x}{\log x}. \] Substituting into the block inequality yields \[ L_{c_2}(x) \ge \frac{\pi(x)}{B_H(x)+1} \gg \frac{x/\log x}{H x/(\log x)^2+1} \gg \frac{\log x}{H+1} \] for all sufficiently large $x$. Since $H=\lfloor c_2\rfloor$, this is exactly \[ L_{c_2}(x)\gg \frac{\log x}{1+\lfloor c_2\rfloor}. \] $\square$

This sharpens Round 1 by making the $c_2$-dependence explicit.

Now comes the obstruction statement.

Lemma 238.2.2 (sharpness of the block-counting step). Let $m\ge 1$ and $B\ge 0$ be integers. There exists a path on $m$ vertices with exactly $B$ marked edges such that the largest connected component after deleting the marked edges has size at most \[ \left\lceil \frac{m}{B+1}\right\rceil. \] Equivalently: from the single datum "at most $B$ bad gaps among $m-1$ total gaps", the inequality \[ L\ge \frac{m}{B+1} \] is best possible up to rounding.

Proof. Write \[ m=q(B+1)+r \qquad (0\le r\le B). \] Construct $B+1$ blocks of vertices, with $r$ blocks of size $q+1$ and $B+1-r$ blocks of size $q$. Separate consecutive blocks by one marked edge. Then the total number of vertices is exactly \[ r(q+1)+(B+1-r)q = q(B+1)+r = m, \] and the number of marked edges is exactly $B$. The largest block has size $q+1=\lceil m/(B+1)\rceil$. $\square$

Corollary 238.2.3 (method barrier). Suppose one only knows a bound of the form \[ B_H(x)\ll H\frac{x}{(\log x)^2} \] and then argues solely by partitioning the prime path into blocks. Then, even in the abstract combinatorial model, one can force at most \[ L_{c_2}(x)\gg \frac{\log x}{H} \asymp \frac{\log x}{c_2}. \] Thus the full conjecture for arbitrary $c_1$ cannot follow from global counting of small gaps alone; one needs additional information on their distribution.

Proof. Take $m\asymp x/\log x$ and $B\asymp Hx/(\log x)^2$. By Lemma 238.2.2 there are abstract configurations with longest good block of order exactly $m/(B+1)\asymp \log x/H$. So no argument using only the scalar bound on $B$ can prove a larger lower bound in general. $\square$

6) ADVERSARIAL VERIFICATION

• What about the case $0<c_2<1$? I handled it separately. Then every prime gap except possibly the initial gap $1$ already exceeds $c_2$, so the theorem is stronger than stated.

• Did I use pairwise differences or only adjacent gaps? For consecutive primes these are equivalent: if every adjacent gap in the block exceeds $c_2$, then any non-adjacent difference is a sum of such gaps and is therefore even larger.

• Could the prime-pair count overcount bad gaps? Yes, deliberately so. Every bad gap gives a prime pair, and overcounting is harmless for an upper bound on $B_H(x)$.

• Is the barrier lemma really relevant to the prime problem? It is relevant to the method. It shows that the precise Round-1/2 strategy based only on counting bad gaps is saturated; to improve the theorem one must bring in extra arithmetic information.

• Did the new theorem solve the original conjecture? No. It still gives only a fixed multiple of $\log x$; the original conjecture asks for more than $c_1\log x$ for every prescribed $c_1>0$.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The strict new advances beyond Round 1 are:

• an explicit quantitative bound \[ L_{c_2}(x)\gg \frac{\log x}{1+\lfloor c_2\rfloor}; \]
• a proof that the underlying sieve-plus-pigeonhole method is already combinatorially sharp up to constants, so any further progress toward the full conjecture must use information beyond the total number of small gaps.

This identifies the real obstruction left by Round 1: not the quantity of small gaps, but their spacing pattern.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 68%

References

Only references actually used or checked in this round are listed.

1. T. F. Bloom, Erdős Problem #234, erdosproblems.com, accessed 2026-03-07.
2. T. F. Bloom, Erdős Problem #236, erdosproblems.com, accessed 2026-03-07.
3. T. F. Bloom, Erdős Problem #238, erdosproblems.com, accessed 2026-03-07.
4. H. Halberstam and H.-E. Richert, Sieve Methods, Academic Press, 1974.
5. H. L. Montgomery and R. C. Vaughan, Multiplicative Number Theory I: Classical Theory, Cambridge University Press, 2007.

Erdős Problem #238: independent continuation

1) TARGET AND SOURCE AUDIT

All supplied versions considered: 238.tex. The source gives a fixed multiple of $\log x$ from the count of bad gaps. Its sharpness lemma omits $0\le B\le m-1$ and incorrectly calls the maximum $q+1$ when the remainder is zero. Both defects are repaired by the exact formula below.

2) WORK

A more informative input would be a local bad-gap count. For any consecutive index interval $I$ containing $m_I$ prime vertices and $b_I$ bad internal gaps, the same proof gives \[ L_{c_2}(x)\ge\max_I\left\lceil{m_I\over b_I+1}\right\rceil. \] Thus a sufficient genuinely stronger route is to find intervals with $m_I/(b_I+1)\gg c_1\log x$ for any desired $c_1$. A global count $B$ does not guarantee them: the balanced construction above distributes the deleted edges nearly periodically and attains the global lower bound on every large block up to endpoint errors.

3) ADVERSARIAL VERIFICATION

4) FINAL

5) SOURCES CHECKED

6) COMPLETION ESTIMATE

Erdős Problem #238

1. FORMAL RESTATEMENT.

   Fix constants $c_1,c_2>0$. For $x\ge 2$, let \[2=p_1<p_2<p_3<\cdots<p_{\pi(x)}\le x\] be the primes up to $x$.

   A "block of $L$ consecutive primes $\le x$" means an index $i$ such that \[p_i, p_{i+1},\dots,p_{i+L-1}\le x\] (and these primes are consecutive in the global sequence of primes).

   The condition "the difference between any two is $>c_2$" for a block of consecutive primes is equivalent to requiring that every adjacent gap inside the block satisfies \[p_{i+j+1}-p_{i+j}>c_2\qquad (0\le j\le L-2),\] because all other pairwise differences are sums of adjacent gaps and are therefore even larger.

   Claim/conjecture. For every $c_1,c_2>0$, for all sufficiently large $x$ there exists a block of length \[L > c_1\log x\] consecutive primes $\le x$ such that all adjacent gaps within the block exceed $c_2$.

   Equivalently, if $M(x)$ denotes the maximum length of a consecutive-prime block $\le x$ with all internal gaps $>c_2$, the conjecture asserts that \[\forall c_1>0\ \exists x_0:\ \forall x\ge x_0,\quad M(x)>c_1\log x,\] i.e. $M(x)/\log x\to\infty$.

2. QUICK LITERATURE/CONTEXT CHECK.

   A standard sieve bound (Brun/Selberg) gives for each fixed integer $d\ge 1$ an upper bound of the shape \[\#\{p\le x: p\ \text{and}\ p+d\ \text{prime}\}\ \ll_d\ \frac{x}{(\log x)^2}. \] From this one can deduce that the number of prime gaps $\le c_2$ up to $x$ is $\ll x/(\log x)^2$, which already implies the conjectured phenomenon for sufficiently small $c_1$ (depending on $c_2$): there must be at least one long block with no such small gaps. This matches the partial result attributed to Erdős on the problem page.

   The full conjecture asks for blocks longer than any constant multiple of $\log x$, i.e. a super-logarithmic block length; this is currently out of reach in this write-up.

3. ATTACK PLAN.

   Proof strategies.

   • $P1$ Bound the number $B(x)$ of indices $i<\pi(x)$ with gap $p_{i+1}-p_i\le c_2$ by sieve methods; then use a pigeonhole/block decomposition argument to force a long run of gaps $>c_2$.
   • $P2$ Strengthen $P1$ by proving that such "small gaps" cannot be too evenly distributed in $i$, forcing a block length $\omega(\log x)$. (No known unconditional method in this write-up accomplishes this strengthening.)

   Disproof/construction strategies.

   • $D1$ A counterexample would require exhibiting $c_1,c_2$ and arbitrarily large $x$ for which every block of $>c_1\log x$ consecutive primes $\le x$ contains a gap $\le c_2$. Establishing this would in particular require strong lower bounds and distributional control on the occurrence of small prime gaps, beyond what is known here.

   Best path chosen here. I carry out $P1$ completely, yielding the known "$c_1$ sufficiently small" version with a fully rigorous proof assuming a standard Brun/Selberg sieve upper bound for prime pairs.

4. WORK.

   Lemma 238.1 (Sieve upper bound for prime pairs).

   Fix an integer $d\ge 1$. Let \[\pi_2(x;d):=\#\{p\le x: p\ \text{and}\ p+d\ \text{are prime}\}.\] Then there exists a constant $C(d)>0$ and an $x_0(d)$ such that for all $x\ge x_0(d)$, \[\pi_2(x;d)\le C(d)\,\frac{x}{(\log x)^2}.\]
   Proof[Justification]: This is a standard consequence of Brun's sieve / the Selberg upper-bound sieve applied to the admissible 2-tuple $(0,d)$. The constant $C(d)$ is ineffective in this write-up but depends only on $d$. ∎

   Theorem 238.2 (Erdős' "small $c_1$" version).

   Fix $c_2>0$. Then there exists a constant $c_1^\ast=c_1^\ast(c_2)>0$ such that for all sufficiently large $x$ there are more than $c_1^\ast\log x$ consecutive primes $\le x$ whose pairwise differences are all $>c_2$ (equivalently, all adjacent gaps inside the block are $>c_2$).
   Proof: Let $p_1<p_2<\dots<p_m\le x$ be the primes $\le x$, where $m=\pi(x)$. For $1\le i\le m-1$ call the index $i$ bad if the consecutive gap satisfies \[p_{i+1}-p_i\le c_2. \] Let $B(x)$ be the number of bad indices.

   Step 1: block decomposition. Removing the $B(x)$ bad "edges" partitions the ordered list $p_1,\dots,p_m$ into at most $B(x)+1$ consecutive blocks, each block having all internal adjacent gaps $>c_2$. Let $L(x)$ be the maximum block length (number of primes in the largest such block). Then \[m\le (B(x)+1)\,L(x),\] so \[L(x)\ge \frac{m}{B(x)+1}. \]

   Step 2: bound the number of bad indices. For each integer $d\in\{1,2,\dots,\lfloor c_2\rfloor\}$ let $N_d(x)$ be the number of indices $i$ with $p_{i+1}-p_i=d$. Then \[B(x)=\sum_{d\le c_2} N_d(x). \] For each $d$, the pair $(p_i,p_{i+1})$ counted by $N_d(x)$ is certainly a pair of primes $(p,p+d)$ with $p\le x$, hence \[N_d(x)\le \pi_2(x;d). \] Therefore \[ B(x)\le \sum_{d\le c_2} \pi_2(x;d). \] Applying Lemma 238.1 for each fixed $d$ and absorbing the finite sum into a single constant gives \[ B(x)\le C(c_2)\,\frac{x}{(\log x)^2} \] for all sufficiently large $x$, for some constant $C(c_2)>0$.

   Step 3: finish using PNT. By the Prime Number Theorem, for all sufficiently large $x$, \[m=\pi(x)\ge \frac{1}{2}\frac{x}{\log x}. \] Hence, for large $x$, \[ L(x)\ge \frac{m}{B(x)+1} \ge \frac{\tfrac12 x/\log x}{2C(c_2)\,x/(\log x)^2} =\frac{1}{4C(c_2)}\,\log x. \] Taking \[c_1^\ast:=\frac{1}{5C(c_2)} \] and enlarging $x$ if necessary ensures $L(x)>c_1^\ast\log x$. Any block of length $L(x)$ then supplies $>c_1^\ast\log x$ consecutive primes with all internal gaps $>c_2$, hence all pairwise differences $>c_2$. ∎

   Remark. The open problem asks whether $L(x)/\log x\to\infty$ (equivalently: for every fixed $c_1>0$ and all large $x$, $L(x)>c_1\log x$). The above argument gives only $L(x)\gg_{c_2}\log x$.

5. VERIFICATION.
   • Equivalence of "any two" vs "adjacent". For a block of consecutive primes, if each adjacent difference is $>c_2$, then any non-adjacent pair differs by a sum of adjacent gaps and is therefore also $>c_2$.
   • Block counting inequality. If $B$ edges are removed from a path on $m$ vertices, one gets at most $B+1$ connected components (blocks). The maximum block size is at least $m/(B+1)$.
   • Use of sieve bound. We only require an upper bound on prime pairs at distance $d$; no conjectural asymptotic is used.
   • Edge cases. Small primes (e.g. the gap $1$ between $2$ and $3$) affect only finitely many indices and do not matter for large $x$.

6. FINAL.

   UNRESOLVED.

   • (i) Strongest fully proved partial result obtained here. For each fixed $c_2>0$, there exists $c_1^\ast(c_2)>0$ such that for all sufficiently large $x$ there are $>c_1^\ast\log x$ consecutive primes $\le x$ whose internal gaps are all $>c_2$.
   • (ii) First gap. To reach the full conjecture for an arbitrary prescribed $c_1>0$, one would need to prove $L(x)/\log x\to\infty$, which is strictly stronger than the counting argument driven only by the bound $B(x)\ll x/(\log x)^2$.
   • (iii) Top 3 next moves.
     • Prove that the indices of small gaps $\le c_2$ cannot be "nearly evenly spaced" on the scale of $\log x$; any quantitative irregularity would push $L(x)$ above a fixed multiple of $\log x$.
     • Seek stronger upper bounds of the form $B(x)=o(x/(\log x)^2)$ (or local versions on intervals) which would immediately force $L(x)=\omega(\log x)$ by the same block argument.
     • Investigate whether modern results on correlations of primes (or conditional Hardy--Littlewood inputs) imply that the longest run of gaps $>c_2$ is typically much larger than its average spacing.
   • (iv) What a minimal counterexample would likely look like. Fixed $c_1,c_2>0$ and an unbounded sequence $x_j\to\infty$ such that every block of $>c_1\log x_j$ consecutive primes $\le x_j$ contains a gap $\le c_2$; i.e. the "small-gap indices" form a hitting set for all long blocks.

7. COMPLETION ESTIMATE (MANDATORY).
   COMPLETION: 60%.