Slashdot Mirror
Mathematician Claims Proof of Riemann Hypothesis
TheSync points to this press release about a Purdue University mathematician, Louis de Branges de Bourcia, who claims to have "proven the Riemann hypothesis, considered to be the greatest unsolved problem in mathematics. It states that all non-trivial zeros of the zeta function lie on the line 1/2 + it as t ranges over the real numbers. You can read his proof here. The Clay Mathematics Institute offers a $1 million prize to the first prover."
Ha! They've already found an error in the proof! All that he posted was his apology! :-)
Yes, I was actually confused at first. For the non-math geeks like myself, who are feeling stupid, look at definition 2a of apology.Apology - 2: a formal written defense of something you believe in strongly
This should at most have earned a "Funny", or is there something I'm missing here?
Note to mods: Mod parent funny, not interesting! This is a play off a quote from the beginning credits sequence in Monty Python and the Holy Grail. As for the pdf link, it's the first link in the purdue page referenced in the article. RTFA, people!
Shameless self promotion
The Riemann Hypothesis, among other things, implies that the Prime Number Theorem is off in the distribution of primes by no more than O(sqrt(n)*log(n)). However even without the full result, we already had very good error bounds for the approximation of the prime number theorem for "small" numbers, including numbers far larger than any which come up in cryptography.
The art of cryptography can be summed up as: Easy to encode, but hard to decode.
Prime numbers are easy to multiply together. Little CPU needed.
But it's hard to do the reverse: Factor a big number into two separate prime numbers. Lots of CPU needed.
It's based on that principle.
Sorry to burst the bubble, but some usenetting shows:
The same guy claimed to have solved the same problem at least 4 years ago.
The guy has a reputation for sometimes getting it wrong.
(Probably because he has published flawed proofs of other well-known problems.)
He could be right, but I wouldn't get my hopes up.
The problem is simple enough to understand, assuming you know some math basics. As most of you know, any function f(X) where f(Xo)=0 is said to have a zero at Xo. For functions of complex numbers f(z) where z=x+iy and x,y are real numbers, you obviously have the function taking on different values for every x and y, so the zeros can be anywhere on the x-y plane. For the zeta function, "trivial zeros" occur at the negative even integers (z=-2+i0,-4+i0,...) and also at points on the line x=1/2 (i.e 1/2 +iy for certain y).The Riemann Hypothesis says that all zeros that aren't negative even integers lie on this line.
Most of you have who have taken basic calculus courses have probably seen a simplified definition of the zeta function for real intergers greater than 1. when z=n, a natural number, the zeta function reduces to the infinite series Zeta(n)= SUM (k=1-->inf) 1/k^n
Nope, probably not.
Most mathematicians felt that the Riemann Hypothesis was true so that this view has been taken into consideration into mathematics for a long time. Perhaps if he developed some new methods for playing with numbers in the proof, but it doesn't seem like it to me.
There's a ton of math papers that begin with "Assume the extended riemann hypothesis...".
At least that's my guess.
It's actually a little more complex than that.
Riemann was investigating the distribution of prime numbers. Along the way he devised (discovered?) the Zeta Function, which describes with considerable accuracy the distribution of prime numbers. While working with the Zeta Function, he discovered an interesting property: It appeared that all the non-trivial zeroes of the function had a real part of one-half. However, since this property of the function was not related to the prime-distribution work he was doing, he did not bother to prove this apparent property, which came to be known as the "Riemann Hypothesis" (presumably, once it is proven it will be known as the Riemann Theorem, or some such).
Thus, the Riemann Hypothesis is in fact tangential to (and possibly unrelated to) the distribution of prime numbers. Riemann's notes on the Zeta Function, regarding his work on prime distribution, are pretty explicit about this.
Any sufficiently well-organized community is indistinguishable from Government.
does it's proof have any impact on crypto?
No. Almost all mathematicians have assumed for years that GRH is true anyway; proving it would mean that all those footnotes ([1] Under the assumption of the Riemann Hypothesis) could be removed, but that's the only practical effect it would have.
Tarsnap: Online backups for the truly paranoid
The 23 page "apology" is not the actual purported proof, contrary to what the article and press release say. The actual proof is the manuscript "Riemann zeta functions", the third link on de Branges' home page, which weighs in at 124 pages!
So if his "proof" isn't obviously wrong, it'll likely take quite a while for the experts to verify.
A cool overview of why this is such an interesting hypothesis.
If nothing else check out the animation.
mind-boggling
First: complex numbers, explained. You may have heard the question asked, "what is the square root of minus one?" Well, maths has an answer and we call it i. i*i = -1. If the real number line ...-4, -3, -2, -1, 0, 1, 2, 3, 4... is represented as a horizontal line, then the numbers ...-4i, -3i, -2i, -i, 0, i, 2i, 3i, 4i... can be thought of as the *vertical* axis on this diagram. The whole plane taken together is then called the complex plane. This is a two-dimensional set of numbers. Every number can be represented in the form a+bi. For real numbers, b=0.
Right. Now the Riemann Zeta Function is a function/map (like f(x)=x^2 is a function) on the complex plane. For any number a+bi, zeta(a+bi)will be another complex number, c+di.
Now, a zero of a function is (pretty obviously) a point a+bi where f(a+bi)=0. If f(x)=x^2 then the only zero is obviously at 0, where f(0)=0. For the Riemann Zeta Function this is more complicated. It basically has two types of zeros: the "trivial" zeroes, that occur at all negative even integers, that is, -2, -4, -6, -8... and the "nontrivial" zeroes, which are all the OTHER ones.
As far as we know, *all* the nontrivial zeroes occur at 1/2 + bi for some b. No others have been found in a lot of looking... but are they ALL like that? The Riemann Hypothesis suggests that they are... but until today nobody has been able to prove it.
qntm.org
Actually, as with most things Euler was the first to study it. The zeta function is also the simplest of a class of functions that Dirichlet studied Dirichlet L-series. There is also a Generalized Riemann Hypothesis that states that no Dirichlet L-series has zero with real part greater than 1/2.
The Riemann Hypothesis is more than tangential to the study of the distribution of primes. There is a function derived from the distribution of the primes that can be expressed in terms of the non-trivial zeros of the zeta function. The Prime Number Theorem is also equivalent to the statement that the zeta function has no zeros with real part 1. The Generalized Riemann Hypothesis implies the weak form of Goldbach's conjecture (i.e. that any odd number greater than 7 can be expressed as the sum of three odd primes).
My only political goal is to see to it that no political party achieves its goals.
Not to spoil your joke or anything, but actually, AFAIK, NP-complete problems are perfectly solvable. The problem is how long it takes to solve them in general (a certain instance of a problem could prove easy). They cannot be solved deterministically in polynomial time (i.e., quickly).
The reasons why most specialists doubt that his approach can ever yield the result are well described in this paper from 1998:
(i.e., despite the name, the "generalized RH" proved by de Branges actually did not include the standard RH as a special case.)This is...
O
U
T
R
A
G
E
O
U
S
!
mathworld.wolfram.com
Riemann Hypothesis "Proof" Much Ado About Noithing A June 8 Purdue University news release reports a proof of the Riemann Hypothesis by L. de Branges. However, both the 23-page preprint cited in the release (which is actually from 2003) and a longer preprint from 2004 on de Branges's home page seem to lack an actual proof. Furthermore, a counterexample to de Branges's approach due to Conrey and Li has been known since 1998. The media coverage therefore appears to be much ado about nothing
The proof (or, better said, the sketch of the proof) actually starts at the end of page 21, very close to the last page. The original work is actually pretty hard to find since it is buried in so many unrelated side notes.
/. until now :-)
Here is the general outline:
1) At the end of page 19 he mentions that "The positivity condition which is introduced implies the Riemann hypothesis if it applies to Dirichlet zeta functions."
2) After some introduction of the quantum gamma functions that lasts two pages, the actual proof starts at the end of page 21 with the phrase "A quantum gamma function is obtained when is nonnegative. A proof of positivity is given from properties of the Laplace transformation."
3) The proof ends in the middle of page 23 with the a verification that W(z) is a quantum gamma function with quantum q = exp(-2*pi), obtained from a spectral theory of the shift operator.
Overall this is just a very brief sketch of the whole proof.
BTW, to add gas on fire, here is an exceprt from mathworld.com, which surprisingly was missed by
http://mathworld.wolfram.com
Riemann Hypothesis "Proof" Much Ado About Noithing (sic)
A June 8 Purdue University news release reports a proof of the Riemann Hypothesis by L. de Branges. However, both the 23-page preprint cited in the release (which is actually from 2003) and a longer preprint from 2004 on de Branges's home page seem to lack an actual proof. Furthermore, a counterexample to de Branges's approach due to Conrey and Li has been known since 1998. The media coverage therefore appears to be much ado about nothing.
The counterexample to Brangles approach can be reached here: http://arxiv.org/abs/math.NT/9812166
Don't try to use the force. Do or do not, there is no try.
It would appear that mathworld.com agrees with you...
----------------
Riemann Hypothesis "Proof" Much Ado About Noithing
A June 8 Purdue University news release reports a proof of the Riemann Hypothesis by L. de Branges. However, both the 23-page preprint cited in the release (which is actually from 2003) and a longer preprint from 2004 on de Branges's home page seem to lack an actual proof. Furthermore, a counterexample to de Branges's approach due to Conrey and Li has been known since 1998. The media coverage therefore appears to be much ado about nothing.
Slashdot: where don knuth is an idiot because he cant grasp the awesome power of php
The definition of NP-Complete has nothing to do with whether the problem can be solved in polynomial time.
...is one of *two* equivalent definitions of the class NP. The other is:
Not quite correct, because:
The set NP is defined as all problems whose solutions can be verified in polynomial time
"Set of all problems which can be solved in polynomial time by a nondeterministic Turing Machine."
So the question "Does P equal NP?" is also the question "Does an NTM have the same computional power(in time) as a TM, or does it have more?" (It is already known that as far as decidiblity is concerned, TMs and NTM are equivalent.)
Because of the way the proofs have been constructed, if you can solve any of the NP-Complete problems in polynomial time, you can solve all of them in polynomial time.
Some more detail here:
An NP-hard problem is a problem to which any problem in NP can be reduced in polynomial time.
(Essentially, it can be used as a subroutine for any NP problem, with only a polynomial number of calls. Thus a solution to it is a solution to any problem in NP.)
An NP-complete problem is one that is:
1. NP-hard
2. In the set NP.
Thus if a polynomial-time solution exists to an NP-complete problem, then P=NP, because a polynomial number of calls to a function that terminates in polynomial time is O({polynomial}*{polynomial}) = O({polynomial}) .
Please note, however, that not all NP-hard problems are NP-complete.
NOTICE: This notice will appear at the bottom of all my slashdot posts.