4 ms·

The Riemann Hypothesis - one of the outstanding unsolved problems in math

gulbrandr 16y ago
"We would like to see the prime numbers distributed as regularly as possible." Why? I don't understand why mathematicians seek regularity in prime numbers so much.
- arethuza 16y ago
  I think it is just an odd way of expressing a hope that the Riemann hypothesis is true and therefore we are confident that we know a bit more about the distribution of prime numbers. I wouldn't read into it any more than that.
  - gulbrandr 16y ago
    Thanks. I found some great answers in this Math.SE question: http://math.stackexchange.com/q/540/6831 http://math.stackexchange.com/q/540/6831
    - arethuza 16y ago
      You might want to have a look at RSA encryption - which is the most commonly used asymmetric encryption algorithm, it is built around some properties of prime numbers: http://en.wikipedia.org/wiki/RSA http://en.wikipedia.org/wiki/RSA
- btilly 16y ago
  In this case it is statistical regularity. :-) The primes act very much like they were a random set of numbers with n having probability 1/log(n) of being prime. (Mathematicians always mean "natural log" when they say log.) Except, of course, that this is obviously false. Because, for example, there is only one even prime. It is more accurate to say that the primes act very much like they were {2} plus a random set of odd numbers with n having probability 2/log(n) of being prime if it is odd. Except, of course, that this is obviously false. Because, for example, there is only one prime that is divisible by 3. One can continue refining this statement in the obvious way of special casing more and more primes. Other than the obvious corrections that come from these refinements, anything that you'd conjecture from this description is either known to be true, or believed to be true. The number of primes below n. The number of primes below n in an arithmetic sequence. The density of twin primes. And so on, and so forth. Now let's focus on the average of primes below n. (Mathematicians call that number pi(n).) If the primes all were independently random, then you'd expect that to be close to the sum, for i in 2 to n, of 1/log(i), which is approximately the integral from 2 to n of 1/log(x). The usual name for that integral is li(x). li(x) is approximately n/log(n). This estimate is known to be true. That's called the prime number theorem. One of many equivalent forms of the Riemann Hypothesis is that pi(n) - li(n) is O(sqrt(n)). From the "random prime" hypothesis we can see why this is reasonable. It turns out that for large n, (pi(n) - li(n))/sqrt(li(n)) should follow a standard normal distribution. From which it is easy to show that the Riemann Hypothesis should have 100% odds of being true.
  - btilly 16y ago
    When I woke up and thought about this problem again, I realized that I didn't explain one detail. Why should (pi(n) - li(n))/sqrt(li(n)) follow a standard normal distribution? Here is why. pi(n) is the sum of a bunch of many independent random variables, each of which looks like a flip of a biased coin. If you pick the right version of the central limit theorem (see http://en.wikipedia.org/wiki/Lyapunov_condition http://en.wikipedia.org/wiki/Lyapunov_condition for the right version), it is clearly going to be approximately normal. Its average will be the sum of the averages, which is 1/log(2) + 1/(log(3) + ... + 1/log(n) which is going to be li(n) plus O(1). If n is large the li(n) term dominates. Its variance will be the sum of the variances of the individual random variables. The variance of a coin with probability x of turning up 1 is x(1-x). Therefore the sum of the variances is (1/log(2) - (1/log(2)2) + (1/log(3) - (1/log(3)2) + ... + (1/log(n) - (1/log(n)2) which is (modulo a O(1) error) the integral from 2 to n of 1/log(x) - (1/log(x))2 which is li(x) - O(n/log(n)2), which is dominated by the li(x) term. Therefore the average and variance of pi(n) are approximately li(x). So (pi(n) - li(n))/sqrt(li(n)) should have approximately a standard normal distribution.
btilly 16y ago
I can't ever read a claim that the Riemann Hypothesis is unsolved without putting a small asterisk beside that claim. See http://www.lrb.co.uk/v26/n14/karl-sabbagh/the-strange-case-of-louis-de-branges http://www.lrb.co.uk/v26/n14/karl-sabbagh/the-strange-case-o... for why.
- freyrs3 16y ago
  The proof has been checked and it contained errors. See: http://mathoverflow.net/questions/38049/what-exactly-has-louis-de-branges-proved-about-the-riemann-hypothesis/38057#38057 http://mathoverflow.net/questions/38049/what-exactly-has-lou...
  - btilly 16y ago
    The cited paper that found holes is from before the proof discussed in the article I pointed. The update points to a more recent paper that is behind a paywall, so I can't find what it says.
    - thebooktocome 16y ago
      de Branges currently claims (as of September 2010) that he's fixed the problem pointed out by Li. There's supposed to be a pre-print in the works, but I haven't heard anything lately.
  - hsmyers 16y ago
    So did the work of Andrew Wiles--- and instead of slamming the door on the effort support, suggestions and help came from all around until the effort was successful. Yes Andrew was probably a much more well-liked player, but that should have no bearing on scientific inquiry. The subject mathematician has a track record and is not considered (even by his obvious enemies) a crank. Makes you wonder what else is being suppressed...
deleted 16y ago
[deleted]
mckoss 16y ago
And for the JS heads - a prime number sieve in JavaScript: http://wiki.pageforest.com/#js-patterns/prime-sieve http://wiki.pageforest.com/#js-patterns/prime-sieve
- harlowja 16y ago
  And for a classic. http://alpha61.com/primenumbershittingbear/ http://alpha61.com/primenumbershittingbear/

"We would like to see the prime numbers distributed as regularly as possible." Why? I don't understand why mathematicians seek regularity in prime numbers so much.

arethuza 16y ago
I think it is just an odd way of expressing a hope that the Riemann hypothesis is true and therefore we are confident that we know a bit more about the distribution of prime numbers. I wouldn't read into it any more than that.
- gulbrandr 16y ago
  Thanks. I found some great answers in this Math.SE question: http://math.stackexchange.com/q/540/6831 http://math.stackexchange.com/q/540/6831
  - arethuza 16y ago
    You might want to have a look at RSA encryption - which is the most commonly used asymmetric encryption algorithm, it is built around some properties of prime numbers: http://en.wikipedia.org/wiki/RSA http://en.wikipedia.org/wiki/RSA
btilly 16y ago
In this case it is statistical regularity. :-) The primes act very much like they were a random set of numbers with n having probability 1/log(n) of being prime. (Mathematicians always mean "natural log" when they say log.) Except, of course, that this is obviously false. Because, for example, there is only one even prime. It is more accurate to say that the primes act very much like they were {2} plus a random set of odd numbers with n having probability 2/log(n) of being prime if it is odd. Except, of course, that this is obviously false. Because, for example, there is only one prime that is divisible by 3. One can continue refining this statement in the obvious way of special casing more and more primes. Other than the obvious corrections that come from these refinements, anything that you'd conjecture from this description is either known to be true, or believed to be true. The number of primes below n. The number of primes below n in an arithmetic sequence. The density of twin primes. And so on, and so forth. Now let's focus on the average of primes below n. (Mathematicians call that number pi(n).) If the primes all were independently random, then you'd expect that to be close to the sum, for i in 2 to n, of 1/log(i), which is approximately the integral from 2 to n of 1/log(x). The usual name for that integral is li(x). li(x) is approximately n/log(n). This estimate is known to be true. That's called the prime number theorem. One of many equivalent forms of the Riemann Hypothesis is that pi(n) - li(n) is O(sqrt(n)). From the "random prime" hypothesis we can see why this is reasonable. It turns out that for large n, (pi(n) - li(n))/sqrt(li(n)) should follow a standard normal distribution. From which it is easy to show that the Riemann Hypothesis should have 100% odds of being true.
- btilly 16y ago
  When I woke up and thought about this problem again, I realized that I didn't explain one detail. Why should (pi(n) - li(n))/sqrt(li(n)) follow a standard normal distribution? Here is why. pi(n) is the sum of a bunch of many independent random variables, each of which looks like a flip of a biased coin. If you pick the right version of the central limit theorem (see http://en.wikipedia.org/wiki/Lyapunov_condition http://en.wikipedia.org/wiki/Lyapunov_condition for the right version), it is clearly going to be approximately normal. Its average will be the sum of the averages, which is 1/log(2) + 1/(log(3) + ... + 1/log(n) which is going to be li(n) plus O(1). If n is large the li(n) term dominates. Its variance will be the sum of the variances of the individual random variables. The variance of a coin with probability x of turning up 1 is x(1-x). Therefore the sum of the variances is (1/log(2) - (1/log(2)2) + (1/log(3) - (1/log(3)2) + ... + (1/log(n) - (1/log(n)2) which is (modulo a O(1) error) the integral from 2 to n of 1/log(x) - (1/log(x))2 which is li(x) - O(n/log(n)2), which is dominated by the li(x) term. Therefore the average and variance of pi(n) are approximately li(x). So (pi(n) - li(n))/sqrt(li(n)) should have approximately a standard normal distribution.

btilly 16y ago

I can't ever read a claim that the Riemann Hypothesis is unsolved without putting a small asterisk beside that claim. See http://www.lrb.co.uk/v26/n14/karl-sabbagh/the-strange-case-of-louis-de-branges http://www.lrb.co.uk/v26/n14/karl-sabbagh/the-strange-case-o... for why.

freyrs3 16y ago
The proof has been checked and it contained errors. See: http://mathoverflow.net/questions/38049/what-exactly-has-louis-de-branges-proved-about-the-riemann-hypothesis/38057#38057 http://mathoverflow.net/questions/38049/what-exactly-has-lou...
- btilly 16y ago
  The cited paper that found holes is from before the proof discussed in the article I pointed. The update points to a more recent paper that is behind a paywall, so I can't find what it says.
  - thebooktocome 16y ago
    de Branges currently claims (as of September 2010) that he's fixed the problem pointed out by Li. There's supposed to be a pre-print in the works, but I haven't heard anything lately.
- hsmyers 16y ago
  So did the work of Andrew Wiles--- and instead of slamming the door on the effort support, suggestions and help came from all around until the effort was successful. Yes Andrew was probably a much more well-liked player, but that should have no bearing on scientific inquiry. The subject mathematician has a track record and is not considered (even by his obvious enemies) a crank. Makes you wonder what else is being suppressed...

deleted 16y ago

[deleted]

mckoss 16y ago

And for the JS heads - a prime number sieve in JavaScript: http://wiki.pageforest.com/#js-patterns/prime-sieve http://wiki.pageforest.com/#js-patterns/prime-sieve

harlowja 16y ago
And for a classic. http://alpha61.com/primenumbershittingbear/ http://alpha61.com/primenumbershittingbear/