Erdős problem #970 — wave w026

Accessed 2026-07-29. This is a partial result, not a solution of the quadratic upper-bound conjecture.

Claim labels

• (a) elementary-rigorous: proved below from elementary facts.
• (b) rigorous modulo named theorem: the deduction is rigorous, conditional

only on the correctly cited published theorem.

• (c) plausible/structural-unverified: heuristic or an explicitly identified

possible route, not used as a theorem.

• (d) computational-only: established by the exhaustive program supplied

with this report, or reported as computation by a cited paper.

0. Mandatory live-page check

The page <https://www.erdosproblems.com/970> was loaded through the Bright Data browser path, not datacenter curl. The rendered page said OPEN.

Verbatim current statement

Let \(h(k)\) be Jacobsthal's function, defined to as the minimal \(m\) such that, if \(n\) has at most \(k\) prime factors, then in any set of \(m\) consecutive integers there exists an integer coprime to \(n\). Determine the order of magnitude of \(h(k)\). In particular, is it true that \[ > h(k)\ll k^2? > \]

Verbatim known-results text

That \(h(k) \ll k^2\) is a conjecture of Jacobsthal. Iwaniec [Iw78] proved \[ > h(k)\ll(k\log k)^2. > \] The best lower bound known is \[ > h(k)\gg > \frac{(\log k)(\log\log\log k)}{(\log\log k)^2}k, > \] due to Ford, Green, Konyagin, Maynard, and Tao [FGKMT18].

This is a more general form of the function considered in [687].

(b, page-source) The page displayed all of the following:

| field | live value | |---|---| | comments | 0 comments on this problem | | claimed proofs | 0 claimed proofs for this problem | | Interested in collaborating | None | | Currently working on this problem | None | | Likes / difficult / tractable / formalisable markers | all None | | formalisation | No |

Thus no stop condition applied.

1. Notation warning

The literature uses incompatible names for three functions. I use:

Here \(\omega(n)\) counts distinct prime divisors. Powers do not affect coprimality, so the live page's function is \(H(k)\), regardless of whether its phrase “prime factors” is read with or without multiplicity. (a)

This distinction matters: much computational literature calls the primorial-only function \(h\), while the live page calls the general maximum \(h\).

2. Primary-source literature audit

1. Iwaniec (1978). H. Iwaniec, “On the problem of Jacobsthal,”

Demonstratio Mathematica 11 (1978), 225–232, DOI <https://doi.org/10.1515/dema-1978-0121>. The paper defines \(C(r)\) as the maximum length of a consecutive sequence covered by \(r\) arbitrary primes and proves the corollary \(C(r)\ll r^2\log^2 r\). Since \(H(r)=C(r)+1\), this is exactly the upper estimate quoted on the live page. (b)

1. Ford–Green–Konyagin–Maynard–Tao (2018). K. Ford, B. Green,

S. Konyagin, J. Maynard and T. Tao, “Long gaps between primes,” JAMS 31 (2018), 65–105, DOI <https://doi.org/10.1090/jams/876>, arXiv <https://arxiv.org/abs/1412.5029>. Their Definition 1 and equations (1.2), (1.3) state \[ Y(x)=j(P(x))-1,\qquad Y(x)\gg \frac{x\log x\,\log_3x}{\log_2x}, \tag{FGKMT} \] where \(P(x)=\prod_{p\le x}p\) and \(\log_i\) is the \(i\)-fold iterated logarithm. (b)

1. Hajdu–Saradha (2012). L. Hajdu and N. Saradha, “Disproof of a

conjecture of Jacobsthal,” Mathematics of Computation 81 (2012), 2461–2471, DOI <https://doi.org/10.1090/S0025-5718-2012-02581-6>. Theorem 1.2 proves \(H(k)=h_{\rm prim}(k)\) for \(k\leq23\), but \(H(24)=236>234=h_{\rm prim}(24)\). This verifies that primorial computations cannot silently be substituted for the live function. (b)

1. Ziller (2019). M. Ziller, “New computational results on a conjecture

of Jacobsthal,” arXiv:1903.11973v2, <https://arxiv.org/abs/1903.11973>. Table 2 reports exhaustive general values through \(H(43)=610\), with several further failures of \(H(k)=h_{\rm prim}(k)\). This is an arXiv computational preprint, so I classify its table as (d) rather than silently promoting it to a theorem. The exact computation below does not import its values.

Targeted searches for the exact title, “maximum Jacobsthal function,” “order of magnitude of Jacobsthal's function,” later citing work, and post-2019 arXiv papers found no later primary source improving Iwaniec's general upper bound or extending the general exact table past \(k=43\). This is an honest search miss, not a proof that no such source exists.

3. A stronger lower bound already follows from the cited FGKMT theorem

This is the main rigorous progress in this run.

Set \(x=p_k\) in (FGKMT). The integer

has exactly \(k\) distinct prime divisors, hence

By the prime number theorem \(p_k\sim k\log k\), and therefore

Consequently

This deduction is (b), rigorous modulo FGKMT and the prime number theorem.

The shape on the live page is

The ratio of (1)'s shape to the page's shape is exactly

Thus the page's displayed estimate is a valid weaker consequence but is not the strongest reparameterisation of the very paper it cites. The standalone checker recomputes this algebraic ratio numerically as a guard against a lost iterated logarithm. (a) for the algebra; (b) for (1).

This does not approach the conjectured upper bound: the verified current gap remains

Both inequalities here are (b).

4. Exact finite reduction for concrete cases

4.1 Residue-cover equivalence

There are \(L\) consecutive integers, all non-coprime to a number with at most \(k\) distinct prime factors, if and only if \([1,L]\) can be covered by at most \(k\) classes

using at most one class for each distinct prime \(p\). The forward implication takes \(r_p\equiv-a\pmod p\) for a run \(a+1,\ldots,a+L\). Conversely, the Chinese remainder theorem supplies one \(a\) satisfying \(a\equiv-r_p\pmod p\) for every selected prime. (a)

A prime \(p\geq L\) meets \([1,L]\) in at most one point. Every such class can therefore be treated as a singleton. Conversely, every singleton can be assigned its own fresh prime \(q>L\), after which the Chinese remainder theorem again applies. Hence fixed-\((L,k)\) coverability is the finite problem:

• enumerate primes \(p<L\), one residue class at most for each;
• allow the remaining budget as singleton points.

This removes the apparent infinite choice of primes without a conjectural cutoff. (a)

4.2 Separating the prime 2

Let \(\Omega(s)\) be the largest \(L\) coverable by at most \(s-1\) distinct odd-prime classes. If a \(k\)-prime cover omits 2, its longest run has length \(\Omega(k+1)\). If it uses 2, one parity is covered by 2 and the other parity, after division by 2 modulo every odd prime, is an interval covered by \(k-1\) odd-prime classes. This gives the exact identity

Achievability of the second branch is explicit: if classes \((p,r_p)\) cover \([1,m]\), then

cover \([1,2m+1]\). (a)

4.3 Exhaustive algorithm

The supplied program performs a depth-first decision search on the bit mask of uncovered points. At each node it chooses an uncovered pivot and exhausts:

1. every residue class of every unused prime \(p<L\) that covers the pivot and

at least one other currently uncovered point;

1. a singleton branch for the pivot.

Skipping a class with marginal gain one is safe because a fresh prime \(q>L\) replaces it using the same budget. The only numerical prune sums, over the remaining primes, the largest possible marginal gains while ignoring overlaps and fills unused slots with gain-one singletons. It is an upper bound on possible future coverage, so pruning when even that sum is too small is sound. Failed states \((\text{uncovered mask},\text{used primes},\text{budget})\) are memoised. (a) for search completeness and pruning validity.

The resulting values are computational claims:

| \(s\) | \(\Omega(s)\) | nodes exhausting \([1,\Omega(s)+1]\) | seconds | |---:|---:|---:|---:| | 2 | 1 | 1 | 0.000 | | 3 | 2 | 1 | 0.000 | | 4 | 4 | 1 | 0.000 | | 5 | 6 | 3 | 0.000 | | 6 | 10 | 7 | 0.000 | | 7 | 12 | 13 | 0.000 | | 8 | 16 | 55 | 0.001 | | 9 | 19 | 129 | 0.003 | | 10 | 22 | 470 | 0.010 | | 11 | 28 | 1,132 | 0.028 | | 12 | 32 | 4,519 | 0.163 | | 13 | 36 | 23,486 | 0.867 | | 14 | 44 | 95,529 | 5.000 | | 15 | 49 | 362,468 | 21.439 |

Applying (2) gives:

| \(k\) | live-page function \(H(k)\) | |---:|---:| | 1 | 2 | | 2 | 4 | | 3 | 6 | | 4 | 10 | | 5 | 14 | | 6 | 22 | | 7 | 26 | | 8 | 34 | | 9 | 40 | | 10 | 46 | | 11 | 58 | | 12 | 66 | | 13 | 74 | | 14 | 90 |

Every lower value has a residue-class/CRT witness; every upper value comes from exhausting the next interval for the relevant \(\Omega\)-values. The complete run took 28.643 wall-seconds on one core and ended ALL CHECKS PASSED. The exact table is (d); its reduction to the finite search is (a). It independently agrees with the corresponding portion of Hajdu–Saradha's table.

5. Explicit largest-case certificate from this computation

Let

and

The following 14 classes cover every \(t\in[1,89]\):

The checker verifies from scratch that

for every column and hence

It also verifies

Thus \(j(n)\geq90\) for an \(n\) with 14 distinct prime factors. This lower certificate is (a). Combined with the exhaustive finite upper search, it gives the computationally exact \(H(14)=90\), classified (d).

6. The next exact case and the computational wall

Ziller's table ends at \(H(43)=610\). A directly checked primorial certificate uses

The checker forms the product \(N\) of the first 44 primes and verifies

with the two neighbouring terms coprime to \(N\). Therefore

The explicit lower certificate is (a); it is not an exact value.

An improvement through the branch containing 2 would require only one very specific object: 43 distinct odd-prime residue classes covering \([1,308]\). Interleaving with the class \(1\bmod2\) would then prove \(H(44)\geq618\). Under Ziller's balanced-cover Proposition 2.8 it suffices, for a maximal cover, to consider odd primes at most 293. (b)

I encoded that \(308\)-point target with 8,273 Boolean residue choices: at most one residue per prime, at most 43 selected primes, and one coverage clause per point. A 60-second single-core hinted CP-SAT optimisation retained the checked 307-point primorial cover and returned objective 307 with upper bound 308. An initial 60-second eight-worker feasibility diagnostic also returned UNKNOWN. These are (d) non-results: neither output is evidence that a 308-cover does not exist. The optional command

python runs/erdos970_wavew026_reverify.py --max-k 1 --probe44-seconds 60

reconstructs the single-core experiment. It is deliberately separate from the exact standard-library verifier.

To turn this into an exact result one needs either:

1. a covering witness (immediately and cheaply checkable); or
2. a proof-producing exhaustive non-cover certificate for \([1,308]\), followed

by control of the all-odd \(\Omega(45)+1\) branch in (2).

A concrete sharding design that fixes “unused or one residue” for the first five odd primes has

top-level shards. At ten single-core minutes per shard this is about 5,376 core-hours, before the separate \(\Omega(45)\) check. This is a costed campaign design, not a prediction that every shard finishes in ten minutes; calibration is required. I did not run it. (c)

7. Why the asymptotic upper bound stalls

The exact missing uniform statement is:

For every choice of \(k\) distinct primes and every choice of one residue class modulo each, an interval of length \(Ck^2\) has an uncovered point, for one absolute \(C\).

This is simply the conjecture in its finite covering form. Iwaniec's shifted linear-sieve argument proves the same assertion at length \(C(k\log k)^2\). The source explicitly notes the one-dimensional sieve limit: the method reaches exponent 2 but retains the logarithmic loss. Removing that loss requires a new uniform lower bound for the sifted set in an adversarial individual interval, not an average-over-shifts estimate. No such lemma was found in the primary-source search. (b) for what Iwaniec proves; (c) for the diagnosis that a new parity-breaking/uniform remainder input is the needed route.

Finite computations cannot supply the uniformity in \(k\), and the stronger lower bound (1) does not decide the quadratic upper bound. The original problem therefore remains open.

8. Reproduction

Run:

python runs/erdos970_wavew026_reverify.py

The verifier uses no downloaded table and no non-standard package for the exact \(k\leq14\) computation. It recomputes primes, residue masks, witnesses, CRT starts, exhaustive non-cover searches, the fixed \(k=14\) certificate, and the \(k=44\) primorial lower certificate.

PARTIAL: FGKMT plus \(x=p_k\) rigorously strengthens the cited lower bound to \(H(k)\gg k(\log k)^2\log_3k/\log_2k\); an independent exhaustive checker gives exact \(H(k)\) for \(k\leq14\), but the quadratic upper bound remains open.