4 ms·

Random how? We can prove the prime number theorem, we know roughly how many primes there are in a span of numbers and we know the approximate frequency of pri

Random how? We can prove the prime number theorem, we know roughly how many primes there are in a span of numbers and we know the approximate frequency of prime numbers in that span. We know on average how far apart the primes are in a particular span of numbers. All from the prime number theorem and related theorems. This stuff has been proven. Likewise, if the Riemann hypothesis is true then primes would have a very regular distribution. What we can't yet do is create a generator function that catches most primes. We can create generators though (For example: (n! +1) is prime but it misses tons and tons of primes.) There are no hard fast rules that catch a majority of only primes. This probably doesn't qualify as "random distribution" unless you take a really simple definition of random. It's the non-randomness of their distribution that allows us to test the primality of numbers for cryptography.

deleted 16y ago
[deleted]
deleted 16y ago
[deleted]
gjm11 16y ago
I agree with the point you're making, but unfortunately almost all the particular statements above are wrong :-). n!+1 is not always prime. For instance, 4!+1 = 25 = 5^2, 5!+1 = 121 = 11^2, 6!+1 = 721 = 7.103. If RH is true, then the number of primes < x differs from the naive prediction you get from saying n is prime with probability 1/log(n) by at most something like sqrt(x) log(x). That's entirely comparable to the accuracy you'd get if the primes really were randomly distributed. (More precisely: the variance of something that's 1 with probability p, else 0, is p(1-p), which is roughly equal to p when p is small, and variances of independent things are additive, so on the random-distribution hypothesis the variance of pi(x) would be comparable to the sum of 1/log(n), which is to say n/log(n). I haven't actually done the calculations, but I think this means that with probability 1 some bound of the same type that you get from RH should hold. So the bound you get from RH doesn't show that the primes are any more regularly distributed than the simple random model suggests. Similarly, "primes" generated according to the simple random model would, with probability 1, obey theorems of the sort that we know how to prove about the distribution of primes. (And some that we don't know how to prove.) It is possible to define mathematical functions that recognize primes, or that take on all the primes (and nothing else) as values. But they're generally contrived and inefficient to evaluate.

deleted 16y ago

[deleted]

deleted 16y ago

[deleted]

gjm11 16y ago

I agree with the point you're making, but unfortunately almost all the particular statements above are wrong :-). n!+1 is not always prime. For instance, 4!+1 = 25 = 5^2, 5!+1 = 121 = 11^2, 6!+1 = 721 = 7.103. If RH is true, then the number of primes < x differs from the naive prediction you get from saying n is prime with probability 1/log(n) by at most something like sqrt(x) log(x). That's entirely comparable to the accuracy you'd get if the primes really were randomly distributed. (More precisely: the variance of something that's 1 with probability p, else 0, is p(1-p), which is roughly equal to p when p is small, and variances of independent things are additive, so on the random-distribution hypothesis the variance of pi(x) would be comparable to the sum of 1/log(n), which is to say n/log(n). I haven't actually done the calculations, but I think this means that with probability 1 some bound of the same type that you get from RH should hold. So the bound you get from RH doesn't show that the primes are any more regularly distributed than the simple random model suggests. Similarly, "primes" generated according to the simple random model would, with probability 1, obey theorems of the sort that we know how to prove about the distribution of primes. (And some that we don't know how to prove.) It is possible to define mathematical functions that recognize primes, or that take on all the primes (and nothing else) as values. But they're generally contrived and inefficient to evaluate.