Erik Westzynthius's cool upper bound argument: update?

So it turns out that sieve theory already has some results that can give bounds for this problem. It took me a while to track down a paper that gives an explicit result, but I finally found this one.

Using the Bonferroni inequalities gives you what is called "Brun's pure sieve". According to Wikipedia, Brun's pure sieve gives a bound of the form $n^{b\log\log(n)}$ for some $b$.

According to the result in the paper, using the full power of Brun's sieve (which involves splitting up the primes we are sifting by into buckets of primes based on their sizes, throwing out terms of the inclusion-exclusion rule which have too many primes from the large buckets and then applying an inequality similar to the Bonferroni inequalities), we get that the number of numbers in an interval of length $x$ that are relatively prime to the first $n$ primes is at least

$x(\prod_{p\le p_n}(1-\frac{1}{p}))(1-2\frac{\lambda^{2b}e^{2\lambda}}{1-(\lambda e^{1+\lambda})^2}(1+o(1)))+O \left(p_n^{2b-1+\frac{2}{e^{2\lambda}-1}+\epsilon}\right)$,

where $b$ is an integer we get to choose, $\lambda$ is a positive real number we get to choose, and $\epsilon$ is greater than $0$.

If we plug in $b = 1$ and $\lambda = 0.2533$, we get that for sufficiently large $n$, any interval of size $O(n^{4.032})$ contains a number relatively prime to the first $n$ primes.

You can probably get better bounds with other sieves.

As far as what the best bound really is, I'm going to conjecture that the longest stretch of numbers that are not relatively prime to the first $n$ primes always has length less than $2p_n$. Computer search shows that this is true for $p_n \le 31$, and the worst case example for primes up to $31$ looks like this:

X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X .X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X. ...X....X....X....X....X....X....X....X....X....X....X... X......X......X......X......X......X......X......X......X ......X..........X..........X..........X..........X...... ..X............X............X............X............X.. ...........X................X................X........... .........X..................X..................X......... .....X......................X......................X..... ...........................X............................X .............................X........................... 

where the columns represent numbers, the rows represent primes, and an X means that the number corresponding to the column has been sieved out by the prime corresponding to the row.

I present the following as unverified information and would appreciate others who could confirm and supplement any of it.

Erik Westzynthius seems to have a middle name Johan. I am hoping he is the only mathematically inclined Erik Westzynthius in Finland, but there are several Erik Westzynthius' in Finnish genealogy. He was born in Helsinki on March 9, 1901, and had a sister and later a wife, but I have not found any children of his, biologic or academic.

There seem to be contributions by him to Scandinavian actuarial publications as early as 1924, and his name appears (without Johan) in a 1957 Scandinavian mathematical congress roster and also in the 1978 ICM held in Helsinki. He also seems to be acknowledged in a book on surgery for his mathematical assistance; I am searching Google Books using the term "Erik Westzynthius" and am finding only snippets. I have not found any other number theory contributions from him.

The work referenced in the question was communicated to the journal in September 1931 by R. Nevanlinna and E. Lindelof, but it is not clear that this work is what got Erik his fil. dr.; his result was a significant advance in the study of prime gaps however, so my money says it was the Finnish equivalent of his doctoral dissertation. Further, several reviews in different languages of the result appear shortly thereafter, and it isn't long before Erdos and Rankin find improvements.

I am placing this entry as community wiki and invite the MathOverflow community, especially the Scandinavian portion, to improve upon it.

Gerhard "Not Quite The Gentleman Scholar" Paseman, 2012.01.19

Here is a partial answer. For those who want more information on this subject, Will Jagy has been kind enough to forward appropriate emails to me, to which I respond. I ask that you send requests about this to him to forward to me, until such time as I get a public email address set up.

For me, the key bit in the argument above is $E(t)$. I put it in because I intended to follow up with a post that ran through the argument again, except using only odd numbers (as per Westzynthius's footnote), and then certain thin sets ($S(k)$, the integers relatively prime to $P_k$: I have not seen this idea of applying thin sets to this sum elsewhere) . For example, using not the integers but instead the set $S(2)$ of numbers which are of the form $6m + 1$ or $6m - 1$, we can run through the argument again, except we replace $x/t$ by $\rho*x/t$ and $E(t)$ by $E_2(x/t)$. $\rho$ is the density (= 1/3) of $S(2)$ in the integers, and $E_2(x/t)$ is a more complicated error function which has a maximum value of 4/3. When the dust settles, we get for large $n$ a value for $x$ close to $Q * 2^{n-2}$.

Of course the idea of using even thinner sets now occurs. To set that up, suppose that $f(k)$ is an increasing function of $k$ to be constrained soon. For notational convenience, set $M(k)$ to be the maximum of the function $E_k(y)$ as $y$ ranges over all real numbers. Let us assume:

(subexponential growth in $k$ of $E_k(y)$ ) $M(k)*f(k) < 2^k$ .

Now with this assumption on $E_k$, the argument runs as follows: set up $I_0$ again with an inclusion exclusion argument, but count subsets $J_t$ of $S(k)$, the integers relatively prime to the $k$th primorial which are multiples of $t$. $t$ now ranges over the divisors of $P_n/P_k$. We get a sum of $2^{n-k}$ terms card($J_t$), each of which is replaced by a linear approximation as before, but now I change notation slightly and use the error function $E_k(y)$, and replace $Q$ by $Q_n$. I collect terms as before to get

$I_0 >= x/Q_n - \sum_{t \mid (P_n/P_k)} E_k(x/t)$ .

The smaller I can make this last sum, the better an upper bound I can get on $x$.

Using the growth assumption, I can bound the sum by $2^{n-k}*M(k)$, which is $2^n/f(k)$. I can then get an upper bound of $2^n/f(n-1) * Q_n$ on $x$ just by assuming the worst case values as well as the rather mild growth assumption.

However, it gets better than that. One thing I do know is that $E_k(y)$ is bounded by 1 when $y$ is less than 2. So for many $k$ and many large $t$, I can safely choose $x$ so that $E_k(x/t)$ is bounded by 1 for many $t$, so the sum looks like $2^{n-k} + D*(M(k) - 1)$, where $D$ can be much smaller than $2^{n-k}$.

The problem is that I do not know $M(k)$ or $E_k(y)$ that well. It is likely that $E_k(y)$ not only satisfies the subexponential growth assumption but also that $M(k)$ is bounded by a low degree polynomial in $k$. If this stronger assumption is true, then $x$ will also be bounded by a low degree polynomial in $n$. However, I want something like the growth assumption to hold so that I can comfortably choose $x$.

Now that I have committed myself, I will grind through the calculations to come up with an explicit bound. I predict that $x <= n^2$, that is, that the maximum gap in the sequence $S(n)$ is no bigger than $n^2$.
Now to try proving it.

Gerhard "Ask Me About System Design" Paseman, 2010.12.14

If someone had told me months ago that work on Jacobsthal's function provided bounds for a generalized version of this problem, I might have walked away from the problem and done nothing more. As it is, I've taught myself quite a bit, and will share some of it.

Aaron Meyerowitz was kind enough not only to do some computations for me but also to show me a better way to compute some quantities I was interested in to solve the problem. Inspired by his efforts, I convinced myself that a sequence of error terms I was using satisfied $E_{i+1}(x) \le 2E_i(x)$, which then led me to improve Westzynthius's result to $Q*2^{g(n)}$ where $g(n)$ was $n/2 + O(\log(n))$.

Aaron also pointed me towards a sequence in the Online Encyclopedia of Integer Sequences which led me to Hagedorn's 2009 paper on computing certain values of Jacobsthal's function.
http://www.tcnj.edu/~hagedorn/papers/JacobPaper.pdf As a result, I have an answer to 2 of my questions and an improvement on a result in the literature. For question 1, the answer is yes, there is other work giving provable upper bounds on the order of $2^{\text{polylog}(n)}$. For question 2, the answer is also yes; a 1977 result of Harlan Stevens gives an explicit bound where an important step uses the equivalent of the Bonferroni inequalities. I looked over his argument and decided to tweak it to give an asymptotically better result. (Other work, especially by Iwaniec, give even better asymptotic upper bounds, but do not give explicit constants, so it is hard to tell precisely when those bounds are better.) I give most of Stevens' argument and some related material below.

$m$ will be a positive integer, and I prefer $m \gt 1$. Jacobsthal's function $j(m)$ gives the smallest positive integer $j$ such that, for any interval $I$ of $j$ integers of the form $[a+1,\ldots,a+j]$, it is guaranteed that one of the integers in $I$ is coprime to $m$, i.e. $\gcd(m,a+i)=1$ for at least one $a+i \in I$. Let $\text{rad}(m) = \prod_{p \text{ prime,} p \mid m} p$ be the largest squarefree factor of $m$; $j(\text{rad}(m))=j(m)$ and also $j(m)$ is the size of the largest gap between consecutive members of the set of integers which are relatively prime to $m$. In my problem above, I wanted nice upper bounds on $j(P_n)$, or Jacobsthal's function evaluated at the $n$th primorial.

There are lots of accessible results on $j(m)$. For example, if if $m_1,\ldots,m_n$ are all the distinct prime factors of $m$ (and so of $\text{rad}(m)$), and each of them is greater than $n$, then the Chinese Remainder Theorem is used in showing $j(m) \ge n+1$, and in fact for such $m$, $j(m) = n+1$. This can be generalized with a little bit of help: say $m$ and $r \gt 1 $ are such that $\sum_{1 \le i \le n} 1/m_i \lt (1 - 1/r)$. Then $j(m) \le rn$. Since it will introduce notation to be used later, I sketch a proof.

Proof sketch: For an interval $I$ having $l$ consecutive integers, and for a positive integer $t$ let $J_t$ be the number of (integer) multiples of $t$ inside $I$. Then $\text{ceil}(l/t) \ge J_t \ge \text{floor}(l/t)$. So the count of numbers in $I$ not coprime with $m$ is at most $n + \sum_{1 \le i \le n} l/m_i \lt n + l(1-1/r)$ . Now if $l \ge rn$, then the right hand side of the inequality is at least $l$, meaning at least 1 number in $I$ is coprime with $m$. End of Proof sketch.

One can do better, since for small primes $m_1$ and $m_2$ there may be a multiple of $m_1m_2$ inside the interval. Kanold, Jacobsthal, Erdos and others have done some improving in this area. However, I now show the result by Harlan Stevens.

Theorem (Stevens) $j(m) < 2n^{(2 + 2e\log(n))}$.

Improvement? (Paseman): For sufficiently large $n$, $j(m) \le O^*(n^{(2 +2e \log(\log(p_n)))})$.

The reasons for the $O^*$ will appear, as I will discuss Stevens's proof and the improvement together. In discussing the improvement, I will ask that $n \gt 30$.

Stevens starts out using (equivalents of) $I$, $l$, and $J_t$ as above. He uses inclusion-exclusion to compute $L$, the number of integers coprime to $m$ in the interval $I$. For ease, I assume $m$ is squarefree, and here $\mu(t)$ is the Moebius function, so $\mu(t)$ is (-1) to the power of the number of distinct prime divisors of (squarefree) $t$. Thus,

$L = \sum_{t \mid m} \mu(t)J_t$.

Now Stevens cites Landau to use what I think of as a Bonferroni inequality. Breaking the sum up by $\nu(t)$, the number of distinct prime factors of $t$, one has for odd values of $s$ the following:

$L \ge \sum_{0 \le i \le s} (-1)^i ( \sum_{t \mid m , \nu(t) = i} J_t) $.

Using the estimate $\mid J_t - l/t \mid \le 1$ (except for $t=1$, when $l=J_t$),

$L \ge lT_s - SB $, where $T_s = \sum_{0 \le i \le s} (-1)^i (\sum_{t \mid m , \nu(t) = i} 1/t)$. and $SB = \sum_{1 \le i \le s} \binom{n}{s}$

Now normally one finds $s$ so that $T_s$ and $SB$ can be well estimated, and then one says that for any $l > SB/T_s$, $L$ will be positive, giving that $SB/T_s$ (or the appropriate estimate) is an upper bound for $j(m)$. Stevens doesn't do that. He instead rewrites $T_s$ as $P - T$, finds estimates for $T',P',$ and $SB'$ so that $ SB'/(P' - T') \ge SB/T_s$, ensures that $P' > T'$, and then concludes that $j(m) \le SB'/(P' - T')$. I will do the same, except I will use more refined estimates.

Let's do $SB$. Stevens's replacement is $n^s$; mine is $\binom{n+1}{s}$ times a small fudge factor, which will be strictly less than $n^s$ for $s \gt 2$ and $n$ sufficiently larger than $2s$. The small fudge factor is from dominating the sum by a geometric series with common ratio $\binom{n+1}{s-2} / \binom{n+1}{s}$. This gives $1 + (s(s-1))/((n+2)(n+3-2s))$.

Now Stevens defines $P = \sum_{0 \le i \le n} (-1)^i \sum_{t \mid m , \nu(t) = i} 1/t$. As in the question above, this gives $P = \prod_{1 \le i \le n}(1 - 1/m_i)$ (Recall that the distinct prime factors of $m$ are the $m_i$.) Then $T = P - T_s$, so

$T = \sum_{s \lt i \le n} (-1)^i \sum_{t \mid m , \nu(t) = i} 1/t$ .

Now Stevens estimates $T$ by $T' > T$, first by replacing the inner sum (and throwing away $(-1)^i$), and then by having the index of the outer sum go past $n$. He then uses Taylor's theorem with remainder on $e^{h(n)}$ for a certain choice of $h(n)$ to come up with a compact term that bounds the infinite sum. Then $s$ is restricted to arrive at a $T'$ which bounds $T$ but is still small.

Here we go. For $n$ sufficiently large

$ (i!)\sum_{t \mid m , \nu(t) = i} 1/t \le (\sum_{1 \le j \le n} 1/m_j)^i \le h(n)^i$, so $T \lt \sum_{s \lt i \le n} ((\sum_{1 \le j \le n} 1/m_j)^i)/(i!)$,

so $T \lt \sum_{s \lt i } (h(n)^i)/(i!) \le e^{h(n)}(h(n)^{s+1})/((s+1)!)$.

Stevens chose $\log(n) > \sum_{1 \le j \le n} 1/p_j \ge \sum_{1 \le j \le n} 1/m_j$ for $n > 2$ to use as $h(n)$. I choose $\alpha_n + \log(\log(p_n))$ for $h(n)$, and will talk about the positive constant $\alpha_n < 1$ and the allowed values of $n$ later. (Thinking of $\alpha_n = 0.75$ is good.) Now let's get to $T'$.

If we replace $(s+1)!$ with the smaller $((s+1)/e)^{s+1}$ and choose $s$ so that $s+1 \gt 2eh(n)$, then $T' = e^{h(n)}2^{-s-1} \gt e^{h(n)}(h(n)^{s+1})/((s+1)!) \gt T$.

Also $P = \prod_{1 \le i \le n}(1 - 1/m_i) \gt \prod_{1 \le i \le n}(1 - 1/p_i) \gt 1/(\beta_n\log(p_n))$, so let $P' = 1/(\beta_n\log(p_n))$. Again the valid range of $n$ depends on the choice of $\beta_n$. For now choose them (say, $\beta_n = 3$) so that $P > P'$. (Stevens chose $1/n$ for $P'$.) Then $P- T \gt P' -T'$, and $SB' > SB$. We just need to find odd $s > 2eh(n) -1$ and ensure that $P' > T'$, and then combine everything. Stevens's form is similar to what is below; I will use my versions of $P'$ and $T'$. Writing $z$ for $\log(p_n)$,

$P' - T' = 1/(\beta_n z) - e^{\alpha_n}z(1/2)^{2e(\alpha_n + \log(z))}$.

Now $(1/2)^{2e\log(z)} = z^{-2e\log(2)}$. So

$P' -T' = (\beta_n z)^{-1} - (e/2^{2e})^{\alpha_n} z^{-2e\log(2) + 1} = (\beta_n z)^{-1} - ((e^{\alpha_n})z)^{-2e\log(2) + 1}$

$ = z^{-1} ( (\beta_n)^{-1} - (e^{\alpha_n})^{-2e\log(2) + 1} z^{-2e\log(2) + 2} ) $

Since we will have $n$ large enough so that $\beta_n \lt (e^{\alpha_n})^{2e\log(2) - 1}$, and since $z^{2e\log(2) - 2}\gt 1$, we get that $P' - T' > 0$ .

Now to put it all together. If $s$ is odd and $s+1 \gt 2e(\alpha_n + \log(\log(p_n)))$ then

$ \binom{n+1}{s} ( 1 +(s(s-1))/((n+2)(n+3 -2s)) ) (z/[(\beta_n)^{-1} - (e^\alpha_n)^{-2e\log(2) + 1} z^{-2e\log(2) + 2}]) \gt SB/(P-T)$ and this gives a value for $l$ which in turn gives $L > 0$. Since for the improvement I assume $n > 30,$ the fudge factor is at most 18/11, and when $\beta_n=3$ and $\alpha_n = 0.75$, the denominator of the last fraction goes from some value above 1/5 to 1/3 as $n$ increases. So the whole expression is bounded by $9 \binom{n+1}{s} z$, or $9 \binom{n+1}{s} \log{p_n}$. Since $\log(\log(p_n)) $ is increasing, the whole ball of wax is bounded by $n^{2e(\log\log(p_n) + \alpha_n) +1}\log(p_n)$.

Now as to the choice of $\alpha_n$ and $\beta_n$. They were chosen generously: Mertens showed that $\sum_{1 \le i \le n} 1/p_i \lt \log\log(p_n) + B + \delta$, where $B$ is a constant close to 0.26 and $\delta$ is an error bounded in size by a sum of two terms, the largest of which is $4/\log(p_n +1)$. So using Merten's estimate, $p_n + 1$ should be bigger than (some number not much larger than) $e^8$. Similarly, Mertens has an estimate on $\prod_{1 \le i \le n} (1 - 1/p_i)$, which is $e^{-(\gamma + \delta)}/\log(p_n)$, where $e^{-\gamma}$ is close to 1/1.78 and $\delta$ is bounded by a sum of three terms, the largest of which is again $4/\log(p_n+1)$, again requiring that $p_n + 1$ be bigger than (something close to) $e^8$. However, computations seem to show that the constants chosen seem to allow the rquired estimates to hold for $n \gt 30$ and some $n$ smaller than 30. The major block is on $n \gt 2s \gt 2eh(n) - 1$.

I welcome any constructive input and error checking. I will revise this in the coming weeks.

Gerhard "Almost Ready To Shelve This" Paseman, 2011.02.25

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

After studying Kanold's 1967 paper on Jacobsthal's function, (and being inspired by a preprint http://arxiv.org/abs/1208.5342 that I discuss below,) I found an argument, mostly very simple, which gives some nice results for the effort given.  While Kanold deserves some of the credit for the argument, I have yet to see a statement by him or by anyone else that gives these results, so I present them here.  (Kanold wrote several articles on Jacobsthal's function, many of which I am tracking down, which might have this argument.  I am happy to accept help in obtaining electronic copies of them.)  This is the post I promised over a few months ago in a supplement to a question of Timothy Foo, Analogues of Jacobsthal's function  .

For maximum ooh-aah effect, I assume $n$ is squarefree and has $k \gt 2$ prime factors, one of which I call Peter, or $p$ for short.Now $1+tn$ is coprime to $n$ for any integer $t$.  So are most integers of the form $1 + tn/p$, the exceptions being those that are multiples of $p$, and those multiples do not occur as consecutive terms.  Thus, every interval of length $2n/p (=g(p)n/p)$ has at least one integer coprime to $n$ of the form $1+tn/p$.

Let's go further with this.  Let $d \gt 1$ and divide $n$, and let $f=n/d$.  (Here I use $n$ squarefree to get $f$ coprime to $d$.)  Then numbers of the shape $1+tf$ form an arithmetic progression, are coprime to $f$, and (as can be seen by multiplying by $f$'s inverse in the ring of integers mod $d$) you can't pick $g(d)$ consecutive members of this progression without hitting something coprime to $d$ also.  So $g(n) \leq g(d)f = g(d)n/d$ .

While I'm here, let me sharpen the inequality, assuming $f \gt 1$ and $d \gt 1$ are coprime: there are $\phi(f)$ totients $c$ of $f$ in the interval $[0,f]$, so I can repeat the argument with $c+tf$ instead of $1+tf$.  In the worst case, using all $\phi(f)$ progressions, I get $g(fd) \leq g(d)f - f + g(f)$, which mildly improves upon Kanold's bound $g(d)f -\phi(f)+1$, and matches it when $f$ is prime.  (Of course, for $n=fd$ I really want $g(n)$ to be near $O(g(d)+g(f))$, but I don't yet know how to show that with grade school arithmetic.)

How to use this inequality? Pick the largest divisor $d$ for which one can comfortably compute (a subquadratic in $k$ upper bound for) $g(d)$; I pick $d$ to contain most of the large prime factors of $n$: find prime $q$ dividing $n$ so that $\sigma^{-1}(d)=\sum_{p \text{ prime,} p|n, p \geq q} 1/p$ is less than $1 + 1/2q$; a routine argument yields $g(d)$ is $O(qk)$.  The ugly part is to show that $q \lt k^{0.5}$ (or else $d=n$), that $n/d \lt 2^{3q/2}$ which for large $k$ approaches $2^{3(k^{\epsilon + 1/e})/2}$, and that asymptotically $g(n)$ is $O(e^{k^{1/e}+D\log(k)})$.  This isn't hard after using one of Mertens's theorems and a Chebyshev function; it just isn't pretty.  (Also for smaller $n$, $\epsilon + 1/e$ can be close to $1/2$, but with patience $\epsilon$ will tend to zero.)

This gives a bound that is asymptotically better than my first efforts at this, improves slightly ($k^{0.5}$ replaced by $Ck^{0.37}+ D\log(k)$ on Kanold's bound of $2^\sqrt{k}$ for $k$ not too large, and does not need Kanold's requirement that $k > e^{50}$.  Up until one chooses $d$ and crunches the formulae, it is also a very elementary argument; I suspect even Legendre knew about using the multiplicative inverse to transform a general arithmetic progression to a (effectively) consecutive sequence of integers and still preserve the property of interest here, being a unit in a certain ring (or missing it by that much). 

(One of the benefits of letting this sit for a few months before posting is that I can add cool observations like: If I could get the inequality down to $g(n) \leq g(d)g(n/d)$, I could iterate the above simple estimate to get an explicit bound of $O(k^c)$, where $c$ is a positive number less than 3.  Or like: using more advanced work combined with the above, I can get $g(n) \leq e^{k^{e^{-a}}}Ck^{a}$ for some integers $a$, which seems better than $Ck^{4\log\log{k}}$ if you don't look too closely.)

Further, one can use a computer to refine the method slightly and get estimates which do quite well for small values of $n$, where small here means $k<100$.  Asymptotically though, Stevens's and my upper bounds eventually outperform this bound.

Also, there has been a nice result out of University College Dublin that I will briefly interpret.  Fintan Costello and Paul Watts find a way of presenting a related function recursively, then numerically compute a lower bound on this function which implies an upper bound on Jacobsthal's function computed on some particular values.  I thank them for reminding me about using a multiplicative inverse mod $d$ for $f$, so they deserve a "piece of the action".

These authors work in (and sometimes away from) the integer interval $BM = [b+1,b+2,\ldots,b+m]$.  Given squarefree $n$ and its distinct prime factors, listed in some order as $q_1$ to $q_k$, define $Q_i$ as  $\prod_{0 \lt j \leq i} q_j$. One approach to computing the size $\pi(b,m,n)$ of the set $CP(b,m,n)$ which has those integers in $BM$ coprime to $n$ is to do the standard inclusion-exclusion argument: if we represent by $F(b,m,d)$ the multiples of $d$ in $BM$, and say there are $f(b,m,d)$ many such multiples, and abuse some notation, I then write $CP(b,m,n) = \sum_{d | n} sgn(d,F(b,m,d))$ .  Here $sgn$ is to suggest adding elements of the set $F(b,m,d)$ if $d$ has an even number of prime factors, and subtracting them instead when $d$ has an odd number of prime factors.

To set up for the recurrent expression, Costello and Watts use just some of the terms on the right hand side of the abused equation, and reorganize the rest of the terms.  In my interpretation of their work, they start with the multiset identity

$$CP(b,m,n) \cup \biguplus_{0 \lt i \leq k} F(b,m,q_i) = BM \uplus  \biguplus_{0 \lt i \lt j \leq k} RCP(i,j)$$

where $RCP(i,j)$ is $F(b,m,q_iq_j) \cap CP(b,m,Q_{i-1})$, or the subset of $BM$ which has those multiples of $q_iq_j$ whose soonest prime factor in common with $n$ is $q_i$. 

One sees this identity holds by considering a member of $BM$ which has exactly $t$ distinct prime factors in common with $n$. If $t$ is $0$, then the member occurs only once in $CP(b,m,n)$ and similarly only once in $BM$.  Otherwise, it occurs exactly $t$ times in the left hand side in $t$ distinct terms $F(b,m,q_i)$, and if $l$ is soonest such that $q_l$ is a prime factor of the member, the member occurs only once in each of $t-1$ sets $RCP(l,j)$ (remember $l$ comes sooner than $j$) and only once in $BM$.

Now the term $RCP(i,j)$ is a subset of an arithmetic progression $A$ with common difference $q_iq_j$. By using the technique above of multiplying by a suitable inverse of $q_iq_j$ in the ring of integers mod $Q_{i-1}$, $A$ corresponds with an integer interval starting near some integer $c_{ijbm}$ of length $f(b,m,q_iq_j)$ which preserves the coprimality status with respect to $Q_{i-1}$: to wit, the size of $RCP(i,j)$ is $\pi(c_{ijbm},f(b,m,q_iq_j),Q_{i-1})$.  Using the $\pi$ term for the size of $CP$ and translating the other sets to numbers gives the numerical recurrent formula of Costello and Watts: $$\pi(b,m,n) = m - \sum_{0 \lt i \leq k} f(b,m,q_i) + \sum_{0 \lt i \lt j \leq k} \pi(c_{ijbm},f(b,m,q_iq_j),Q_{i-1})$$.

Following work of Hagedorn who computed $h(k)=g(P_k)$ for $k$ less than 50, where $P_k$ is the $k$th primorial, Costello and Watts use their formula and some analysis of coincidence of prime residues to compute an inequality for $\pi_{min}(m,n)$ which is the minimum over all integers $b$ of $\pi(b,m,n)$.  They underestimate $f(b,m,q_iq_j)$ by $\lfloor m/q_iq_j \rfloor$, ignore the $c$'s by using $\pi_min$, pull out the $i=1$ terms from the double sum and rewrite that portion to include a term $E$, depending only on $m$ and the $p_i$, which arises from looking at when estimates for the sizes of the $F(b,m,p_i)$  and $F(b,m,2p_i)$ sets can be improved, and come up with (a refined version, using $p$'s for $q$'s, of) the inequality $$m - \sum_{0 \lt i \leq k}  \lceil \frac{m}{p_i} \rceil + \sum_{1 \lt i \leq k} \lfloor \frac{m}{2p_i} \rfloor + E + \sum_{1 \lt i \lt j \leq k} \pi_{min}(\lfloor \frac{m}{p_ip_j} \rfloor,P_{i-1}) \leq \pi_{min}(m,P_k)$$.

With this inequality, Costello and Watts compute $\pi_{low}$, a lower bound approximation to $\pi_{min}$.  Since $h(k) \leq m$ iff $\pi_{min}(m,P_k) \gt 0$, computing $\pi_{low}(m,P_k)$ for various $m$ will give an upper bound on $h(k)$.  They say their computations for $k \leq 10000$ suggest $h(k) \leq Ck^2 \log k$, where $C$ is a constant less than $0.3$ .  Although this data is achieved using data from Hagedorn's work, even without that their algorithm yields values which are a vast improvement on known and easily computable bounds, even the ones listed above.

One item to explore is how an algorithm based on this approximation will perform given different orderings of the prime factors.  I suspect that letting the larger primes come first will give tighter results.  Another item to explore is to see if there is a better term $F$ that will supplant $E$ and some of the recurrent terms in the double sum.  The idea of rewriting the $\pi$ function recursively, while not new, is given new life in this double sum form, and suggests revisiting some old approaches with an eye toward computability.

Gerhard "Ask Me About Coprime Integers" Paseman, 2013.02.05