Order of magnitude of Jacobsthal's function $h(k)$: is $h(k)\ll k^2$? (Erdős #970)
Statement
For a positive integer $n$, let $g(n)$ be the least $m$ such that every run of $m$ consecutive integers contains one coprime to $n$ (the maximal gap between integers coprime to $n$). Jacobsthal's function is $$h(k)=\max_{\omega(n)\le k} g(n),$$ the maximum of $g(n)$ over all $n$ with at most $k$ distinct prime factors $\omega(n)$ (the maximum is attained at products of the first $k$ primes). Determine the order of magnitude of $h(k)$. In particular, is Jacobsthal's conjecture $h(k)\ll k^2$ true?
Acceptance. FULLY RESOLVES: a proof (machine-checkable preferred, else a complete written proof) determining the order of magnitude of $h(k)$ — in particular a proof of Jacobsthal's conjecture $h(k)\ll k^2$ (matched against the easy lower bound $h(k)\gg k$), or a rigorous disproof exhibiting faster growth. ADVANCES (proof or reproducible certificate required; must strictly beat the bound stated in the background): (a) improve the upper bound below $(k\log k)^2$ of Iwaniec; (b) improve the lower bound beyond the Ford–Green–Konyagin–Maynard–Tao bound stated above; or (c) compute new exact values of $h(k)$ beyond the currently tabulated range, via a reproducible search program plus a certificate that the reported run length is maximal (extending OEIS A048669 / A048670). Deliver the proof/formalization, or the search code plus the new certified values.
Background
Posed by Erdős [Er65b], building on Jacobsthal's function; listed as open on erdosproblems.com/970 (fetched 2026-07-21, status 'open'). The bound $h(k)\ll k^2$ is a conjecture of Jacobsthal. The best known upper bound is $h(k)\ll (k\log k)^2$, due to Iwaniec [Iw78]. The best known lower bound 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], as a byproduct of their work on large gaps between primes. This is a more general form of the function studied in Erdős #687 (erdosproblems.com/687). Related values are catalogued in OEIS A048669 (Jacobsthal's function $g(n)$). Attacker's tool: exact computation of $g(P_k)$ for primorials $P_k=p_1\cdots p_k$ — a search for the longest run of consecutive integers each sharing a factor with $P_k$ — to extend the table of $h(k)$ and sharpen the leading constant, together with sieve/covering constructions pushing the lower bound.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #970 (T. F. Bloom) | website |
| REF-02 | OEIS A048669 — Jacobsthal's function g(n) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.