Erdős problem 854 — live-page audit, literature audit, a new lower bound, and exact checks

Date: 2026-07-27 (UTC)

Claim labels

• (a) elementary-rigorous: proved below from first principles.
• (b) rigorous-modulo-named-theorem: the only imported results are named explicitly.
• (c) plausible/structural-unverified: heuristic, search miss, or extrapolation; never used as a theorem.
• (d) computational-only: established by the companion exhaustive checker or reported as someone else's computation.

0. Mandatory live-page audit

I fetched the Cloudflare-protected live page with the Bright Data browser on 2026-07-27, then opened the full discussion thread in oldest-first order and expanded the hidden comment. The page says:

• status: OPEN;
• 0 claimed proofs;
• Currently working on this problem: None;
• Interested in collaborating: None;
• all the other displayed interest/difficulty/formalisation markers: None;
• seven comments;
• last page edit: 2025-11-04.

Thus the mandatory stop condition did not fire.

Verbatim current statement

> Let \(n_k\) denote the \(k\)th primorial, i.e. the product of the first \(k\) primes.

>

> If \(1=a_1

> \[ > \gg \max_i (a_{i+1}-a_i) > \]

> many even integers of the form \(a_{j+1}-a_j\)?

The page attributes this to [Er85c,p.80][Ob1]. Its listed remarks say that Erdős initially expected every even \(t\) up to the maximum gap to occur, but Lacampagne and Selfridge found the failure \(k=6\): the maximum is \(22\), while \(20\) does not occur. It also records Erdős's questions about the number and first position of maximum gaps.

All seven comments read

1. Dogmachine clarified that “smallest integer” must mean smallest even integer, since otherwise the answer is \(1\).

2. StijnC posted a long analysis of the different problem involving arbitrary differences \(a_i-a_j\), explicitly labelling it as a different variant.

3. StijnC removed another comment because it concerned that other variant.

4. Woett pointed out that arbitrary differences do not answer the consecutive-gap problem.

5. Dogmachine agreed that this explains why the problem remained open.

6. StijnC linked OEIS A389839 for the first missing consecutive gap and OEIS A048670 for primorial Jacobsthal values, noted the trivial “plus two” comparison, and reported no primorial hit in a small Scholar search.

7. Alfaiz reported that [Ob1] did not load a reference; the comment is marked as addressed by a site update.

No comment claims a proof of the stated problem.

1. Notation and a small convention issue

Let

where the coprime sequence is extended periodically. Put

(a) The periodic convention adds the wrap gap from \(P_k-1\) to \(P_k+1\), which is \(2\). For \(k=2\), the literal finite list on the live page is \((1,5)\), so its gap set is \(\{4\}\), while the periodic set is \(\{2,4\}\). Thus the literal finite answer at \(k=2\) is \(2\), whereas OEIS A389839 uses the periodic answer \(6\).

(a) For every \(k\geq3\), gap \(2\) also occurs internally. For example, impose by CRT that the left endpoint is \(2\bmod 3\), \(1\bmod5\), and an endpoint-safe residue modulo every later prime. This gives an internal coprime pair two apart. Every cyclic gap larger than \(2\) is automatically internal, because the two coprimes adjacent to a period boundary are \(P_k-1\) and \(P_k+1\). Hence the finite and periodic gap sets agree for all \(k\geq3\). All asymptotic claims below therefore answer the live statement without a convention change.

(a) \(H(k)\) is the primorial Jacobsthal function: a gap of length \(h\) is equivalent to \(h-1\) consecutive integers having a nontrivial common factor with \(P_k\), bounded on both sides by coprimes.

2. Primary-source literature check

Erdős's source

The primary scan P. Erdős, “Some Problems on Number Theory”, Congressus Numerantium 54 (1986), 225–244, states on printed page 231 that \(P_6=30030\), \(H(6)=22\), \(9461-9439=22\), and \(20\) is absent. It then asks for a positive constant proportion of occurring values below \(H(k)\) and for the first missing even value.

(d) The companion checker independently confirms

and checks every integer from \(9440\) through \(9460\) has gcd \(>1\) with \(30030\). It also enumerates the full \(P_6\)-period and confirms that \(20\) is absent.

The directly relevant paper missing from the live page

The exact-title search found Mario Ziller, “On differences between consecutive numbers coprime to primorials”, arXiv:2007.01808v1 [math.NT], 2020. The arXiv record and PDF exist and say exactly the following.

• (b) Ziller proves the same restricted-covering equivalence derived independently in §3 below.
• (b) His Corollary 2.8 proves that every \(2,4,\ldots,2k\) occurs. In the present notation this is \(F(k)\geq2k+2\).
• (d, author-reported) His adapted greedy permutation algorithm exhaustively computes through \(k=44\), including all missing values below \(H(k)\).
• (d, independently rechecked here for the stated range) The present checker reproduces \(F(k)\) exactly through \(k=13\), and directly enumerates the complete gap sets through \(k=8\).
• (c) Ziller conjectures \(F(k)>H(k-1)\), equivalently that every even value through \(H(k-1)\) occurs at stage \(k\). His table verifies this only for \(k\leq44\).

The Ziller table includes the original exceptions \(20\) at \(k=6\) and \(32\) at \(k=8\), and further missing values at later stages. It does not settle either asymptotic question.

OEIS and later-search result

OEIS A389839 currently gives

for \(F(k)\), \(2\leq k\leq12\), under the cyclic convention. It links the Erdős page but does not currently link Ziller from that entry. OEIS A048670, the sequence \(H(k)\), does link Ziller.

I searched exact titles, N_min(k) notation, “restricted coverings,” A389839, and combinations of “primorial,” “consecutive coprimes,” and “log log.” I found the Ziller paper, OEIS, the original Erdős scan, and derivative citations, but no later primary source proving a stronger bound for \(F(k)\) or resolving \(Q(k)\gg H(k)\). (c) This is an honest search miss, not a claim that no such source exists.

3. Exact reduction to endpoint-safe residue coverings

Lemma

(a) For \(k\geq2\) and \(r\geq1\), the even number \(2r\) lies in \(\mathcal G_k\) if and only if for every odd prime \(p\leq p_k\) one can choose a residue \(b_p\bmod p\) such that

and

Proof

Suppose \(x\) and \(x+2r\) are consecutive coprimes to \(P_k\). Both are odd. For every odd \(p\leq p_k\), set

Endpoint coprimality gives (1). Each odd-offset interior integer \(x+(2t-1)\) is even. Each even-offset interior integer \(x+2t\), \(1\leq t

Conversely, given (1)–(2), the Chinese remainder theorem supplies \(x\) satisfying

Condition (1) makes both endpoints coprime to \(P_k\). Odd-offset interior values are divisible by \(2\), and (2) gives an odd prime divisor of every even-offset interior value. Thus the endpoints are consecutive coprimes and their gap is \(2r\). ∎

This lemma also gives a transparent exhaustive algorithm: branch on an uncovered \(t\); any solution must assign one unused prime \(p\) its unique possible class \(t\bmod p\).

4. New rigorous progress: \(F(k)\) is at least order \(k\log\log k\)

Finite covering proposition

Let \(S\) be a set of odd primes not exceeding both \(r\) and \(p_k\), and write

(a) If

then \(2r\in\mathcal G_k\).

Proof

For every \(p\in S\), choose any class \(b_p\) satisfying (1). Such a class exists because \(p\geq3\). In a complete block of \(M\) consecutive positions, the number avoiding all selected classes is exactly

by the CRT. Splitting \(1,\ldots,r-1\) into complete \(M\)-blocks and one remainder shows that the uncovered set \(U\) satisfies

There are exactly \(k-\pi(r)\) primes \(q\) with \(r

Asymptotic theorem

Let \(\gamma\) denote Euler's constant.

(b) One has

Consequently,

Proof

Take

The prime number theorem in its \(\vartheta\)-form and Mertens's product theorem give

and

Choose \(\eta_k\to0\) slowly enough that

for example, the sum of

\(\sqrt{\log\log k/\log k}\) and \(k^{-1/4}\) works for all sufficiently large \(k\). Put

Then \(R=O(k\log\log k)\), so the prime number theorem gives

For every \(y\leq r\leq R\), equations (7)–(9) imply

The finite proposition therefore constructs every gap \(2r\) in this range.

For \(1\leq r

Thus \(2,4,\ldots,2R\) all occur. Hence \(F(k)\geq2R+2\) and \(Q(k)\geq R\). Finally, (8) gives

which proves (5)–(6). ∎

This improves the published uniform lower bound \(F(k)\geq2k+2\) by an unbounded factor. The targeted literature search above did not locate this \(k\log\log k\) bound, but (c) priority or novelty cannot be certified from a search alone.

5. Independent computation

The standalone checker is:

Run it from the repository root with:

python runs/erdos854_wave7p_verify.py

It uses only the Python standard library and has three independent layers.

5.1 Direct complete-period enumeration

(d) Every reduced residue is enumerated for \(3\leq k\leq8\):

| \(k\) | \(P_k\) | \(F(k)\) | \(H(k)\) | \(Q(k)\) |

|---:|---:|---:|---:|---:|

| 3 | 30 | 8 | 6 | 3 |

| 4 | 210 | 12 | 10 | 5 |

| 5 | 2310 | 16 | 14 | 7 |

| 6 | 30030 | 20 | 22 | 10 |

| 7 | 510510 | 28 | 26 | 13 |

| 8 | 9699690 | 32 | 34 | 16 |

The code separately constructs the finite and wrap-inclusive gap sets and asserts that they agree for every row.

5.2 Exhaustive restricted-cover search

For fixed \(k,r\), the solver stores the positions \(1,\ldots,r-1\) in a bitset. It chooses an uncovered position with the fewest available primes and branches over every possible prime that could cover it. It prunes only when either:

1. the union of all remaining classes cannot cover the uncovered set, or

2. the sum of the best individual remaining-prime capacities is too small.

Both are necessary conditions, so a negative result is exhaustive.

The core exhaustive step is:

position = an_uncovered_position_with_fewest_candidates()
for p in every_still_unused_prime_that_can_cover(position):
    # The residue is forced: b_p = position (mod p).
    search(covered | mask[p, position % p], used_primes | {p})

(d) This independently gives:

| \(k\) | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |

|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|

| \(F(k)\) | 6 | 8 | 12 | 16 | 20 | 28 | 32 | 42 | 48 | 60 | 68 | 76 |

The solver's positive certificates are checked class by class. For \(3\leq k\leq8\), every solver answer through and beyond \(H(k)\) is cross-checked against the independent gcd enumeration.

5.3 A concrete new certificate range at \(k=100\)

(d) For each \(1\leq r\leq240\), the checker:

1. greedily uses endpoint-safe classes for primes through \(47\);

2. assigns each remaining position a distinct prime \(q>r\);

3. completes all unused prime classes;

4. solves the resulting CRT system for an endpoint \(x\);

5. verifies \(\gcd(x,P_{100})=\gcd(x+2r,P_{100})=1\); and

6. verifies by gcd that every one of the \(2r-1\) interior integers is not coprime to \(P_{100}\).

Therefore

For the tight final construction \(r=240\), the small classes leave \(48\) positions and exactly \(48\) primes \(>240\) are used. The 100th primorial has 220 decimal digits.

5.4 Last executed output

direct enumeration (cyclic convention)
k  primorial  first_missing  max_gap  distinct_gaps
3 30 8 6 3
4 210 12 10 5
5 2310 16 14 7
6 30030 20 22 10
7 510510 28 26 13
8 9699690 32 34 16

exact restricted-cover search
k  first_missing  nodes_for_negative_instance
2 6 1
3 8 1
4 12 1
5 16 6
6 20 11
7 28 57
8 32 110
9 42 579
10 48 3110
11 60 10009
12 68 57714
13 76 473457

k=100 certificates: every 2r with 1<=r<=240 occurs; hence F(100)>=482
r=240 used 48 leftover positions and 48 primes >240; primorial digits=220; CRT endpoint digits=219

ALL CHECKS PASSED

6. What remains and the precise wall

(a) The original density question is \(Q(k)\gg H(k)\). The result here gives only

This is not a constant proportion of \(H(k)\).

(b) Known Jacobsthal machinery supplies an upper bound of shape

(Iwaniec's Jacobsthal bound, as recorded in the primary literature cited by Ziller). Combining it with (6) still leaves a factor on the order of \(k(\log k)^2/\log\log k\). It therefore cannot prove \(Q(k)\gg H(k)\).

The exact missing lemma can be stated in either of two useful forms:

1. Initial-segment route: prove \(F(k)\gg H(k)\). Ziller's stronger conjecture \(F(k)>H(k-1)\), plus a uniform comparison \(H(k-1)\gg H(k)\), would suffice, but neither required uniform statement is known.

2. Direct-count route: show that endpoint-safe one-class-per-prime coverings exist for \(cH(k)\) distinct lengths \(r\leq H(k)/2\), without requiring those lengths to form an initial interval. Existing unrestricted Jacobsthal coverings control only the maximum length and do not provide this endpoint-safe multiplicity.

(d) The simple exact solver also hits a concrete computational wall: the first negative instance used 473,457 nodes at \(k=13\), while a separate benchmark at \(k=14\) used 2,212,737 nodes and 55.48 seconds. The \(k=15\) run was stopped rather than exceed the few-minute policy. If the observed factor persisted, \(k=15\) would cost roughly 4–6 core-minutes and \(k=16\) roughly 20–30 core-minutes, but (c) that extrapolation is not a theorem or a reliable estimate at large \(k\). Ziller's specialized adapted GPA, not this transparent verifier, is the appropriate tool for extending the \(k=44\) table.

The problem remains open: no uniform comparison with \(H(k)\), no asymptotic for \(F(k)\), and no proof of a positive proportion of distinct gaps is obtained.

PARTIAL: Proved (modulo PNT and Mertens) liminf F(k)/(k log log k) >= e^gamma and Q(k) >= (e^gamma/2-o(1))k log log k; independently verified exact F(k) through k=13, full gap sets through k=8, and F(100)>=482, but Q(k) >> H(k) remains open.