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

\S 1 Are there still unsolved problems about the numbers 1, 2, 3, 4, \ldots ?

In a 2005 Clay Math Institute invited large lecture to a popular audience at MIT ‘Are there still unsolved problems about the numbers 1, 2, 3, 4, \ldots ?’, 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 N, say N = one million, and ask you for the first number after N 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 N 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 k primes, can we generate the prime p(k+1) algorithmically, without testing any number larger than p(k) for primality?

I: A PRIME NUMBER GENERATING THEOREM

Theorem: For all i < k, let p(i) denote the i'th prime, and define a(i) such that:

a(i) < p(i),

and:

p(k) + a(i) \equiv 0\ (mod\ p(i)).

Let d(k) be such that, for all d < d(k), there is some i such that:

d \equiv a(i)\ (mod\ p(i)).

Then:

p(k+1) = p(k) + d(k).

Proof: For all d < d(k), there is some i such that:

p(k) + d \equiv 0\ (mod\ p(i)).

Since p(k+1) < 2p(k):

d(k) < p(k).

Hence:

p(k) + d(k) < p(k)^{2},

and so it is the prime p(k+1).

II: TRIM NUMBERS

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

We define Trim numbers recursively by t(1) = 2, and t(n+1) = t(n) + d(n), where p(i) is the i‘th prime and:

(1) d(1) = 1, and a(2, 1) = 1 is the only element in the 2nd array;

(2) d(n) is the smallest even integer that does not occur in the n‘th array \{a(n, 1), \ldots, a(n, n-1)\};

(3) j is selected so that:

0 \leq a(n+1, i) = (a(n, i) - d(n) + j*p(i) < p(i) for all 0 < i \leq (n-1).

It follows that the Trim number t(n+1) is, thus, a prime unless all its prime divisors are less than d(n).

The Trim Number Algorithm

\line(1,0){285}

n    t(n)

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

\line(1,0){285}

2    3            1      \textit{2}      5

3    5            1      1      \textit{2}      7

4    7            1      2      3      \textit{4}       11

5    11           1      1      4      3       \textit{2}      13

6    13           1      2      2      1       9      \textit{4}       17

7    17           1      1      3      4       5      9       \textit{2}      19

8    19           1      2      1      2       3      7       15      \textit{4}      23

9    23           1      1      2      5      10      3       11     15      \textit{4}       27

10   27          1      0      3      1       6      12       7      11      19       \textit{2}        29

11   29           1      1      1      6       4      10       5       9      17                  \textit{2}      31

\ldots

n    t(n)            r_{_{1}}     r_{_{2}}     r_{_{3}}     r_{_{4}}      r_{_{5}}     r_{_{6}}       r_{_{7}}     r_{_{8}}      r_{_{9}}     r_{_{10}}       r_{_{11}}    …    \textit{\ldots}

\line(1,0){285}

NOTE: The first 50 Trim Numbers upto t(50) = 199 consist of the first 46 primes and the 4 composites:

(i) Trim composite t(10): 27 = 3.3.3

(ii) Trim composite t(32): 125 = 5.5.5

(iii) Trim composite t(37): 147 = 3.7.7

(iv) Trim composite t(46): 189 = 3.3.3.7

Theorem: For all n > 1, t(n) < n^{^{2}}

II A: k-TRIM NUMBERS

For any given natural number k>2, we define k-Trim numbers recursively by t_k(1) = 2, and t_k(n+1) = t_k(n) + d(n), where p(i) is the i‘th prime and:

(1) d(1) = 1, and a(2, 1) = 1 is the only element in the 2nd array;

(2) d(n) is the smallest even integer that does not occur in the n‘th array \{a(n, 1), \ldots, a(n, k-1)\};

(3) j is selected so that:

0 \leq a(n+1, i) = (a(n, i) - d(n) + j*p(i) < p(i) for all 0 < i \leq (k-1).

It follows that the k-Trim number t_k(n+1) is, thus, not divisible by any prime \leq p(k) unless the prime is smaller than d(n).

III: COMPACT NUMBERS

Compact numbers are defined recursively by c(1) = 2, and c(n+1) = c(n) + d(n), where p(i) is the i‘th prime and:

(1) d(1) = 1, and a(2, 1) = 1 is the only element in the 2nd array;

(2) d(n) is the smallest even integer that does not occur in the nth array \{a(n, 1), \ldots, a(n, k)\};

(3) j is selected so that:

0 \leq a(n+1, i) = (a(n, i) - d(n) + j*p(i) < p(i) for all 0 < i \leq k;

(4) k is selected so that:

p(k)*p(k) < c(n) \leq p(k+1)*p(k+1);

(5) a(n, k+1) = 0 if c(n) = p(k+1)*p(k+1).

It follows that the compact number c(n+1) is either a prime, or a prime square, unless all, except a maximum of 1, prime divisors of the number are less than d(n).

The Compact Number Algorithm

\line(1,0){285}

n    c(n)

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

\line(1,0){285}

2    3            1      \textit{2}      5

3    5            1      \textit{2}      7

4    7            1      \textit{2}      9

5    9            1      0      \textit{2}     11

6    11           1      1      \textit{2}    13

7    13           1      2      \textit{4}    17

8    17           1      1      \textit{2}    19

9    19           1      2      \textit{4}     23

10  23           1      1      \textit{2}     25

11   25           1      2      0      \textit{4}     29

12   29           1      1      1      \textit{2}     31

13   31           1      2      4      \textit{6}     37

14   37           1      2      3      \textit{4}     41

15   41           1      1      4      \textit{2}     43

16   43           1      2      2      \textit{4}     47

17   47           1      1      3      \textit{2}     49

18   49           1      2      1      0      \textit{4}      53

19   53           1      1      2      3      \textit{4}      57

20   57           1      0      3      6      \textit{2}      59

21   59           1      1      1      4      \textit{2}      61

22   61           1      2      4      2      \textit{6}      67

23   67           1      2      3      3      \textit{4}       71

24   71           1      1      4      6      \textit{2}       73

25   73           1      2      2      4      \textit{6}       79

26   79           1      2      1      5      \textit{4}       83

27   83           1      1      2      1      \textit{4}       87

28   87           1      0      3      4      \textit{2}       89

29   89           1      1      1      2      \textit{4}       93

30   93           1      0      2      5      \textit{4}       97

31   97           1      2      3      1      \textit{4}       101

32   101          1      1      4      4      \textit{2}      103

33   103          1      2      2      2      \textit{4}      107

34   107          1      1      3      5      \textit{2}      109

35   109          1      2      1      3      \textit{4}      113

36   113          1      1      2      6      \textit{4}       117

37   117          1      0      3      2      \textit{4}       121

38   121          1      2      4      5      0       \textit{6}       127

39   127          1      2      3      6      5       \textit{4}       131

40   131          1      1      4      2      1       \textit{6}       137

41   137          1      1      3      3      6       \textit{2}       139

42   139          1      2      1      1      4       \textit{6}       145

43   145          1      2      0      2      9       \textit{4}       149

44   149          1      1      1      5      5       \textit{2}       151

45   151          1      2      4      5      0       \textit{6}       157

46   157          1      2      3      4      8       \textit{6}       163

47   163          1      2      2      5      2       \textit{4}       167

48   167          1      1      3      1      9       \textit{2}       169

49   169          1      2      1      6      7       0       \textit{4}       173

50   173          1      1      2      2      3       9       \textit{4}       177

51   177          1      0      3      5      10     5       \textit{2}       179

52   179          1      1      1      3      8       3       \textit{2}       181

53   181          1      2      4      1      6       1       \textit{8}       189

54   189          1      0      1      0      9       6       \textit{2}       191

55   191          1      1      4      5      7       4       \textit{2}       193

56   193          1      2      2      3      5       2       \textit{4}       197

57   197          1      1      3      6      1       11      \textit{2}       199

58   199          1      2      1      4      10      9       \textit{6}       205

59   205          1      2      0      5      4       3        \textit{6}       211

60   211          1      2      4      6      9       10      \textit{8}       219

61   219          1      0      1      5      1       2        \textit{4}       223

62   223          1      2      2      1      8       11       \textit{4}       227

63   227          1      1      3      4      4       7        \textit{2}       229

64   229          1      2      1      2      2       5        \textit{4}       233

65   233          1      1      2      5      9       14      \textit{4}       237

66   237          1      0      3      1      5       10      \textit{2}       239

67   239          1      1      1      6      3       8        \textit{2}       241

68   241          1      2      4      4      1       6        \textit{8}       249

69   249          1      0      1      3      4       11      \textit{2}       251

70   251          1      1      4      1      2       9        \textit{6}       257

71   257          1      1      3      2      7       3        \textit{4}       261

72   261          1      0      4      5      3       12      \textit{2}       263

73   263          1      1      2      3      1       10      \textit{4}       267

74   267          1      0      3      6      8       6        \textit{2}       269

75   269          1      1      1      4      6       4        \textit{2}       271

76   271          1      2      4      2      4       2        \textit{6}       277

77   277          1      2      3      3      9       9        \textit{4}       281

78   281          1      1      4      6      5       5        \textit{2}       283

79   283          1      2      2      4      3       3        \textit{6}       289

\ldots

n     c(n)            r_{_{1}}     r_{_{2}}     r_{_{3}}     r_{_{4}}      r_{_{5}}     r_{_{6}}       r_{_{7}}     r_{_{8}}       r_{_{9}}     r_{_{10}}       r_{_{11}}    …

\line(1,0){285}

NOTE: The first 79 Compact Numbers upto c(79) = 283 consist of the first 61 primes, 5 prime squares, and 13 composites.

Theorem 1: There is always a Compact Number c(m) such that n^{^{2}} < c(m) \leq (n+1)^{^{2}}.

Theorem 2: For sufficiently large n,\ d(n) < constant.\frac{\sqrt{c(n)}}{log_{_{e}}c(n)}.

\S 2 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, 2-dimensional matrix, representation of the residues r_{i}(n), defined for all n \geq 2 and all i \geq 2 by:

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

Density‘: For instance, the residues r_{_{i}}(n) can be defined for all n \geq 1 as the values of the non-terminating sequences Ri (n) = \{i-1, i-2, \ldots, 0, i-1, i-2, \ldots, 0, \ldots\}, defined for all i \geq 1 (as illustrated below in Fig.1).

Fig.1

\line(1,0){285}

Sequence    R_{_{1}}    R_{_{2}}    R_{_{3}}    R_{_{4}}    R_{_{5}}    R_{_{6}}    R_{_{7}}    R_{_{8}}    R_{_{9}}    R_{_{10}}    R_{_{11}}     …    R_{_{n}}

\line(1,0){285}

n=1                \textbf{0}      1      2      3       4      5       6      7      8       9       10      …    n-1

n=2                0      \textbf{0}      1      2       3      4       5      6      7       8        9       …    n-2

n=3                0      1      \textbf{0}      1       2      3       4      5      6       7        8       …    n-3

n=4                0      0      2      \textbf{0}       1      2       3      4      5       6        7       …    n-4

n=5                0      1      1      3       \textbf{0}      1       2      3      4       5        6       …    n-5

n=6                0      0      0      2       4      \textbf{0}       1      2      3       4        5       …    n-6

n=7                0      1      2      1       3      5       \textbf{0}      1      2       3        4       …    n-7

n=8                0      0      1      0       2      4       6      \textbf{0}      1       2        3       …    n-8

n=9                0      1      0      3       1      3       5      7      \textbf{0}       1        2       …    n-9

n=10               0      0      2      2       0      2       4      6      8       \textbf{0}        1       …    n-10

n=11               0      1      1      1       4      1       3      5      7       9        \textbf{0}       …    n-11

\ldots

n                     r_{_{1}}     r_{_{2}}    r_{_{3}}     r_{_{4}}      r_{_{5}}     r_{_{6}}     r_{_{7}}     r_{_{8}}     r_{_{9}}    r_{_{10}}      r_{_{11}}     …    \textbf{0}

\line(1,0){285}

We note that:

\bullet For any i \geq 2, the non-terminating sequence R_{_{i}}(n) cycles through the values (i-1, i-2, \ldots 0) with period i;

\bullet For any i \geq 2 the ‘density’—over the set of natural numbers—of the set \{n\} of integers that are divisible by i is \frac{1}{i}; and the ‘density’ of integers that are not divisible by i is \frac{i-1}{i}.

Primality: The residues r_{_{i}}(n) can be alternatively defined for all i \geq 1 as values of the non-terminating sequences, E(n) = \{r_{_{i}}(n) : i \geq 1\}, defined for all n \geq 1 (as illustrated below in Fig.2).

Fig.2

\line(1,0){285}

Sequence    R_{_{1}}    R_{_{2}}    R_{_{3}}    R_{_{4}}    R_{_{5}}    R_{_{6}}    R_{_{7}}    R_{_{8}}    R_{_{9}}    R_{_{10}}    R_{_{11}}     …    R_{_{n}}

\line(1,0){285}

E(1)             \textbf{0}      1      2      3       4      5       6      7      8       9       10      …    n-1

\textbf{E(2)}             0      \textbf{0}      1      2       3      4       5      6      7       8        9       …    n-2

\textbf{E(3)}             0      1      \textbf{0}      1       2      3       4      5      6       7        8       …    n-3

\textit{E(4)}              0      0      2      \textbf{0}       1      2       3      4      5       6        7       …    n-4

\textbf{E(5)}             0      1      1      3       \textbf{0}      1       2      3      4       5        6       …    n-5

\textit{E(6)}              0      0      0      2       4      \textbf{0}       1      2      3       4        5       …    n-6

\textbf{E(7)}             0      1      2      1       3      5       \textbf{0}      1      2       3        4       …    n-7

\textit{E(8)}              0      0      1      0       2      4       6      \textbf{0}      1       2        3       …    n-8

\textit{E(9)}              0      1      0      3       1      3       5      7      \textbf{0}       1        2       …    n-9

\textit{E(10)}             0      0      2      2       0      2       4      6      8       \textbf{0}        1       …    n-10

\textbf{E(11)}            0      1      1      1       4      1       3      5      7       9        \textbf{0}       …    n-11

\ldots

E(n)               r_{_{1}}     r_{_{2}}    r_{_{3}}     r_{_{4}}      r_{_{5}}     r_{_{6}}     r_{_{7}}     r_{_{8}}     r_{_{9}}    r_{_{10}}      r_{_{11}}     …    \textbf{0}

\line(1,0){285}

We note that:

\bullet The non-terminating sequences \textbf{E(n)} highlighted in bold correspond to a prime p (since r_{_{i}}(p) \neq 0 for any 1 < i < p) in the usual, linearly displayed, Eratosthenes sieve:

E(1), \textbf{E(2)}, \textbf{E(3)}, \textit{E(4)}, \textbf{E(5)}, \textit{E(6)}, \textbf{E(7)}, \textit{E(8)}, \textit{E(9)}, \textit{E(10)}, \textbf{E(11)}, \ldots

\bullet The non-terminating sequences \textit{E(n)} highlighted in italics identify a crossed out composite n (since r_{_{i}}(n) = 0 for some 1 < i < n) in the usual, linearly displayed, Eratosthenes sieve.

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

Fig.1 illustrates that although the probability P(a) of selecting a number that has the property of being prime from a given set S of numbers is definable if the precise proportion of primes to non-primes in S is definable, 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) = P(n\ is\ a\ prime) cannot be defined in N (see Chapter 2, p.9, Theorem 2.1, here).

The probability P(b) of determining a proper factor of a given number n

Fig.2 illustrates, however, that the probability P(b) of determining a proper factor of a given number n is \frac{1}{\pi(\sqrt{n})}, since this paper 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.

We thus have that \pi(n) \approx n.\prod_{_{i = 1}}^{^{\pi(\sqrt{n})}}(1-\frac{1}{p_{_{i}}}), with a binomial standard deviation.

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

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 putative non-heuristic probability that a given n is a prime.

\S 3 “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 X the number of prime numbers less than X (denoted \pi(X)) is approximately X/ log X in the sense that the ratio \frac{\pi(X)}{X/ log X} tends to 1 as X goes to infinity. The Riemann Hypothesis would give us a much more accurate “count” for \pi(X) in that it will offer a specific smooth function R(X) (hardly any more difficult to describe than X/ log X) and then conjecture that R(X) is an essentially square root accurate approximation to \pi(X); i.e., for any given exponent greater than 1/2 (you choose it: 0.501,\ 0.5001,\ 0.50001, for example) and for large enough X where the phrase “large enough” depends on your choice of exponent the error term i.e., the difference between R(X) and the number of primes less than X in absolute value is less than X raised to that exponent (e.g. < X^{0.501}, < X^{0.5001}, etc.)"

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

Bhupinder Singh Anand

Advertisements