**Why primality is polynomial time, but factorisation is not**

**Differentiating between the signature of a number and its value**

**A brief review: The significance of evidence-based reasoning**

In a paper: `The truth assignments that differentiate human reasoning from mechanistic reasoning: The evidence-based argument for Lucas’ Gödelian thesis’, which appeared in the December 2016 issue of *Cognitive Systems Research* [An16], I briefly addressed the philosophical challenge that arises when an intelligence—whether human or mechanistic—accepts arithmetical propositions as true under an interpretation—either axiomatically or on the basis of subjective *self-evidence*—without any specified methodology for objectively *evidencing* such acceptance in the sense of Chetan Murthy and Martin Löb:

“It is by now folklore … that one can view the *values* of a simple functional language as specifying *evidence* for propositions in a constructive logic …” … Chetan. R. Murthy: [Mu91], \S 1 Introduction.

“Intuitively we require that for each event-describing sentence, say (i.e. the concrete object denoted by exhibits the property expressed by ), there shall be an algorithm (depending on **I**, i.e. ) to decide the truth or falsity of that sentence.” … Martin H Löb: [Lob59], p.165.

**Definition 1** (*Evidence-based reasoning in Arithmetic*): Evidence-based reasoning accepts arithmetical propositions as true under an interpretation if, and only if, there is some specified methodology for objectively *evidencing* such acceptance.

The significance of introducing *evidence-based* reasoning for assigning truth values to the formulas of a first-order Peano Arithmetic, such as PA, under a well-defined interpretation (see Section 3 in [An16]), is that it admits the distinction:

(1) algorithmically *verifiable* `truth’ (Definition 2}); and

(2) algorithmically *computable* `truth’ (Definition 3).

**Definition 2** (*Deterministic algorithm*): A deterministic algorithm computes a mathematical function which has a unique value for any input in its domain, and the algorithm is a process that produces this particular value as output.

Note that a deterministic algorithm can be suitably defined as a `*realizer*‘ in the sense of the *Brouwer-Heyting-Kolmogorov* rules (see [Ba16], p.5).

For instance, under *evidence-based* reasoning the formula of the first-order Peano Arithmetic PA must always be interpreted *weakly* under the classical, standard, interpretation of PA (see [An16], Theorem 5.6) in terms of algorithmic *verifiability* (see [An16], Definition 1); where, if the PA-formula interprets as an arithmetical relation over :

**Definition 2** (*Algorithmic verifiability*): The number-theoretical relation is algorithmically *verifiable* if, and only if, for any natural number , there is a deterministic algorithm which can provide evidence for deciding the truth/falsity of each proposition in the finite sequence .

Whereas must always be interpreted *strongly* under the finitary interpretation of PA (see [An16], Theorem 6.7) in terms of algorithmic *computability* ([An16], Definition 2), where:

**Definition 3** (*Algorithmic computability*): The number theoretical relation is algorithmically *computable* if, and only if, there is a deterministic algorithm that can provide evidence for deciding the truth/falsity of each proposition in the denumerable sequence .

The significance of the distinction between algorithmically *computable* reasoning based on algorithmically *computable* truth, and algorithmically *verifiable* reasoning based on algorithmically *verifiable* truth, is that it admits the following, hitherto unsuspected, consequences:

(i) PA has two well-defined interpretations over the domain of the natural numbers (including ):

(a) the *weak* non-finitary standard interpretation ([An16], Theorem 5.6),

and

(b) a *strong* finitary interpretation ([An16], Theorem 6.7);

(ii) PA is *non-finitarily* consistent under ([An16], Theorem 5.7);

(iii) PA is *finitarily* consistent under ([An16], Theorem 6.8).

**The significance of evidence-based reasoning for Computational Complexity**

In this investigation I now show the relevance of *evidence-based* reasoning, and of distinguishing between algorithmically *verifiable* and algorithmically *computable* number-theoretic functions (as defined above), for Computational Complexity is that it assures us a formal foundation for placing in perspective, and complementing, an uncomfortably counter-intuitive entailment in number theory—Theorem 2 below—which has been treated by conventional wisdom as sufficient for concluding that the prime divisors of an integer *cannot* be proven to be mutually independent.

However, I show there that such informally perceived barriers are, in this instance, illusory; and that admitting the above distinction illustrates:

(a) *Why* the prime divisors of an integer are mutually independent Theorem 2;

(b) *Why* determining whether the signature (Definition 3 below) of a given integer —coded as the key in a modified Bazeries-cylinder (see Definition 7 of this paper) based combination lock—is that of a prime, or not, can be done in polynomial time (Corollary 4 of this paper); as compared to the time given by Agrawal et al in [AKS04], and improved to by Lenstra and Pomerance in [LP11], for determining whether the value of a given integer is that of a prime or not.

(c) *Why* it can be cogently argued that determining a factor of a given integer cannot be polynomial time.

**Definition 4** (*Signature of a number*): The signature of a given integer is the sequence where for all primes .

Unique since, if and have the same signature, then ; whence since for by appeal to Bertrand’s Postulate ; and the uniqueness is easily verified for .

**Definition 5** (*Value of a number*): The *value* of a given integer is any well-defined interpretation—over the domain of the natural numbers—of the (unique) numeral that represents in the first-order Peano Arithmetic PA.

We note that Theorem 2 establishes a lower limit for [AKS04] and [LP11], because determining the *signature* of a given integer does not require knowledge of the *value* of the integer as defined by the Fundamental Theorem of Arithmetic.

**Theorem 1**: (*Fundamental Theorem of Arithmetic*): Every positive integer can be represented in exactly one way as a product of prime powers:

where are primes and the are positive integers (including ).

** Are the prime divisors of an integer mutually independent?**

In this paper I address the query:

**Query 1**: Are the prime divisors of an integer mutually independent?

**Definition 6** (*Independent events*): Two events are independent if the occurrence of one event does not influence (and is not influenced by) the occurrence of the other.

Intuitively, the prime divisors of an integer *seem* to be mutually independent by virtue of the Fundamental Theorem of Arithmetic

Moreover, the prime divisors of can also be *seen* to be mutually independent in the usual, linearly displayed, Sieve of Eratosthenes, where whether an integer is crossed out as a multiple of a prime is *obviously* independent of whether it is also crossed out as a multiple of a prime :

~~1~~, 2, 3, ~~4~~, 5, ~~6~~, 7, ~~8~~, ~~9~~, ~~10~~, 11, ~~12~~, 13, ~~14~~, ~~15~~, ~~16~~, 17, ~~18~~, 19 …

Despite such compelling evidence, conventional wisdom appears to accept as definitive the counter-intuitive conclusion that although we can *see* it as true, we cannot mathematically prove the following proposition as *true*:

**Proposition 1**: Whether or not a prime divides an integer is independent of whether or not a prime divides the integer .

We note that such an *unprovable-but-intuitively-true* conclusion makes a *stronger* assumption than that in Gödel’s similar claim for his arithmetical formula —whose Gödel-number is —in [Go31], p.26(2). *Stronger*, since Gödel does not assume his proposition to be *intuitively true*, but shows that though the arithmetical formula with Gödel-number is not provable in his Peano Arithmetic yet, for any -numeral , the formula whose Gödel-number is *is* -provable, and therefore *meta-mathematically true* under any well-defined Tarskian interpretation of (cf., [An16], Section 3.).

Expressed in computational terms (see [An16], Corollary 8.3), under any well-defined interpretation of , Gödel’s formula translates as an arithmetical relation, say , such that is algorithmically *verifiable*, but not algorithmically *computable*, as always true over , since is -provable ([An16], Corollary 8.2).

We thus argue that a perspective which denies Proposition 1 is based on perceived barriers that reflect, and are peculiar to, *only* the argument that:

**Theorem 2**: There is no deterministic algorithm that, for any given , and any given prime , will evidence that the probability that divides is , and the probability that does not divide is .

**Proof** By a standard result in the Theory of Numbers ([Ste02], Chapter 2, p.9, Theorem 2.1, we cannot define a probability function for the probability that a random is prime over the probability space .

(Compare with the informal argument in [HL23], pp.36-37.)

In other words, treating Theorem 2 as an absolute barrier does not admit the possibility—which has consequences for the resolution of outstanding problems in both the theory of numbers and computational complexity—that Proposition 1 is algorithmically *verifiable*, but not algorithmically *computable*, as *true*, since:

**Theorem 3**: For any given , there is a deterministic algorithm that, given any prime , will evidence that the probability that divides is , and the probability that does not divide is .

## Leave a comment

Comments feed for this article