Gerhard Paseman asked a question about bounds on the Jacobsthal function a while ago, which made me curious about whether the known bounds are best possible. Briefly, the Jacobsthal function $j(n)$ is defined to be the smallest integer $m$ such that any sequence of $m$ consecutive integers always contains an integer relatively prime to $n$. Most interesting (to me) are bounds on $j(P_n)$, where $P_n$ is the product of the first $n$ primes.

Hagedorn's paper has a good survey of known results for the Jacobsthal function, along with a calculation of $j(P_n)$ for $n \le 49$. The best known result, due to Iwaniec, says that $j(P_n) \ll n^2\log^2(n)$.

To see whether Iwaniec's result is in some sense best possible, I defined a "linearized jacobsthal function": for $n$ squarefree, $j_{lin}(n)$ is defined to be the largest $I$ such that there exist constants $a_D \ge 0$ for $D \mid n$ such that for any $d \mid n$, we have

$-1 \le \frac{I}{d}-\sum_{d\mid D,D\mid n}a_D \le 1$, and

$a_1 = 0$.

Alternatively, by duality, $j_{lin}(n)$ is the minimum value of

$\frac{\sum_{d\mid n} |c_d|}{\max\left( \sum_{d\mid n} \frac{c_d}{d}, 0\right)}$

over all sets of real constants $c_d$ such that for any $D \mid n$, $D > 1$, we have

$\sum_{d\mid D} c_d \le 0$.

The first few values of $j_{lin}(P_n)$ are $4, 12, 25.7143, 49.4118, 80.1156, 118.403,...$. Iwaniec's upper bound also applies to $j_{lin}$, so we know that in general, $j_{lin}(P_n) \ll n^2\log^2(n)$.

The prime 2

After calculating $j_{lin}(P_n)$ up to $n = 75$, I noticed that in every single case we have $c_d = -c_{2d}$. At first I assumed it was a coincidence, but now I'm starting to wonder:

Can we prove that for an optimal sieve, we always have $c_d = -c_{2d}$?

If we can, then we can show that $j_{lin}(P_n) = 4j_{lin}(P_n/2)$, since then

$\frac{\sum_{d\mid P_n} |c_d|}{\sum_{d\mid P_n} \frac{c_d}{d}} = \frac{\sum_{2d\mid P_n} 2|c_d|}{\sum_{2d\mid P_n} \frac{1}{2}\frac{c_d}{d}} = 4\frac{\sum_{2d\mid P_n} |c_d|}{\sum_{2d\mid P_n} \frac{c_d}{d}}$.

This is important to me because calculating $j_{lin}(P_n/2)$ takes up much less time and memory than calculating $j_{lin}(P_n)$. Note that we easily have $j(P_n) = 2j(P_n/2)$, so this would imply that $j(P_n) \le j_{lin}(P_n)/2$.

If this is true, then any proof has to use something special about the prime $2$: for instance, we don't always have $c_d = -c_{3d}$.

I've been trying to prove this using a construction: suppose we are given $I, a_D$ for $j_{lin}(P_n/2)$. Let $\alpha_D$ be the "expected value" of $a_D$, i.e. $\alpha_D = \frac{\phi(P_n/2)}{\phi(D)P_n/2}I$. Then if we take $b_D = 2a_D$, $b_{2D} = 3\alpha_D-a_D$ for $D \mid P_n/2$, we get

$\frac{4I}{d} - \sum_{d|D,D|P_n} b_D = \frac{4I}{d} - \sum_{d\mid D,2D\mid P_n} (3\alpha_D + a_D) = \frac{I}{d} - \sum_{d\mid D,2D\mid P_n} a_D$ for $d$ odd, and

$\frac{4I}{2d} - \sum_{2d|D,D|P_n} b_D = \frac{2I}{d} - \sum_{d\mid D,2D\mid P_n} (3\alpha_D-a_D) = -(\frac{I}{d} - \sum_{d\mid D,2D\mid P_n} a_D)$ for $2d$ even.

The only problem with this construction is that $b_{2D} = 3\alpha_D - a_D$ isn't guaranteed to be nonnegative. At first I hoped that we could show that it is always nonnegative using an upper bound sieve (which I think should show something along the lines of $2\alpha_D+\epsilon \ge a_D$ with $\epsilon$ not too large), but in fact when I examined the $a_D$s I get while computing $j_{lin}(P_n/2)$, there are lots of examples where we have $3\alpha_D < a_D$, typically with $D$ large and $|3\alpha_D-a_D|$ small. For example, when $n = 75$, we have $I = j_{lin}(P_{75}/2) \approx 7603.73$, and the worst offender is $D = 379$ for which we have $a_D \approx 14.7$, $\alpha_D \approx 3.77$, $3\alpha_D - a_D \approx -3.38$.

What lower bounds can we put on the $b_{2D}$s?

Is there a way to modify this construction slightly, to make all the $b_{2D}$s positive?

One thing to keep in mind is that we can make a similar construction that I suspect can't work for any prime $p > 2$. To do this, take $b_D = 2a_D$, $b_{pD} = \frac{p+1}{p-1}\alpha_D - a_D$, and we get

$\frac{2pI}{(p-1)d} - \sum_{d|D,D|P_n} b_D = \frac{2pI}{(p-1)d} - \sum_{d\mid D,pD\mid P_n} (\frac{p+1}{p-1}\alpha_D + a_D) = \frac{I}{d} - \sum_{d\mid D,pD\mid P_n} a_D$, and

$\frac{2I}{(p-1)d} - \sum_{pd|D,D|P_n} b_D = \frac{2I}{(p-1)d} - \sum_{d\mid D,pD\mid P_n} (\frac{p+1}{p-1}\alpha_D-a_D) = -(\frac{I}{d} - \sum_{d\mid D,pD\mid P_n} a_D)$,

so if we had $\frac{p+1}{p-1}\alpha_D - a_D \ge 0$ for all $D$, we would get $j_{lin}(P_n) = \frac{2p}{p-1}j_{lin}(P_n/p)$.

  • $\begingroup$ I think Hagedorn covers the prime 2 in his paper, and N Saradha has kindly given me a preprint which might help with (if not directly imply) your c_d = -c_2d for odd d. If you figure out the Hangman puzzle on my registered MathOverflow page, I invite you to email me so that I can tell you more of Saradha's work. I can also send you improved bounds ala Stevens, although not as good as Iwaniec has for large n. Gerhard "Ask Me About System Design" Paseman, 2011.06.15 $\endgroup$ Jun 16, 2011 at 2:23
  • $\begingroup$ Where does lLinear Programming come into the picture? It is only mentioned in the question title. $\endgroup$ Oct 2, 2021 at 14:11
  • 1
    $\begingroup$ @Mark In order to compute $j_{lin}(n)$, you need to solve a linear program - for $j_{lin}(P_n)$, this linear program has $2^n$ variables (however, it seems to be the case that there are always optimal solutions where only polynomially many of the variables are nonzero). $\endgroup$
    – zeb
    Oct 2, 2021 at 17:25

1 Answer 1


Kanold gives the general recurrence $j(p \times n) \leq p \times ((j(n)-1)+1$, which covers Hagedorn's result $j(2 \times n) = 2 \times j(n)-1$ (Kanold, Math. Annal. 157 (1965), 358-362). This might help with any further relations you find.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.