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

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 socalled critical strip (it is a vertical strip in the complex plane). The hypothesis of riemann is that all of these nontrivial 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. 
Quote:
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. 
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? 
Quote:

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)=(xt)g(x) for some other polynomial g.

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

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 ecommerce 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. 
Quote:
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. 
Quote:
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). 
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' 
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.

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 ecommerce and any kind of cryptography. 
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. 
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. 
Quote:
However the RabinMiller 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 Lfunctions 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. 
Quote:

All times are GMT 5. The time now is 10:38 AM. 
Powered by vBulletin Copyright ©2000  2014, Jelsoft Enterprises Ltd.
© 2014 Physics Forums