Physics Forums

Physics Forums (http://www.physicsforums.com/index.php)
-   Linear & Abstract Algebra (http://www.physicsforums.com/forumdisplay.php?f=75)
-   -   The Riemann Hypothesis (http://www.physicsforums.com/showthread.php?t=98766)

-Job- Nov6-05 09:10 PM

The Riemann Hypothesis
 
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 :smile: )?

matt grime Nov7-05 06:07 AM

Consider the function

[tex] \zeta(s)=\sum_{n \in \mathbb{N}} n^{-s}[/tex]

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 Nov7-05 10:27 AM

Quote:

Quote by matt grime
..(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- Nov8-05 10:09 PM

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 Nov9-05 02:02 AM

Quote:

Quote by -Job-
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 Nov9-05 05:53 AM

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 Nov13-05 01:46 AM

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 Nov15-05 01:18 AM

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 Nov15-05 09:31 AM

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/st...298728,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 Nov15-05 12:40 PM

Quote:

Quote by 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?

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 Nov15-05 12:48 PM

Quote:

Quote by ComputerGeek
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 Nov16-05 07:11 AM

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 Nov16-05 01:52 PM

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.

shmoe Nov16-05 02:30 PM

The zeta function was initially studied because of the implications it has on the prime number theorem. Let [tex]\pi(x)[/tex] be the number of primes less than or equal to x and [tex]Li(x)=\int_2^x\frac{dx}{\log x}[/tex]. Then the prime number thoerem tells us that [tex]\pi(x)\sim Li(x)[/tex]. 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

[tex]\pi(x)=Li(x)+O(\sqrt{x} \log{x})[/tex]

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 Nov16-05 02:38 PM

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 Nov16-05 02:42 PM

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 Nov16-05 03:05 PM

Quote:

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

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, [tex]|Li(x)-\pi(x)|[/tex] that we'd like to show is small compared to the terms themselves. Since [tex]Li(x)[/tex] is about [tex]x/\log(x)[/tex], RH tells us that the error is about the square root of the main term (crudely), so small indeed in comparison.

Robokapp Nov23-05 01:58 AM

Quote:

Quote by matt grime
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?


All times are GMT -5. The time now is 12:41 PM.

Powered by vBulletin Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
© 2014 Physics Forums