# Best possible sieves for the jacobsthal problem, linear programming, and the prime 2

## Background/Motivation

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|}{\left| \sum_{d\mid n} \frac{c_d}{d} \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|}{\left| \sum_{d\mid P_n} \frac{c_d}{d} \right|} = \frac{\sum_{2d\mid P_n} 2|c_d|}{\left| \sum_{2d\mid P_n} \frac{1}{2}\frac{c_d}{d} \right|} = 4\frac{\sum_{2d\mid P_n} |c_d|}{\left| \sum_{2d\mid P_n} \frac{c_d}{d} \right|}$.

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)$.

-
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 – Gerhard Paseman Jun 16 '11 at 2:23

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.