# Erik Westzynthius's cool upper bound argument: update?

Version 2 of this writeup is available, and includes a newer and simple upper bound thanks to MathOverflow 88777 as well as indirect references to future writeups. Details of further work will be found in these writeups. GRP 2014.06.04.

In a paper of Erik Westzynthius,

Ueber die Verteilung der Zahlen, die zu den n ersten Primzahlen teilerfremd sind, Comm. Phys. Math. Soc. Sci. Fenn., Helsingfors (5) 25 (1931), 1-37

I saw the following upper bound argument. Having never studied sieve theory, I was quite impressed by it. The goal is to bound from above the quantity max $(q_{i+1} - q_i)$, where the $q_i$ are the positive integers in increasing order which are relatively prime to $P_n$, the product of the first n primes. Here is a sketch of the argument.

Let $a$ and $x$ be real parameters, with $x > 0$ . Consider the integers in the open interval $(a, a+x)$, and call this set $H$. Let us look at the subsets of $H$ consisting of those integers which are a multiple of the positive integer $t$; call the size of each such subset $I_t$. Step 1 is to use inclusion-exclusion to estimate $I_0$, the number of integers in the interval $(a, a+x)$ which are relatively prime to $P_n$. (I.e. count integers, throw out multiples of 2, throw out multiples of 3, add in multiples of (2*3) to compensate, etc.) We get

$I_0 = \sum_{t \in R} [I_t * (-1)^{\mu(t)}]$.

Here $R$ is the set of positive integers which are of the form (warning: sloppy notation) $\prod_{J \subset n} p_j$, that is all integers whose prime factorizations have only primes less than or equal to the nth prime, and those occuring only to at most the first power. (More succinctly, $R$ is also the set of positive divisors of $P_n$.) For such a number $t \in R$, $\mu(t)$ is precisely the number of prime factors in $t$, and $\mu$ is chosen to suggest the Moebius function whose value at such $t$ is $(-1)^{\mu(t)}$. The equality is exact.

Step 2 is to replace $I_t$ with a linearized approximation plus an error term which I will call $E(t)$. This substitution gives:

$I_0 = \sum_{t \in R} [ (E(t) + x/t) * (-1)^{\mu(t)} ]$ .

Since the number of multiples of $t$ in the interval $(a, a + x)$ is roughly $x/t$, the error term $E(t)$ is bounded in absolute value by $1$. Step 3 will rewrite the RHS and estimate it pessimistically: $E(t) * (-1)^{\mu(t)}$ will be replaced by $-1$, and the alternating sum of $x/t$ terms can be rewritten as a product involving terms of the form $(1 - 1/p_i)$, where $p_i$ is the $i$th prime. There are $2^n$ terms of the form $E(t)$, so one gets:

$I_0 \geq [x * \prod_{1 <= i <= n} (1 - 1/p_i) ] - 2^n = x/Q - 2^n$ .

Here $Q$ is an abbreviation for $1$ divided by the product of the n terms $(1 - 1/p_i)$. It is roughly log n for large n. Here comes the kicker. Step 4 notes that steps 1 through 3 are essentially independent of $a$, and if $x$ can be chosen so that $x/Q - 2^n > 0$, then $I_0 > 0$ which means at least one of the $q_i$ is in the interval $(a, a+x)$ when $a > 0$, and such $x$ would be an upper bound for $q_{i+1} - q_i$ which is independent of $i$. So choose $x = Q * 2^n$ plus epsilon.

I thought it a neat enough argument (especially the kicker) that I am sharing it here with other non-students of sieve theory. Now to the questions.

1) Is there any work done which improves the upper bound for $q_{i+1} - q_i$? The answer to this is yes, since in a footnote Westzynthius shows how to improve the bound to $Q * 2^{n-1}$ by counting odd multiples. So I really want to know if there are even better bounds out there, done by additional researchers. I would expect a provable bound to be $Q * 2^g$, where $g$ is something like a polynomial in log(n), but even having $g$ be n to a fractional power would be something.

2) Is there work done which uses something like the Bonferroni inequalities to improve the above argument?

3) Did Westzynthius publish any other work (possibly nonmathematical) besides the paper that includes the argument above?

Motivation: I am considering improvements to this argument which do establish better upper bounds, and am wondering how to push the exponent from n - o(1) down to poly(log(n)). Especially, I want to know if I am rediscovering how to replace n by cn for some $c < 1$, as opposed to discovering how to do it.

• So $$Q = \frac{P_n}{\phi(P_n)} \; ?$$ – Will Jagy Sep 4 '10 at 3:49
• Using Euler's totient $\phi()$, yes. I had discovered a worse upper bound before I saw this argument. Gerhard "Ask Me About System Design" Paseman, 2010.09.03 – Gerhard Paseman Sep 4 '10 at 4:48
• books.google.com/… Not about the specific article yet; it is thought (Shanks, 1964) that $p_{n+1}$ is sometimes as large as $$p_n + C \log^2 p_n,$$ and $$\limsup \frac{p_{n+1} - p_n}{\log^2 (p_n)} \; \; \neq 0$$ where we can probably take $C=1$ for $p > 20.$ See Richard K. Guy, Unsolved Problems in Number Theory, section A.8. – Will Jagy Sep 4 '10 at 18:54
• I see, Harald Cramer gave the version I mention, Shanks and Granville gave different guesses for the lim sup, lately Granville's value $$2 e^{- \gamma} \approx 1.1229$$ is looking better, see wikipedia on Cramer's conjecture, attempting link en.wikipedia.org/wiki/Cram%C3%A9r's_conjecture and ams.org/journals/mcom/1999-68-227/S0025-5718-99-01065-0/… – Will Jagy Sep 4 '10 at 19:49
• Indeed, Westzynthius was the first to show a good lower bound for lim sup of (nth prime gap)/log(nth prime), namely infinity. I hope to address that part of the paper in another question; right now I think the upper bound can stand improvement, although I don't think I will come up with something as cool to get there. Gerhard "Get Thee Back Into Fashion" Paseman, 2010.09.04 – Gerhard Paseman Sep 4 '10 at 20:30

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.

• Thank you Zeb. I will follow up this line. Meanwhile, Aaron Meyerowitz led me to an OEIS sequence which in turn led me to Jacobsthal's function and a recent paper by Hagedorn which seems to refute your 2p_n conjecture before n reaches 25. Today I just got a 1977 paper of Harlan Stevens which seems to confirm my conjecture, that the max is 2^g where g is close to (mixing log bases here for brevity and inaccuracy) 2e(log(n))^2+2log(n) + 1. This seems to answer my question, but I think I can tweak the argument to get an improvement. Gerhard "Ask Me About System Design" Paseman, 2011.01.22 – Gerhard Paseman Jan 23 '11 at 7:48
• hmm, you're right. Doing a google search on Jacobsthal's function turns up the paper by Hagedorn, which not only refutes my conjecture (the strong law of small numbers strikes again), but also gives a reference to an upper bound of $O(n^2\log(n)^2)$ due to Iwaniec, which is surprisingly close to your predicted $n^2$. – zeb Jan 23 '11 at 10:32

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

• In the book "Rational Number Theory in the 20th Century" by W. Narkiewicz, there is a reference to Westzynthius as being an actuary who lived until 1980. Gerhard "Ask Me About System Design" Paseman, 2012.11.24 – Gerhard Paseman Nov 25 '12 at 0:09

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.

• If you can prove that the maximum gap in this sequence is $o(p_n^2)$, I'd say it's just a small step from that to proving the Goldbach Conjecture along with the Twin Primes Conjecture. I say this because you can define similar sets $S_2(n)$ given by deleting two congruence classes mod the first $n$ primes. I feel like any argument along the lines you sketched that gives a bound for gaps in $S(n)$ should give a similar bound for gaps in $S_2(n)$, and if the gaps are small enough we can show there is an element of $S_2(n)$ smaller than $p_n^2$, giving us primes with desired sum/difference. – zeb Dec 15 '10 at 9:57
• Indeed. One of my early conjectures was that there was a twin prime pair between ${p_n}^2$ and ${p_{n+1}}^2$. Also, I do not see what your $S_2$ is like. I can develop one from any $S(n)$, for example from $S(3)$ I get 10 2 4 2 10 2 ..., but I do not see how to derive the one from $S(4)$ without using all of $S(4)$. How do you build your $S_2$, may I ask? Gerhard "Ask Me About System Design" Paseman, 2010.12.15 – Gerhard Paseman Dec 15 '10 at 20:49
• I'm not sure how you are developing things from $S(n)$... My $S_2(n)$ has a suppressed choice of congruence class pairs for each prime,so there are really many different $S_2$s. For the Twin Primes conjecture, we delete the congruence classes of $0$ and $-2$ mod each prime up to $p_n$. For the Goldbach conjecture, to find two primes summing to $n$, we delete the congruence classes of $0$ and $n$ mod each prime up to $\sqrt{n}$. – zeb Dec 16 '10 at 22:14
• Worst case example: try deleting the congruence classes 1 and 2 mod 3, 1 and 2 mod 5, 2 and 3 mod 7, and 4 and 7 mod 11. Then you get a run of 32 consecutive deleted numbers, and you can't do better with only odd primes up to 11. The farthest I could calculate was the worst case for odd primes up to 23, which has a run of length 182. We get it by deleting 1,2 mod 3, 1,2 mod 5, 3,6 mod 7, 1,6 mod 11, 2,3 mod 13, 12,16 mod 17, 9,18 mod 19, 7,14 mod 23. – zeb Dec 16 '10 at 22:49
• Zeb, I appreciate your input on this. Will Jagy has an email address for me. Send your email address to him and he will forward it to me, if you wish to correspond further by email. Gerhard "Ask Me About System Design" Paseman, 2010.12.17 – Gerhard Paseman Dec 17 '10 at 8:51

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

\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.

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

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.

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

• I am both embarrassed and proud to say that I have another argument which supercedes this one. After it has been vetted, I will post the new estimate and some details of proof. Gerhard "Ask Me About System Design" Paseman, 2011.02.28 – Gerhard Paseman Mar 1 '11 at 7:48