Jacobsthal's function h(k) — finiteness and near-matching two-sided bounds

Statement

For a positive integer $n$, let $g(n)$ be the smallest $m$ such that every run of $m$ consecutive integers contains one coprime to $n$ (equivalently, $1+$ the largest gap between consecutive integers coprime to $n$). Define $$H(k) = \max_{\omega(n)=k} g(n), \qquad h(k) = g(p_1p_2\cdots p_k)$$ where $\omega(n)$ counts $n$'s distinct prime factors and $p_1p_2\cdots p_k$ is the $k$-th primorial. $h(k)$ is "Jacobsthal's function" proper; $H(k)$ is the more general "max gap over all $k$-prime-factor numbers" that this page's target description names.

Two questions surround this object: 1. (Solved on this page.) Is $h(k)$ (and $H(k)$) finite for every $k$, and does it obey polynomial-in-$k$ two-sided bounds? — Yes, resolved by Iwaniec (1978, upper) and Ford–Green–Konyagin–Maynard–Tao (2018, lower). 2. (Still open — this is what erdosproblems.com actually lists as #970 and its prime-restricted sibling #687.) What is the *exact* order of magnitude / sharp constant? Erdős asked whether one can even prove the qualitatively stronger $Y(x) = o(x^2)$ or $Y(x) \ll x^{1+o(1)}$ (the #687 phrasing, $x$ in place of $k$) — a full 44 years after Iwaniec's bound, still open. erdosproblems.com marks both #687 and #970 OPEN as of this writing (2026-07-02).

This page documents result (1) — the finiteness/bounds theorem that both open problems use as their starting point and best current tool — plus a genuinely closed related question, Jacobsthal's own 1962 conjecture about *which* $n$ extremizes $g$.

Facts

- $h(k) = g(P_k)$ for $P_k$ the $k$-th primorial. Small values (OEIS A048670, cross-checked against the Hajdu–Saradha counterexample below): $h(1),\dots,h(10) = 2,4,6,10,14,22,26,34,40,46$; $h(24)=234$. - Jacobsthal's 1962 conjecture — that the primorial always extremizes, i.e. $H(k)=h(k)$ for all $k$ — is a distinct, fully closed sub-question: TRUE for $k\le 23$, FALSE at $k=24$. Hajdu & Saradha, "Disproof of a conjecture of Jacobsthal," Math. Comp. 81 (2012) 2461–2471, exhibited a squarefree $n$ with exactly 24 prime factors (none of them the primorial) with $g(n)=H(24)=236 > 234 = h(24)$, via exhaustive computation building on Hagedorn's exact values of $h(k)$ for $k<50$ (T. Hagedorn, Math. Comp. 78 (2009) 1073–1087, a 3-month, 30-machine cluster computation). This settles (negatively) the question of *which* number of a given prime-factor-count has the largest coprimality gap — the primorial is not always optimal. - Upper bound (Iwaniec, 1978): $h(k) = O\big((k\log k)^2\big)$ — equivalently, restated on the "primes $\le x$" version used in erdos/687, $Y(x) \ll x^2$. H. Iwaniec, "On the problem of Jacobsthal," Demonstratio Math. 11 (1978) 225–231. This is still, as of 2026, the best known upper bound on either problem (no improvement found in this search) — it is the load-bearing "solved" fact this page is centered on. - Lower bound (Ford–Green–Konyagin–Maynard–Tao, 2018): for the primes-up-to-$x$ version, $j(x\#) \gg x\cdot \dfrac{\log x\,\log\log\log x}{\log\log x}$ (equivalently $h(k) \gg k(\log k)^2\log\log\log k/\log\log k$ after $x\sim p_k\sim k\log k$), improving Rankin's 1938 construction. K. Ford, B. Green, S. Konyagin, J. Maynard, T. Tao, "Long gaps between primes," J. Amer. Math. Soc. 31 (2018) 65–105 = arXiv:1412.5029. The same construction, via the classical Erdős–Rankin translation, independently resolved the separate large-prime-gaps problem Erdős #4 — unbounded large gaps between primes (Rankin's constant removed) (status PROVED per erdos/687.md). - Conjectured true order (still open): Maier & Pomerance conjecture $Y(x) \ll x(\log x)^{2+o(1)}$ — strictly between the proven $x^2$ upper bound and the $x^{1+o(1)}$ Erdős asked to reach. The gap between Iwaniec's proven upper bound and the FGKMT lower bound (roughly one $\log\log$ factor) is exactly the content of the still-open #687/#970. - Falsifiability of the *closed* sub-result documented here: none needed — both Iwaniec's bound and the Hajdu–Saradha disproof are complete, published proofs, not open conjectures.

Answer

$h(k)$ and $H(k)$ are finite for every $k$ and satisfy $c\cdot k(\log k)^2\dfrac{\log\log\log k}{\log\log k} \ll h(k) \ll (k\log k)^2$ — a two-sided polynomial bound, proven by combining two structurally different techniques:

1. Iwaniec's sieve-theoretic upper bound (1978) — the technique that first "cracked" the finiteness/growth-rate question. Jacobsthal's function bounds the length of the longest run of consecutive integers each killed (i.e. made non-coprime) by one of $k$ given primes. Iwaniec attacks this with a Buchstab-type combinatorial sieve: instead of trying to locate a survivor directly, he bounds from above the number of integers in a window of length $L$ that are divisible by *some* prime $\le x$ using sieve upper-bound machinery (in the spirit of the linear/Selberg sieve and Brun–Titchmarsh-type density control), and shows that once $L \gg (k\log k)^2$ the sieve's own error-term bookkeeping *forces* a non-covered residue to exist — i.e. the sieve proves a *lower bound on the count of survivors*, which is positive once the window is long enough. This "upper-bound the sifted-out count, deduce a positive survivor count" pattern is the general transferable move: it converts a covering/avoidance existence question into a counting inequality that ordinary sieve theory can supply. 2. **The Rödl-nibble / hypergraph-covering lower bound (Ford–Green–Konyagin–Maynard–Tao, 2018) — the technique that pushed the *matching* direction.** To show $h(k)$ can be *large* (not just finite), one must *construct* a long run of consecutive integers each hit by some prime — the reverse engineering problem. FGKMT's innovation is a generalization of the Pippenger–Spencer hypergraph covering theorem, proved via the semi-random Rödl-nibble method: greedily and randomly select near-disjoint "coverage" assignments (which prime kills which residue) in successive small rounds ("nibbles"), each round covering a near-optimal fraction of what remains uncovered, until almost the whole target window is provably coverable. This explicit-construction technique is what is missing on the upper-bound side of #687/#970 — nobody has found the analogous *impossibility* argument to match it, which is precisely why those problems remain open. 3. Why this pairing is the reusable idea for the open problems downstream: the finiteness/growth-rate question was closed by *pairing an upper-bound sieve argument with a lower-bound explicit-construction argument*, and the residual gap between them (Iwaniec's $x^2$ vs. FGKMT's $x\log x\log\log\log x/\log\log x$) is exactly of the shape "sieve upper bounds are known to be lossy versus the true extremal construction" — the same shape as several other Erdős covering/gap problems (see erdos/687.md's discussion of the "distortion method" as a candidate sharper-impossibility tool). Any future attack on #687 or #970 needs either (a) a sharper *upper*-bound sieve inequality beating Iwaniec's 1978 argument, or (b) a matching stronger explicit construction beating FGKMT — both are direct descendants of the two techniques documented here.

Related

- Erdős #687 — estimate the Jacobsthal covering function Y(x) — the prime-restricted special case ("Jacobsthal covering function $Y(x)$"), open, \$1000 prize; same Iwaniec upper bound / FGKMT lower bound pair, narrower framing (only primes $\le x$, not general $k$-prime-factor $n$). - Erdős #4 — unbounded large gaps between primes (Rankin's constant removed) — unbounded large prime gaps; PROVED, resolved by literally the same FGKMT Rödl-nibble construction used for the lower bound documented here, via the Erdős–Rankin translation. - Erdős #2 — minimum modulus of a covering system cannot be arbitrarily large — Erdős's minimum-modulus covering-systems problem; DISPROVED by Hough; the closest fully-solved precedent in the same "congruence covering system" family for what a full resolution of the #687/#970 upper-bound side would look like. - Sieve theory: Eratosthenes–Legendre, Brun, Selberg, Turán, and the large sieve — Iwaniec's Buchstab/linear-sieve upper-bound technique. - Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings — the semi-random greedy covering-construction technique underlying the FGKMT lower bound. - Pippenger–Spencer hypergraph covering theorem (and the FGKMT generalization) — the Pippenger–Spencer theorem generalized by FGKMT. - Erdős–Rankin construction (covering-congruences translation for large prime gaps) — the classical bridge translating a Jacobsthal-type covering/gap bound into a prime-gap bound (links this page to erdos/4). - concept/jacobsthal-function — the object itself, $g(n)$/$h(k)$/$H(k)$, forward-reference for a dedicated concept page.