The Riemann Hypothesis

1. -Job-

1,132
I know this is one of the famous unsolved problems still hanging around. Could someone give me the "gist" of it, and what the implications are if it is solved one way or the other? I looked it up on Wikipedia but that didn't help me much. Has anyone any idea why it is so hard to solve (i imagine it's hard )?

2. matt grime

9,395
Consider the function

$$\zeta(s)=\sum_{n \in \mathbb{N}} n^{-s}$$

this is well behaved for all complex numbers s with the real part of s>1

By a process called analytic continuation we can extend this to an analytic function on all of the complex plane (with some isolated singularities, ie bits where it must tend to infinity, s=1 is such a point).

This is the zeta function.

The function can be shown to have zeroes at the negative integers, and that all other zeroes lie in the interval 0<re(s)<1 the so-called critical strip (it is a vertical strip in the complex plane).

The hypothesis of riemann is that all of these non-trivial zeroes, the ones in the strip, actually lie on the line re(s)=1/2

It is hard to prove, mainly because no one has a good idea of what to do to get a proof. Many attempts exist but none has come to fruition.

I suppose the most important implication of it being true is for the prime number theorem - it gives what the error term in the asymptotic approximation of the number of primes less than x in terms of the logarithmic integral. All these terms are easily googled and there are better placed people than me to explain it here.

Last edited by a moderator: Nov 13, 2005
3. shmoe

1,994
I just wanted to add that s=1 is the only singularity.

matt has given the basic rundown, what else would you like to know? You can try searching this forum as well, this topic has come up quite often. There's also quite a few recent pop sci books on the topic that try to explain it to a laymen.

4. -Job-

1,132
I'm sorry but i'm not familiar with some of the concepts, if someone could explain...
Looking at the Riemann Zeta Function i can't see what is meant by its zeros. I'm assuming the zeros are in the complex plane. What is a zero in the complex plane? Is it when the imaginary portion is 0?

5. Moo Of Doom

367
A zero on the complex plane is a complex number a + bi such that Zeta(a + bi) = 0. If the imaginary portion is zero, that is a real zero. The idea behind the RH is that all zeros except for the negative even integers are in the form 1/2 + bi.

6. matt grime

9,395
This notation is nothing to do with the Riemann Hypothesis, just maths. If f(t)=0 then t is called a zero of f. This is distinct from a root, root is usually kept for polynomials where t is a root of f if and only if f(x)=(x-t)g(x) for some other polynomial g.

7. Robokapp

218
I don't particularly get what this is about, but I do know a good website. hold on.

http://mathworld.wolfram.com/RiemannZetaFunction.html

This is it. I'm just a Calculus AB student...it looks to me like someone posessed by devil while jailed for life had a moment of creativity and began writing a code language of evil with no meaning at all...But that's my oppinion. Graph pretty interesting too...It makes no sense. I know it's a polar though.

Last edited: Nov 13, 2005
8. johnw188

21
I have a question about Riemann: I keep on hearing people say that if/when its proved its going to cause problems for online encryption. However, during my research I came across a distributed computing site calculating zeroes of the function, and they had some absurdly large number all on the 1/2 line. If the hypothesis was going to have any effect of this kind on RSA or what have you, wouldn't people have been able to apply it as if it were true in these situations and exploited it already?

9. shmoe

1,994
When de Branges announced his "proof" again last year there were a few newspaper articles about it like

http://www.guardian.co.uk/uk_news/story/0,3604,1298728,00.html

This one gives the entire quote by du Sautoy (enough to not be misleading). Some liked to include only the last couple sentences to make the part about bringing e-commerce to it's knees look more plausible without the qualifiers about how the methods used in the proof might be turned into something grander. I think this spawned much unwarrented paranoia.

As it is, there are no consequences of RH that I know of that will have devastating implications on cryptography. You're also correct that if say an extremely efficient factoring algorithm was known to work on the the truth of RH, people would probably just use this algorithm. It wouldn't matter if you had a proof or not, if RH was true such an algorithm would still work.

10. ComputerGeek

534
If the RH was proven, then it would mean that all primes would be known, so, yes, it would cause problems for current encryption methods.

We will have to move to a quantum entanglement type of encryption anyway when Quantum Computers are built because their sheer computing power would enable the prime factorization of any number to occur in mere seconds.

11. shmoe

1,994
RH has implications on the distribution of primes, it tells us that the error term in the prime number theorem is the best possible. It does not somehow mean "all primes would be known", for any reasonable interpretation of this statement I can think of. If you think otherwise, please explain what you mean by "all primes would be known".

I also invite you to give examples of the problems it would mean for cryptosystems. Assume RH is true and find me a hole in RSA (or encryption method of your choice).

12. matt grime

9,395
A proof of RH would not provide any such information as a complete list of primes, or a prime gerenating function. It would mean that the error term in the logarithmic estimate of pi(x) would be a square root, I seem to recall.

I think you may also misunderstand quantum computing as well - it will turn probabilistic algorithms into deterministic ones, it will not factor numbers 'in seconds' unless you mean 'a lot of seconds'

13. Robokapp

218
Okay...in english, putting aside the terminology, can you make the explanation at a highschool level? i'm very curious what the outcome of this "holy grail" will be to mathematics...but i'm interested in practical aplications...not in finding prime numbers with 100 digits.

14. shmoe

1,994
The zeta function was initially studied because of the implications it has on the prime number theorem. Let $$\pi(x)$$ be the number of primes less than or equal to x and $$Li(x)=\int_2^x\frac{dx}{\log x}$$. Then the prime number thoerem tells us that $$\pi(x)\sim Li(x)$$. A big question is just how good this approximation is. It turns out that the larger the zero free region of zeta we can prove, the smaller the error term we can get (the prime number theorem itself was first proven essentially by showing that the Zeta function has no zeros in the half plan Re(s)>=1). Ultimately, if we knew RH was true, we'd know

$$\pi(x)=Li(x)+O(\sqrt{x} \log{x})$$

Which turns out to be the best possible bound for the error term (this bound is also equivalent to RH).

That's the big application we want, a tighter control on the distribution of the primes. The prime number theorem is used in many corners of number theory and having a stronger bound for the error term will strengthen results.

By the way, finding primes with 100 digits and the like are really the most practical applications you'll find out of number theory and this is a honking important one if you like e-commerce and any kind of cryptography.

Last edited: Nov 16, 2005
15. matt grime

9,395
For the love of God, and what, the third or fourth time in this thread, knowing whether or not the RH is true will not help you write down any prime numbers of any size. (I can feel someone is about to come up with a contradiction, but I'll stand by the claim for now).

There is a link between the zeroes of the Riemann Zeta function and the error term in the prime number theorem which, let us remember is an *asymptotic estimate* of the number of primes up to x.

There are certain implications this has, and I know little about them and defer to shmoe, however most people who care about this stuff will often prove something assuming RH is true anyway.

16. matt grime

9,395
Actually, we should probably explain asymptotic.

f(x) is asymptotic to g(x) if the ration f(x)/g(x) tends to 1 as x tends to zero. In particular, whist good for heuristics, it doesn't actually say that we can in anyway use f(x) to obtain g(x) (even if we knew the way the error term behaved). For instance x^2+x is asmyptotic to x^2 but given one of them it's not very closely related in absolute terms to the other.

17. shmoe

1,994
I'm not too in touch with all the crypto applications, but I can't think of any primality tests based on RH or that would speed up given RH so I think your statement is correct.

However the Rabin-Miller primality test, which returns either "probably prime" or "definitely composite", can be made into a deterministic polynomial time algorithm if the generalized riemann hypothesis is true, meaning the Dirichlet L-functions have no zeros to the right of the critical line. I'm not positive but I think it ends up faster than the AKS polynomial time algorithm (which I believe is still not used in practice as it's still slower than other algorithms in the ranges used). Again, crypto ain't exactly my thing so I might be off (and welcome any corrections). I also don't know if GRH will be proven at the same time as RH (assuming it is eventually), but I'd expect it would follow close behind (compare the PNT followed by the PNT for arithmetic progressions, etc)

Good idea explaining what asymptotic means. What I've refered to as the "error term" in the prime number theorem is the "absolute error" of the approximation, $$|Li(x)-\pi(x)|$$ that we'd like to show is small compared to the terms themselves. Since $$Li(x)$$ is about $$x/\log(x)$$, RH tells us that the error is about the square root of the main term (crudely), so small indeed in comparison.

Last edited: Nov 16, 2005
18. Robokapp

218
I need to ask you though...assuming it is Right and there turly are 1/2 whatever whaterevers in whatever...what will it do for mathematics? SOmething with error in finding prime numbers, but...how important is it to know if RSAinfinity has two prime numbers or not? I don't get its applications at all. I mean...it's a "holy Grail", but WHY?

19. matt grime

9,395
You are using the wrong metric to assess how interesting something is.

This is a problem that has been puzzling mathematicians for a hundred years. It is one of the oldest and richest open questions there is. We arguably don't even know how to start proving it: that's why it is a Clay Millenium prize: it is thought it will take some revolutionary new idea to prove it.

And for the umpteenth time it will not tell you the absolute error when calculating pi(x), it tells you an O( ) value; it has no (obvious) way of producing prime numbers or telling you anything exact about prime factors. That is a myth built up in the press and is completely off the radar. Remember my example: x^2 and x^2+x are asymptotically equivalent Yet there is an error of x when estimating x^2 using one instead of the other. That's big. Now, in the prime number theorem even with RH the error is O( ) of something, of the order of, it is only an estimate of the error, one that is really quite big AND uncertain.

Last edited: Nov 23, 2005
20. shmoe

1,994
We've made the implication in the prime number theorem explicit. I'll stress it once again- this doesn't "produce primes".

What is "RSAinfinity" supposed to be? If you're refering to the RSA challenge numbers, we know they all are the product of two primes. We know this because the folks at RSA who made them told us so. RH has no bearing on whether they lied about that or not.

Look at the prime number theorem again. Unconditionally we can't even get an error term of the form $$O(x^{1-\delta})$$ for a fixed $$\delta >0$$. We can still prove pi(x) is asymptotic to li(x), but the error term is terrible compared to what is true on RH. It (and the corresponding versions for related L-functions) has uses all over number theory, but the prime number theorem is the simplest to understand. Primes are incredibly important to number theorists, and there distribution, pi(x), is important in many areas. RH will greatly increase our understanding of pi(x).

The resolution of RH isn't going to have a noticible effect on the general public. But heck, the general public doesn't even care that there are infinitely many primes so they are not a judge of what a mathematician deems important.

Last edited: Nov 23, 2005