Mathematician Claims Proof of Riemann Hypothesis 561
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."
Googlized HTML version (Score:3, Informative)
Failed proof (Score:5, Informative)
Ha! They've already found an error in the proof! All that he posted was his apology! [purdue.edu] :-)
Yes, I was actually confused at first. For the non-math geeks like myself, who are feeling stupid, look at definition 2a of apology [reference.com].He is very brave (Score:2, Informative)
Most of the paper appears to be history, and the results leading up to his proof. Only a few pages at the end make up the actual new proof, so the novel material is far shorter than 23 pages.
I wouldn't be surprised if there is a fairly final verdict on his proof very quickly. This is not like Wiles' proof of Fermat that was very long and nobody had the background to understand. This proof looks reasonably short and straightforward.
Cheers,
Ben Tilly
WTF? Mods? (Score:5, Informative)
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?
Re:Apology (Score:4, Informative)
There is no impact on crypto (Score:4, Informative)
Re:Impact on crypto? (Score:3, Informative)
So, in short, no, no help for cracking crypto based on primes...though the article does mention possible crypto applications down the line. I'm not sure what, exactly, those would be.
Re:Impact on crypto? (Score:4, Informative)
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.
Seems not-unlikely to be wrong (Score:5, Informative)
The same guy claimed [google.com] to have solved the same problem at least 4 years ago.
The guy has a reputation [google.com] for sometimes getting it wrong.
(Probably because he has published flawed proofs [google.com] of other well-known problems.)
He could be right, but I wouldn't get my hopes up.
Re:Impact on crypto? (Score:3, Informative)
Not the best explanation, I prefer this [amazon.com]
The Problem (Score:5, Informative)
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
Re:What are the consequences for cryptography? (Score:5, Informative)
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.
Re:Impact on crypto? (Score:4, Informative)
No. GRH implies that isprime() is in P (by bounding the cost of a strong pseudoprime test); but we already knew that, thanks to AKS.
Re:Impact on crypto? (Score:5, Informative)
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.
Re:Impact on crypto? (Score:5, Informative)
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.
Re:Proof of theory (Score:3, Informative)
Mathematicians tackle difficult problems all of the time, regardless of the (lack of) money involved.
I don't know why you say that interest in "theoretical" mathematical proof is waning. It certainly isn't where I come from. (And what is ultra-math??!)
Usage of "apology" (Score:3, Informative)
actual paper (Score:5, Informative)
So if his "proof" isn't obviously wrong, it'll likely take quite a while for the experts to verify.
Re:Seems not-unlikely to be wrong (Score:5, Informative)
Re:Seems not-unlikely to be wrong (Score:5, Informative)
However, a quick scan suggests that if his proof is indeed verified, it won't do what a lot of people want it to do: Quote from the article: "The proof of the Riemann hypothesis verifies a positivity condition only for those Dirichlet zeta functions which are associated with nonprincipal real characters. The classical zeta function does not satisfy a positivity condition since the condition is not compatible with the singularity of the function. But a weaker condition is satisfied which has the desired implication for zeros."
So I may be wrong, but it looks like he may have found ground on a restricted interpretation of the GRH (or Generalized Riemann Hypothesis), -ie concerning Dirichlet zeta functions which are associated with nonprincipal real characters only.
As for consequences, If GRH is indeed true, then e.g. the Miller-Rabin primality test is guaranteed to run in polynomial time.
Re:The Reimann Hypothesis (Score:3, Informative)
For influences on math, consider Dirac (crazy British scientist who predicted to existence of the positron) whose ideas led L. Schwartz, L. to write "Théorie des distributions. Tome I,II"; distribution theory has had a huge influence on analysis.
Re:verification (Score:1, Informative)
*Creating* proofs is the hard part, and was proven undecidable. But verifying ones that exist is not.
Melissa <3
"Apology" an old paper? (Score:4, Informative)
Cool background material (Score:5, Informative)
If nothing else check out the animation [ex.ac.uk].
mind-boggling
The Riemann Hypothesis for Non-Mathematicians (Score:1, Informative)
The Riemann hypothesis states that if this function:
sum from n=1 to infinity ((-1)^(n+1) / n^(x+iy))
equals zero, then x = 1/2 . x and y are variables; x+iy is a complex number normally labeled "z".
If you don't want to deal with complex numbers, you can use the equivalent statement about real numbers: If the following function:
(sum from n=1 to infinity ((-1)^(n+1) * cos(y*ln(n)) / n^x))^2 + (sum from n=1 to infinity ((-1)^(n+1) * sin(y * ln(n)) / n^x))^2)
equals zero, then x = 1/2 . The following URL is a picture of the above in normal notation so it's easier to read:
http://www.geocities.com/myriachan/riemann.png
Melissa <3
Re:WTF? Mods? (Score:1, Informative)
Uh, yeah. I'm going to assume that the thing you missed was "Monty Python and the Holy Grail." [imdb.com] Or, at least the opening credits.
Re:The Riemann Hypothesis for Non-Mathematicians (Score:1, Informative)
1. The function I showed was *not* the Zeta function. That's because the standard 1 + 1/1^z + 1/2^z +
2. The version not involving complex numbers is pretty easy to derive. Use "a^(b+c) = a^b * a^c", "e^ix = cos x + i sin x", "x^y = e^(y ln x)", and "cos^2 x + sin^2 x = 1", then separate out the real and imaginary parts. The square just acts as an absolute value here. A negative sign on the "sin" half is removed by the square/absolute value.
Melissa <3
The question, explained (Score:5, Informative)
First: complex numbers [wolfram.com], 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 [wolfram.com]. 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 [wolfram.com]. 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 [wolfram.com] 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 [wolfram.com] 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 [wolfram.com] suggests that they are... but until today nobody has been able to prove it.
Re:He is very brave (Score:2, Informative)
Re:Impact on crypto? (Score:2, Informative)
The truth (or falsity) of the Riemann Hypothesis is intimately related to the distribution of the primes. Specifically, if the RH is true, then the primes are distributed about as regularly as possible.[1]
Carl
[1] See, for example, equation (2) of Riemann Hypothesis [wolfram.com]
Re:Impact on crypto? (Score:5, Informative)
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).
background info on this guy (Score:2, Informative)
Re:Impact on crypto? (Score:2, Informative)
No, cryptosystems are based off of simple math based on a pair of very large pre-selected (read not random) prime numbers that make up your public and private key.
Cheers, Ben
Re:If there's one thing I know (Score:5, Informative)
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).
Re:Seems not-unlikely to be wrong (Score:2, Informative)
THE APOLOGY IS NOT THE PAPER! (Score:1, Informative)
Why people haven't believed him so far (Score:5, Informative)
The reasons why most specialists doubt that his approach can ever yield the result are well described in this paper [arxiv.org] 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.)Proof claimed to be invalid (Score:2, Informative)
Riemann Hypothesis Interview (Score:3, Informative)
Probably a hoax: (Score:4, Informative)
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
Much ado about nothing? (Score:5, Informative)
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
Re:The question, explained (Score:5, Informative)
Great Cthulhu help me, but I'm going to try and answer this for you.
We have natural numbers - 1,2,3,
And then we have Zero and once upon a time this disturbed people. You grew up with it, you're happy with it; but we can see that it was less intuitive than 1,2,3,
And yet, the discovery (or creation
Now perhaps at this point, you're nodding and saying 'yes, yes, I know that already.' If so, then good, because you've just understood the principle of a complex number. It's another abstraction that can't easily be represented in the real world (nuclear physicists shut up, please). And yet, it has very real use in making calculations.
If you're a programmer, think about how much code there is behind the scenes of a program to produce the result you want from it. Suppose that your program counts how many oranges people have given you. Maybe it has the line
for (i=0; i < oranges_owed; i++) {}
Well i isn't physically real, it doesn't represent a physical aspect of what you are modelling (the oranges) but it's useful. And in the same way, i is also useful, even if it's just part of a intellectual model.
For a mathematician: I think therefore i is.
The only thing remaining is to give you an example of how it is useful. Easily done - Quantum Physics. All of it.
Hope this helps, IASNAM (I Am Surprisingly Not...)
* Proof that 0x0=0:
Re:Impact on crypto? (Score:1, Informative)
Re:If there's one thing I know (Score:5, Informative)
----------------
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.
Re:The question, explained (Score:2, Informative)
This is fine as a proof that 0 x 0 = 0 once you know that 1 x 0 = 0. The proof (of either) is roughly as in your second and third lines:
a x 0 = a x (0 + 0) = a x 0 + a x 0
Cancelling a x 0 from both sides (which we may do, since we're in a group) gives a x 0 = 0.
Re:If there's one thing I know (Score:3, Informative)
So in practice, NP-complete problems can be solved (you can solve just about anything by just trying every single solution) but for very big instances you will need several times the age of the universe etc.
Several other posters in this thread seem to be mistaken about what the term actually means, but they were being so vague I thought I'd write this up.
Re:If there's one thing I know (Score:2, Informative)
Re:If there's one thing I know (Score:4, Informative)
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.
Re:If there's one thing I know (Score:4, Informative)
NP problems are problems that can be solved by a Nondeterministic Turing machine in Polynomial time. NP-Complete problems are the class of "hardest" problems in NP. All the usual suspects (Traveling Salesman, 3-SAT, SAT, ...) are proven
to be in NPC.
We know that we can solve NPC problems in exponential time (as we can simulate a non-deterministic Turing maschine on deterministic hardware with exponential overhead). What we do not know is if there is any smarter way. That is the P=?=NP question.
Well, not exactly (Score:4, Informative)
It is not proved; he is not at the top of his field; this "paper" will be quickly forgotten among professional mathematicians; and I doubt any professional mathematician is going over the proof with any sort of comb.
L. de Branges first achieved fame for proving the Bieberbach conjecture [wikipedia.org]. His proof went through strange and abstract methods. He went on the road to present his proof at various seminars in France, Russia, etc; IIRC a bunch of Russian students got very excited and basically rewrote his proof. Their new proof was much shorter and avoided the use of strange methods. Nowadays, their proof is remembered and his is not, but the proof still bears his name, since after all he was the first to come up with *some* kind of proof, and their proof did more or less come out of his.
So he deserves credit for that, and it was quite an achievement to prove the Bieberbach conjecture. But even then he was using unwieldy proofs with unnecessarily abstract methods.
For many years he has been claiming to have a proof of the Riemann Hypothesis. Professional mathematicians stopped listening a long time ago.
This guy is washed-up.
I whole-heartedly agree that this short article is hilarious, but I would like to add the adjective condescending. What kind of asshole apologizes for solving a problem? Does he think he lives on some higher plane, and therefore must take direct, personal responsibility for every aspect of our lives?
Look at how G. Perelman submitted his ideas on proving the Poincare conjecture [wikipedia.org] just a little while ago. He didn't waste anyone's time by rehashing the already-available history of the problem or its wider context in mathematics. Nor did he apologize for having an idea. Rather, he submitted his ideas for consideration, with the full awareness that there may have been a mistake.
de Branges is so full of crap, it makes me sick.
zach
Re:The question, explained (Score:3, Informative)
For example, try looking at the difference between n^n and the largest factorial less than or equal to it. This starts 1^1-1!=0, 2^2-2!=2, 3^3-4!=3,... and goes on 136, 2405, 6336, 460663, 13148416, 347503689,... which looks as if it is increasing. Keep going, and it still looks as if it is increasing, but keep going and after more than 4 million steps you are dealing with numbers with around 30 million decimal digits when it suddenly takes a small step down.
Re:If there's one thing I know (Score:4, Informative)
No, you're wrong. NP problems are, by definition, problems that can be solved in polynomial time by a nondeterministic Turing machine
Essentially this means that a Turing machine could solve the problem in polynomial time, if it had some magic 'oracle' which instructed it on the right computational path to follow for a given input.
Obviously there are problems out there that would require exponential time for even a nondeterministic Turing machine to solve. An example from the Wikipedia link I provided is finding the best move in a chess or Go game.
Such problems are not in NP, and proving P=NP would not suddenly give us algorithms for solving these problems deterministically in polynomial time.
However, most problems that are considered NP-Complete are not mathematically proven to be so.
What? Sorry, if there ain't a proof, it ain't NP-complete. There are a lot of problems that are described as "believed to be NP-complete", but that's different.