Mathematical Problems For The New Age

Thanks to David A. Madore who wrote to us regarding seven math problems that have rewards of one million dollars. The project is being done by the Clay Mathematics Institute, and is modeled after Hilbert's list for the 20th century which was announced also in Paris, but in 1900. Read more for more information from David.

"The Clay Mathematics Institute has just (May 24-25, 2000) organized a big meeting in the Collège de France in Paris, to celebrate the hundredth anniversary of the International Congress of Mathematicians meeting in August 1900 (also in Paris) during which the great David Hilbert (a serious candidate for the greatest mathematician of all times, perhaps after Gauss and Euler) announced his list of 23 celebrated problems for the XXth century.

First the Clay Mathematics Awards were given, one two Laurent Lafforgue for his proof of the local Langlands correspondence, and one to Alain Connes for his work on von Neumann factors and noncommutative geometry. Then a list of seven problems for the third millennium was revealed by John Tate and Sir Michael Atiyah. If you solve any of the following problems, you win $1,000,000.

The problems are:

• The Riemann hypothesis: prove (or disprove!) that all the non-trivial zeroes of the Riemann zeta function lie on the critical axis (real part of s = one half).
• The conjecture of Birch and Swinnerton-Dyer: prove (or disprove!) that the algebraic rank of an elliptic curve over Q (the rank of the group of its rational points) equals its analytic rank (the order of cancellation at 1 of its L function).
• Is P=NP? In other words, is it possible for a deterministic Turing machine to solve in polynomial time problems which are solved by a nondeterministic Turing machine in polynomial time, or, on the contrary, is the traveling salesman problem truly "hard" in the sense that no polynomial-time algorithm exists to solve it?
• The Poincaré Conjecture: prove (or disprove!) that any simply connected topological manifold of dimension 3 is homeomorphic to the three-sphere.
• The Hodge Conjecture: prove (or disprove!) that on projective algebraic varieties, all Hodge cycles are rational combinations of algebraic cycles.
• Yang-Mills theory: develop a mathematical foundation for the quantum theory of Yang-Mills fields; specifically, account for the "mass gap" hypothesis.
• Navier-Stokes equations: prove (or disprove!) that the Navier-Stokes equations have smooth solutions for all positive times, given reasonable initial conditions.

Naturally, if you solve any of these, you get to be famous, too.

During the meeting we even got to hear a recording of Hilbert's voice speaking his famous "Wir müssen wissen; wir werden wissen" ("We must know; we shall know") just a hundred years before. It's also engraved on his tomb in Göttingen. Cool. "

Comments

Most of these are much harder than they seem.

[Uruk]

Taking number theory in college and persuing math in my spare time, I've found out that sometimes the ones that look the easiest are actually the most nasty, bastardly, evil problems you've ever seen. Some may look easy, but you have to figure there's a reason why there's a $1 million prize on each question.

Some of the toughest ones are the "prove or disprove" type problems - for example, before fermat's last theorem was proven, (some people are sticklers for long periods of peer review and say that it hasn't been officially proven yet) it was pretty easy with the use of computers to prove that fermat's last theorem held for all integers up through some ungodly number. But proving through "some ungodly number" != proving through all numbers. Induction is the name of the game.

Math is always news for nerds, because programming is very much like the activity proving theorems - you go for simplicity, generality, and ABOVE ALL, conceptual elegance. The really cool part is that when you find a truly elegant, awesome proof, I almost always have that feeling of "damn! It was so OBVIOUS!" -- even though it wasn't, the elegance of the proof makes the concepts surrounding the program just gel perfectly.

I hope to see solutions like that for some of these problems. I'm not really all that great at number theory, but I really enjoy doing it and watching the big boys do it.

Re:Doh

[SgtPepper]

Naw....

"Unsolvable Obscure Math Problems For Dummies"

THERE! NOW IDG will close down slashdot...

shit...maybe i shoulda posted that AC...

Hilbert's problems and undecidability

[cpeikert]

Several of Hilbert's problems in 1900 were of the form "find an algorithm for such-and-such", where such-and-such was something like "determining whether a polynomial of arbitrary degree and arbitrary number of variables has integer roots." These problems were closed, but not strictly solved, since it was proved that there were no such algorithms to do what he wanted.

I would find it extremely interesting if, in the 21st century, it were shown that many of these conjectures were also proved to be undecidable. It would certainly explain why some of them have taken so long to figure out.

If you show that the conjecture is undecidable, you haven't proven or disproven it - so do you still get the million $$? :)

Re:Aleph1 = C?

[smileyy]

You're pretty close there. Aleph0 is the cardinality of the set of all integers, c is the cardinality of the set of all reals. Cantor's diagonalization proof demonstrates that c > Aleph0.

But the exact "value" of c, in relation to other transfinite cardinals was not determined. In particular, its relationship to Aleph1 (which I believe is the cardinality of the power set of Aleph0) is formally undecidable. That is to say, it doesn't make any difference to your system of mathematics if you choose c

It's been a while since I've studied this stuff, but I've found this a decent introduction to the subject.

Hey wake up. We're in year 2000

[El Cabri]

Never heard of the New Economy ?

Giving $1M when the problem _is_ solved is an old-fashioned, actual-results-based, old-economy way of doing things.

CNNfn taught me that the New Economy way of doing it is :

-- give me $10M now. I promise to hire the brightest people on earth.

-- If I don't get anything done, I'll fill an IPO and screw some shareholders.

Which one to try for

[YoJ]

Given the background of most readers of Slashdot, if you are thinking of trying to solve one of these problems the best one might be the P=NP problem. Most of the others require some high-level knowledge of mathematics or physics. The high powered theoretic scientists have all taken a look at P=NP. I think real progress will come from a non-specialist who has really original ideas about new algorithms.

What you have to do: find an algorithm to solve any of the following problems in polynomial time.

• Given a graph, find a cycle (loop) that visits every vertex exactly once (Hamiltonian cycle problem)
• Given a weighted graph, find the least-weight path that visits every vertex (Travelling salesman)
• Given a phrase of boolean variables, determine if any combination of values for variables makes the phrase true (Satisfiability)
• Given a set of numbers, and a target sum, determine if any combination of the numbers add up to the target sum (Subset-sum problem)

Most CS people think that P is not equal to NP. They might be right, but I think we have vastly underestimated the power of polynomial time algorithms.

Problems that are in P can be solved for sure in polynomial time. Problems in NP have solutions that can be verified in polynomial time. For example, in the subset-sum problem it is easy to verify that the sum of a certain combination of numbers adds up to the target. It is harder to come up with the right combination. But is it so much harder that it cannot be done in polynomial time? Maybe not.

-Nathan Whitehead

Re:Which one to try for

[Azog]

P is the set of problems that can be solved in polynomial time; i.e. the set of problems for which polynomial-time algorithms are known.

So what's a polynomial time algorithm?

For some deterministic algorithm 'A', (like quicksort) which takes an input of size 'n' (the objects to be sorted), there is some formula that says how many computational steps must be carried out to complete the algorithm.

A simple example. Suppose you write an algorithm to find the maximum number in an array by scanning through the whole array once. This will take time proportional to the size of the array. In mathematical jargon, this is O(n) "big-Oh of n" where n is the size of the array.

You can have algorithms that are O(n^2) "n squared", O(n^5 + 3n^2 + 50n), or whatever. If the function of n is a polynomial in n, then the algorithm runs in polynomial time.

But if your function is like O(2^n) "two to the n" that is not a polynomial in n, and you don't have a polynomial time algorithm.

As a simple example, consider code breaking. In this case, n is usually the number of bits in the key. If you have a 128-bit key, there are 2^128 possible keys. If your "algorithm" is the obvious one of trying every single key one after another until one works, you will have to check O(2^n) keys. This is exponential time, and it's a very slow way to break codes.

Anyway... A definition of NP is a little harder to understand. NP is not "non-polynomial" although people tend to think of it that way. What it really means is "non-deterministic polynomial". Non-determinstic algorithms cannot be directly implemented in computers. However, they can be converted into deterministic algorithms which run in exponential time.

So: the P=NP question is: For all the problems where we know non-deterministic polynomial time algorithms, are there actually determinstic polynomial time algorithms that we just haven't been smart enough to figure out yet?

Probably not. Why? Well, there's this "NP-completeness" thing. If you find some interesting problem that you can't get a (determinstic) polynomial time algorithm for, you can find a non-determistic algorithm, and then then prove your problem is "equivalent" to a known NP-complete problem. That means that if someone was able to find a deterministic polynomail time to solve YOUR problem, that same solution could be used to solve ALL OTHER NP-complete problems in polynomial time. And since hundreds of people haven't been able to solve them in years of trying, there probably isn't much point in trying to solve yours.

At this point you talk to your thesis advisor and start working on fixed-parameter tractability, or polynomial time approximations, or other more esoteric computer science approaches to the problem...

Now you know more than you wanted to.

Torrey Hoffman (Azog)

Goldbach *not* undecideable.

[divec]

Goldbach's conjecture is a first-order statement, so by Gödel's Completeness Theorem (which is *not* the same as his Incompleteness Theorem) there is either a proof or a disproof.

A "first-order statement" is one which can be formulated without saying "For all X" or "Exists X" for any infinite set X. (It's ok to say "for all/exists x" where x is just a number, or a set element. Also I'm not stating this mathematically precisely).

Goldbach is stated as "for all x there exists y,z such that y prime and z prime and y+z=x". "y prime" is a first order statement: "for all j, j > y or exists k such that jk y".

So there *is* a (dis)?proof of Goldbach, just waiting for someone to find it.

*NEW* problems?

[Kinthelt]

We haven't even finished solving the all of the original 23 problems!

One great example is Goldbach's Conjecture: All even numbers greater than 2 are the sum of two prime numbers.

Mathematicians have tried for years to prove or disprove this one (or to prove it is unprovable), but still haven't come up with an answer. I think the thing that irks most mathematicians is the fact that it is so short and elementary.