# 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|}{\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)$$.

• 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 Jun 16 '11 at 2:23
• Where does lLinear Programming come into the picture? It is only mentioned in the question title. Oct 2 at 14:11
• @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).
– zeb
Oct 2 at 17:25

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.