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

Re:Most of these are much harder than they seem.

[El Cabri]

>> Math is always news for nerds, because programming is very much like the activity proving theorems

Actually proving theorem and programming _are_ the same things under certain constraints (basically that you don't prove that the [the property being false] is false in order to prove that the property is true). This is called the Curry-Howard isomorphism and is the general idea behind many formalizations of programming.

Missed one.

[Black Parrot]

I don't see anything about the famous and all-important karma maximization problem.

--

It's been solved.

[FascDot Killed My Pr]

More than once, in fact.

Method 1: Follow story link. Cut random text and past to /..
Method 2: Create post such that title = "Why this is good for Linux" and body contains random text.
Method 3: Create post such that body contains "I am post anonymously because (insert random reason here)."
Method 4: Post something critical of Jon Katz (only works temporarily, karma rapidly falls off after 5 minutes).
--
Have Exchange users? Want to run Linux? Can't afford OpenMail?

Re:Hilbert's recording

[David A. Madore]

No, it's not available on-line. (Even after hearing it, I would really like to get it a copy.) Maybe by asking Professor Alain Connes (he seems to be the one who found the tape) very politely...

Re:P=NP

[anatoli]

If I prove to you that Halting Problem is not in NP, will I get my $10M?
--

Re:Aleph1 = C?

[bifurcator]

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.

You're pretty close there. But not quite. The cardinality of the power set of Aleph0 is C (the cardinality of the set of all real numbers). Put simply, Aleph 1 is the cardinal that comes right after Aleph0. C looked like a pretty good candidate for some time. C is a cardinal, and it comes after Aleph0. The question was, does it come right after Aleph0, or is there another cardinal in between Aleph0 and C? If my memory serves me right, an American named Cohen proved that you cannot answer 'yes' or 'no' to this question within an axiomatic system like ZFC (Zermelo-Frenkel plus the axiom of choice.)

Math 101

[Anonymous._.Coward]

Excellent, now I don't have to spend any time making up the finals exam questions for my math students.

Prof. AC

another million

[jabkie]

don't forget that proving Goldbach's conjecture is also worth a million bucks

the /. story is here.

the conjecture itself (for the link-following-impaired) is:

Every even number greater than two is the sum of two primes.

Enjoy!
--

Re:Well, the first thing...

[dillon_rinker]

Dear ___Tebriel___,

The first error in your proof occurs on page ____1____, in line _____2____.

Sincerely,

Dillon

When the math department where I went to school received a crank proof, this form letter would be stapled to the front, a grad student would fill it out, and the proof would be returned to its sender.+

My own comments

[David A. Madore]

All right. I posted the story, now here are a few comments of my own.

The problems are all fairly old. The Riemann hypothesis is the oldest, as it dates from around 1860 and it was already part of Hilbert's 1900 list. Surprisingly, almost no progress has been made toward its resolution (except for Deligne's proof in the generalized local case, aka the Weil conjectures, but that isn't really the same problem). The Poincaré conjecture is also rather old. The study of the Navier-Stokes equation is probably as old as the equations themselves, but the mathematical foundations for a rigorous study are more recent.

P=NP is the newest problem, coming as it does from computer science, and also the most likely to be of interest to Slashdot geeks. John Tate rather messed up (IMHO) in his presentation of it (he obviously didn't think it was very interesting), and I gather many mathematicians believe it isn't very rigorously refined (certainly, many French mathematicians, with their usual contempt for logic and computers science). In fact, it is perfectly rigorous and mathematicial. It is probably the easiest problem on the list, as the theory behind it is still not fully developped. For a start, I'd recommend Papadimitriou's book "Computational Complexity" for the present state of knowledge: it is very thorough, well-written and interesting.

Personally, I'm convinced P=NP is undecidable (in a nutshell, my point is that for Turing machines with oracles, by judiciously choosing the oracle we can arrange so that P=NP or P!=NP, see Papadimitriou's above-mentioned book for a proof, and I don't despair of the existence of a notion of forcing on oracles of some kind). It would be a very weird situation (for Pi^1 propositions, as a previous poster pointed out, if it is undecidable then it is true - proviso the consistency of arithmetic which is the hidden assumption in the meta-proof that "unrefutable=>true"; but for P=NP it just looks... weird). I don't think any of the other statements are undecidable (if any of them is, we are light-years away from being able to prove it). Naturally, it is possible for the undecidability of a statement to be undecidable, and so on up to (ordinal) heights of staggering difficulty (though by a theorem of Tarksi, at some point the proposition must be decidable - little comfort in practice).

Some have asked why Goldbach's conjecture (for which someone else is offering $1M) is not in the list. The fact is that it's not interesting. Every one of these seven problems, if solved, would have far-fetching consequences, and its proof would open vast new areas of research. Not so with Goldbach's conjecture. It is amusing because it is very simple, simple enough to be explained to laymen. But apart from a few additive number theorists, nobody is interested in it. Proving it would require ingenuity, certainly, and much technique in sieving methods and circle integrals; but nothing like opening new areas of mathematics. Don't waste your time on Goldbach's conjecture: it is highly technical and intellectually almost worthless.

Anyway, getting back to the seven problems, some people I know have been rather angry that such old problems have been selected, not more recent stuff. In a way the list is rather "conservative". For example, the global case of the Langlands programme, which is probably the most ambitious programme in mathematics (at any rate, in number theory and algebra), the global analogue of what Lafforgue proved in the local ("functions field") case, was not selected. Perhaps also because it is thought to be too difficult...

Re:Goldbach *not* undecideable.

[Chalst]

This is not true. Gödel's completeness theorem only applies to
primitively recursive axiomatisations in first-order logic.
Arithmetic, as Gödel's incompletensss theorem's show, cannot be
captured by by such an axiomatisation. Goldbach's conjecture is a
Pi^0_1 statement of arithmetic (a measure of the intrinsic logical
complexity of a statement that includes the Gödel sentence), so as far
as we know, we might not know of a formalisation capable of proving it
to be true.

Goldbach *not* first order.

[sh_mmer]

Goldbach's conjecture is a first-order statement...

come on: Goldbach obviously is *not* first order. let me slightly rephrase Goldbach, and you will see:

"for every integer n > 2, there exist positive primes p and q such that p+q = 2*n."

that's the proper formulation, and hence the conjecture is apparently *not* first order!

d'accord?

sh_

Well, the first thing...

[Tebriel]

NP = P
NP * 0 = P * 0
0 = 0
q.e.d.
Gimmie my million!

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.