Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

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.

share|improve this answer
1  
I downvoted this post because it is not particularly helpful with the question at hand. I think Zeb's question should remain in the unanswered list, and I would suggest that people refrain from upvoting simply so that the question doesn't get bumped up by the software. –  Gjergji Zaimi Dec 14 '11 at 4:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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