Jacobsthal Function: How OpenAI Proved the Quadratic Bound Beyond the Linear Sieve Barrier

Take the integers 2, 3, and 4. Each shares a prime factor with 6. You need a fourth slot to guarantee a coprime integer wherever the interval starts. How long can that run get with kk primes? OpenAI’s Jacobsthal function proof shows that for every integer k≥1k\ge1, the worst-case interval length is at most Ck2/(log⁡log⁡(3k))2Ck^2/(\log\log(3k))^2 for one absolute constant CC. The guarantee holds for every starting point and every positive modulus with at most kk distinct prime factors. The result answers Jacobsthal’s quadratic-bound question and gains a squared iterated logarithm. The proof reaches the point where the leading linear-sieve lower bound vanishes, then shows that a smaller positive contribution survives in the actual integer count.

1. Jacobsthal Function and OpenAI’s Quadratic-Bound Theorem

A modulus-6 example of the Jacobsthal function shows three blocked integers and a coprime in every four.
A modulus-6 example of the Jacobsthal function shows three blocked integers and a coprime in every four.

For a positive integer nn, the Jacobsthal function j(n)j(n) is the least length for which every interval of that length contains an integer coprime to nn. Write ω(n)\omega(n) for its number of distinct prime divisors. The worst-case function h(k)h(k) is the maximum of j(n)j(n) over positive integers with ω(n)≤k\omega(n)\le k. In the example above, the coprime residues modulo 6 are 1 and 5. Their successive spacings are 4 and 2, repeating, so every four consecutive integers contain one and j(6)=4j(6)=4.

Theorem 1.1 in OpenAI’s September 25, 2026 preprint gives the bound below. All logarithms are natural.

𝒉(𝒌)≤𝑪𝒌2(log⁡log⁡(3𝒌))2(𝒌≥1)\boldsymbol{h(k)\le C\frac{k^2}{(\log\log(3k))^2}\quad(k\ge1)}
Theorem 1.1 measures the worst case over all eligible moduli and interval starts.
Key FactWhat It Means
InputAt most kk distinct prime divisors of a positive modulus
Guaranteed OutcomeA coprime integer in any interval of the length specified by h(k)h(k)
Previous Uniform Scalek2(log⁡k)2k^2(\log k)^2, up to an absolute constant
New Uniform Scalek2/(log⁡log⁡(3k))2k^2/(\log\log(3k))^2, up to an absolute constant

2. The Original Jacobsthal Question and Why Earlier Bounds Fell Short

A prime can cover one residue class at a time. Prime powers give it no additional coverage because coprimality depends only on which primes divide the modulus. The longest fully covered interval has length h(k)−1h(k)-1. Allowing exactly kk primes gives the same maximum since adding prime factors can only extend the set of covered integers. Erdős recorded Jacobsthal’s question about a uniform quadratic upper bound, catalogued as Erdős Problem 970.

Erdős noted that Brun’s method gave a polynomial bound h(k)≪kC0h(k)\ll k^{C_0} for an absolute exponent C0C_0. Vaughan obtained the uniform bound j(n)≪ω(n)2(log⁡(2ω(n)))4j(n)\ll\omega(n)^2(\log(2\omega(n)))^4 for n>1n>1. Iwaniec had obtained the scale k2(log⁡k)2k^2(\log k)^2 for the first kk primes. His later shifted-sieve argument reached that scale for arbitrary prime sets, cutting two logarithmic factors from Vaughan’s bound. Here and below, ≪\ll means bounded above up to a constant.

3. Proof Roadmap From Forbidden Residue Classes to a Quadratic Bound

  1. Turn the gap into a covering problem. Translate the interval into coordinates starting at 1. Each divisor prime forbids one congruence class. First handle every prime up to a chosen cutoff, and aim to leave a reserve of integers.
  2. Build a reference sieve. Sort the excluded integers by their first forbidden hit. Repeat inside progressions. Replace each small-prime count by its density prediction.
  3. Recover the boundary contribution. Follow the reference tree down to small exponents. A renewal calculation aggregates the boundary terms with their signs and proves that the normalized root count is positive.
  4. Compare with actual counts. Locate large errors on individual edges. Many such errors imply rational alignment. Variance estimates and exact counts at selected even nodes keep these errors from using up the reference margin.
  5. Account for the remaining divisor primes. Each large prime removes only a bounded share of the reserve. Choose the cutoff so the total loss leaves at least one coprime integer.

OpenAI’s release attributes the collection’s results to an internal frontier model. These stages reconstruct the manuscript’s argument. The announcement gives collection-level information on how the results were obtained.

4. The Linear Sieve Barrier at the Critical Parameter

	The classical lower-sieve function is zero through s = 2, the critical threshold in the Jacobsthal function proof.
The classical lower-sieve function is zero through s = 2, the critical threshold in the Jacobsthal function proof.

The classical linear sieve compares its modulus level DD with its prime cutoff zz through s=log⁡D/log⁡zs=\log D/\log z. Each intersection counts a residue class modulo a prime product. The level must keep the accumulated endpoint errors under control. At interval length Y≍z2/(log⁡z)2Y\asymp z^2/(\log z)^2, even choosing DD on the scale of YY gives ss tending to 2 from below. The paper’s tree has its own root ratio, which also approaches 2 from below.

The lower and upper functions ff and FF govern the leading sieve bounds. In the paper’s normalization, f(s)=0f(s)=0 for 0≤s≤20\le s\le2, and sF(s)=2eγsF(s)=2e^\gamma for 1≤s≤31\le s\le3, where γ\gamma is Euler’s constant. Just above 2, sf(s)=2eγlog⁡(s−1)sf(s)=2e^\gamma\log(s-1) through s=4s=4. The leading lower bound disappears at 2, leaving finite-cutoff terms to examine.

5. The Uniform Covering Estimate and Its Survivor Count

The Chinese remainder theorem gives a common shift bb satisfying b≡ap(modp)b\equiv a_p\pmod p for each prescribed class apa_p. Avoiding the classes is therefore equivalent to m−bm-b being coprime to the product of the primes. For instance, forbidding the even class and the class 1 modulo 3 makes the forbidden positions m≡0,1,2,4(mod6)m\equiv0,1,2,4\pmod 6. The survivors are 3 and 5 modulo 6, exactly the classes coprime to 6 after subtracting 4.

For a sufficiently large real cutoff zz, put L=log⁡zL=\log z and Y=⌊z2/L2⌋Y=\lfloor z^2/L^2\rfloor. Sieve the small primes up to w=L/(log⁡L)2w=L/(\log L)^2 inside progressions. The primes in (w,z](w,z] build the tree. Define B=L/log⁡wB=L/\log w and V0=∏p≤w(1−1/p)V_0=\prod_{p\le w}(1-1/p), the small-prime density. Let S1(B)S_1(B) be the number of survivors in [1,Y][1,Y]. Theorem 1.2 guarantees an absolute c>0c>0 such that every assignment of classes gives

𝑺1(𝑩)≥𝒄𝒀𝑽0𝑩2.\boldsymbol{S_1(B)\ge c\frac{YV_0}{B^2}.}

Mertens’ theorem gives YV0/B2∼e−γYlog⁡w/L2YV_0/B^2\sim e^{-\gamma}Y\log w/L^2, where ∼\sim means the ratio tends to 1. A guarantee of one survivor could be erased by a single additional prime. This quantitative reserve makes the final step possible.

6. The Decreasing-Prime Tree and Its Admission Rules

At a node with prime product dd, let NdN_d count integers that hit every prescribed class for primes dividing dd and avoid the classes at primes up to ww. Let Sd(b)S_d(b) also require avoiding the available primes above ww up to the node’s cutoff, strict after the root. For a prime pp, write x(p)=log⁡p/log⁡wx(p)=\log p/\log w. Assign each discarded integer to its smallest available forbidden hit. Its child must avoid every smaller available hit, giving equation (3.2).

𝑺𝒅(𝒃)=𝑵𝒅−∑𝒑 available𝑺𝒅𝒑(𝒙(𝒑)).\boldsymbol{S_d(b)=N_d-\sum_{p\ \mathrm{available}} S_{dp}(x(p)).}

This makes the cutoffs decrease. Subtraction reverses the bound at each depth, so even nodes are lower nodes and odd nodes are upper nodes. An even node admits every available child. An odd node can omit a nonnegative child from its subtraction and still give an upper bound. It admits a child of exponent xx only if rd−x≥max⁡(2x,x+2)r_d-x\ge\max(2x,x+2), where rd=logw⁡(Y/d)−a∗+2r_d=\log_w(Y/d)-a_*+2 and a∗=1/100a_*=1/100. This keeps included progressions long enough for a uniform upper sieve. Stopping instead replaces an already admitted even subtree by its exact count.

The reference count μd=YV0/d\mu_d=YV_0/d shrinks by 1/p1/p on an edge, so the reference expansion assigns each path harmonic weight 1/d1/d.

7. Recovering the Boundary Contribution With Delay Functions

Delay equations link the two classical functions. The lower equation (sf(s))′=F(s−1)(sf(s))’=F(s-1) holds for s>2s>2, and the upper equation (sF(s))′=f(s−1)(sF(s))’=f(s-1) holds for s>3s>3. The shift by one corresponds to spending one cutoff unit when forming a child at the current cutoff. The paper continues the logarithmic formula for ff just below 2 at the starting lower state. With r0/B=2−a∗/B+o(B−1)r_0/B=2-a_*/B+o(B^{-1}), the continued root benchmark contributes −a∗eγ/B2+o(B−2)-a_*e^\gamma/B^2+o(B^{-2}) after multiplication by the reference density above ww.

The low end of the tree behaves differently. Its exponents start at 1, and the extra admission constraint matters below exponent 2. At cutoff 2, the proof compares the finite reference polynomial with its classical benchmark for each parity. These boundary discrepancies have signs and decay rapidly for large remaining gap. For example, at odd gap 2 and cutoff 2, no lower child passes admission. The normalized reference value there is 1, while the limiting benchmark is F(1)/2=eγF(1)/2=e^\gamma. The negative discrepancy enters positively at odd depth. Its contribution still has to be combined with those from other states. The Dickman function gives the decay of the difference between the upper and lower functions, while the Buchstab function gives their sum after normalization. Together they identify the benchmark and bound its deviations.

8. Harmonic Paths, Regeneration, and Renewal Theory

Replace reciprocal-prime sums by integrals with measure dx/xdx/x. Positive derivative weights s2f′(s)s^2f'(s) and −s2F′(s)-s^2F'(s) turn the continuous tree with the ratio constraint into an alternating probability process on s=r/bs=r/b, where rr is the remaining gap. A child with exponent xx has ratio t=r/x−1t=r/x-1. The harmonic step dx/xdx/x becomes dt/(t+1)dt/(t+1) after reversing the limits. The change of measure telescopes. Converting a path probability back to harmonic mass introduces a squared endpoint-to-starting gap ratio and a ratio of derivative weights. Compact endpoint ranges therefore contribute at scale B−2B^{-2}.

When an odd state has ratio at most 3, its next draw has the same distribution throughout that range. These returns split the process into independent, identically distributed cycles. The gap decreases multiplicatively, so its logarithmic decrements add. Renewal theory gives the limiting occupation of fixed log-gap windows, using different invariant densities for even and odd states. The parity matters because even and odd boundary terms enter with opposite signs.

The paper couples this process to prime paths using estimates for reciprocal-prime sums in short bins. Tail and quadrature bounds justify transferring the signed integral. Proposition 6.3 proves that B2Pe(r0,B)/eγB^2P_e(r_0,B)/e^\gamma converges to a value greater than 0.020.02, where PeP_e is the even reference value divided by its node density prediction. This includes the negative root contribution and the admission losses.

9. Inverse Estimates for Discrepancies in Actual Residue Classes

Long progression counts are close to μd\mu_d by the fundamental lemma of the sieve. At a short endpoint, a large discrepancy must be visible within the last few edges, where the child count differs sufficiently from the parent count divided by the new prime. The paper groups regular paths into boxes of short prime bins. An isolated earlier prime and the prime on the witnessing edge can vary independently inside the full box.

The inverse estimate runs from unusual counts back to arithmetic structure. The additive large sieve bounds how often such biased residue tests can occur across edge primes. If too many witnessing edges lack a structured explanation, the incidence constraints give many integer points with too few permissible slopes. Small-height polynomial interpolation produces a curve through those points. Convex-arc lattice-point estimates bound the contribution of nonlinear components, and a larger-sieve pair count helps constrain the rational alignments. Outside a small exceptional fraction, a witnessed error comes with a rational A/DA/D from a list fixed for the box. An aligned prime satisfies Dap≡A(modp)Da_p\equiv A\pmod p.

First and second moments for small-prime survival, with uniform estimates as the isolated prime varies, make large errors rare when the effective modulus or scaled intercept is large. The persistent exceptions have small effective size, and their sufficiently large path primes align to the same rational.

10. Stopping Exceptional Branches and Completing the Proof

The Jacobsthal function proof leaves a coprime survivor after controlling counting errors and sieving larger primes.
The Jacobsthal function proof leaves a coprime survivor after controlling counting errors and sieving larger primes.

The proof looks for bins where almost all primes align with one eligible rational. It tags an aligned prefix and stops at the first qualifying even node in a prescribed window, with enough admission slack to vary the tag prime. A marked-renewal argument shows that almost all the remaining exceptional mass passes through such stops. Averaging exact survivor counts over the aligned choices of the tag prime covers the reference subtree values in aggregate.

For expanded nodes 𝒯\mathcal T and stops 𝒮\mathcal S, let R0=YV0Pe(r0,B)R_0=YV_0P_e(r_0,B) be the root reference value and LstopL_{\mathrm{stop}} the stopped lower bound. Equation (3.7) becomes

𝑳stop−𝑹0=∑𝒅∈𝒯(−1)𝝎(𝒅)(𝑵𝒅−𝝁𝒅)+∑𝒅∈𝒮(𝑺𝒅(𝒃𝒅)−𝝁𝒅𝑷𝒆(𝒓𝒅,𝒃𝒅)).\boldsymbol{\begin{gathered}L_{\mathrm{stop}}-R_0\\=\sum_{d\in\mathcal T}(-1)^{\omega(d)}(N_d-\mu_d)\\+\sum_{d\in\mathcal S}\bigl(S_d(b_d)-\mu_dP_e(r_d,b_d)\bigr).\end{gathered}}

Here bdb_d is the cutoff at node dd. The first sum is controlled in absolute value by separating long progressions, small relative errors, and the few bad endpoints left outside stopped subtrees. Together these cost at most three eighths of the guaranteed reference margin. The second sum is nonnegative by the stop comparison. This proves Theorem 1.2.

For Theorem 1.1, choose z=A0klog⁡k/log⁡log⁡kz=A_0k\log k/\log\log k, with A0A_0 a sufficiently large fixed constant. Prescribe the divisor classes in the translated interval and arbitrary classes at the other primes up to zz. Put X=Y/zX=Y/z. Each remaining divisor prime q>zq>z hits at most 1+X1+X positions on one progression. A smaller upper sieve bounds the survivors it can remove by O(1+X/log⁡X)O(1+X/\log X). Summed over at most kk primes, the loss has coefficient proportional to 1/A01/A_0 relative to the reserve. A coprime integer remains in the interval, of length Y≍k2/(log⁡log⁡k)2Y\asymp k^2/(\log\log k)^2. Elementary inclusion-exclusion handles the finitely many smaller kk: the density of coprime residues is at least 1/(k+1)1/(k+1) and the total endpoint error is at most 2k2^k.

11. What the Quadratic Bound Resolves and What Remains Open

Let PkP_k be the primorial, the product of the first kk primes. Hajdu and Saradha found j(P24)=234<h(24)=236j(P_{24})=234<h(24)=236, disproving Jacobsthal’s separate primorial extremality conjecture. Primorials still provide lower bounds. The same covering constructions produce large gaps between consecutive primes. The long covered intervals of Ford, Green, Konyagin, Maynard, and Tao give h(k)≥j(Pk)≫k(log⁡k)2log⁡log⁡log⁡k/log⁡log⁡kh(k)\ge j(P_k)\gg k(\log k)^2\log\log\log k/\log\log k as kk tends to infinity. The symbol ≫\gg denotes a lower bound up to a positive constant. The gap between the upper and lower scales leaves the true growth rate open.

The preprint leaves CC unspecified, so the asymptotic estimate supplies no explicit numerical ceiling for an individual kk. The pinned Lean conclusion states the quadratic theorem. The repository’s formalization scope notes separately report the strengthened iterated-logarithm bound, with arbitrary signed interval starts.

The Jacobsthal function now has a uniform upper bound below the quadratic scale. The proof’s decisive step is to retain enough of the finite boundary term to pay for actual counting errors and the remaining divisor primes. Follow Binary Verse AI for more research explainers that trace the argument from the original question to the theorem.

What did OpenAI prove about Jacobsthal’s function?

OpenAI proved h(k)≪k2/(log⁡log⁡(3k))2h(k)\ll k^2/(\log\log(3k))^2 for every integer k≥1k\ge1, with one absolute implied constant. This gives a uniform bound for every positive modulus with at most kk distinct prime factors and for every interval starting point.

Why did the classical linear sieve fail to establish the quadratic bound?

At the critical sieve parameter s=2s=2, the classical lower-sieve function satisfies f(2)=0f(2)=0. The leading estimate gives no positive lower bound there. The proof recovers a smaller positive boundary contribution and controls the discrepancy between the reference calculation and the actual counts.

What is the key mathematical innovation in OpenAI’s proof?

The proof uses a decreasing-prime tree and renewal theory to establish a positive reference margin. Inverse estimates and variance bounds identify the difficult residue-class configurations, and exact counts at selected even nodes preserve the margin in the actual sieve.

Does the proof show that primorials always maximize Jacobsthal’s function?

That separate conjecture is false. The paper cites j(P24)=234j(P_{24})=234 and h(24)=236h(24)=236, where P24P_{24} is the product of the first 24 primes. The new upper bound applies to arbitrary prime sets.

Does the quadratic-bound proof determine the exact growth of Jacobsthal’s function?

The exact growth of the worst-case function remains open. The theorem improves the uniform upper bound, and a substantial gap remains between the established upper and lower bounds.

Can the new theorem calculate an explicit maximum gap for a given number of prime factors?

The theorem establishes the existence of one absolute constant CC and leaves its value unspecified. It therefore gives an asymptotic upper bound without calculating the exact worst-case gap h(k)−1h(k)-1 for a given kk.

Leave a Comment