Jacobsthal’s function: how long can primes cover an interval?

← All digests

Family 021 · Number theory
Importance 3/5 · Provisional editorial rating
Sources consulted 2026-10-10

1. The question

Choose a positive integer $n$ and scan consecutive integers until one is coprime to it. How long might the wait be? For $n=6$, the integers coprime to $n$ are those avoiding divisibility by two and three. Larger moduli can create longer stretches in which every integer shares a prime factor with $n$.

The size of $n$ is not the most natural parameter. Replacing $n$ by the product of its distinct prime divisors leaves coprimality unchanged. The real resource is the number $k$ of available primes: how long an interval can they cover by their divisibility classes?

Family 021 claims a uniform bound of order

$$\frac{k^2}{(\log\log(3k))^2}.$$

It answers Jacobsthal’s quadratic-bound question and includes a further slowly growing saving. The primes may be arbitrarily large, and the interval may start anywhere.

2. Background and essential definitions

Jacobsthal’s function $j(n)$ is the least positive integer $m$ such that every interval of $m$ consecutive integers contains an integer coprime to $n$. Let $\omega(n)$ count distinct prime divisors, with $\omega(1)=0$, and define

$$h(k)=\sup_{\substack{n\ge1\\\omega(n)\le k}}j(n).$$

Thus $h(k)-1$ is the longest possible interval covered by divisibility by at most $k$ primes. Prime powers do not add covering power: divisibility by $p$ already detects every failure of coprimality caused by $p^a$.

For example, $j(6)=4$. The interval $2,3,4$ contains no integer coprime to six, while every four consecutive integers include an integer congruent to one or five modulo six. This small example illustrates that the question concerns the worst translated interval, not just the interval starting at one.

A useful equivalent formulation assigns one forbidden residue class $a_p\pmod p$ to each chosen prime. The Chinese remainder theorem supplies an integer $b$ satisfying all these congruences. Then

$$m\not\equiv a_p\pmod p\text{ for every chosen }p \quad\Longleftrightarrow\quad \gcd\!\left(m-b,\prod p\right)=1.$$

Arbitrary forbidden classes therefore encode arbitrary interval translations. A statement uniform over all classes is exactly the kind of worst-case estimate needed here.

A sieve counts integers left after excluding specified congruence classes. The simple heuristic says that removing one class modulo each prime up to $z$ should leave a proportion resembling

$$\prod_{p\le z}\left(1-\frac1p\right).$$

That heuristic describes averages, but an adversarial choice of residue classes can make an individual short interval much harder. Controlling those choices is the main issue.

Throughout, logarithms are natural. The notation $A\ll B$ means $A\le CB$ for a constant $C$. In the headline theorem the constant is absolute, independent of the primes, modulus and interval.

3. Development history and previous partial results

Jacobsthal studied these gaps beginning in 1960. Erdős recorded his question whether $h(k)\ll k^2$, while noting that Brun’s method already gave some polynomial upper bound.

The distinction between special and arbitrary prime sets matters historically. Iwaniec first obtained an estimate of order $k^2\log^2 k$ for the primorial setting, where the modulus is the product of the first $k$ primes. Vaughan proved the uniform bound

$$j(n)\ll\omega(n)^2\bigl(\log(2\omega(n))\bigr)^4$$

in his 1977 paper. Iwaniec’s 1978 shifted-sieve argument then established $h(k)\ll k^2\log^2 k$ for arbitrary prime sets.

The exponent two reflects a barrier in the ordinary one-dimensional sieve. Its lower-bound function vanishes at the critical sieve parameter two, so the leading term alone ceases to prove that a survivor exists. The new paper works at this limiting scale and retains a smaller contribution that the leading approximation loses.

Another conjecture asked whether the first $k$ primes always create the longest possible gap. They do not. Hajdu and Saradha’s 2012 paper found

$$j(P_{24})=234<236=h(24),$$

where $P_k$ is the product of the first $k$ primes. A theorem about primorials alone therefore cannot settle the uniform quadratic problem.

Lower bounds come from long covered-interval constructions, closely related to large prime gaps. The manuscript cites Ford–Green–Konyagin–Maynard–Tao for a lower bound of order

$$h(k)\gg k(\log k)^2\frac{\log\log\log k}{\log\log k}$$

for sufficiently large $k$, already attained as a lower bound for primorial gaps. This remains far below the new claimed upper bound. Vaughan also suggested the much stronger possible estimate $h(k)\ll_\varepsilon k^{1+\varepsilon}$ for every fixed $\varepsilon>0$.

4. What the new manuscripts claim

The family has one manuscript. Its Theorem 1.1 states that an absolute constant $C>0$ exists with

$$\boxed{h(k)\le C\frac{k^2}{(\log\log(3k))^2}\qquad(k\ge1).}$$

The factor $3k$ keeps the iterated logarithm positive throughout the stated range. The result is uniform over every set of at most $k$ distinct prime divisors and every translated interval. No upper bound on the primes is assumed. The constant is not made explicit.

The stronger intermediate covering estimate explains how the theorem is obtained. For large $z$, set

$$L=\log z,\qquad Y=\left\lfloor\frac{z^2}{L^2}\right\rfloor,\qquad w=\frac{L}{(\log L)^2},\qquad B=\frac{L}{\log w},$$

and

$$V_0=\prod_{p\le w}\left(1-\frac1p\right).$$

Theorem 1.2 claims that, for every choice of one forbidden class at each prime $p\le z$,

$$\#\{1\le m\le Y:m\not\equiv a_p\pmod p\text{ for every }p\le z\} \ge c\frac{YV_0}{B^2}$$

for an absolute $c>0$. Mertens’ theorem makes the scale comparable to $Y\log w/L^2$. This is a lower bound for many survivors, not just one.

To deduce the statement in terms of $k$, the paper chooses

$$z\asymp\frac{k\log k}{\log\log k}$$

with a sufficiently large constant. A separate upper sieve controls how many of the surviving integers the remaining divisor primes above $z$ can remove. The survivor lower bound dominates that loss, while $Y$ has the desired order $k^2/(\log\log k)^2$.

5. Why the advance matters

Provisional importance: 3/5. Taken as stated, the theorem settles a longstanding uniform bound in sieve theory and improves the previous general estimate by more than its two logarithmic factors.

The result controls worst-case residue coverings. It does not assume that the classes are random or typical, nor that small primes are extremal. This makes it useful as a structural estimate whenever one needs an integer avoiding a prescribed finite set of prime obstructions in a short interval.

The broader methodological interest is its treatment of the critical sieve boundary. A positive reference calculation is not enough when the actual residue classes can be highly structured; the paper supplies a comparison that accounts for those configurations. The rating reflects a substantial advance within analytic number theory, with the true growth order still unresolved.

6. The main idea

Organize exclusions into a tree

The proof expands the sieve by recording the least prime responsible for excluding an integer, then repeats the process. This creates paths indexed by strictly decreasing primes. Even and odd depths give lower and upper bounds, much like carefully organized inclusion–exclusion.

A stopping or admission rule keeps only progressions long enough for available upper-sieve estimates. Replacing each small-prime count by its expected progression length times $V_0$ produces a reference tree.

At the critical parameter two, its leading lower-sieve term disappears. The paper instead computes a boundary contribution on the smaller scale $B^{-2}$. Reciprocal-prime weights are approximated by harmonic integrals. Derivatives of the usual upper and lower sieve functions normalize the resulting transitions into a probability process, whose regeneration and renewal behavior evaluate the contribution.

The claimed positive margin survives several losses, including the root’s displacement slightly below the critical parameter. That gives the reference lower bound, but a further argument is needed to transfer it to actual residue classes.

Large discrepancies reveal rational alignment

On long progressions, the fundamental lemma of sieve theory controls the difference between actual and reference counts. A short progression can behave badly. The manuscript shows that a large discrepancy must already be visible on one of a few recent edges of the prime path.

It groups these paths into boxes where selected prime factors can vary independently. An inverse estimate then says that many discrepant edges force the forbidden classes to align with one of finitely many rational numbers $A/D$:

$$D a_p\equiv A\pmod p.$$

This is an example of a recurring principle in inverse sieve problems: repeated modular concentration cannot remain arbitrary; it must reveal algebraic structure. Here the rational list is fixed for the whole box, rather than chosen separately for each endpoint.

Variance estimates remove most of these aligned possibilities unless their effective denominators and intercepts are small. The remaining structured cases cannot simply be discarded as errors because their total contribution could matter at the delicate boundary scale.

Stop structured branches where exact counts help

For the hard endpoints, many earlier primes align with the same rational. The proof stops those branches at suitable even depths. The stopping rule preserves enough freedom to average one aligned prime over a large portion of its prime interval.

At those stops, exact arithmetic supplies more survivors than the reference subtree requires. A marked renewal argument shows that almost all the problematic path weight reaches a useful stop. Combining the reference margin, inverse estimate, variance control and stopped counts gives Theorem 1.2.

Finally, the upper sieve removes the effect of the at most $k$ divisor primes above the chosen cutoff. This last step is why the quantitative number of survivors is essential: positivity before those extra exclusions would not suffice.

7. Scope, limitations, and open questions

The theorem gives an upper bound with an unspecified absolute constant. It does not provide exact values of $h(k)$, a numerical best constant or an asymptotic formula.

It does not revive the false primorial-extremality conjecture. Arbitrary prime sets are included precisely because the first $k$ primes need not maximize the gap.

The known lower constructions and the claimed upper bound remain separated by a substantial power-scale gap. Near-linear bounds of the type Vaughan suggested are not established. Connections with prime gaps should also be interpreted carefully: a uniform upper bound for intervals covered by a chosen set of primes is not directly a sharp upper bound for all gaps between consecutive primes.

The intermediate theorem excludes one class per prime. More general covering systems with several classes at each prime have different sieve dimensions and require additional analysis.

8. Sources and further reading

Theorem 1.1 gives the bound for $h(k)$; Theorem 1.2 is the quantitative survivor estimate. The introduction distinguishes the arbitrary-prime problem, primorial computations and lower-bound constructions. Sections 3–6 develop the reference tree, while Sections 7–10 compare it with the actual classes. Section 11 removes the remaining large divisor primes.

Vaughan, Iwaniec and Hajdu–Saradha are linked in section 3. The manuscript’s bibliography supplies the large-prime-gap construction and inverse-sieve antecedents. Optional background on Jacobsthal’s function and sieve theory gives further examples and terminology.

Source manuscripts

• M1. OpenAI, A quadratic bound for Jacobsthal’s function (2026).

Sources consulted on 10 October 2026 at repository revision fd4aeeb. Download the manuscript citations.