# Are primes just random ?

1. Mar 2, 2009

### 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?

2. Mar 2, 2009

### CRGreathouse

Re: Are primes just "random"?

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

3. Mar 2, 2009

### Gerenuk

Re: Are primes just "random"?

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:
Are primes useful for anything apart from cryptography?

4. Mar 2, 2009

### yyat

Re: Are primes just "random"?

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/" [Broken] discussion on structure and randomness of the prime numbers.

Last edited by a moderator: May 4, 2017
5. Mar 2, 2009

Re: Are primes just "random"?

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.

Last edited: Mar 2, 2009
6. Mar 2, 2009

### csprof2000

Re: Are primes just "random"?

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

7. Mar 2, 2009

### ramsey2879

Re: Are primes just "random"?

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.

Last edited: Mar 2, 2009
8. Mar 2, 2009

### Hurkyl

Staff Emeritus
Re: Are primes just "random"?

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

Last edited by a moderator: May 4, 2017
9. Mar 2, 2009

### CRGreathouse

Re: Are primes just "random"?

The Riemann hypothesis. Nothing else is even close.

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.

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.

10. Mar 2, 2009

### CRGreathouse

Re: Are primes just "random"?

It's weaker than Grantham's test.

11. Mar 3, 2009

### Gerenuk

Re: Are primes just "random"?

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

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

12. Mar 3, 2009

Re: Are primes just "random"?

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

13. Mar 3, 2009

### Gerenuk

Re: Are primes just "random"?

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

14. Mar 3, 2009

### CRGreathouse

Re: Are primes just "random"?

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?

15. Mar 3, 2009

### Gerenuk

Re: Are primes just "random"?

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

16. Mar 3, 2009

### CRGreathouse

Re: Are primes just "random"?

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

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

17. Mar 3, 2009

### ramsey2879

Re: Are primes just "random"?

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?

18. Mar 3, 2009

### CRGreathouse

Re: Are primes just "random"?

Your test* is the Lucas test. It has counterexamples/pseudoprimes http://www.research.att.com/~njas/sequences/A005845 [Broken] = 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.

Last edited by a moderator: May 4, 2017
19. Mar 3, 2009

### Gerenuk

Re: Are primes just "random"?

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?

20. Mar 4, 2009

### Coin

Re: Are primes just "random"?

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