Three Theorems on Modular Sieves that suggest the Prime Difference is

_{}

Bhupinder Singh Anand[1]

Although
this 1964 paper is not, strictly, a foundational paper, it developed as an off-shoot to the foundational query: Do we discover the natural
numbers (Platonically), or do we construct them linguistically? The paper also
assumes computational significance in the light of Agrawal,
Kayal and Saxena's August
2002 paper, “PRIMES is in P”, since both the Trim and Compact Number Generating
algorithms - each of which generates all the primes - **
are deterministic algorithms that run in
polynomial time, and suggest that the Prime Difference,** *d*_{P}(*n*), is _{}

Contents

1. A Prime Number Generating Theorem

2.3 Is the Theorem significant?

3.1 Two Compact Number Theorems …

3.2 … and two more conjectures

1: A PRIME NUMBER
GENERATING THEOREM (1964)

We address the question:

Do we necessarily discover
the primes, as in the sieve of Eratosthenes, or can we also generate them
sequentially?

In other words, given the
first *k* primes, can we
generate the prime *p*(*k*+1) algorithmically, without testing any number larger
than *p*(*k*) for primality?

We give an affirmative
answer, defining two algorithms based on the following theorem (where *i*, *j*, *k*, …
represent natural numbers):

**Theorem 1.1**: For any given natural number *k*, and all *i* < *k*,
let *p*(*i*) denote the *i*'th
prime, and define the sequence {*a*_{P}(*i*): *i* = 1 to *k*} such that *a*_{P}(*i*) < *p*(*i*), and:

*p*(*k*)
+ *a*_{P}(*i*) ≡ 0 (mod *p*(*i*))

Let *d*_{P}(*k*)
be such that, for all *l*
< *d*_{P}(*k*), there is some *i* such that:

*l* ≡ *a*_{P}(*i*) (mod *p*(*i*)).

Then *d*_{P}(*k*)
is the Prime Difference, defined by:

*p*(*k*+1)
- *p*(*k*) = *d*_{P}(*k*).

**Proof**: For all *l*
< *d*_{P}(*k*), there is some *i* such that:

*p*(*k*)
+ *l* ≡ 0 (mod *p*(*i*)).

Since, by Bertrand’s Postulate ([HW60], p343), *p*(*k*+1) < 2*p*(*k*) for all natural numbers *k*, it follows that:

*d*_{P}(*k*)
< *p*(*k*)

Hence, *p*(*k*)
+ *d*_{P}(*k*) < *p*(*k*)^{2}, and so it is the prime *p*(*k*+1)□

The significance of the Prime
Number Generating Theorem is seen in the following algorithm.

We define Trim numbers
recursively by *t*(1)
= 2, and *t*(*n*+1) = *t*(*n*) + *d*_{T}(*n*), where *p*(*i*) is the*
i'th* prime and:

(*i*) *d*_{T}(1)
= 1, and *a*_{T}(2, 1) = 1:

(*ii*) *d*_{T}(*n*)
is the smallest even integer that does not occur in the *n*'th sequence:

{* a _{T}*(

(*iii*) *j _{i}* ≥ 0 is selected so that, for all 0 <

0 ≤ *a*_{T}(*n*+1,
*i*) = {(* a _{T}*(

It follows that the Trim number *t*(*n*+1) is, thus, a prime unless
all its prime divisors are less than *d*_{T}(*n*).

(In [An64] I illustrate how Trim numbers are generated sequentially as a 2-dimensional modular sieve.)

2.1: A TRIM NUMBER THEOREM
… (1964)

**Theorem 2.1: **For all *n*
> 1, *t*(*n*) < *n*^{2}.

**Proof: ***t*(*n*)
= {*t*(*n*-1) + *d*_{T}(*n*-1)}

*d*_{T}(*n*-1) < 2(*n*-1)

*t*(*n*)
< {*t*(*n*-1) + 2(*n*-1)}

*t*(*n*)
< [{*t*(*n*-2) + 2(*n*-2)}
+ 2(*n*-1)]

*t*(*n*)
< {2 + 2(*n*-1)
+ 2(*n*-2) + … + 2(1)}

*t*(*n*)
< [2 + 2{(*n*-1)**n*/2}]

*t*(*n*)
< (*n*^{2} - *n*
+ 2)

Hence,
for all *n* > 1, *t*(*n*) < *n*^{2}□

2.2: ... AND TWO CONJECTURES
(1964)

**Conjecture 1.1: **For all *k*,
*t*(*k*) ≤ *p*(*n*) ≤ *t*(*k*+1) for some *n*.

**Conjecture 1.2: **If *p*(*n*+1)
= {*p*(*n*) + *d*_{P}(*n*)}, then *d*_{P}(*n*) = O(*n*).

2.3: IS THE THEOREM
SIGNIFICANT? (2005)

The significance of the above
theorem lies in the following observation [Ca05]:

“Is there always a prime
between *n*^{2} and (*n*+1)^{2}?
In 1882 Opperman stated π(*n*^{2}+*n*) > π(*n*^{2}) >
π(*n*^{2}-*n*),
(*n*>1), which also
seems very likely, but remains unproven ([Ri95], p248).

Both of these conjectures
would follow if we could prove the conjecture that the prime gap following a
prime *p* is bounded by a
constant times (log *p*)^{2}.”

Compact numbers are defined
recursively by *c*(1)
= 2, and *c*(*n*+1) = *c*(*n*) + *d*_{C}(*n*),

where *p*(*i*) is the *i*'th prime and:

(*i*) *d*_{C}(1)
= 1, and *a*_{C}(2, 1) = 1;

(*ii*) *d*_{C}(*n*)
is the smallest even integer that does not occur in the *n*’th sequence:

{*a*_{C}(*n*, 1), …, *a*_{C}(*n*, *k*)};

(*iii*) *j _{i}* ≥ 0 is selected so that, for all 0 <

0
≤ *a*_{C}(*n*+1,
*i*) = {* a _{C}*(

(*iv*) *k* is selected so that:

*p*(*k*)^{2}
< *c*(*n*) ≤ *p*(*k*+1)^{2};

(*v*) if *c*(*n*) = *p*(*k*+1)^{2}, then:

*a*_{C}(*n*, *k*+1)
= 0.

It follows that the compact
number *c*(*n*+1) is either a prime, or a prime square, unless all,
except a maximum of 1, prime divisors of the number are less than *d*_{C}(*n*).

(In [An64] I illustrate how Compact numbers are generated sequentially as a significantly more compact, 2-dimensional, modular sieve.)

3.1: TWO COMPACT
NUMBER THEOREMS … (1964)

**Theorem 3.1: **There is always a compact number *c*(*m*) such that *n*^{2} < *c*(*m*) ≤ (*n*+1)^{2}.

**Proof: **If *p*(*k*)
≤ *n* < *p*(*k*+1), then (*n*+1) ≤ *p*(*k*+1).

Now
{(*n*+1)^{2} – *n*^{2}} = {2*n* + 1} > 2*p*(*k*)
> 2*k*.

Hence (*n*+1)^{2}
> {*n*^{2} + 2*k*}.

Since
there is always a compact number in any interval larger than 2*k* between *p*(*k*)^{2}
and *p*(*k*+1)^{2}, the theorem follows□

**Theorem 3.2: **For sufficiently large *n*, *d*_{C}(*n*)
< constant*{*c*(*n*)/log *c*(*n*)}^{1/2}

**Proof: **By definition, *d*_{C}(*n*)
≤ 2*k*, where *p*(*k*)^{2} < *c*(*n*) ≤ *p*(*k*+1)^{2}.

The
theorem follows from the Prime Number Theorem, since *k* is the number of primes less than *c*(*n*)^{1/2}□

3.2: ... AND TWO MORE CONJECTURES (1964)

**Conjecture 3.1: **If *p*(*k*)^{2}
< *p*(*n*) < *p*(*k*+1)^{2}, then:

{*p*(*n*+1) - *p*(*n*)} = O(k)

= O(** _{}**).

**Conjecture 3.2:**

_{}{Number of primes < *n*}/{Number of compacts < *n*} = 1/2.

References

[An64] Anand,
B. S. 1964. *Two Series containing the Primes and a Conjecture concerning the
Prime Difference * Transcribed notes.

<http://alixcomsi.com/Prime_number_generator.htm>

[Ca05] Caldwell,
Chris. K. 2005. *Prime
Conjectures and Open Questions*. Web resource.

<http://www.utm.edu/research/primes/notes/conjectures/>

[HW60] Hardy, G. H. and Wright, E.
M. 1960. *An Introduction to the Theory of Numbers*.
4^{th} edition. Clarendon Press,

[Ri95] Ribenboim, P.
1995.* The new book of prime number records.* 3^{rd} edition,

(*Transcribed
from original notes: Thursday 8 ^{th} December 2005 2:17:06 AM IST by
re@alixcomsi.com. Updated:
Saturday June 09, 2007 08:14:21 PM IST by
re@alixcomsi.com*)

[1]
The author is an independent scholar. E-mail: re@alixcomsi.com;
anandb@vsnl.com. Postal address: 32, Agarwal House,