show/hide this revision's text 2 edited body

Since the question has acquired over 1000 views (of which I am sure less than half were done by me), I thought I would celebrate by giving an improvement that I promised half a year ago. This is a refinement of a version I sent to several people; I invite the reader to submit corrections and/or criticism.

$\newcommand{piim}{\pi^{-1}(m)} \newcommand{sigim}{\sigma^{-1}(m)}$ The goal is to use Stevens's argument with improved estimates so as to reduce the exponent given by his method, which gives an upper bound on Jacobsthal's function. The preliminaries have been covered in the question and another answer, so I start with the following: for $m$ a squarefree positive integer, $7 \lt n =\nu(m) =$ the number of distinct prime factors of $m$, $j(m)$ the value of Jacobsthal's function, one has after the use of inclusion-exclusion and the Bonferroni inequalties that there is an odd positive integer $s$ such that $SB/(P-T) \gt 0$, which would imply that $j(m) \leq SB/(P-T)$, where $$SB= \sum_{1 \leq i \leq s} {{n} \choose {i}}\text{ , } P=\piim=\prod_{p \text{ prime, }p \mid m}(1 - 1/p) \text{, and } T = \sum_{s \lt k \leq n} (-1)^k \sum_{d \mid m, \nu(d)=k} 1/d . $$ The smaller a value of $s$ we can find, the better an upper bound we can form.

I will find $T'$ big enough that $T' > T$, yet small enough to get a nice value for $s$ and show that $P - T' > 0$. Then I will massage $P - T'$ and $SB$ to give a slightly weaker upper bound that is easier to write down.

Let's write $\sigim = \sum_{1<=i<=n} 1/m_i$ with $m_i$ being the distinct prime divisors of $m$. (I use $-1$ as a superscript, NOT as an exponent, in both $\piim$ and $\sigim$.) Now $T$ is an alternating series, and for $k \gt 0$, $$\sigim\sum_{d \mid m, \nu(d)=k} 1/d \gt (k+1)\sum_{d \mid m, \nu(d)=(k+1)} 1/d,$$ so if $s$ is odd and larger than $\sigim$, then it would suffice to replace $T$ by $D=\sum_{d \mid m, \nu(d)=s+1} 1/d$, provided we can show $D < P$. Instead, we use an upper bound for $D$, namely $T' = \sigim^{s+1}/(s+1)!$, which follows by using the inequality above $s$-many times.

Let us find a value for $s$ such that $P(s+1)! > \sigim^{s+1} = (s+1)!T'$. An earlier version of this result did some work to show that one could pick $s+1 >= 4\sigim > 0$, and in fact $4$ can sometimes be replaced by a smaller constant. The choice of $T'$ saves some work, and using $4$ will also make things easier.

The following steps require $m \gt 1$, $s+1 \gt 1$, $s+1 \geq 4\sigim$, $0\lt P \lt 1$, and finally $e \lt P^{-1/\sigim} \leq 4 \in (e,4]$ (which is proved in [1]).

\begin{eqnarray*} & e \lt 4^{3/4} \text{, so } e* P^{-1/4\sigim}\lt e*4^{1/4} \lt 4, \\ \text{so} & \sigim \lt P^{1/4\sigim} 4\sigim/e \leq P^{1/s+1}((s+1)/e), \\ \text{so} & \sigim^{s+1} \lt P((s+1)/e)^{s+1} \lt P(s+1)! . \end{eqnarray*}

Now that we have a candidate for $s$, let us choose the smallest odd $s$ such that $s+1 \geq 4\sigim$. Then

$$\frac{\sum_{1 \leq i \leq s} {{n}\choose{i}}}{P - \sigim^{s+1}/(s+1)!} \gt 0$$, 0,$$ so this is an upper bound on $j(m)$. Our choice of $s$ gives that the denominator $P - T$ is actually larger than $(\sqrt{2\pi(s+1)} - 1)\sigim^{s+1}/(s+1)!$, and we can collapse the summands in the binomial sum to get

$$j(m) \lt \frac{(s+1)![\sum_{0 \leq 2j \lt s} {{n+1} \choose {s-2j}}]} {(\sqrt{2\pi(s+1)} - 1)\sigim^{s+1}} .$$

Now for $\sigim \leq 1$ there are better bounds. In particular, given $m_1$ is the smallest prime factor of $m$, one has a bound when $\sigim \leq 1 + 1/m_1$ as
$j(m)< (2n - 1 - \sigim + 1/m_1)/(1 - \sigim + 1/m_1)$. So the estimate above is interesting primarily for $n > 7$.

If we compare this to Kanold's simpler bound ($2^n$ for all $m \gt 1$, $2^\sqrt{n}$ for $n> e^{50}$), we find that this improves upon the $2^n$ bound for $n \gt 30$, and even improves upon the $2^\sqrt{n}$ bound for $n$ as small as $22500$. There are other bounds out there which improve upon this, but do not make the constants explicit.

For $n>7$, we can upper bound the sum by a geometric series, and replace it by a single binomial times a fudge factor which gets close to 1 as n grows. Writing $K= 1 + s(s-1)/(n+2)(n + 3 - 2s)$,and rewriting the term $(s+1)! {{n+1}\choose{s}}$, one gets

$$\text{for } n \gt 7, j(m) \lt \frac{K (s+1)[(n-(s-3)/2)/\sigim]^s}{(\sqrt{2\pi(s+1)} - 1)\sigim}$$

where this is most useful for $ 1 \le \sigim $ and $s$ the smallest odd integer greater tham $4\sigim$.

I may show some later refinements of this. However, $\sigim < 1 + \log\log n $ for $n > 7$ so the exponent $s$ grows very slowly. This will do for now.

[1] G. Paseman, "The Waltraud and Richard R. Paseman Theorem", private manuscript, March 2011.

Gerhard "Ask Me About System Design" Paseman, 2011.09.08
show/hide this revision's text 1

Since the question has acquired over 1000 views (of which I am sure less than half were done by me), I thought I would celebrate by giving an improvement that I promised half a year ago. This is a refinement of a version I sent to several people; I invite the reader to submit corrections and/or criticism.

$\newcommand{piim}{\pi^{-1}(m)} \newcommand{sigim}{\sigma^{-1}(m)}$ The goal is to use Stevens's argument with improved estimates so as to reduce the exponent given by his method, which gives an upper bound on Jacobsthal's function. The preliminaries have been covered in the question and another answer, so I start with the following: for $m$ a squarefree positive integer, $7 \lt n =\nu(m) =$ the number of distinct prime factors of $m$, $j(m)$ the value of Jacobsthal's function, one has after the use of inclusion-exclusion and the Bonferroni inequalties that there is an odd positive integer $s$ such that $SB/(P-T) \gt 0$, which would imply that $j(m) \leq SB/(P-T)$, where $$SB= \sum_{1 \leq i \leq s} {{n} \choose {i}}\text{ , } P=\piim=\prod_{p \text{ prime, }p \mid m}(1 - 1/p) \text{, and } T = \sum_{s \lt k \leq n} (-1)^k \sum_{d \mid m, \nu(d)=k} 1/d . $$ The smaller a value of $s$ we can find, the better an upper bound we can form.

I will find $T'$ big enough that $T' > T$, yet small enough to get a nice value for $s$ and show that $P - T' > 0$. Then I will massage $P - T'$ and $SB$ to give a slightly weaker upper bound that is easier to write down.

Let's write $\sigim = \sum_{1<=i<=n} 1/m_i$ with $m_i$ being the distinct prime divisors of $m$. (I use $-1$ as a superscript, NOT as an exponent, in both $\piim$ and $\sigim$.) Now $T$ is an alternating series, and for $k \gt 0$, $$\sigim\sum_{d \mid m, \nu(d)=k} 1/d \gt (k+1)\sum_{d \mid m, \nu(d)=(k+1)} 1/d,$$ so if $s$ is odd and larger than $\sigim$, then it would suffice to replace $T$ by $D=\sum_{d \mid m, \nu(d)=s+1} 1/d$, provided we can show $D < P$. Instead, we use an upper bound for $D$, namely $T' = \sigim^{s+1}/(s+1)!$, which follows by using the inequality above $s$-many times.

Let us find a value for $s$ such that $P(s+1)! > \sigim^{s+1} = (s+1)!T'$. An earlier version of this result did some work to show that one could pick $s+1 >= 4\sigim > 0$, and in fact $4$ can sometimes be replaced by a smaller constant. The choice of $T'$ saves some work, and using $4$ will also make things easier.

The following steps require $m \gt 1$, $s+1 \gt 1$, $s+1 \geq 4\sigim$, $0\lt P \lt 1$, and finally $e \lt P^{-1/\sigim} \leq 4 \in (e,4]$ (which is proved in [1]).

\begin{eqnarray*} & e \lt 4^{3/4} \text{, so } e* P^{-1/4\sigim}\lt e*4^{1/4} \lt 4, \\ \text{so} & \sigim \lt P^{1/4\sigim} 4\sigim/e \leq P^{1/s+1}((s+1)/e), \\ \text{so} & \sigim^{s+1} \lt P((s+1)/e)^{s+1} \lt P(s+1)! . \end{eqnarray*}

Now that we have a candidate for $s$, let us choose the smallest odd $s$ such that $s+1 \geq 4\sigim$. Then

$$\frac{\sum_{1 \leq i \leq s} {{n}\choose{i}}}{P - \sigim^{s+1}/(s+1)!} \gt 0$$, so this is an upper bound on $j(m)$. Our choice of $s$ gives that the denominator $P - T$ is actually larger than $(\sqrt{2\pi(s+1)} - 1)\sigim^{s+1}/(s+1)!$, and we can collapse the summands in the binomial sum to get

$$j(m) \lt \frac{(s+1)![\sum_{0 \leq 2j \lt s} {{n+1} \choose {s-2j}}]} {(\sqrt{2\pi(s+1)} - 1)\sigim^{s+1}} .$$

Now for $\sigim \leq 1$ there are better bounds. In particular, given $m_1$ is the smallest prime factor of $m$, one has a bound when $\sigim \leq 1 + 1/m_1$ as
$j(m)< (2n - 1 - \sigim + 1/m_1)/(1 - \sigim + 1/m_1)$. So the estimate above is interesting primarily for $n > 7$.

If we compare this to Kanold's simpler bound ($2^n$ for all $m \gt 1$, $2^\sqrt{n}$ for $n> e^{50}$), we find that this improves upon the $2^n$ bound for $n \gt 30$, and even improves upon the $2^\sqrt{n}$ bound for $n$ as small as $22500$. There are other bounds out there which improve upon this, but do not make the constants explicit.

For $n>7$, we can upper bound the sum by a geometric series, and replace it by a single binomial times a fudge factor which gets close to 1 as n grows. Writing $K= 1 + s(s-1)/(n+2)(n + 3 - 2s)$,and rewriting the term $(s+1)! {{n+1}\choose{s}}$, one gets

$$\text{for } n \gt 7, j(m) \lt \frac{K (s+1)[(n-(s-3)/2)/\sigim]^s}{(\sqrt{2\pi(s+1)} - 1)\sigim}$$

where this is most useful for $ 1 \le \sigim $ and $s$ the smallest odd integer greater tham $4\sigim$.

I may show some later refinements of this. However, $\sigim < 1 + \log\log n $ for $n > 7$ so the exponent $s$ grows very slowly. This will do for now.

[1] G. Paseman, "The Waltraud and Richard R. Paseman Theorem", private manuscript, March 2011.

Gerhard "Ask Me About System Design" Paseman, 2011.09.08