A quadratic bound for Jacobsthal’s function

The explanation

Take the number 210. It is 2 × 3 × 5 × 7, so it has four distinct prime factors. Now look at the run 2, 3, 4, 5, 6, 7, 8, 9, 10. Every one of these nine numbers shares a factor with 210. Each is even, or a multiple of 3, 5 or 7. The next number, 11, shares no factor with 210. Mathematicians call such a number coprime to 210.

So 210 allows a run of nine numbers with no coprime number in it. A computer search over every starting point finds no longer run. Every stretch of 10 consecutive whole numbers therefore contains a number coprime to 210. Jacobsthal's function, j(n), records exactly this: the shortest length that always works for n. Here j(210) = 10.

A bigger question asks about every number with at most k prime factors at once. Call the answer h(k). It is the shortest interval length that always contains a number coprime to any such number. The interval may start anywhere. For k = 4 the answer is again 10. Hajdu and Saradha proved that the first k primes give the worst case for every k up to 23. At k = 24 that pattern breaks. There, the first 24 primes give 234, but the true worst case is 236.

There is a second way to see the problem. For each prime, cross out one chosen remainder class, such as every number leaving remainder 1 when divided by 3. Then ask how long a run of whole numbers can be crossed out entirely. The paper notes that this is the same problem. It also explains why arbitrary primes and arbitrary starting points come together.

Jacobsthal studied this function in papers beginning in 1960. Erdős later recorded his question: does h(k) grow no faster than a constant times k squared? Erdős observed that Brun's method gives some fixed power of k. In 1977, Vaughan proved a bound of order k² times the fourth power of log k. Here log means the natural logarithm, a slowly growing function. In 1978, Iwaniec improved this to order k² times (log k)². That logarithmic factor never went away. At a million primes, (log k)² is already about 191.

Vaughan explained where the square comes from. The standard counting tool, called a sieve, estimates how many numbers survive the crossing out. At exactly the quadratic length, its guaranteed lower count drops to zero. So the usual method says nothing useful right at the scale Jacobsthal asked about. The paper keeps a small boundary term that the standard method throws awaySource 1. It then shows that cleverly chosen remainder classes cannot cancel that termSource 2. Classes that try to do so are forced into a rigid, predictable pattern, and that pattern can be handled.

This paper proves that the answer to Jacobsthal's question is yesSource 3. There is a fixed constant C that works for every k. The bound says h(k) is at most C k² divided by (log log 3k)²Source 3. That is slightly better than k² itself. The bound holds for any set of primes and any starting pointSource 4. In the example's terms, no k primes and remainders can cross out a run longer than C k².

The result has limits. The constant C is not made explicit, so the theorem gives no concrete number for any given kSource 5. It also does not settle the true growth rate. Ford, Green, Konyagin, Maynard and Tao gave the best known lower bound. It grows like k times a few slow logarithmic factors. Vaughan suggested that the true growth might be only slightly faster than k. The gap between these bounds remains substantialSource 6.

How sure is this? A computer proof checker called Lean has checked a formal version of the main bound. It covers one fixed C and every k. Intervals may start at any integer, including negative ones. The plain quadratic bound is checked as a separate statement. No specialists have published a review yet.

What it doesn't show. This does not find the true growth rate of Jacobsthal's function, and it gives no explicit constant.