This argument laid the foundation for this later post and this investigation.

(Notations, non-standard concepts, and definitions used commonly in these investigations are detailed in this post.)

Abstract: We show the joint probability \mathbb{P}(p_{i} | n\ \cap\ p_{j} | n) that two unequal primes p_{i},\ p_{j} divide 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 Integer Factorising is necessarily of the order O(n/log_{e}\ n).

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

We define 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.

We note 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 [2] \mathbb{P}(e) of an event e, we then have 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 [3]:

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 [4] 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.

Since n is a prime if, and only if, it is not divisible by any prime p \leq \sqrt{n} we may, without any loss of generality, take integer factorising to mean determining at least one prime factor p \leq \sqrt{n} of any given n \geq 2.

\S 4 Integer Factorising is not in P

It then immediately follows from Theorem 1 that:

Corollary 3: Integer Factorising is not in P.

Proof: We note that any computational process to identify a prime divisor of n \geq 2 must necessarily appeal to a logical operation for identifying such a factor.

Since n may be the square of a prime, it follows from Theorem 1 that we necessarily require at least one logical operation for each prime p \leq \sqrt{n} in order to logically identify a prime divisor of n.

Moreover, since the number of such primes is of the order O(n/log_{e}\ n), any deterministic algorithm that always computes a prime factor of n cannot be polynomial-time—i.e. of order O((log_{e}\ n)^{c}) for any c—in the length of the input n.

The corollary follows if P is the set of such polynomial-time algorithms. \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

GS97 Charles M. Grinstead and J. Laurie Snell. 1997. Introduction to Probability. Second Revised Edition, 1997, American Mathematical Society, Rhode Island, USA.

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

Ko56 A. N. Kolmogorov. 1933. Foundations of the Theory of Probability. Second English Edition. Translation edited by Nathan Morrison. 1956. Chelsea Publishing Company, New Yourk.

An05 Bhupinder Singh Anand. 2005. Three Theorems on Modular Sieves that suggest the Prime Difference is O(\pi(p(n)^{1/2})). Private investigation.

Notes

Return to 1: HW60, p.49.

Return to 2: Ko56, Chapter I, Section 1, Axiom III, p.2; see also GS97, Chapter 1, Section 1.2, Definition 1.2, p.19.

Return to 3: Ko56, Chapter VI, Section 1, Definition 1, pg.57 and Section 2, pg.58; see also GS97, Chapter 4, Section 4.1, Theorem 4.1, pg.140.

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

Author’s working archives & abstracts of investigations

Bhupinder Singh Anand

Advertisements