Jacobsthal’s function and residue coverings

Source and verification

This article explains family 021 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Gaps between integers coprime to a modulus

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

$$h(k)=\underset{\omega (n)\le k}{\sup }j(n).$$

Prime powers do not matter: replacing $n$ by the product of its distinct prime divisors leaves $j(n)$ unchanged. The starting point of the interval can be any signed integer.

For example, the residues coprime to six are one and five. The three consecutive integers $2,3,4$ are all excluded, while every four consecutive integers contain a survivor. Thus $j(6)=4$.

Claimed uniform bound

The manuscript asserts an absolute $C>0$ such that

$$\begin{array}{c}h(k)\le C\frac{k^2}{(\log \log (3k){)}^2}\\ (k\ge 1).\end{array}$$

The denominator is well-defined and nonzero even at $k=1$. The constant is not made explicit, and the optimal order is not determined. (OpenAI, 2026)

This is a theorem about arbitrary prime sets, not only the first $k$ primes. The source recalls that the primorial need not maximize $j(n)$ for a prescribed number of prime divisors.

🏷️ A covering interpretation

For a finite prime set, prescribe one forbidden class $a_p(\mathrm{mod}p)$ at each prime. The Chinese remainder theorem gives a common integer $b$ with $b\equiv a_p(\mathrm{mod}p)$. Then

$$\begin{array}{c}n\not\equiv a_p(\mathrm{mod}p)\text{for every }p\\ ⟺\gcd \left(n-b,\prod p\right)=1.\end{array}$$

Thus arbitrary classes are equivalent to translating the original coprimality problem. One must control the worst choice, not a randomly selected covering.

For large $z$, the source uses

$$\begin{array}{c}L=\log z,Y=\lfloor z^2/L^2\rfloor ,\\ w=L/(\log L{)}^2,\\ B=L/\log w,\\ V_0=\prod _{p\le w}(1-1/p).\end{array}$$

Its principal intermediate theorem claims at least $cY{V}_0/B^2$ survivors in $[1,Y]$, for every assignment of forbidden classes at all primes $p\le z$. By Mertens’ estimate, this is of order

$$\frac{Y\log w}{L^2}.$$

The number of survivors is crucial: positivity alone would leave no reserve against the remaining prime divisors.

🏷️ From a size cutoff to a number of primes

Given at most $k$ divisor primes, choose

$$z=A_0\frac{k\log k}{\log \log k},$$

with $A_0$ a sufficiently large fixed constant. Then $Y\asymp k^2/(\log \log k{)}^2$.

Use the survivor theorem at the primes up to $z$, inserting arbitrary extra forbidden classes if necessary. This can only remove more integers than the original small-prime restrictions.

The primes $q>z$ dividing the prescribed modulus remove some of the survivors. A progression upper sieve bounds their total loss by

$$\begin{array}{c}O(k(1+X/\log X)),\\ X=Y/z.\end{array}$$

The claimed small-prime reserve dominates this loss once $A_0$ is sufficiently large. At least one integer survives every divisor prime, giving the desired interval length. A larger absolute constant handles bounded $k$.

This calculation explains why the intermediate theorem is quantitative and why its cutoff is chosen in terms of $k\log k/\log \log k$.

🏷️ The critical sieve boundary

The linear sieve has a lower-bound function that vanishes at its critical parameter two. The source works near this boundary, where the leading term cannot furnish the needed positive count.

It expands exclusions by the first prime at which an integer hits a forbidden class. Iteration creates strictly decreasing prime paths. Even-depth truncations give lower bounds and odd-depth truncations give upper bounds.

A reference calculation replaces actual small-prime counts in progressions by their expected lengths times $V_0$. After reciprocal-prime sums become harmonic integrals, a renewal process evaluates a smaller boundary contribution of scale $B^{-2}$. The claimed positivity lives at this secondary scale.

However, positivity of a reference model is not yet a theorem about arbitrary prescribed classes. Short progressions may deviate strongly from the expected density.

🏷️ Controlling the discrepancy

The inverse estimate says that many discrepant paths force alignment with a finite list of rational numbers $A/D$. At a prime $p$, alignment means

$$D{a}_p\equiv A(\mathrm{mod}p).$$

Polynomial interpolation, lattice-point estimates, and a larger-sieve comparison supply this structure. Variance estimates then restrict which rationals can account for much of the bad mass.

Remaining paths contain many earlier primes aligned with the same rational. The proof stops these paths at selected even nodes and averages over one aligned prime. At such a stop, the actual survivor count exceeds the reference subtree requirement. A renewal estimate controls paths that never reach a useful stop.

The final comparison combines the positive reference margin, discrepancy bounds, and stopped counts. Fixed prime-bin widths are chosen before $z$ tends to infinity; the result does not assert uniformity for shrinking bins.

🏷️ Key steps and proof outlines

A first-bad-prime partition fixes every sign in the sieve tree

At a node with product $d$ of already selected primes, let $N_d$ count integers hitting their prescribed classes and avoiding the classes for primes at most $w$. Let $S_d(b)$ additionally avoid the still available primes, all smaller than the last selected prime. The source uses the exact identity

$$S_d(b)=N_d-\sum _{p\text{ available}}{S}_{dp}(x(p)),x(p)=\frac{\log p}{\log w}.$$

Proof outline. Partition the excluded integers by their smallest bad available prime $p$. Such an integer hits $p$ and avoids all smaller available primes, exactly the child condition. The partition uses the smallest bad prime, while successive recursion selects decreasing primes; these descriptions are compatible.

Call even-depth nodes lower nodes and odd-depth nodes upper nodes. At a lower node include every child and use upper bounds on its subtracted child counts. At an upper node one may omit nonnegative child counts and use lower bounds on those retained. Induction upward from the leaves proves the alternating lower bound at the root. The admission condition also ensures that every progression left in the tree has length at least $w^{1/100}$, where the small-prime estimates apply. (OpenAI, 2026)

Stopping is an exact replacement, not deletion of an inconvenient error

Let ${\mu }_d=(Y/d)V_0$ be the reference count. Replacing every $N_d$ by ${\mu }_d$ defines a reference subtree value ${\mu }_d{P}_{\mathrm{even}}(r_d,b_d)$ at an even node, where $r_d$ records its remaining logarithmic length and $b_d$ its prime cutoff.

Proof outline. Choose a prefix-free collection of lower nodes: no chosen node is a descendant of another. At each one retain its exact count $S_d(b_d)$ and do not expand its descendants. An exact count is a valid lower bound, so the alternating-sign induction still applies. Expand the reference tree to these same stops and subtract. If $\mathcal{T}$ contains the expanded nodes and $\mathcal{S}$ the stops, the identity is

$$\begin{array}{rl}{L}_{\mathrm{stop}}-Y{V}_0{P}_{\mathrm{even}}(r_0,B)=& \sum _{d\in \mathcal{T}}(-1{)}^{\omega (d)}(N_d-{\mu }_d)\\ & +\sum _{d\in \mathcal{S}}\left[S_d(b_d)-{\mu }_d{P}_{\mathrm{even}}(r_d,b_d)\right].\end{array}$$

This tells us precisely what a stopping theorem must prove. The source bounds the first sum absolutely and makes the second nonnegative in aggregate. It does not assert that each stopped node has a nonnegative individual excess.

Structural estimates protect a secondary reference margin

The renewal calculation supplies $P_{\mathrm{even}}(r_0,B)\ge c_L/B^2$. Since this is a secondary term at the critical sieve boundary, the total errors must be smaller than $Y{V}_0/B^2$, not merely $o(Y{V}_0)$.

Proof outline. Large-gap nodes have exponentially small relative small-prime errors, and the occupation estimate bounds their total contribution. Compact-gap nodes with small relative error are controlled by their total harmonic mass, where a path has weight $1/d$. For a remaining bad node, the inverse theorem extracts a witnessing discrepancy and alignment with one of a fixed finite list of rationals. The variance theorem either puts it in a small exceptional set or forces many aligned earlier primes. The hard-stopping theorem then sends it into a stopped subtree, apart from another small exceptional set. This exhausts the possibilities; counting the number of boxes would be insufficient, because the estimates control their weighted mass.

Contribution	Allocated absolute error
Large-gap nodes	At most $(c_L/8)Y{V}_0/B^2$
Good compact-gap nodes	At most $(c_L/8)Y{V}_0/B^2$
Bad compact-gap nodes still retained	At most $(c_L/8)Y{V}_0/B^2$
Aggregate stopped-subtree difference	Nonnegative

Insert these four conclusions into the exact stopped-tree identity. At least $(5c_L/8)Y{V}_0/B^2$ remains, and hence the weaker claimed reserve $(c_L/2)Y{V}_0/B^2$. Constants, finite rational lists, and exception tolerances are fixed before the bin width; the bin width is then fixed before $z\to \infty$. The renewal, inverse, and variance estimates are substantive source inputs, while this assembly explains their required strengths and dependence order.

The surviving reserve pays for every remaining divisor prime

For $z=A_{0}k\log k/\log \log k$, put $X=Y/z$. A prime $q>z$ meets the original interval in at most $1+Y/q\le 1+X$ progression positions. Its step is invertible modulo the smaller sieve primes.

Proof outline. Apply an upper-bound sieve in those progression coordinates. The positions already surviving all primes up to $z$ avoid the required residue classes for primes up to a small fixed power of $X$. Thus each $q$ removes at most $C_1(1+X/\log X)$ survivors, uniformly even when $q>Y$. There are at most $k$ such divisor primes. With the preceding scale definitions,

$$\frac{k(1+X/\log X)}{Y\log w/L^2}⟶\frac{1}{A_0}.$$

Choose the fixed $A_0$ larger than twice the ratio of the deletion constant to the survivor constant. The total deletion is then strictly smaller than the reserve. At least one integer survives, and $Y\asymp k^2/(\log \log k{)}^2$. Translating the forbidden classes handles every signed interval start; the argument has not used any assumption that the divisor primes are consecutive.

🏷️ Connections

Large prime-gap frequency uses a different sieve construction to create adjacent prime-containing and empty intervals. Inverse Goldbach also uses simultaneous residue restrictions and an inverse estimate.

🏷️ Manuscripts and verification scope

• A quadratic bound for Jacobsthal’s function — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page selects the quadratic bound and its iterated-logarithm improvement, with arbitrary signed interval starts. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. A quadratic bound for Jacobsthal’s function.