I've been reading the wonderful slides by Terry Tao and thought about this question.
Primes appear to be quite random, and the formal statement should be that there are some characteristics of primes that are indistinguishable by any algorithm from the a sequence of random numbers. I think an easy example should be the distribution of the first digit of the prime number (bounded by C where C goes to infinity), which is basically known, so it's possible to say that this distribution is the same as that of some random sequence.
Are there any formal statements of this kind?
Best Answer
There is no general statement, but there is a general philosophy.
The general idea in mathematics is that things do not happen for no reason. For example, almost every mathematician would be willing to bet that alpha=e^e+pi^sqrt(2) is irrational, as the 'generic' number is irrational, and a genuine reason is needed for a number to be non-generic. Of course, with current technology there is hardly any hope of proving that alpha is irrational, and we must do with proofs of irrationality of numbers such as e and pi, that have more structure that can be exploited in the proofs. Of course, it does not mean that e or pi are indistinguishable from a generic number. For example, the continued fraction expansion of e exhibits a very regular pattern.
Similarly, it is hard to imagine how say a sequence a_n=floor(n^sqrt(2))+p_n, where p_n denotes n'th prime, can behave in substantially different way from a random sequence. Again, there is hardly a hope of proving that. The primes themselves enjoy more noticeable structure than {a_n} however, making it much easier to prove things about them. Of course, primes are not a generic sequence. For example, there is only one even prime.
With this principle in mind one can easily make a myriad of conjectures expressing the idea that 'primes should behave like a generic sequence unless there is an obvious reason that they do not'. Most of these conjectures will be true, but only a few will be provable with current ideas.
The value of proving such conjectures is that since they involve an object so simply defined as the primes, they are likely to involve general mathematical techniques that are useful elsewhere. Like transcendence proofs that gave rise to many ideas in function interpolation, and algebraic number theory, the proofs of conjectures about pseudorandomness of primes led to much progress. For example, proving law of large numbers for primes (which is generally known as the prime number theorem) stimulated the development of the order of entire complex-analytic function. Dirichlet's theorem on uniform distribution mod q led to the introduction of L-functions that are now useful far beyond the original application.