What is the Riemann Hypothesis and why is it so difficult to solve?

[-Job-]

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 )?

 

[matt grime]

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.

 

[shmoe]

..(with some isolated singularities, ie bits where it must tend to infinity, s=1 is such a point).

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.

 

[-Job-]

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?

 

[Moo Of Doom]

What is a zero in the complex plane? Is it when the imaginary portion is 0?

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.

 

[matt grime]

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.

 

[Robokapp]

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.

 

[johnw188]

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?

 

[shmoe]

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.

 

[ComputerGeek]

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?

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.

 

[shmoe]

If the RH was proven, then it would mean that all primes would be known...

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).

 

[matt grime]

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'

 

[Robokapp]

Okay...in english, putting aside the terminology, can you make the explanation at a high school 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.

 

[shmoe]

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.

 

[matt grime]

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.

 

[matt grime]

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.

 

[shmoe]

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).

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 referred 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.

 

[Robokapp]

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.

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?

 

[matt grime]

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.

 

[shmoe]

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,

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

but...how important is it to know if RSAinfinity has two prime numbers or not?

What is "RSAinfinity" supposed to be? If you're referring 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.

I don't get its applications at all. I mean...it's a "holy Grail", but WHY?

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 &gt;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.

 

[-Job-]

Its solution may also be useful in solving other problems, it's another tool to add to the math belt.

 

[matt grime]

Well, most people who need RH to be true for their results tend to assume it is already, indeed a lot of maths I am this area assumes that GRH is true, and there is no reason not to if it helps you: all results are only based upon some hypotheses anyway.

 

[-Job-]

Is there a possibility that this is an unsolvale problem? Being in the area of Computer Science I've come across unsolvable problems such as the "Halting Problem".

 

[matt grime]

Of course it's a possibility. Is it likely to be is a different matter entirely. I'd would say no: it is solvable and it is true. To paraphrase jon alperin: the evidence is good enough that if it were a capital case we could hang it. he was talking about another conjecture at the time.

the correct version of RH for certain L functions is known to be true, the zeroes up to some astronimical point are in the right place, some strictly positive proportion are on the line and it damn well ought to be true.

 

[shmoe]

I wouldn't say number theorists assume RH is true so much as there are many conditional results based on it. You'll often see papers with "we know undconditionaly for this problem that Blah is true, assuming RH we can prove Blech, in the paper we'll improve Blah but fall short of Blech". Sometimes "Blech" can be exceeded unconditionally, RH isn't the heaviest hammer in the box. If they use a result that's dependent on RH, it's always mentioned that it's a conditional result.

I don't know what happens in the programming applications though. Do people actually implement algorithms whose correctness relies on RH or other unproven hypothesis? I'm not sure.

By "unsolvable" do you mean in the sense of one of Goedel's theorems? I can't claim to fully understand them, but I thought this sort of thing won't apply to statements that can be proven false with a counter example. It's certainly possible it's unsolvable in the sense that we humans will never manage to resolve it one way or another.

 

[matt grime]

to clarify, when I say people often assume RH, i don't mean that they simply take it as obviously true but lacking a proof, but that they write statements as shmoe states: assuming RH we have this... Indeed you van do better sometimes without RH. Can't recall the situation but there was a speaker here 2 years ago who improved some bound with RH to a better bound without RH.

 

[fourier jr]

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?

from what little I've read about it, gauss' prime number theorem says the number of primes less then an integer n is approximately n/ln(n). it's pretty close to the actual number pi(n) if you count them up by hand. what riemann did was plug complex variables into euler's zeta function (& got riemann's zeta function) & using that somehow he got an EXACT formula for the number of primes less than n. whether or not this is true depends on whether or not all the (nontrivial) zeros of the zeta function have real part =1/2; that's the riemann hypothesis. (i think that's all true :shy: )

 

[shmoe]

to clarify, when I say people often assume RH, i don't mean that they simply take it as obviously true but lacking a proof, but that they write statements as shmoe states:...

That is what I thought you had meant, but I didn't want to rule out the possibility that you knew something about programming applications say, and if unproven hypotheses are (ab)used in practice.

what riemann did was plug complex variables into euler's zeta function (& got riemann's zeta function) & using that somehow he got an EXACT formula for the number of primes less than n. whether or not this is true depends on whether or not all the (nontrivial) zeros of the zeta function have real part =1/2; that's the riemann hypothesis. (i think that's all true )

Riemann obtained an exact expression for pi(x), the so-called explicit formula, that is true regardless of the truth of RH. The "defect" of this exact form is it involves an infinite sum over the nontrivial zeros of zeta, making it hard to work with since we don't know exactly where they are. It's the main tool that allows us to translate from locations of the zeros to an error term in the prime number theorem- the closer the zeros are to the critical line, the smaller we can guarantee the sum over these zeros is.

see https://www.physicsforums.com/showthread.php?t=88468&highlight=explicit+formula for a little more on the explicit formula

by the way, Gauss later conjectured the logarithmic integral version of the prime number theorem, which is more accurate in absolute terms (though asymptotically the same) as x/log(x)

 

[eljose]

I gave a real potential that generated all the NOn-trivial roots of \zeta(a+is) in the form:

V(x)=\int_{-\infty}^{\infty}dxR(x,n)[g(n)+g(n)*+i(2a-1)B(n)-E_{n}^0]

where E_{n}^0, B(n) are real g(n) can be complex a is real and R(x,n) is real this potential comes from the fact that s and s*+i(2a-1) are roots (No trivial ones) of the zeta function evaluated at a+is,set a=1/2 and you get RH..i don,t want controversy so i will kindly solve any doubts of my potential.

 

[Lukas_23]

It's importance comes from the fact that if it is true primes are pseudo-random and we will never find a pattern. Also, hundreds of papers are dependent on it and if it is proved they automatically become theorems. Like I read somewhere, "while before mathematicians battled with spears, once proved they will have a tank instead".

The correct number of primes π(x) is given by the Riemman zeta function if we add all the zeros. They are infinite, as proved by Hardy which means we will never get the exact correction.

Is there a statistical way to get how many zeros are required to get into accuracy more than 1 and give whether it is under or overestimation and round up appropriately to find the actual π(x)?

Since if π(x) - π(x-1) = 1 it means x is a prime which woud mean we can use the hypothetical exact correction to find a new prime.

The question is how much work does it need and if it is more efficient than other methods so as to be worth it.