My Math Forum (http://mymathforum.com/math-forums.php)
-   Number Theory (http://mymathforum.com/number-theory/)
-   -   Proof Primes are not "random" (http://mymathforum.com/number-theory/341440-proof-primes-not-random.html)

 complicatemodulus August 14th, 2017 01:01 AM

Proof Primes are not "random"

Is there any Official Proof that Primes are not "Random" numbers ?

 cjem August 14th, 2017 04:46 AM

They are clearly deterministic rather than truly random - as soon as you've defined the ring of integers, the primes and their distribution are completely determined.

You probably didn't mean "truly random" when you said "random", but the issue is that what you've asked is incredibly ambiguous. Until you make your statement precise, it's meaningless to ask if there's a proof of it.

 Benit13 August 14th, 2017 04:56 AM

Quote:
 Originally Posted by complicatemodulus (Post 577556) Is there any Official Proof that Primes are not "Random" numbers ?
I guess you mean something like "Is there any structure to the underlying distribution of prime numbers?"

There's certainly metrics about the distribution and rate of change of primes as you look to higher numbers, but as far as I know there is no deterministic function \$\displaystyle f(n)\$ that can predict the sequence of primes; current algorithms that determine prime numbers are NP in complexity.

 complicatemodulus August 14th, 2017 05:00 AM

Is also clear to me that primes follows a fixed pattern, so they are not "ramdomly" placed.

So I would like to know if, and where to find it, there is a official proof.

I'm playing with my Complicate Numbers and I saw that applying a function to Integers or to Primes will produce a very similar output behavior, so is clear they are not "randomly" placed or the final behavior must be partially or fully different from integer's one.

Thanks
Ciao
Stefano

 idontknow August 14th, 2017 05:19 AM

A sequence \$\displaystyle \; f(n)=PRIME \; \$ exists

 Benit13 August 14th, 2017 09:18 AM

Quote:
 Originally Posted by idontknow (Post 577578) A sequence \$\displaystyle \; f(n)=PRIME \; \$ exists
Of course the sequence exists. What I said was that there is no function that determines the sequence in a deterministic way. Specifically, all algorithms that exist to compute f(n) are NP algorithms.

Quote:
 Is also clear to me that primes follows a fixed pattern, so they are not "ramdomly" placed.
- What do you mean by "follows a fixed pattern"?

If you mean "has a predictable distribution" then yes, (as far as I'm aware...) there are metrics that characterize the distribution of primes and allow you to make predictions such as what the number of primes are within a certain interval.

However, if you mean "the function to determine the sequence of primes is deterministic" then my question to you is this:

Also...

- Who's saying that they are "randomly placed"? What do you mean by that?

 cjem August 14th, 2017 09:40 AM

Quote:
 Originally Posted by Benit13 (Post 577597) Of course the sequence exists. What I said was that there is no function that determines the sequence in a deterministic way. Specifically, all algorithms that exist to compute f(n) are NP algorithms.
I think you're a little confused. Sequences of real numbers (such as \$f(n)\$ here) are by definition functions from the naturals to the reals. I also don't see the relevance of whether the algorithms are NP: whether something is deterministic is not dependent on how easy it is to determine it in practice...

 JeffM1 August 14th, 2017 10:13 AM

This whole thread seems to have been destined from the start to generate confusion, which is not surprising given that complicatemodulus initiated it.

Obviously the function f(n) = the nth prime exists. It relates positive integers to positive integers. (Why involve the reals?)

f(1) = 2. f(2) = 3. f(3) = 5. And so on. But so what?

The further question of whether that function is "random" or "deterministic" depends on how those words are defined. Moreover, a general formula for the function is not known, which makes it difficult or perhaps impossible to analyze the function in terms of those definitions.

If someone defines what unique properties a "random" function has or what unique properties a "deterministic" function has and also specifies the properties of f(n) = the nth prime, then we can have a sensible conversation. Until then, it is a will of the wisp.

 Maschke August 14th, 2017 10:16 AM

Quote:
 Originally Posted by JeffM1 (Post 577606) f(1) = 2. f(2) = 3. f(3) = 5. And so on. But so what? The further question of whether that function is "random" or "deterministic" depends on how those words are defined. Moreover, a general formula for the function is not known, which makes it difficult or perhaps impossible to analyze the function in terms of those definitions.
If you give me n, I can deterministically obtain f(n) via the sieve of Eratosthenes. It's deterministic. Someone complained that it's not efficiently computable. That's irrelevant. It's computable. Give me n and I'll give you f(n) via a deterministic algorithm that halts in a finite number of steps.

 JeffM1 August 14th, 2017 10:57 AM

Quote:
 Originally Posted by Maschke (Post 577607) If you give me n, I can deterministically obtain f(n) via the sieve of Eratosthenes. It's deterministic. Someone complained that it's not efficiently computable. That's irrelevant. It's computable. Give me n and I'll give you f(n) via a deterministic algorithm that halts in a finite number of steps.
Is the question whether we can determine primes?

If so, the answer is "of course, we can"

I doubt, however, that is what the intended question is. My point was that without understanding the question, we can spin our wheels forever. I suspect the question is whether there is a simpler pattern to the primes than a list of the primes themselves and whether that pattern can be expressed in a formula.

All times are GMT -8. The time now is 10:04 AM.