Are prime numbers truly unpredictable?

[Gerenuk]

Are primes just "random"?

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]

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]

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:

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]

You may also want to read http://terrytao.wordpress.com/2007/04/05/simons-lecture-i-structure-and-randomness-in-fourier-analysis-and-number-theory/" discussion on structure and randomness of the prime numbers.

 

[Dadface]

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 realized that I don't know what the hypothesis is.

 

[csprof2000]

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

 

[ramsey2879]

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 $$C(-F_{A},F_{D}) = -1 \mod N$$

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

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

 

[Hurkyl]

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; postulate[/url] implies there's one between p and 2p. This wiki page references some further results on this topic.

 

[CRGreathouse]

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

The Riemann hypothesis. Nothing else is even close.

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.

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]

How does This Test Compare with the ones you noted


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

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

Here $$F_{A} = F_{(N-3)/2}$$ and $$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]

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? :)

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]

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

 

[Gerenuk]

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]

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]

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]

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).

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)
• ...

 

[ramsey2879]

It's weaker than Grantham's test.

In what way is it weaker. I understand that Grantham's test has known counterexamples or presudoprimes. As far as I know there are no counterexamples to my test. I admit that I have not sufficiently investigated my test nor have any proof of its validity. I only checked it for integers less than 200, a rather trival number, but what if my test were proven true?

 

[CRGreathouse]

In what way is it weaker. I understand that Grantham's test has known counterexamples or presudoprimes. As far as I know there are no counterexamples to my test. I admit that I have not sufficiently investigated my test nor have any proof of its validity. I only checked it for integers less than 200, a rather trival number, but what if my test were proven true?

Your test* is the Lucas test. It has counterexamples/pseudoprimes http://www.research.att.com/~njas/sequences/A005845 = 705, 2465, 2737, 3745, 4181, 5777, 6721, 10877, 13201, 15251, 24465, 29281, 34561, 35785, 51841, 54705, 64079, 64681, 67861, 68251, 75077, 80189, 90061, 96049, 97921, 100065, 100127, 105281, 113573, 118441, 146611, ...

* I believe that your original statement reversed the cases 1 and 3 mod 4. In the reversed form most primes are counterexamples.

 

[Gerenuk]

I asked this question some time ago, but only got very exotic answers I couldn't understand:

Do primes have any applications in physics/technology?

 

[Coin]

Gerenuk, for the most canonical example, primes are critical in modern cryptography.

 

[slider142]

Prime numbers are also linked to quantum mechanics: http://seedmagazine.com/news/2006/03/prime_numbers_get_hitched.php , as well as the evolutionary presence of Eratosthenes's Sieve in biology: http://www.mariomarkus.com/save/GreatMomentsInScience.htm