You are currently browsing the tag archive for the ‘mutually independent divisors’ tag.

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

1. Since, by the Prime Number Theorem, the number of primes $\leq \sqrt n$ is $O(\frac{\sqrt n}{log_{_{e}}\sqrt n})$, it would follow that determining a factor of $n$ requires at least one logical operation for each prime $\leq \sqrt n$, and therefore cannot be done in polynomial time—whence $P \neq NP$IF whether or not a prime $p$ divides an integer $n$ were independent of whether or not a prime $q \neq p$ divides the integer $n$.

2. Currently, conventional approaches to determining the computational complexity of Integer Factorising apparently appeal critically to the belief that:

(i) either—explicitly (see here)—that whether or not a prime $p$ divides an integer $n$ is not independent of whether or not a prime $q \neq p$ divides the integer $n$;

(ii) or—implicitly (since the problem is yet open)—that a proof to the contrary must imply that if $P(n\ is\ a\ prime)$ is the probability that $n$ is a prime, then $\sum_{_{i = 1}}^{^{\infty}} P(i\ is\ a\ prime) = 1$.

3. If so, then conventional approaches seem to conflate the two probabilities:

(i) The probability $P(a)$ of selecting a number that has the property of being prime from a given set $S$ of numbers;

Example 1: I have a bag containing $100$ numbers in which there are twice as many composites as primes. What is the probability that the first number you blindly pick from it is a prime. This is the basis for setting odds in games such as roulette.

(ii) The probability $P(b)$ of determining that a given integer $n$ is prime.

Example 2: I give you a $5$-digit combination lock along with a $10$-digit number $n$. The lock only opens if you set the combination to a proper factor of $n$ which is greater than $1$. What is the probability that the first combination you try will open the lock. This is the basis for RSA encryption, which provides the cryptosystem used by many banks for securing their communications.

4. In case 3(i), if the precise proportion of primes to non-primes in $S$ is definable, then clearly $P(a)$ too is definable.

However if $S$ is the set $N$ of all integers, and we cannot define a precise ratio of primes to composites in $N$, but only an order of magnitude such as $O(\frac{1}{log_{_{e}}n})$, then equally obviously $P(a)$ cannot be defined in $N$ (see Chapter 2, p.9, Theorem 2.1, here).

5. In case 3(ii) the following paper proves $P(b) = \frac{1}{\pi(\sqrt{n})}$, since it shows that whether or not a prime $p$ divides a given integer $n$ is independent of whether or not a prime $q \neq p$ divides $n$:

Why Integer Factorising cannot be polynomial time

Not only does it immediately follow that $P \neq NP$ (see here), but we further have that $\pi(n) \approx n.\prod_{_{i = 1}}^{^{\pi(\sqrt{n})}}(1-\frac{1}{p_{_{i}}})$, with a binomial standard deviation. Hence, even though we cannot define the probability $P(n\ is\ a\ prime)$ of selecting a number from the set $N$ of all natural numbers that has the property of being prime, $\prod_{_{i = 1}}^{^{\pi(\sqrt{n})}}(1-\frac{1}{p_{_{i}}})$ can be treated as the de facto probability that a given $n$ is prime, with all its attended consequences for various prime-counting functions and the Riemann Zeta function (see here).

Author’s working archives & abstracts of investigations

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

Author’s working archives & abstracts of investigations

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

Author’s working archives & abstracts of investigations

### Start here

Join 84 other followers

LobeLog

Critical Perspectives on U.S. Foreign Policy

What's new

Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao

Quanta Magazine

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

The Brains Blog

Since 2005, a leading forum for work in the philosophy and science of mind

Logic Matters

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

A Neighborhood of Infinity

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

Combinatorics and more

Gil Kalai's blog

Mathematics and Computation

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

Foundations of Mathematics, Logic & Computability

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

John D. Cook

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

Shtetl-Optimized

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

Nanoexplanations

the blog of Aaron Sterling

Eric Cavalcanti

Quantum physicist

East Asia Forum

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

Tanya Khovanova's Math Blog

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

The polymath blog

Massively collaborative mathematical projects

Gowers's Weblog

Mathematics related discussions