Re: Towards a Formula for Primes


WARNING - SCI.MATH IS NOTORIOUS FOR BICKERING. Those who bicker are
not rigorous, as has been shown before.

A more detailed account of this discovery was sent to sci.math
yesterday but without the history of the discovery that preceeds it.
It did not appear.

---------------------------------------------------------
An Axiomatic Theorem on the Decidability of Primes.

It was under the guiding light of the Gödel Incompleteness Theorem
that I sought a missing axiom that might lead to the resolution of the
problem of creating a GENERAL formula for Primes. This must work for
ALL primes.

Having created the Pythagorean Perimeters Theorem, by which a perfect
rectangle of Diophantine ratio converts to a Diophantine right
triangle (Pythagorean triangle) of the same perimeter, I noticed that
this was creating NEW PRIMES.

Explanation: If the ratio of the perfect rectangle is coprime, a new
prime must have been created, because a Pythagorean BASE TRIPLE (eg
3:4:5 but not 6:8:10) is always coprime. So a coprime DUPLE becomes a
coprime TRIPLE, and somewhere the mathematics is generating a prime.

This I called the "neogenesis of primes".

My first approach was destroyed, amidst the background bickering for
which sci.math is notorious, by somebody who gave is Internet handle
as "Quasi".

If A and B are coprime, A with B and with (A+B) are also coprime. A
coprime duple is converted to a coprime triple even by the simple
arithmetical function of addition.

This is an excellent example of the mathematical principle of
"couterexample" because of its simplicity.

I continued to think publicly when I proved the corollary that the
principle of the "neogenesis of primes" is also contained within
subtraction. The proof is trivial because addition and subtraction are
"mirror-image twins" containing the same axioms.

So the "neogenesis of primes" is contained within arithmetic itself,
and does not need to be "imported" from geometry to compensate for one
of the missing axioms.

Having been helped to leave an unfruitful path of logic, I examined
the way in which primes can initially be selected by the 6n plus-or-
minus 1 algorithm. This gives ALL primes, but some "false primes" like
25, 35 and 49. Can arithmetic decide to remove the "false primes".

I was thinking in a Hilbert way (more on this later). I wrote
"ARITHMETIC CANNOT DECIDED".

After "thinking in public" further, I corrected my statement. I was
thinking in a Turing way (more on this later) and wrote "ARITHMETIC
CAN DECIDE".

I mentioned the Hilbert Decidability Problem (German -
"Entscheidungsproblematik")., and decided to investigate.

Dr. Yuri Matiyasevich of St. Petersburg, Russia gave an perfectly
clear account of Turing's response to the Hilbert problem, excellently
translated into English, here:

http://logic.pdmi.ras.ru/~yumat/H10Pbook/par_5_7.htm

They were researching the parameters of a future "computing engine",
and Turing suggested that a box might have a "ticker-tape" such as was
used for stock-market reports at the time. This one-dimensional array
is a paradigm that imitates the one-dimensional array of RAM in a
modern computer, so that a "Turing Machine" is not an obsolete model.

Hilbert had required that M n-tuples be selected by some test, in
order that two lists be created. One is a list of those that pass the
test, which might be at address 123 (or whatever), and another is a
list of those that fail the test, such at address 0.

Notice that a "Turing Machine" has "random access" (a misnomer,
because neither 0 nor 123 is random, but the way in which the machine
toggles from one list to another seems arbitrary because it depends on
the "decision" of the test).

My own concept of "to decide" proved to be intimately bound up with
this, because I was looking upon the Turing box as a kind of toolbox,
where the tools inside are arithmetic and logic, and the axioms
thereof influence the outside behaviour of the box.

George Boole had taken the concept of arithmetic, such as the
addition, and used it as a generator of logical OR.

Arithmetic (addition):
1 + 1 = 2
1 + 0 = 1
0 + 1 = 1
0 + 0 = 0

Here, in positive logic, zero is "false" whilst any other number (a
Diophantine) is "true".

It may have been simply to stop the 1s and 2s looking like numbers
that he decided to standardise the value of "true":

Logic (or):
1 + 1 = 1
1 + 0 = 1
0 + 1 = 1
0 + 0 = 0

However, the result had wider implications than mere tidiness.

Given a Turing Machine, we can use arithmetic to find the "0". So the
output of the arithmetic is a Diophantine or zero. This we multiply by
123.

Those that fail the test are delivered to the list at address 0. They
are all together. So arithmetic CAN decide a zero.

Those that pass the test return from the arithmetic with any
Diophantine. So they "spray" the results into locations 1*123, 2 *123,
3 * 123 and other places. The results that pass the test are therefore
not kept together in a single list, but scattered arbitrarily in the
RAM at intervals of 123. These will be addresses 123, 246, 369 and
infinitely more possible locations. So arithmetic CANNOT make a second
clear decision.

This is the TURING SEMI-DECIDABILITY principle, and also an example of
the Gödel INCOMPLETENESS of axioms. Half of the "decidability" is
missing.

However, if we had carried out some BOOLEAN process upon the
arithmetical result, prior to the computation of the list address, the
Boolean result would have given only 0 and 1. When multiplied by 123,
it would have given zero and 123 for the two lists. Of course, one can
add a constant, and get 100 and 223, or any other two list-addresses.
The important point is that it TOGGLES between two addresses. This is
Hilbert (full) decidability. Arithmetic cannot do this.

We can create the COMPLEMENTARY arithmetical formula for the above
test. It would be a test for non-primes, for example, instead of for
primes. In such a case, zero would mean "false - it is NOT non-prime".
So we would get 0 for primes. We could subtract this from 123, and it
would land at exactly the same list-address (zero) where the non-
primes are listed, at 123.

However, when this complementary Turing semi-decidability is used to
get a "true", we get 123 minus 123 sometimes (a correct address), and
-123 or -246 on other occasions. The Turing complement is still semi-
decidable.

So the first arithmetical test has a one-word vocabulary "NO". In the
second case, we asked the question backwards and got a "NO" which
means a "YES" to the first question.

One test can only say "NO". The other can only say "YES". How do we
link the two semi-decidables?

The ONLY way is by means of a Hilbert decidable, which understands
BOTH words and can interpret between them. Only a Boolean function can
do this.

Conclusion so far:
Arithmetic is "Turingian".
Boolean logic, or arithmetic with Boolean, is "Hilbertian".

Further point:
An example of the Gödel incompleteness of an axiomatic system is seen
here in the arithmetic, where half its deciding power is missing.

And now, to the primes:

We consider the "Sieve of Eritosthenes", but carefully because we are
examining its "decidability" properties.

The "True" word of our logic will be called "Accept", in that we
accept the number as prime. The "False" word of our logic will be
called "Reject" in that we reject it even when it was previously
accepted.

Can we "sieve" the primes with a one-word logic?

We "Accept" all the Diophantines.

However, to be generous we retract that statement. Let us say that the
Diophantines are given.

We plan to "Reject" the non-primes with a "sieve".

Where do we start?

We can start at 4 and add 2 to land on the next even. Then we go on to
the 8, 10 and so on. We sieve out all evens and are left with odds,
other than 2.

What do we sieve out next?

We need to create a list of primes. A factor can only be a factor if
it is BELOW the number of which it is a factor.

We could go to 3, and see if multiples of 2 land upon it. This is
trivial, because everything is odd.

Then we could go to the 4, and see if the PREVIOUS LIST of primes
divides into it.

Then we could go into the 5, and check the previous list of primes.

And so on. We are just REJECTING those that have factors.

However, at the start, there is NO PREVIOUS LIST.

To start, we have to ACCEPT the 2 into the primes list. Only then can
the 3 be found and put into the list, and then the 5 and then the 7.

There are no primes below the 2, so it cannot be obtained from the
number-line by rejecting others around it. It is an AXIOM that 2 is
prime - not the result of a "sieving" action but because of "common-
sense" outside of the "Sieve of Eratosthenes" algorithm.

Such a prime, upon being accepted into the list, requires the
availability not only of "Reject" but also of "Accept".

So the problem of Primes is "Hilbertian".

A "Turingian" system like arithmetic CANNOT generate a general formula
for primes, valid to infinity.

CONCLUSION:
If a claim is made that a "formula" gives ALL the primes to infinity,
it must be checked for the presence of at least one single Boolean
construct. If such a thing as AND, or NAND, or OR, or NOR, or XOR, or
XNOR, or NOT, or "IF" or "BOOLEAN" or every other Boolean is missing,
then the formula will always break down. It will not deliver all
primes.

There are very good approximations, however, that deliver many.

I conceived the word "BOOLEAN" because it is easily implemented on a
computer. It may already exist.

In Basic, Pascal or similar:

(Arithmetical, or Turning semi-decidable side)
If number then number = 1
(Logical, or Hilbert decidable side).

In Pentium code, the number in EAX:

;;; (Arithmetical, or Turning semi-decidable side)
and eax ;;; Make eax set or reset the zero flag
jz Hilbert ;;; Zero stays zero
mov eax,1 ;;; Diophantine overwritten by 1
Hilbert:
;;; (Logical, or Hilbert decidable side).

It only takes a single Hilbert construct to import the missing half of
the "decidability" into the arithmetic. Such an arithmetic, that has
some logic added, I dubbed a "logical transarithmetic".

Arithmetic cannot solve the primes problem. Only a logically-augmented
arithmetic - a logical transarithmetic - can

Charles Douglas Wehner


.

Relevant Pages

  • Re: Length of sequence of consecutive primes starting at 2
    ... >I would like to know how long the list of consecutive primes (i.e. not ... >skipping any primes in between) is and can I find it somewhere. ... lists of all primes up to at least 10^12 ... into permanent or even semi-permanent storage. ...
    (sci.math)
  • Re: Tuple question
    ... totally bogus to me. ... Say I want to work with some primes and I have a primes generator. ... that keep screamign LISTS, ...
    (comp.lang.python)
  • Re: Chez Watt: Prime Idiocy
    ... figured criticism for slop was better than criticism for ommission. ... There is a disclaimer that the lists are only ... "primes" if you haven't got a clue what you are talking about. ...
    (talk.origins)
  • Re: Prime lists and Computation
    ... > Q2 Is their a complete list of primes to X Published? ... sufficient storage is available to store them all. ... prime lists for trial division. ... of digits by 3 would double the factoring time. ...
    (sci.math)