You are currently browsing the category archive for the ‘Theory of Numbers’ category.

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

**A: A conventional perspective on why the prime divisors of an integer are not mutually independent**

In a post *Getting to the Roots of Factoring* on the blog *Gödel’s Lost Letter and P = NP* (hosted jointly by him and Professor of Computer Science at Georgia Tech College of Computing, *Richard Lipton*) Professor of Computer Science and Engineering at the University of Buffalo, *Kenneth W. Regan* `revisits’ a 1994 paper on factoring by his co-host.

What I find intriguing in the above post is that the following extract subsumes, almost incidentally, a possibly implicit belief which may be inhibiting not only a resolution of the computational complexity of Integer Factoring (see *this investigation*) by conventional methods but, for similar reasons, also resolution of a large class of apparently unrelated problems (see, for instance, *this investigation* and *this previous post*):

“Here is the code of the algorithm. … the input is a product of two prime numbers, is a polynomial in just one variable, and refers to the greatest-common-divisor algorithm expounded by Euclid around 300 B.C. …

Repeat until exit:

a random number in ;

;

if then exit.

Exiting enables carrying out the two prime factors of …

How many iterations must one expect to make through this maze before exit? How and when can the choice of the polynomial speed up the exploration? …

Note that we cannot consider the events and to be independent, even though and are prime, because and may introduce bias.”

The following reasoning shows why it is not obvious whether the assertion that:

“… we cannot consider the events and to be independent”

is intended to narrowly reflect a putative proof in the particular context of the assertion, or to echo a more general belief.

**B: Defining the probability that a given integer is divisible by a given smaller integer**

(1) We consider the questions:

(a) What is the probability for any given and , where , that:

?

(b) What is the compound probability for any given , where , , and , that:

, and ?

(c) What is the compound probability for any given , where , , and , that:

divides , and divides ?

**C: Why the prime divisors of an integer are mutually independent**

(2) We note that:

(a) The answer to query (1a) above is that the probability the roll of an -sided cylindrical die will yield the value is by the probability model for such an event as definable over the probability space ;

(b) The answer to query (1b) above is that the probability the simultaneous roll of one -sided cylindrical die and one -sided cylindrical die will yield the values and , respectively, is by the probability model for such a simultaneous event as defined over the probability space .

(3) We trivially conclude that:

The compound probability of determining and correctly from the simultaneous roll of one -sided cylindrical die and one -sided cylindrical die, is the product of the probability of determining correctly from the roll of an -sided cylindrical die, and the probability of determining correctly from the roll of a -sided cylindrical die.

(4) We further conclude non-trivially that the answer to query (1c) above is given by:

(a) If and are co-prime, the compound probability of correctly determining that divides and divides from the simultaneous roll of one -sided cylindrical die and one -sided cylindrical die, is the product of the probability of correctly determining that divides from the roll of an -sided cylindrical die, and the probability of correctly determining that divides from the roll of a -sided cylindrical die.

(b) The assumption that and be co-prime is also necessary, since 4(a) would not always be the case if and were not co-prime.

For instance, let . The probability that an -sided cylindrical die will then yield —and allow us to conclude that divides —is , and the probability that a -sided cylindrical die will then yield —and allow us to conclude that divides —is ; but the probability of determining both that divides , and that divides , from a simultaneous roll of the two cylindrical dice is , and not .

(5) We thus conclude non-trivially that, if and are two unequal primes, the probability of determining whether divides is independent of the probability of determining whether divides .

**Author’s working archives & abstracts of investigations**

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

**A: The twin prime conjecture**

In the post *Notes on the Bombieri asymptotic sieve* on his blog *What’s new*, 2006 *Fields Medal* awardee and Professor of Mathematics at UCLA, *Terence Tao*, writes and comments that:

“The twin prime conjecture, still unsolved, asserts that there are infinitely many primes such that is also prime. A more precise form of this conjecture is (a special case) of the Hardy-Littlewood prime tuples conjecture, which asserts that:

… (1)

as , where is the von Mangoldt function and is the twin prime constant:

.

Because is almost entirely supported on the primes, it is not difficult to see that (1) implies the twin prime conjecture.

One can give a heuristic justification of the asymptotic (1) (and hence the twin prime conjecture) via sieve theoretic methods. …

It may also be possible that the twin prime conjecture could be proven by non-analytic means, in a way that does not lead to significantly new estimates on the sum (though this sum will of course have to go to infinity as if the twin prime conjecture holds).”

**B: Why heuristic approaches to the twin prime conjecture may not suffice**

1. What seems to prevent a non-heuristic determination of the limiting behaviour of prime counting functions is that the usual approximations of for finite values of are apparently derived from real-valued functions which are asymptotic to , such as , and Riemann’s function .

2. The degree of approximation for finite values of is thus determined only heuristically, by conjecturing upon an error term in the asymptotic relation that can be seen to yield a closer approximation than others to the actual values of .

3. Moreover, currently, conventional approaches to evaluating prime counting functions for finite may also subscribe to the belief:

(i) either—explicitly (see *here*)—that whether or not a prime divides an integer is ** not** independent of whether or not a prime divides the integer ;

(ii) or—implicitly (since the twin-prime problem is yet open)—that a proof to the contrary must imply that if is the probability that is a prime, then .

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

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

*Example 1*: I have a bag containing 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 of *determining* that a *given* integer is prime.

*Example 2*: I give you a -digit combination lock along with a -digit number . The lock only opens if you set the combination to a proper factor of which is greater than . 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.

5. In case 4(i), if the precise proportion of primes to non-primes in is definable, then clearly too is definable.

However if is the set of all integers, and we cannot define a precise ratio of primes to composites in , but only an order of magnitude such as , then equally obviously cannot be defined in (see Chapter 2, p.9, Theorem 2.1, *here*).

6. In case 4(ii) it follows that , since we can show (see Corollary 2.9 on p.14 of *this investigation*) that whether or not a prime divides a given integer ** is** independent of whether or not a prime divides .

7. We thus have that , with a binomial standard deviation. Hence, even though we cannot define the probability of selecting a number from the set of all natural numbers that has the property of being prime, can be treated as the de facto probability that a given is prime.

8. Moreover, by considering the asymptotic density of the set of all integers that are not divisible by the first primes we can show that, for any , the expected number of such integers in any interval of length is:

.

9. We can then show that a non-heuristic approximation—with a binomial standard deviation—for the number of primes less than or equal to is given for all by:

for some constant .

10. We can show, similarly, that the expected number of Dirichlet and twin primes in the interval () can be estimated similarly; and conclude that the number of such primes is, in each case, cumulatively approximated non-heuristically by a function that .

11. The method can, moreover, be generalised to apply to a large class of prime counting functions (see Section 5.A on p.22 of *this investigation*).

**C: A non-heuristic proof that there are infinitely many twin primes**

1. In particular, instead of estimating:

heuristically by analytic considerations, one could also estimate the number of twin primes non-heuristically as:

where is the de facto probability that a given is prime; and where we need to allow for the possibility that the two probabilities may not be independent.

2. One way of approaching this would be to define an integer as a integer if, and only if, and for all , where is defined for all by:

3. Note that if is a integer, then both and are not divisible by any of the first primes .

4. The asymptotic density of integers over the set of natural numbers is then:

.

5. Further, if is a integer, then is a prime and either is also a prime, or .

6. If we define as the number of integers , the expected number of integers in any interval is given—with a binomial standard deviation—by:

7. Since is at most one less than the number of twin-primes in the interval , it follows that:

8. Now, the expected number of integers in the interval is given by:

.

9. We conclude that the number of twin primes is given by the cumulative non-heuristic approximation:

.

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

**We investigate whether the probabilistic distribution of prime numbers can be treated as a heuristic model of quantum behaviour, since it too can be treated as a quantum phenomena, with a well-defined binomial probability function that is algorithmically computable, where the conjectured values of differ from actual values with a binomial standard deviation, and where we define a phenomena as a quantum phenomena if, and only if, it obeys laws that can only be represented mathematically by functions that are algorithmically verifiable, but not algorithmically computable.**

**1. Thesis: The concept of ‘mathematical truth’ must be accountable**

The thesis of this investigation is that a major philosophical challenge—which has so far inhibited a deeper understanding of the quantum behaviour reflected in the mathematical representation of some laws of nature (see, for instance, *this paper* by Eamonn Healey)—lies in holding to account the uncritical acceptance of propositions of a mathematical language as true under an interpretation—either axiomatically or on the basis of subjective self-evidence—without any specified methodology of accountability for objectively evidencing such acceptance.

**2. The concept of ‘set-theoretical truth’ is not accountable**

Since current folk lore is that all scientific truths can be expressed adequately, and communicated unambiguously, in the first order Set Theory ZF, and since the Axiom of Infinity of ZF cannot—even in principle—be objectively evidenced as true under any putative interpretation of ZF (as we argue in *this post*), an undesirable consequence of such an uncritical acceptance is that the distinction between the truths of mathematical propositions under interpretation which can be objectively evidenced, and those which cannot, is not evident.

**3. The significance of such accountability for mathematics**

The significance of such a distinction for mathematics is highlighted in this paper due to appear in the December 2016 issue of *Cognitive Systems Research*, where we address this challenge by considering the two finitarily accountable concepts of algorithmic verifiability and algorithmic computability (first introduced in *this paper* at the *Symposium on Computational Philosophy* at the AISB/IACAP World Congress 2012-Alan Turing 2012, Birmingham, UK).

**(i) Algorithmic verifiability**

A number-theoretical relation is algorithmically verifiable if, and only if, for any given natural number , there is an algorithm which can provide objective evidence for deciding the truth/falsity of each proposition in the finite sequence .

**(ii) Algorithmic computability**

A number theoretical relation is algorithmically computable if, and only if, there is an algorithm that can provide objective evidence for deciding the truth/falsity of each proposition in the denumerable sequence .

**(iii) Algorithmic verifiability vis à vis algorithmic computability**

We note that algorithmic computability implies the existence of an algorithm that can decide the truth/falsity of each proposition in a well-defined denumerable sequence of propositions, whereas algorithmic verifiability does not imply the existence of an algorithm that can decide the truth/falsity of each proposition in a well-defined denumerable sequence of propositions.

From the point of view of a finitary mathematical philosophy—which is the constraint within which an applied science ought to ideally operate—the significant difference between the two concepts could be expressed by saying that we may treat the decimal representation of a real number as corresponding to a physically measurable limit—and not only to a mathematically definable limit—if and only if such representation is definable by an algorithmically computable function (Thesis 1 on p.9 of *this paper* that was presented on 26th June at the workshop on *Emergent Computational Logics* at UNILOG’2015, 5th World Congress and School on Universal Logic, Istanbul, Turkey).

We note that although every algorithmically computable relation is algorithmically verifiable, the converse is not true.

We show in the CSR paper how such accountability helps define finitary truth assignments that differentiate human reasoning from mechanistic reasoning in arithmetic by identifying two, hitherto unsuspected, Tarskian interpretations of the first order Peano Arithmetic PA, under both of which the PA axioms interpret as finitarily true over the domain of the natural numbers, and the PA rules of inference preserve such truth finitarily over .

**4. The ambit of human reasoning vis à vis the ambit of mechanistic reasoning**

One corresponds to the classical, non-finitary, putative standard interpretation of PA over , and can be treated as circumscribing the ambit of human reasoning about ‘true’ arithmetical propositions.

The other corresponds to a finitary interpretation of PA over that circumscibes the ambit of mechanistic reasoning about ‘true’ arithmetical propositions, and establishes the long-sought for consistency of PA (see *this post*); which establishes PA as a mathematical language of unambiguous communication for the mathematical representation of physical phenomena.

**5. The significance of such accountability for the mathematical representation of physical phenomena**

The significance of such a distinction for the mathematical representation of physical phenomena is highlighted in *this paper* that was presented on 26th June at the workshop on *Emergent Computational Logics* at UNILOG’2015, 5th World Congress and School on Universal Logic, Istanbul, Turkey, where we showed how some of the seemingly paradoxical elements of quantum mechanics may resolve if we define:

**Quantum phenomena**: *A phenomena is a quantum phenomena if, and only if, it obeys laws that can only be represented mathematically by functions that are algorithmically verifiable but not algorithmically computable.*

**6. The mathematical representation of quantum phenomena that is determinate but not predictable**

By considering the properties of Gödel’s function (see 4.1 on p.8 of *this preprint*)—which allows us to strongly represent any non-terminating sequence of natural numbers by an arithmetical function—it would follow that, since any projection of the future values of a quantum-phenomena-associated, algorithmically verifiable, function is consistent with an infinity of algorithmically computable functions, all of whose past values are identical to the algorithmically verifiable past values of the function, the phenomena itself would be essentially unpredicatable if it cannot be represented by an algorithmically computable function.

However, since the algorithmic verifiability of any quantum phenomena shows that it is mathematically determinate, it follows that the physical phenomena itself must observe determinate laws.

**7. Such representation does not need to admit multiverses**

Hence (contrary to any interpretation that admits unverifiable multiverses) only one algorithmically computable extension of the function is consistent with the law determining the behaviour of the phenomena, and each possible extension must therefore be associated with a probability that the next observation of the phenomena is described by that particular extension.

**8. Is the probability of the future behaviour of quantum phenomena definable by an algorithmically computable function?**

The question arises: Although we cannot represent quantum phenomena explicitly by an algorithmically computable function, does the phenomena lend itself to an algorithmically computable probability of its future behaviour in the above sense?

**9. Can primes yield a heuristic model of quantum behaviour?**

We now show that the distribution of prime numbers denoted by the arithmetical prime counting function is a quantum phenomena in the above sense, with a well-defined probability function that is algorithmically computable.

**10. Two prime probabilities**

We consider the two probabilities:

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

*Example 1*: I have a bag containing 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 of determining a proper factor of a given number .

*Example 2*: I give you a -digit combination lock along with a -digit number . The lock only opens if you set the combination to a proper factor of which is greater than . 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.

**11. The probability of a randomly chosen number from the set of natural numbers is not definable**

Clearly the probability of selecting a number that has the property of being prime from a given set of numbers is definable if the precise proportion of primes to non-primes in is definable.

However if is the set of all integers, and we cannot define a precise ratio of primes to composites in , but only an order of magnitude such as , then equally obviously cannot be defined in (see Chapter 2, p.9, Theorem 2.1, *here*).

**12. The prime divisors of a natural number are independent**

Now, the following paper proves , since it shows that whether or not a prime divides a given integer is independent of whether or not a prime divides :

*Why Integer Factorising cannot be polynomial time*

We thus have that , with a binomial standard deviation.

Hence, even though we cannot define the probability of selecting a number from the set of all natural numbers that has the property of being prime, can be treated as the putative non-heuristic probability that a given is a prime.

**13. The distribution of primes is a quantum phenomena**

The distribution of primes is thus determinate but unpredictable, since it is representable by the algorithmically verifiable but not algorithmically computable arithmetical number-theoretic function , where is the ‘th prime.

The Prime Number Generating Theorem and the Trim and Compact algorithms detailed in *this 1964 investigation* illustrate why the arithmetical number-theoretic function is algorithmically verifiable but not algorithmically computable (see also *this Wikipedia proof* that no non-constant polynomial function with integer coefficients exists that evaluates to a prime number for all integers .).

Moreover, although the distribution of primes is a quantum phenomena with probabilty , it is easily seen (see Figs. 7-11 on pp.23-26 of *this preprint*) that the generation of the primes is algorithmically computable.

**14. Why the universe may be algorithmically computable**

By analogy, this suggests that although the measurable values of some individual properties of particles in the universe over time may represent a quantum phenomena, the universe itself may be algorithmically computable if the laws governing the generation of all the particles in the universe over time are algorithmically computable.

1. Since, by the Prime Number Theorem, the number of primes is , it would follow that determining a factor of requires at least one logical operation for each prime , and therefore cannot be done in polynomial time—whence —** IF** whether or not a prime divides an integer were independent of whether or not a prime divides the integer .

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 divides an integer is ** not** independent of whether or not a prime divides the integer ;

(ii) or—implicitly (since the problem is yet open)—that a proof to the contrary must imply that if is the probability that is a prime, then .

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

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

*Example 1*: I have a bag containing 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 of *determining* that a *given* integer is prime.

*Example 2*: I give you a -digit combination lock along with a -digit number . The lock only opens if you set the combination to a proper factor of which is greater than . 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 is definable, then clearly too is definable.

However if is the set of all integers, and we cannot define a precise ratio of primes to composites in , but only an order of magnitude such as , then equally obviously cannot be defined in (see Chapter 2, p.9, Theorem 2.1, *here*).

5. In case 3(ii) the following paper proves , since it shows that whether or not a prime divides a given integer ** is** independent of whether or not a prime divides :

*Why Integer Factorising cannot be polynomial time*

Not only does it immediately follow that (see *here*), but we further have that , with a binomial standard deviation. Hence, even though we cannot define the probability of selecting a number from the set of all natural numbers that has the property of being prime, can be treated as the de facto probability that a given is prime, with all its attended consequences for various prime-counting functions and the Riemann Zeta function (see *here*).

**The Riemann Hypothesis (see also this paper) reflects the fact that all currently known approximations of the number of primes are heuristic**

All known approximations of the number of primes are currently derived from real-valued functions that are asymptotic to , such as , and Riemann’s function , where the degree of approximation for finite values of is determined only heuristically by conjecturing upon an error term in the asymptotic relation that can be `seen’, but not yet proven, to yield `good’ approximations of (as described, for instance, by Barry Mazur and William Stein on p.36 of their absorbingly written, but without sacrificing rigour, entry-level book *Prime Numbers and the Riemann Hypothesis*).

The above graph compares the actual number (red) of primes with the distribution of primes as estimated variously by the functions (blue), (black), and (green), where is Riemann’s function .

**Two non-heuristic approximations of the number of primes **

The following introduces, and compares, two non-heuristic prime counting functions (investigated more fully *here*) that, prima facie, should apparently yield square-root accurate approximations of :

(i) (green); and

(ii) (red);

Based on manual and spreadsheet calculations, Figs.1 and 2 compare the values of the two non-heuristically estimated prime counting functions (both of which have binomial standard deviations) with the actual values of (blue) for and .

Fig.1: The above graph compares the non-heuristically estimated values of (green) and (red) vs the actual values of (blue) for .

Fig.2: The above graph compares the non-heuristically estimated values of (green) and (red) vs the actual values of (blue) for . Note that the gradient of both and of in the interval is .

**Three intriguing queries**

Since (by the Prime Number Theorem), whilst (by Mertens’ Theorem, where is the Euler-Mascheroni constant and ), and it can be shown (see Corollary 3.2 *here*) that for some , this raises the interesting queries (see also 2 of *this initial investigation*):

Fig.3. The overlapping rectangles represent for . Figures within each rectangle are the primes and estimated primes corresponding to the functions and , respectively, within the interval for .

Fig.4: Graph of . The rectangles represent for . Figures within each rectangle are the primes corresponding to the functions and within the interval for . The area under the curve is .

(a) Which is the least , if any, such that ?

(b) Which is the largest , if any, such that ?

(c) Is an *algorithmically verifiable, but not algorithmically computable* (see Definitions 1 and 2 *here*), oscillating function which is *discontinuous in the limit* (in the sense of Zeno’s paradox in 2-dimensions considered in Case 4 *here*)?

** Are there still unsolved problems about the numbers **

In a 2005 Clay Math Institute invited large lecture to a popular audience at MIT ‘*Are there still unsolved problems about the numbers *’, co-author with William Stein of *Prime Numbers and the Riemann Hypothesis*, and Gerhard Gade Harvard University Professor, *Barry Mazur* remarked that (p.6):

“If I give you a number , say = one million, and ask you for the first number after that is prime, is there a method that answers that question without, in some form or other, running through each of the successive numbers after rejecting the nonprimes until the first prime is encountered? **Answer: unknown**.”

Although this may represent conventional wisdom, it is not, however, strictly true!

** Reason**: The following

*1964 Theorem*yields two algorithms (

*Trim/Compact*), each of which affirmatively answers the questions:

(i) Do we necessarily discover the primes in a Platonic domain of the natural numbers, as is suggested by the sieve of Eratosthenes, or can we also generate them sequentially in a finitarily definable domain that builds into them the property of primality?

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

**I: A PRIME NUMBER GENERATING THEOREM**

**Theorem**: For all , let denote the 'th prime, and define such that:

,

and:

.

Let be such that, for all , there is some such that:

.

Then:

.

**Proof**: For all , there is some such that:

.

Since :

.

Hence:

,

and so it is the prime .

**II: TRIM NUMBERS**

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

We define Trim numbers recursively by , and , where is the ‘th prime and:

(1) , and is the only element in the nd array;

(2) is the smallest even integer that does not occur in the ‘th array ;

(3) is selected so that:

for all .

It follows that the Trim number is, thus, a prime unless all its prime divisors are less than .

*The Trim Number Algorithm*

n

1 **2** **2** **3** **5** **7** **11** **13** **17** **19** **23** *27* **29** **31** **37**

2 **3** 1 **5**

3 **5** 1 1 **7**

4 **7** 1 2 3 **11**

5 **11** 1 1 4 3 **13**

6 **13** 1 2 2 1 9 **17**

7 **17** 1 1 3 4 5 9 **19**

8 **19** 1 2 1 2 3 7 15 **23**

9 **23** 1 1 2 5 10 3 11 15 *27*

10 *27* 1 0 3 1 6 12 7 11 19 **29**

11 **29** 1 1 1 6 4 10 5 9 17 **31**

n …

**NOTE**: The first Trim Numbers upto consist of the first primes and the composites:

(i) Trim composite :

(ii) Trim composite :

(iii) Trim composite :

(iv) Trim composite :

**Theorem**: For all

**II A: -TRIM NUMBERS**

For any given natural number , we define -Trim numbers recursively by , and , where is the ‘th prime and:

(1) , and is the only element in the nd array;

(2) is the smallest even integer that does not occur in the ‘th array ;

(3) is selected so that:

for all .

It follows that the -Trim number is, thus, not divisible by any prime unless the prime is smaller than .

**III: COMPACT NUMBERS**

Compact numbers are defined recursively by , and , where is the ‘th prime and:

(1) , and is the only element in the nd array;

(2) is the smallest even integer that does not occur in the nth array ;

(3) is selected so that:

for all ;

(4) is selected so that:

;

(5) if .

It follows that the compact number is either a prime, or a prime square, unless all, except a maximum of , prime divisors of the number are less than .

*The Compact Number Algorithm*

n

1 **2** **2** **3** **5** **7** **11** **13** **17** **19** **23** **29** **31** **37** **41**

2 **3** 1 **5**

3 **5** 1 **7**

4 **7** 1 *9*

5 *9* 1 0 **11**

6 **11** 1 1 **13**

7 **13** 1 2 **17**

8 **17** 1 1 **19**

9 **19** 1 2 **23**

10 **23** 1 1 *25*

11 *25* 1 2 0 **29**

12 **29** 1 1 1 **31**

13 **31** 1 2 4 **37**

14 **37** 1 2 3 **41**

15 **41** 1 1 4 **43**

16 **43** 1 2 2 **47**

17 **47** 1 1 3 *49*

18 *49* 1 2 1 0 **53**

19 **53** 1 1 2 3 *57*

20 *57* 1 0 3 6 **59**

21 **59** 1 1 1 4 **61**

22 **61** 1 2 4 2 **67**

23 **67** 1 2 3 3 **71**

24 **71** 1 1 4 6 **73**

25 **73** 1 2 2 4 **79**

26 **79** 1 2 1 5 **83**

27 **83** 1 1 2 1 *87*

28 *87* 1 0 3 4 **89**

29 **89** 1 1 1 2 *93*

30 *93* 1 0 2 5 **97**

31 **97** 1 2 3 1 **101**

32 **101** 1 1 4 4 **103**

33 **103** 1 2 2 2 **107**

34 **107** 1 1 3 5 **109**

35 **109** 1 2 1 3 **113**

36 **113** 1 1 2 6 *117*

37 *117* 1 0 3 2 *121*

38 *121* 1 2 4 5 0 **127**

39 **127** 1 2 3 6 5 **131**

40 **131** 1 1 4 2 1 **137**

41 **137** 1 1 3 3 6 **139**

42 **139** 1 2 1 1 4 *145*

43 *145* 1 2 0 2 9 **149**

44 **149** 1 1 1 5 5 **151**

45 **151** 1 2 4 5 0 **157**

46 **157** 1 2 3 4 8 **163**

47 **163** 1 2 2 5 2 **167**

48 **167** 1 1 3 1 9 *169*

49 *169* 1 2 1 6 7 0 **173**

50 **173** 1 1 2 2 3 9 *177*

51 *177* 1 0 3 5 10 5 **179**

52 **179** 1 1 1 3 8 3 **181**

53 **181** 1 2 4 1 6 1 *189*

54 *189* 1 0 1 0 9 6 **191**

55 **191** 1 1 4 5 7 4 **193**

56 **193** 1 2 2 3 5 2 **197**

57 **197** 1 1 3 6 1 11 **199**

58 **199** 1 2 1 4 10 9 *205*

59 *205* 1 2 0 5 4 3 **211**

60 **211** 1 2 4 6 9 10 *219*

61 *219* 1 0 1 5 1 2 **223**

62 **223** 1 2 2 1 8 11 **227**

63 **227** 1 1 3 4 4 7 **229**

64 **229** 1 2 1 2 2 5 **233**

65 **233** 1 1 2 5 9 14 *237*

66 *237* 1 0 3 1 5 10 **239**

67 **239** 1 1 1 6 3 8 **241**

68 **241** 1 2 4 4 1 6 *249*

69 *249* 1 0 1 3 4 11 **251**

70 **251** 1 1 4 1 2 9 **257**

71 **257** 1 1 3 2 7 3 *261*

72 *261* 1 0 4 5 3 12 **263**

73 **263** 1 1 2 3 1 10 *267*

74 *267* 1 0 3 6 8 6 **269**

75 **269** 1 1 1 4 6 4 **271**

76 **271** 1 2 4 2 4 2 **277**

77 **277** 1 2 3 3 9 9 **281**

78 **281** 1 1 4 6 5 5 **283**

79 **283** 1 2 2 4 3 3 *289*

n …

**NOTE**: The first Compact Numbers upto consist of the first primes, prime squares, and composites.

**Theorem 1**: There is always a Compact Number such that .

**Theorem 2**: For sufficiently large .

** A 2-dimensional Eratosthenes sieve**

A *later investigation* (see also *this post*) shows why the usual, linearly displayed, Eratosthenes sieve argument reveals the structure of divisibility (and, ipso facto, of primality) more transparently when displayed as the 1964, -dimensional matrix, representation of the residues , defined for all and all by:

, where .

‘**Density**‘: For instance, the residues can be defined for all as the values of the non-terminating sequences , defined for all (as illustrated below in Fig.1).

*Fig.1*

Sequence …

n=1 1 2 3 4 5 6 7 8 9 10 … n-1

n=2 0 1 2 3 4 5 6 7 8 9 … n-2

n=3 0 1 1 2 3 4 5 6 7 8 … n-3

n=4 0 0 2 1 2 3 4 5 6 7 … n-4

n=5 0 1 1 3 1 2 3 4 5 6 … n-5

n=6 0 0 0 2 4 1 2 3 4 5 … n-6

n=7 0 1 2 1 3 5 1 2 3 4 … n-7

n=8 0 0 1 0 2 4 6 1 2 3 … n-8

n=9 0 1 0 3 1 3 5 7 1 2 … n-9

n=10 0 0 2 2 0 2 4 6 8 1 … n-10

n=11 0 1 1 1 4 1 3 5 7 9 … n-11

n …

We note that:

For any , the non-terminating sequence cycles through the values with period ;

For any the ‘density’—over the set of natural numbers—of the set of integers that are divisible by is ; and the ‘density’ of integers that are not divisible by is .

**Primality**: The residues can be alternatively defined for all as values of the non-terminating sequences, , defined for all (as illustrated below in Fig.2).

*Fig.2*

Sequence …

1 2 3 4 5 6 7 8 9 10 … n-1

0 1 2 3 4 5 6 7 8 9 … n-2

0 1 1 2 3 4 5 6 7 8 … n-3

0 0 2 1 2 3 4 5 6 7 … n-4

0 1 1 3 1 2 3 4 5 6 … n-5

0 0 0 2 4 1 2 3 4 5 … n-6

0 1 2 1 3 5 1 2 3 4 … n-7

0 0 1 0 2 4 6 1 2 3 … n-8

0 1 0 3 1 3 5 7 1 2 … n-9

0 0 2 2 0 2 4 6 8 1 … n-10

0 1 1 1 4 1 3 5 7 9 … n-11

…

We note that:

The non-terminating sequences highlighted in bold correspond to a prime (since for any ) in the usual, linearly displayed, Eratosthenes sieve:

The non-terminating sequences highlighted in italics identify a crossed out composite (since for some ) in the usual, linearly displayed, Eratosthenes sieve.

**The significance of expressing Eratosthenes sieve as a -dimensional matrix**

Fig.1 illustrates that although the probability of selecting a number that has the property of being prime from a given set of numbers is definable if the precise proportion of primes to non-primes in is definable, if is the set of all integers, and we cannot define a precise ratio of primes to composites in , but only an order of magnitude such as , then equally obviously cannot be defined in (see Chapter 2, p.9, Theorem 2.1, *here*).

**The probability of determining a proper factor of a given number **

Fig.2 illustrates, however, that the probability of determining a proper factor of a given number is , since *this paper* shows that whether or not a prime divides a given integer is independent of whether or not a prime divides .

We thus have that , with a binomial standard deviation.

**The putative non-heuristic probability that a given is a prime**

Hence, even though we cannot define the probability of selecting a number from the set of all natural numbers that has the property of being prime, can be treated as the putative non-heuristic probability that a given is a prime.

** “What** *sort* **of Hypothesis is the Riemann Hypothesis?”**

The significance of the above perspective is that (see *this investigation*) it admits non-heuristic approximations of prime counting functions with what appear to be (see Fig.15 of *the investigation*) square root accurate errors, where:

“It has long been known that that for any real number the number of prime numbers less than (denoted is approximately in the sense that the *ratio* tends to as goes to infinity. The *Riemann Hypothesis* would give us a much more accurate “count” for in that it will offer a specific smooth function (hardly any more difficult to describe than ) and then conjecture that is an *essentially square root accurate approximation* to ; i.e., for any given exponent greater than (you choose it: , for example) and for large enough where the phrase “large enough” depends on your choice of exponent the error term i.e., the difference between and the number of primes less than in absolute value is less than raised to that exponent (e.g. , etc.)"

… Barry Mazur and William Stein, ‘What is Riemann’s Hypothesis‘

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

Abstract We define the residues for all and all such that if, and only if, is a divisor of . We then show that the joint probability of two unequal primes dividing any integer is the product . We conclude that the prime divisors of any integer are independent; and that the probability of being a prime is . The number of primes less than or equal to is thus given by . We further show that , and conclude that does not oscillate.

** The residues **

We begin by defining the residues for all and all as below:

**Definition 1:** where .

Since each residue cycles over the values , these values are all incongruent and form a complete system of residues ^{[1]} .

It immediately follows that:

**Lemma 1:** if, and only if, is a divisor of .

** The probability **

By the standard definition of the probability of an event , we conclude that:

**Lemma 2:** For any and any given integer , the probability that is , and the probability that is .

We note the standard definition:

**Definition 2:** Two events and are mutually independent for if, and only if, .

** The prime divisors of any integer are mutually independent**

We then have that:

**Lemma 3:** If and are two primes where then, for any , we have:

where and .

**Proof:** The numbers , where and , are all incongruent and form a complete system of residues ^{[2]} . Hence:

.

By Lemma 2:

.

The lemma follows.

If and in Lemma 3, so that both and are prime divisors of , we conclude by Definition 2 that:

**Corollary 1:** .

**Corollary 2:** .

**Theorem 1:** The prime divisors of any integer are mutually independent. ^{[3]}

** The probability that is a prime**

Since is a prime if, and only if, it is not divisible by any prime , it follows immediately from Lemma 2 and Lemma 3 that:

**Lemma 4:** For any , the probability of an integer being a prime is the probability that for any if .

**Lemma 5:** ^{[4]}.

** The Prime Number Theorem**

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

**Lemma 6:** .

This now yields the Prime Number Theorem:

**Theorem 2:** .

**Proof:** From Lemma 6 and Mertens’ Theorem that

^{[5]}:

it follows that:

The behaviour of as is then seen by differentiating the right hand side, where we note that :

Hence does not oscillate as .

**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 ; from which we conclude that integer factorising cannot be in the class 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.

Although not a foundational investigation, I updated and posted this 1964 curiosity for those with an interest in the elementary theory of numbers. The Eta-Function and the Homogeneous function appeared to be particularly fascinating at the time! The former since it seemed that development of the theory of the Riemann Zeta-Function should be more naturally through the series , rather than through the Euler product because of the occurrence of in ; whereas can only be developed through since the numerator in the Dirichlect series of was seemingly an `unknowable’ function of .

**Unusual connections between additive and multiplicative number theory, with roots in a trivial multiplicative analogue for the Grecian perfect numbers.**

**A: Grecian perfect numbers**

(i) Ancient Greek mathematicians considered a number (eg. ), as perfect if it equalled the sum of all its proper divisors, so that:

(ii) Euclid, in his *Elements*, showed that every number of the form:

is perfect if is prime ^{[1]}, and Euler showed that every even perfect number is necessarily of this form ^{[2]}.

(iii) Later mathematicians extended the above investigation to numbers whose multiple equals the sum of the power of all their proper divisors ^{[3]}, so that:

**B: Multiplicative -perfect numbers**

(i) A trivial ^{[4]} analogous extension has been to consider numbers that are multiplicatively *-perfect*, and equal the product of all their proper divisors, so that:

(ii) The triviality lies in the unremarkable completeness with which such numbers can be distinguished for, if is the number of divisors of such an , then:

and so .

(iii) Now if , then , and so:

(a) either , and ,

(b) or , and ;

so the number is trivially of the form or , where and are distinct primes.

Conversely, every number of such form is trivially* -perfect.*

**C: Extended multiplicative -perfect numbers**

(i) An intriguing question, however arises:

Why should ?

The answer lies in extending the concept, as has been done in the additive case, to *-perfect* numbers that equal the product of the power of all their proper divisors, so that:

(ii) It follows that:

and so , which can now take any integral value provided admits of rational values.

(iii) Thus every composite number is *-perfect* in the extended sense, of fractional degree .

(iv) The converse question now becomes interesting:

Which are the *-perfect* numbers of a given fractional degree , when is an integer?

(v) This too can be answered completely:

For every factorisation:

of the given integer into factors, numbers of the form:

are *-perfect* of degree , the ‘s being distinct primes.

(vi) The above follows since, in this case:

and, since:

we have:

**D: Unrestricted factorisations of **

(i) However, this last result raises an unusually interesting, non-trivial question of the number of forms of *-perfect* numbers corresponding to a suitably given degree , since each form corresponds uniquely to a particular factorisation of the given integer of the form .

(ii) Stated simply:

In how many distinct ways can any given integer be unrestrictedly factorised, where is not a factor, and the order of factors is not important?

(iii) In §E.2 below we show that this too can be answered completely.

**E: Factorisations of **

We consider:

In how many distinct ways can any given integer (or ) be factorised as a product of its factors?

**Case 1: The Riemann Zeta-Function**

If we restrict the factors to being only distinct primes or powers of primes, then we have only one, unique prime decomposition of , and the generating function for such representation is the well-known Riemann Zeta Function ^{[5]}:

**Case 2: The Eta Function**

In the general case (which answers the query in §D(ii) above), if represents the number of distinct ways in which can be represented as a product of its factors, where is not a factor and the order of factors is not important, we have the generating function:

Also, if denotes the number of distinct ways in which can be represented as a product of factors, where is not a factor and the order of factors is not important, we have:

However, if denotes the number of ways in which can be represented as a product of factors, where may be a repeated factor and the order of factors is important, the generating function is the power of the Zeta function ^{[6]}:

**Case 3: The Partition Function**

If we restrict the form of to a prime power , there are as many distinct factorisations of as there are unrestricted partitions of .

If represents the number of factorisations of into distinct factors (equivalent to the number of partitions of into parts), is generated by ^{[7]}:

while the generating function for , the total number of distinct factorisations of ( being the total number of unrestricted partitions of ) is ^{[8]}:

**Case 4: The Homogeneous Function**

If we restrict the form of to a product of distinct primes , then the number of distinct factorisations of into factors obeys the functional equation:

for , and is seen to be the Homogeneous Function (product) over the set of degree :

where each term in the summation is distictly different.

The generating function for is then:

while the generating function for the total number of factorisations:

is the formal series:

**References**

**Di18** Leonard Eugene Dickson. 1918.* History of the Theory of Numbers Volume I.* 1952. Chelsea Publishing Company, New York.

**Di20** Leonard Eugene Dickson. 1920.* History of the Theory of Numbers Volume II.* 1952. Chelsea Publishing Company, New York.

**HW59** G. H. Hardy and E. M. Wright. 1959. *An Introduction to the Theory of Numbers. *Fourth Edition. 1960. Oxford University Press, London.

**La27** Edmund Landau. 1927. *Elementary Number Theory. *Translation into English, by Jacob E. Goodman, of the German language work *Elementare Zahlentheorie* (Volume of *Vorlesungen Über Zahlentheorie*), by Edmund Landau. 1958. Chelsea Publishing Company, New York.

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

**Notes**

Return to 1: Di18, p.3; HW59, p.239.

Return to 2: Di18, p.19; HW59, p.240.

Return to 3: Di18, p.38; cf. HW59, p.239, Theorem 274.

Return to 4: Di18, p.58; La27, p.31.

Return to 5: Ti51; HW59, p.245.

Return to 6: Ti51, p.4.

Return to 7: Di20, p.104.

Return to 8: Di20, p.104; HW59, p.274.

## Recent comments