Are primes just "random"?

**Gerenuk** · Mar2-09, 09:13 AM

What are the indications that primes follow some patterns and that maybe some day someone will find algorithmically simple rules for prime properties?

I was thinking that maybe one merely can prove that prime numbers exist, but they represent some highly complex something that never will reveal simple pattern.

Similarly to the Mandelbrot set, which is just a complex pattern - not completely random, but probably does not involve much more features beyond it's definition?

**CRGreathouse** · Mar2-09, 10:15 AM

Originally Posted by Gerenuk

What are the indications that primes follow some patterns and that maybe some day someone will find algorithmically simple rules for prime properties?

What would you consider algorithmically simple?

We have fast methods for locating primes (thanks to Atkin/Bernstein) that take less time (asymptotically) to enumerate primes on an interval than to enumerate the interval itself.

The number of primes on an interval can be computed in near-sqrt time (Lagarias and Odlyzko 1987).

Under the Riemann hypothesis, the number of primes can be approximated in polylogarithmic time with only sqrt * log error.

The status (prime/nonprime) of an isolated number can be determined in polynomial time (AKS).

The status of an isolated number can be determined with high probability in quadratic time (Rabin, Grantham).

A simple expression is equivalent to the primality of a number greater than four (Wilson).

A polynomial exists which has solutions in positive integers exactly when a number k (k + 2 in most versions) is prime (Jones, Sato, Wada, & Wiens 1976).

**Gerenuk** · Mar2-09, 01:58 PM

Originally Posted by CRGreathouse

What would you consider algorithmically simple?

I'm not sure about my question, but your examples sound convincing enough :)

Hmm, then what would you call the most outstanding prime problems nowadays?

Could you give me the references for:

Originally Posted by CRGreathouse

The status of an isolated number can be determined with high probability in quadratic time (Rabin, Grantham).

Are primes useful for anything apart from cryptography?

**yyat** · Mar2-09, 03:10 PM

You may also want to read this discussion on structure and randomness of the prime numbers.

**Dadface** · Mar2-09, 05:30 PM

Gerenuk I think that proving the Riemann hypothesis stands high on the list of unsolved problems.I tried it this morning over breakfast but I got nowhere.Then I realised that I dont know what the hypothesis is.

~~csprof2000~~ · Mar2-09, 05:52 PM

Is it true that between any prime number p and p*p, there exists a prime number q?

**ramsey2879** · Mar2-09, 07:08 PM

Originally Posted by CRGreathouse

What would you consider algorithmically simple?

We have fast methods for locating primes (thanks to Atkin/Bernstein) that take less time (asymptotically) to enumerate primes on an interval than to enumerate the interval itself.

The number of primes on an interval can be computed in near-sqrt time (Lagarias and Odlyzko 1987).

Under the Riemann hypothesis, the number of primes can be approximated in polylogarithmic time with only sqrt * log error.

The status (prime/nonprime) of an isolated number can be determined in polynomial time (AKS).

The status of an isolated number can be determined with high probability in quadratic time (Rabin, Grantham).

A simple expression is equivalent to the primality of a number greater than four (Wilson).

A polynomial exists which has solutions in positive integers exactly when a number k (k + 2 in most versions) is prime (Jones, Sato, Wada, & Wiens 1976).

How does This Test Compare with the ones you noted

If N = -1 mod 4 then N is prime if and only if $LaTeX Code: C(-F_{A},F_{D}) = -1 \\mod N$

If N = 1 mod 4 then N is prime if and only if $LaTeX Code: C(F_{D},F_{A}) = 1 \\mod N$

Here $LaTeX Code: F_{A} = F_{(N-3)/2}$ and $LaTeX Code: F_{D} = F_{(N+3)/2$ are the Fibonacci numbers and C(a,b) = a^2 +ab - b^2.

**Hurkyl** · Mar2-09, 07:17 PM

Originally Posted by csprof2000

Is it true that between any prime number p and p*p, there exists a prime number q?

You can do much better than that; Bertrand's postulate implies there's one between p and 2p. This wiki page references some further results on this topic.

**CRGreathouse** · Mar2-09, 07:42 PM

Originally Posted by Gerenuk

Hmm, then what would you call the most outstanding prime problems nowadays?

The Riemann hypothesis. Nothing else is even close.

Originally Posted by Gerenuk

Could you give me the references for:

Michael O. Rabin, "Probabilistic algorithm for testing primality", Journal of Number Theory 12:1 (1980), pp. 128-138.

Jon Grantham, "Frobenius pseudoprimes", Mathematics of Computation, 70:234 (2001), pp. 873-891.

Originally Posted by Gerenuk

Are primes useful for anything apart from cryptography?

Almost everything in number theory relates to the primes in some way. They're important for understanding the structure of numbers and for fast numerical algorithms.

**CRGreathouse** · Mar2-09, 07:43 PM

Originally Posted by ramsey2879

How does This Test Compare with the ones you noted

If N = -1 mod 4 then N is prime if and only if $LaTeX Code: C(-F_{A},F_{D}) = 1 \\mod N$

If N = 1 mod 4 then N is prime if and only if $LaTeX Code: C(F_{D},F_{A}) = -1 \\mod N$

Here $LaTeX Code: F_{A} = F_{(N-3)/2}$ and $LaTeX Code: F_{D} = F_{(N+3)/2$ are the Fibonacci numbers and C(a,b) = a^2 +ab - b^2.

It's weaker than Grantham's test.

**Gerenuk** · Mar3-09, 04:22 AM

Originally Posted by CRGreathouse

The Riemann hypothesis. Nothing else is even close.

Which important results follow from the Riemann hypothesis? Some results the final converge into real world applications?
What would be the second most important problem about primes? :)

Originally Posted by CRGreathouse

Almost everything in number theory relates to the primes in some way. They're important for understanding the structure of numbers and for fast numerical algorithms.

So numerical algorithms can be improved with primes. Which for example? I mean something that in the end has some "real world" application. Not something which is a dead end in some fictional world of thoughts. I mean I'm also interested a bit in number theory, but I honestly cannot explain to some people why it's useful (apart from cryptography).

**Dadface** · Mar3-09, 04:47 AM

Gerenuk try googling the following:
1.millenium prize problems
2.the music of the primes

**Gerenuk** · Mar3-09, 05:29 AM

Originally Posted by Dadface

Gerenuk try googling the following:
1.millenium prize problems
2.the music of the primes

Thx.
1. I couldn't find any other prime related problems
2. I dig into that a bit more. Unfortunately the reference to nature is a bit slim.

I looked up Riemann hypothesis. Didn't we find zeros of expressions at school? Can't remember the equation though. For the problem I guess you substitute z->z+1/2 and show that all zeros are imaginary. Unfortunately I don't have the time to continue here

**CRGreathouse** · Mar3-09, 07:52 AM

Originally Posted by Gerenuk

1. I couldn't find any other prime related problems

The RH is the only prime-related question among the Millennium Problems. Here are some other prime-related problems:

Are there infinitely many twin primes? Do the number of prime values taken by a polynomial follow the expected (Hardy-Littlewood) distribution? Is there always a prime between positive squares? The Goldbach conjectures: is every even number greater than two the sum of three primes? Is evey odd number greater than five the sum of three primes? De Polignac's conjecture: is every positive even number the difference between consecutive primes infinitely often? Are there finitely many Fermat primes? Cramer's conjecture: is the gap between consecutive primes always less than (some multiple of) the square of the logarithm of the smaller prime?

**Gerenuk** · Mar3-09, 08:57 AM

Originally Posted by CRGreathouse

Are there infinitely many twin primes? Do the number of prime values taken by a polynomial follow the expected (Hardy-Littlewood) distribution? Is there always a prime between positive squares? The Goldbach conjectures: is every even number greater than two the sum of three primes? Is evey odd number greater than five the sum of three primes? De Polignac's conjecture: is every positive even number the difference between consecutive primes infinitely often? Are there finitely many Fermat primes? Cramer's conjecture: is the gap between consecutive primes always less than (some multiple of) the square of the logarithm of the smaller prime?

Thanks for the list!
The problem you mentioned below to two categories:
- density/number of primes
- sums or difference of primes
Are there significant other theorems (apart from say existence and divisibility theorems like little Fermat's)?

**CRGreathouse** · Mar3-09, 03:01 PM

Originally Posted by Gerenuk

The problem you mentioned below to two categories:
- density/number of primes
- sums or difference of primes

That's probably biased toward my interests (combinatorial and additive number theory, respectively).

Originally Posted by Gerenuk

Are there significant other theorems (apart from say existence and divisibility theorems like little Fermat's)?

Theorems? I've only talked about conjectures thus far. Interesting prime-related theorems:

Prime Number Theorem: there are about n/log n primes below n. (Rosser and Dusart have effective versions of this; Shoenfeld has a better effective version conditional on the RH.)
Green-Tao Theorem: the primes contain arbitrarily long arithmetic progressions
Bertrand's postulate: there is a prime between n and 2n
Vinogradov's theorem: All large enough odds are the sum of three primes.
Dirichlet's theorem: there are the 'expected number' of primes in arithmetic progressions (with a similar but effective by Brun & Titchmarsh)
...