# Why not randomness for primes' distribution?

zankaon
Isn't perfect randomness an unattainable ideal? So wouldn't some sort of pattern to distribution of prime numbers (i.e. other than randomness) seem to be expected?
http://en.wikipedia.org/wiki/Prime_numbers" [Broken] with attention to Open Questions section.

Last edited by a moderator:

Homework Helper
There are lots of patterns to the primes. For example: their density is roughly n/log n, they are never even for p > 2, etc.

LukeD
Zankaon, I don't think you understand what random means. If the distribution of primes were random, then no matter how far out you would go, you could find two primes as close together as you want. However, this is not the case. Instead the density of primes seems to be a function of how far our you go.

Homework Helper
LukeD, I believe it is still unknown whether you can always find two primes as close together as possible, i.e. with difference 2.

density theorems say nothing about behavior of a small finite set of primes.

Homework Helper
Perhaps LukeD means if they were genuinely random, in whatever sense, then there would be infinitely many consecutive primes, i.e. p and p+1 prime. Whether or not a given number is prime is entirely a deterministic idea. That they behave sufficiently close to being random odd numbers is a remarkably powerful tool, though, I'm led to believe. References anyone?

huba
Julian Havil (2003), in "Gamma", p.163, quotes Euler:
"Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the mind will never penetrate."
And then Havil goes on to quote Erdős: "God may not play dice with the Universe, but there's something strange going on with the prime numbers."
Further, R.C. Vaughan: "It is evident that the primes are randomly distributed but, unfortunately, we don't know what random means."

LukeD
Bah, sorry, completely ignore what I said. I haven't studied any number theory, so I really don't know anything about primes.

Staff Emeritus
Gold Member
There is an obvious pattern to the distribution prime numbers -- they happen to be exactly those integers greater than 1 that do not have a nontrivial factor.

Homework Helper
thanks matt, i completely ignored the sea we swim in, that all primes > 2 are odd! (They seem also mostly to avoid numbers ending in 5, on first experimentation.)

so randomness seems to mean within those restrictions allowed by "Dirichlet", i.e. integers congruent to 1,3,7,9, mod 10.

e.g. primes are evenly distributed in those equivalence classes, asymptotically.

So the theorem on primes in arithmetic distributions is one of the first big results on some randomness of primes.

In a way, most of the results I know on primes are sort of randomness statements.

I.e. Euclid says no matter how far out you go you keep finding them.

then there are all the results that an infinite number of primes exist congruent to 3 mod4, and also congruent to 1 mod 4, and finally dirichlet sums these results all up together, with a randomness result that says the modulus and the remainder are irrelevant beyond being relatively prime.

but now we go in the other direction, with gauss's conjecture, the prime number theorem, that primes look sort of like the graph of that function Li(x)?

then Helmut Maier and others have theorems i need to check out that may describe other special behavior of primes.

hmmm.... good, enlightening question, at least for me, helping put known results in context.

by the way, if you believe primes are truly randomly distributed, within known elementary restrictions, then I guess the twin prime conjecture should be true.

indeed maybe gauss's prime number theorem conjecture, is also just a pattern based on elementary restrictions arising from seive constructions.

i dont know anything about it, but if you think about it, the process of seiving should place a restriction on the pattern of primes up to a certain limit.

i.e. the first step, crossing out even numbers, gives matt's observation against true randomness, then the next integer, namely 3 has to be prime, and the second step is crossing out all multiples of three.

then we must eliminate 2,4 and 3,6, which leaves 5,......,

this seems to completely determine the pattern of primes, but in a very complicated way, which may be approximated in the prime number theorem.

but i am a total novice here.

Last edited:
Homework Helper
well further research on the web suggests that most results about primes are concerned with the extent of randomness of their distribution, subject to the usual elementary constraints.

green and tao proved e.g. that "arbitrary arithmetic distributions exist within the primes", subject of course to matt's observation that we tend to ignore the restriction that the common difference should not be 1.

beginning with helmut maier's work from the 80's and subsequent work of andrew granville, there is also a lot of attention to primes in "short intervals" showing apparently some deviations from expected behavior, where presumably "expected" always means in the sense dictated by probabilistic notions of randomness.

i have trouble reading these articles, and do not presently have access to their AMS reviews which hopefully are written more for the general mathematical public.

Homework Helper
ok, here you go, an article in the math monthly, written for anyone.

http://www.dms.umontreal.ca/~andrew/PDF/PrimeRace.pdf

the argument there is that if we had the naively expected degree of randomness of prime distribution, then for all large x, th number of primes less than x, and congruent to 1 mod4, should have a 50-50 chance of being greater than the number of such primes congruent to 3 mod4.

but it isnt true. the primes congruent to 3 mod4, exceed the others for almost all x.

in general granville excels at being able to make number theory interesting and understandable to a broad audience, when that is his goal.

huba
The Sieve of Eratosthenes is a simple algorithm to find primes, and what possibly looks so strange is that the application of simple rules can lead to randomness or unpredictability. As I understand, chaos theory and complexity theory deal with such issues: the iterative application of simple rules leading to unpredictable behaviour.
It has been pointed out that there is a big difference between rule-based and non-rule-based unpredictability, though.
(I can't make a reference, as I am not allowed to post a URL)

Homework Helper
Umm, nope, Huba. 5 is still a prime, irrespective of chaos theory. And 6 is composite. Such fundamental misunderstandings of what chaos theory really states don't help. Any number that ends in a 0 is going to be composite... your understanding seems to be way off. There is on one sense nothing unpredictable about the primes, but in a very real way there is a randomness there - see the conjectures of Hardy, and the work of Gowers, Green-Tao. And it isn't anything really to do with dynamical systems (which is chaos theory) in the sense you mean. That is a deliberate qualification, since almost any two areas of mathematics can share common ground at some level.

huba
Sorry, I shouldn't have mentioned chaos theory as I know too little about it.

huba
On the other hand, John Derbyshire ("Prime Obsession", 2003) mentions chaos theory in the context of the distribution of primes, and briefly describes the "Montgomery-Odlyzko law", which says that "the distribution of the spacings between successive non-trivial zeros of the Riemann zeta function (suitably normalized) is statistically identical with the distribution of eigenvalue spacings in a GUE operator" (Derbyshire, 2003, p.292).
GUE operators (definitions can be found http://www.secamlocal.ex.ac.uk/people/staff/mrwatkin/zeta/random.htm" [Broken], are used to model certain quantum dynamical systems.
As I understand (and please do correct me if I am wrong), the relevant property of random Hermitian matrices is that the spacing of their eigenvalues, which fit energy levels observed in experiments with quantum-dynamical systems, is not exactly random, because it is unusual for two values to be as close as could be expected for a random distribution, that is, there is a a "repulsion" between energy levels that does not allow two levels to be as close as random distribution would otherwise allow. The distribution of the non trivial zeros of the zeta function also shows this repulsion effect.

About some history of the hypothesised link between the zeta zeros and the eigenvalues of Hermitian matrices, it is interesting to look at http://www.dtc.umn.edu/~odlyzko/polya/index.html" [Broken].

Last edited by a moderator:
Homework Helper
The link you're talking about is to do with an integral that appears in two previously unlinked areas. It's actually quite straight forward (I went through the derivation once). I'm not too sure of the causal explanations, but if you just think about it, the eigenvalues of a random matrix can't be independent r.v.s, and thinking about the diagonalization probabilistically gives you the integral.

This is distinct from how you introduced chaos theory, though.

bd2357
Since the idea of prime is independent of base, and all primes are one more or one less than a multiple of six, then in base 6 all primes end in 1 or 5, yet they are still randomly distributed.

Remember randomness is difficult for humans to actually deal with, and hind-sight is 20-20. The difference between predicting something and describing something.

Just some useless ramblings.

DeaconJohn
All,

Hmmm, an impressive discussion. Curious that Zankaon has not joined in after his initial post.

You still out there somewhere Zankaon?

DJ

lewdtenant
Since the idea of prime is independent of base, and all primes are one more or one less than a multiple of six, then in base 6 all primes end in 1 or 5, yet they are still randomly distributed.

wow, i think you just blew my mind a little bit, thank you

lewdtenant
Since the idea of prime is independent of base, and all primes are one more or one less than a multiple of six, then in base 6 all primes end in 1 or 5, yet they are still randomly distributed.

wow, i think you just blew my mind a little bit, thank you