PDA

View Full Version : Mathematics Institute Millennium Problems



Rincewind
20-03-2010, 03:03 PM
First Clay Mathematics Institute Millennium Prize Announced Today

Prize for Resolution of the Poincaré Conjecture Awarded to Dr. Grigoriy Perelman

Read more here... http://www.claymath.org/poincare/index.html

Of course this is old news and the world media has probably dealt with Perelman a couple of years ago. But on March 18 the Clay Institute officially announced the prize for proving the Poincaré Conjecture has been awarded.

Perelman refused the Fields Medal and as far as I knew also eschewed the US$1M prize from the Clay Institute. So I don't know if that is changed or is the Institute is just announcing officially that they will not accept any other claims for proving the conjecture.

Either way, there are still six to go:


Birch and Swinnerton-Dyer Conjecture
Hodge Conjecture
Navier-Stokes Equations
P vs NP
Riemann Hypothesis
Yang-Mills Theory


Any bets on which will be the next to fall and when?

arosar
23-03-2010, 05:15 PM
I'm not really a math person, but I always find such mysteries really interesting. Any chance you can give us a synopsis on these conjectures?

Thanks.

AR

Rincewind
23-03-2010, 06:38 PM
I'm not really a math person, but I always find such mysteries really interesting. Any chance you can give us a synopsis on these conjectures?

I only really have a passing interest in three of them. The Navier-Stokes equations, P vs NP, and the Riemann Hypothesis. The first because I should the third because it is fascinating and P vs NP because computational problems are interesting maybe due to my previous life.

I can try to give a potted synopsis of these three for a non-mathematical audience but it will take some preparation. Check back in this thread over the next week or so.

AzureBlue
23-03-2010, 07:07 PM
Yeah, have a shot at the Riemann :) It's pretty famous but no one has solved it as of yet, right?

Rincewind
29-03-2010, 05:42 PM
This is really about finding out something about the distribution of the prime numbers.

For the last couple of hundred years mathematicians have noticed that the distribution of primes in the natural numbers is locally random. For example, looking at the first few primes we have...

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ...

There is a pattern (apart from the first few the last digit has to be a 1, 3, 7, or 9. However looking further along it is not so easy to tell if say

2351, 2353, 2357 or 2359

are prime. As it turns out 2351 and 2357 are prime, the other two are 13x181 and 7x337. So looking at specific cases (locally) a pattern is hard to discern.

However, globally, the number of prime numbers less than a particular number has been looked at and shown to be very close to n/ln(n). So for example, we know the number of primes less than 1,000 is 168, and 1000/ln(1000) is around 145. It's not an exact figure but asymptotically in the limit of n approaching infinity, the relative error approaches zero.

As an aside, there is a better approximation which relates to the continuous integral from 2 to n of the reciprocal of ln(x), this was the principle matter that Riemann was interested in showing in his paper which lead to the statement known as the Riemann hypothesis. Unfortunately his proof was flawed (it has been patched up since then) and by the way for n = 1000 this integral has a value of around 176.56.

So anyway, this is a bit of a mystery. We know the asymptotic pattern of prime numbers for n approaching infinity but locally no pattern is known.

How does this relate to the Riemann hypothesis?

Riemann was interested in prime distributions and to prove what he had shown he defined a new function which he denoted with a zeta as an infinite sum as

ζ(s) = sum of all 1/n^s for n = 1, 2, 3, ....

So zeta of 2 would be the sum of the reciprocals of the perfect squares, that is

ζ(2) = 1/1 + 1/4 + 1/9 + 1/16 + 1/25 + ... (We know this particular sum converges to the value of approximately 1.644934068...)

However, the argument s is not necessarily restricted to purely real numbers. Riemann was interested in extending s into the complex plane (complex numbers have two components, the real and imaginary parts and may be written s = x + iy, when x is the real part x=Re(s), y is the imaginary part y=Im(s), and i is the square-root of -1). The sum definition given above really only works for s where the real part is greater than 1, but by a process called continuation, this can be extended to (almost) the entire complex plane (there is a simple pole at s=1, where ζ(1)= 1 + 1/2 + 1/3 + 1/4 + ... which is called the harmonic series and is known to diverge).

So Riemann could show that ζ(s)=0 when s is a negative integer, these are known as the trivial roots of zeta. However apart from these he could also prove that any other zeroes must lie in the "critical strip" which means the real part of s lies between 0 and 1. Furthermore, he could prove that the roots are distributed symmetrically about the line Re(s)=1/2.

Finally what Riemann did was to look at the first few roots of ζ(s)=0 the critical strip and noticed that they had Re(s)=1/2. So rather than being pairs located symmetrically about Re(s)=1/2 the two pairs were equal (repeated roots) and they lay on the line Re(s)=1/2 exactly.

His famous final comment was roughly, "these three roots lie on the line Re(s)=1/2 and I suspect all non trivial roots lie on this line but I haven't a proof for this as yet". This statement has become known as the Riemann hypothesis.


So why do we care? Well it turns out that this is an important question because the size of the error between the number of primes less than n and n/ln(n) (or more precisely that continuous integral mentioned above) is related to the question of all roots of zeta(s) lying on Re(s)=1/2.

Why are prime numbers important? Well apart from being fundamental to our understanding of numbers in general, prime numbers are also an integral part of most computer security systems. The security systems that electronic trading is based on relies on the fact that it (currently) takes a long time to factor large numbers down to their prime factors. The more we discover about prime numbers the less secure these methods might be and it will provide vital pointers into the way new encryption methods will have to work to maintain a virtually unbreakable security.

A proof of the Riemann hypothesis does more than just give us a better idea on the error in the prime number theorem. It has found to have implications in other fields such as the growth of arithmetic functions, and more esoteric ideas called the Lindelöf hypothesis and the Large prime gap conjecture. But I don't know so much about those so check out the wiki pages if you want to find out more.


So that wraps up a brief spray on the Riemann hypothesis. Hopefully it wasn't too wrong. Thanks to Google and Wiki, Maple for some numerical and factorisations and H. M. Edwards book Riemann's Zeta Function, which I didn't refer to directly very much but most of my recollections here are based on what I could remember from a more careful reading of that book. The correct parts above are due to others but all the mistakes are entirely mine and I apologise in advance for them all.

Ian Murray
31-03-2010, 09:13 PM
Not to mention their significance in communicating with extraterrestrials, as per Jodie Foster in Contact

Memorable quotes:
Ellie Arroway: [listening to the message] Those are primes! 2,3,5,7, those are all prime numbers and there's no way that's a natural phenomenon!

Ellie Arroway: So what's more likely? That an all-powerful, mysterious God created the Universe, and decided not to give any proof of his existence? Or, that He simply doesn't exist at all, and that we created Him, so that we wouldn't have to feel so small and alone?

Ellie Arroway: [to a group of children] I'll tell you one thing about the universe, though. The universe is a pretty big place. It's bigger than anything anyone has ever dreamed of before. So if it's just us... seems like an awful waste of space. Right?

Capablanca-Fan
18-06-2010, 02:21 PM
A Different Kind of Multiplication (http://www.phy6.org/outreach/edu/roman.htm)

(How the Romans multiplied by inadvertently using binary)

Rincewind
18-06-2010, 02:59 PM
A Different Kind of Multiplication (http://www.phy6.org/outreach/edu/roman.htm)

(How the Romans multiplied by inadvertently using binary)

It's an interesting piece and while I assume many people would use that method without knowing why it worked (in much the same way some people do long division without knowing why it works). However, I suspect the method itself was not found by trial and error.

While the Romans are not generally known as great mathematicians, the Greeks and Arabs before them were, and the Roman's were not above using the ideas from conquered people if it suited their purpose.

Rincewind
11-08-2010, 01:00 PM
Vinay Deolalikar has distributed what he is claiming to show that P does not equal NP. If accepted this will be a solution to another of the Clay Institute's Millennium problems - and qualify him for the $1M prize.

For more details check out

Has the Devilish Math Problem “P vs NP” Finally Been Solved? (http://blogs.discovermagazine.com/80beats/2010/08/10/has-the-devilish-math-problem-p-vs-np-finally-been-solved/)

The process of checking and possible strengthening of the proof may take some time but if basically sound it is a big result in the field of computational mathematics.

New Scientist article for the same

P ≠ NP? It's bad news for the power of computing (http://www.newscientist.com/article/dn19287-p--np-its-bad-news-for-the-power-of-computing.html)

Oepty
15-08-2010, 08:17 PM
Vinay Deolalikar has distributed what he is claiming to show that P does not equal NP. If accepted this will be a solution to another of the Clay Institute's Millennium problems - and qualify him for the $1M prize.

For more details check out

Has the Devilish Math Problem “P vs NP” Finally Been Solved? (http://blogs.discovermagazine.com/80beats/2010/08/10/has-the-devilish-math-problem-p-vs-np-finally-been-solved/)

The process of checking and possible strengthening of the proof may take some time but if basically sound it is a big result in the field of computational mathematics.

New Scientist article for the same

P ≠ NP? It's bad news for the power of computing (http://www.newscientist.com/article/dn19287-p--np-its-bad-news-for-the-power-of-computing.html)

Although this is so far above my head it is not measurable it appears that this proof is seriously flawed. At least that is what I think Terrence Tao and others like him are saying. They also appear to be saying that the way the proof is written makes it hard to understand.
Scott

Kevin Bonham
15-08-2010, 10:10 PM
One observer is so convinced the proof is wrong he has offered to pay an extra $200,000 if it is correct!

Rincewind
17-08-2010, 12:53 PM
This is what I'm hearing too. The proof is interesting but in the end it probably doesn't prove what the author is claiming.