show/hide this revision's text 4 Improved accuracy, added latex.

In a paper of Erik Westzynthius,

Uber

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. $1$. Step 3 will rewrite the RHS and estimate it pessimistically: $E(t) * (-1)^{\mu(t)}$ will be replaced by -1, $-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 $Q$ is an abbreviation for 1 $1$ divided by the product of the n terms $(1 - 1/p_i)$. It is roughly log(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 < 11$, as opposed to discovering how to do it.

Gerhard "Ask Me About System Design" Paseman, 2010.09.03
show/hide this revision's text 3 wrote out "Westzynthius"; moved reference to the top; edited title

Erik W.'s Westzynthius's cool upper bound argument: update?

In a paper of Erik Westzynthius,

Uber 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 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. 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 >= [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(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.

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

Gerhard "Ask Me About System Design" Paseman, 2010.09.03
show/hide this revision's text 2 no preview, so one more latex fixing pass

Erik W'.s W.'s cool upper bound argument: update?

In a paper of Westzynthius, 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 $a$ and x $x$ be real parameters, with $x > 0 0$ . Consider the integers in the open interval $(a, a+x)$, and call this set I. $H$. Let us look at the subsets of I $H$ consisting of those integers which are a multiple of the integer t; $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 $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. For such a number $t \in RR$, $\mu(t)$ is precisely the number of prime factors in t, $t$, and $\mu$ is chosen to suggest the Moebius function whose value at such t $t$ is $(-1)^\mu(t)$. (-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) -1)^{\mu(t)} ]$ .

Since the number of multiples of t $t$ in the interval $(a, a + x)$ is roughly x/t, $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)$ -1)^{\mu(t)}$ will be replaced by -1, and the alternating sum of x/t $x/t$ terms can be rewritten as a product involving terms of the form $(1 - 1/p_i)$, where $p_i$ is the ith $i$th prime. There are $2^n$ terms of the form $E(t)$, so one gets:

$I_0 >= [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(log(n)) for large n. Here comes the kicker. Step 4 notes that steps 1 through 3 are essentially independent of a, $a$, and if x $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 > 00$, and such x $x$ would be an upper bound for $q_(i+1) q_{i+1} - q_i$ which is independent of i. $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+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)$ 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 $g$ is something like a polynomial in log(n), but even having g $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.

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

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