9
$\begingroup$

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?

Improve this question
$\endgroup$

6 Answers 6

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

One example of a conjectured statement of pseudo-randomness for the primes that formalizes what Tao describes in his slides is the Hardy-Littlewood conjecture for k-tuples, which roughly says that you can get estimates for the number of occurrences of various patterns in the primes by treating them like a random sequence generated by counting each positive integer x as "prime" independently with probability 1/log x, then making adjustments to account for the non-uniform behavior of the primes modulo small integers.

Mathworld has a statement of the conjecture at http://mathworld.wolfram.com/k-TupleConjecture.html , and Tao has a nice exposition of the conjecture at

http://terrytao.wordpress.com/2008/01/07/ams-lecture-structure-and-randomness-in-the-prime-numbers/

Improve this answer
$\endgroup$
2
$\begingroup$

I'm not sure if this is exactly what you're talking about, but one of the main tools in Green and Tao's proof that there are arbitrarily long APs of primes is the fact that the primes are a positive-density subset of a certain pseudorandom set.

You probably know this already, but primes are very uniformly distributed "little-endianly"; that is, the primes (mod n) are uniformly distributed except that there are only finitely many primes congruent to a (mod n) when a is not coprime to n.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Ah, an old Dirichlet principle... it's still weaker than anything about pseudorandomness I think (pseudorandom things must be evenly distributed among all characteristics simultaneously). $\endgroup$
    – Ilya Nikokoshev
    Commented Oct 19, 2009 at 19:55
  • $\begingroup$ You at least get things like that since the primes are uniformly distributed among the four residue classes {1, 5, 7, 11} mod 12, primes are uniformly distributed among the pairs of possible residues mod 3 and 4. (Is there some standard definition of "pseudorandom" in this context?) $\endgroup$
    – Michael Lugo
    Commented Oct 19, 2009 at 21:02
  • $\begingroup$ The formal definition of pseudorandom sequence generator in computer science is that no program can tell the difference between sequences generated by this generator and sequences of random numbers. This obviously cannot be applied when there's only sequence, but that's the direction. $\endgroup$
    – Ilya Nikokoshev
    Commented Oct 22, 2009 at 7:59
2
$\begingroup$

Have you heard about Ulam Spiral? There are some relations between prime numbers which make them less than completely random.

Improve this answer
$\endgroup$
1
$\begingroup$

The Copeland–Erdős constant is formed by concatenating all the primes base 10, and is known to be normal.

Improve this answer
$\endgroup$
0
$\begingroup$

Perhaps a reference would be: Statistical Independence in Probability, Analysis and Number Theory by Mark Kac.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Eh, sorry I'm not near the library. Could you briefly say what's the good thing to find at that reference? $\endgroup$
    – Ilya Nikokoshev
    Commented Oct 23, 2009 at 21:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .