This argument laid the foundation for this investigation. See also this arXiv preprint, and this broader update.

Abstract We define the residues r_{i}(n) for all n \geq 2 and all i \geq 2 such that r_{i}(n) = 0 if, and only if, i is a divisor of n. We then show that the joint probability \mathbb{P}(p_{i} | n\ \cap\ p_{j} | n) of two unequal primes p_{i},\ p_{j} dividing any integer n is the product \mathbb{P}(p_{i} | n).\mathbb{P}(p_{j} | n). We conclude that the prime divisors of any integer n are independent; and that the probability \mathbb{P}(n \in \{p\}) of n being a prime p is \prod_{i = 1}^{\sqrt{n}}(1 - 1/p_{i}) \sim 2e^{-\gamma}/log_{e}\ n. The number of primes less than or equal to n is thus given by \pi(n) \approx \sum_{j = 1}^{n}\prod_{i = 1}^{\pi(\sqrt{j})}(1 - 1/p_{i}). We further show that ((\pi(x).log_{e}\ x)/x)' = o(1/x), and conclude that (\pi(x).log_{e}\ x)/x does not oscillate.

\S 1 The residues r_{i}(n)

We begin by defining the residues r_{i}(n) for all n \geq 2 and all i \geq 2 as below:

Definition 1: n + r_{i}(n) \equiv 0\ (mod\ i) where i > r_{i}(n) \geq 0.

Since each residue r_{i}(n) cycles over the i values (i-1, i-2, \ldots, 0), these values are all incongruent and form a complete system of residues [1] mod\ i.

It immediately follows that:

Lemma 1: r_{i}(n) = 0 if, and only if, i is a divisor of n.

\S 2 The probability \mathbb{P}(e)

By the standard definition of the probability \mathbb{P}(e) of an event e, we conclude that:

Lemma 2: For any n \geq 2,\ i \geq 2 and any given integer i > u \geq 0, the probability \mathbb{P}(r_{i}(n) = u) that r_{i}(n) = u is 1/i, and the probability \mathbb{P}(r_{i}(n) \neq u) that r_{i}(n) \neq u is 1 - 1/i.

We note the standard definition:

Definition 2: Two events e_{i} and e_{j} are mutually independent for i \neq j if, and only if, \mathbb{P}(e_{i}\ \cap\ e_{j}) = \mathbb{P}(e_{i}).\mathbb{P}(e_{j}).

\S 3 The prime divisors of any integer n are mutually independent

We then have that:

Lemma 3: If p_{i} and p_{j} are two primes where i \neq j then, for any n \geq 2, we have:

\mathbb{P}((r_{p_{_{i}}}(n) = u) \cap (r_{p_{_{j}}}(n) = v)) = \mathbb{P}(r_{p_{_{i}}}(n) = u).\mathbb{P}(r_{p_{_{j}}}(n) = v)

where p_{i} > u \geq 0 and p_{j} > v \geq 0.

Proof: The p_{i}.p_{j} numbers v.p_{i} + u.p_{j}, where p_{i} > u \geq 0 and p_{j} > v \geq 0, are all incongruent and form a complete system of residues [2] mod\ (p_{i}.p_{j}). Hence:

\mathbb{P}((r_{p_{_{i}}}(n) = u) \cap (r_{p_{_{j}}}(n) = v)) = 1/p_{i}.p_{j}.

By Lemma 2:

\mathbb{P}(r_{p_{_{i}}}(n) = u).\mathbb{P}(r_{p_{_{j}}}(n) = v) = (1/p_{i})(1/p_{j}).

The lemma follows. \Box

If u = 0 and v = 0 in Lemma 3, so that both p_{i} and p_{j} are prime divisors of n, we conclude by Definition 2 that:

Corollary 1: \mathbb{P}((r_{p_{_{i}}}(n) = 0) \cap (r_{p_{_{j}}}(n) = 0)) = \mathbb{P}(r_{p_{_{i}}}(n) = 0).\mathbb{P}(r_{p_{_{j}}}(n) = 0).

Corollary 2: \mathbb{P}(p_{i} | n\ \cap\ p_{j} | n) = \mathbb{P}(p_{i} | n).\mathbb{P}(p_{j} | n).

Theorem 1: The prime divisors of any integer n are mutually independent. [3]

\S 4 The probability that n is a prime

Since n is a prime if, and only if, it is not divisible by any prime p \leq \sqrt{n}, it follows immediately from Lemma 2 and Lemma 3 that:

Lemma 4: For any n \geq 2, the probability \mathbb{P}(n \in \{p\}) of an integer n being a prime p is the probability that r_{p_{_{i}}}(n) \neq 0 for any 1 \leq i \leq k if p_{k}^{2} \leq n < p_{k+1}^{2}. \Box

Lemma 5: \mathbb{P}(n \in \{p\}) = \prod_{i = 1}^{\pi(\sqrt{n})}(1 - 1/p_{i}) \sim 2e^{-\gamma}/log_{e}\ n [4]. \Box

\S 5 The Prime Number Theorem

The number of primes less than or equal to n is thus given by:

Lemma 6: \pi(n) \approx \sum_{j = 1}^{n}\prod_{i = 1}^{\pi(\sqrt{j})}(1 - 1/p_{i}). \Box

This now yields the Prime Number Theorem:

Theorem 2: \pi(x) \sim x/log_{e}\ x.

Proof: From Lemma 6 and Mertens’ Theorem that
[5]:

\prod_{p \leq x}(1 - 1/p_{i}) = e^{o(1)}.e^{-\gamma}/log_{e}\ x

it follows that:

(\pi(n).log_{e}\ n)/n \approx (log_{e}\ n/n)\sum_{j = 1}^{n}\prod_{i = 1}^{\pi(\sqrt{j})}(1 - 1/p_{i})

(\pi(n).log_{e}\ n)/n \approx (log_{e}\ n/n)\sum_{j = 1}^{n}(2.e^{o(1)}.e^{-\gamma})/log_{e}\ n

(\pi(x).log_{e}\ x)/x \sim c.(log_{e}\ x/x)\int_{2}^{x}(1/log_{e}\ t).dt

(\pi(x).log_{e}\ x)/x \sim c.(log_{e}\ x/x)[log_{e}.log_{e}\ t + log_{e}\ t + \sum_{2}^{\infty}(log_{e}\ t)^{k}/(k. k!)]_{2}^{^{x}}

(\pi(x).log_{e}\ x)/x \sim c.(log_{e}\ x/x)[log_{e}.log_{e}\ x + log_{e}\ x + \sum_{2}^{\infty}(log_{e}\ x)^{k}/(k. k!)]

(\pi(x).log_{e}\ x)/x \sim c.(log_{e}\ x/x).f(log_{e}\ x)

The behaviour of (\pi(x).log_{e}\ x)/x as x \rightarrow \infty is then seen by differentiating the right hand side, where we note that f(log_{e}\ x)' = 1/log_{e}\ x:

(c.(log_{e}\ x/x).f(log_{e}\ x))' = c/x + c.f(log_{e}\ x).(1/x^{2} - log_{e}\ x/x^{2})

(c.(log_{e}\ x/x).f(log_{e}\ x))' = c/x + (c.f(log_{e}\ x).(1 - log_{e}\ x))/x^{2}

(c.(log_{e}\ x/x).f(log_{e}\ x))' = o(1/x)

Hence (\pi(x).log_{e}\ x)/x does not oscillate as x \rightarrow \infty. \Box

Acknowledgements

I am indebted to my erstwhile classmate, Professor Chetan Mehta, for his unqualified encouragement and support for my scholarly pursuits over the past fifty years; most pertinently for his patiently critical insight into the required rigour without which the argument of this 1964 investigation would have remained in the informal universe of seemingly self-evident truths.

References

HW60 G. H. Hardy and E. M. Wright. 1960. An Introduction to the Theory of Numbers 4th edition. Clarendon Press, Oxford.

Ti51 E. C. Titchmarsh. 1951. The Theory of the Riemann Zeta-Function. Clarendon Press, Oxford.

Notes

Return to 1: HW60, p.49.

Return to 2: HW60, p.52, Theorem 59.

Return to 3: In the previous post we have shown how it immediately follows from Theorem 1 that integer factorising is necessarily of order O(n/log_{e}\ n); from which we conclude that integer factorising cannot be in the class P of polynomial-time algorithms.

Return to 4: By HW60, p.351, Theorem 429, Mertens’ Theorem.

Return to 5: By the argument in Ti51, p.59, eqn.(3.15.2).

Return to 6: HW60, p.9, Theorem 7.

Author’s working archives & abstracts of investigations

Bhupinder Singh Anand

Follow me on Academia.edu

Advertisements