Mathematical Problems For The New Age 353
"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. "
Re:what's the name of this math trick? (Score:1)
Genius!
Re:Relevance (Score:1)
Speaking of strange problems: My favorite is this one. Pick a number $x>1$ not an integer. Look at its powers $x^n$, $n>1$. Look at the fractional part of its powers. Any pattern? It is known that for "almost all" numbers (in the sense of Lebesgue), the fractional parts are uniformly distributed. But no-one knows for specific numbers like $e$ or $\pi$. No one knows what the distribution is for $x=3/2$. But check out $x=\frac{1+\sqrt{5}}2$, the golden ratio. The fractional parts all are either 0.000... or 0.9999 (alternating) after awhile. Algebraic numbers with this property are called Pisot numbers. No one knows if there are transcendental numbers that do this.
Re:Well, the first thing... (Score:1)
Re:Math 101 (Score:1)
This is extra credit. Answer all parts. No partial credit will be given.
a) Prove or disprove Goldbach's Conjecture.
b) Prove or disprove the RSA Assumption
(i.e. breaking RSA is hard)
c) Prove or disprove : P = NP.
The way I heard it, some people took it seriously
and complained to the prof that it was "too hard..."
P != NP (Score:2)
Re:Uber-Math (Score:2)
Accually your odds of winning the lottery (By which we mean the biggest jackpot in the largest drawing, since smaller lotteries are winnable) is almost exactly the same wither you buy a ticker or not. Remember you can find the winning ticket on the sidewalk. For normal statistics you can ignore those events as insignificant, but winning the lottery is so statisticly unlikely at you have to factor finding the winning ticket it, which is only slightly smaller. (Order of mangnitude yes, but not significant)
The odds that I will come up with any solution in my lifetime are very low as I currently stand - I don't think about math in general much. If I decided to solve one problem my odds of doing so in my lifetime increase dramaticly. Of course deciding that I want to solve one of those problems means that spend all my freetime on it. I'd sell my boat since I wouldn't use it, move into a tiny house (preferabbly near a major university so I can access their library and professors... perhaps even become a professor though as others have said I'd be unlikely to make tenure) I'm smart enough to make reasonable progress in a solution if I dedicated my life to it. I may or may not find a solution, but I have a chance.
Dedicate your life to being the big winnder in the lottery doesn't depend much on your brains. While it is true that I can increase my odds of winning the lottery, to do so significantly would mean leaving cheaply (again, no boat...) and making enough money that in the end I'd have more money saving it all then I'd get when I got the winning ticket.
Re:Hilbert's problems and undecidability (Score:2)
Re:*NEW* problems? (Score:2)
It is not the case that M (in the previous) post must be prime. It is possible for it to be divisible by some prime greater than pn.
The smallest such example is 2*3*5*7*11*13 + 1 which is 59*509 (both of which are primes).
Secondly, checking divisibility by primes is enough, because if some non prime N was a factor of M, then any prime that divided into N would also divide into M. So the only factors of N (and it must have non-unit factors, since it is not a prime) can be composites (non primes). Then apply the same process to them (i.e. they can only have composite factors) and so on. The problem is that your factors are always getting smaller and are always positive. Eventually you run out of positive integers, so the original assumption that N has only composite factors must be wrong.
(OK, that last paragraph was a little more complicated that I was intending it to be.)
Re:Einstein couldn't do simple math... (Score:2)
Nope. Replace 'simple' by 'esoteric non-trivial' and you come closer to real thing.
Einstein was pondering about how to extend his theory of special relativity, which is suited for uniform motion to be extended to the case where acceleration happens.
He was a genius in the art of thought experiments, and realized that if you are closed into an elevator without the means to look outside, you can't distinguish if you experience acceleration to the bottom of the elevator by a source of gravity or by someone accelerating/pulling the elvevator.
More abstract, he concluded an eminent physical priciple:
Dynamical and gravitational mass are the same!
That the 'm' for mass that shows up in Newton's equation of motion is the same as the 'm' that shows up in the law of gravitation, the gravitational charge of materia so to say.
He went one and found that this narrows the set of all possible physical laws down considerably. (Physical laws must be covariant).
So he talked to his friend Marcel Grossman, that he should go to the library and look for a mathematical framwork that had this and that features.
Like other people order pizza, Einstein orderd non-Eucledean geometry this way.
Grossman could report to him that Bernhard Riemann, based on work of Carl Friedrich Gauss, had already developed a suitable theory a hundered years before. Differential Geometry on Manifolds in a modern speaking, Tensor calculus in more old fashioned formulation.
That stuff is not easy. It is not standard curriculum in Physics and except for mathematicians, only some mechanical engineers in fluid and solid dynamics use that framework.
Re:Uber-Math (Score:2)
The GPS system (basically a bunch of high precision atomic clocks that send down their time) uses general relativistic corrections to achieve its high position resolution!
On the other hand I know no application of the theory of strong interaction (Quantumn chromodynamics - think quarks) of any kind.
Re:Which one to try for (Score:2)
Correct. I was referring to the "naive algorithm", with is O(2^n), and therefore NP.
Re:Which one to try for (Score:2)
In one of my CS classes, we had to write an algorithm to solve the "subset sum" problem. The naive solution is to, basically, count from 1 to 2^n (where n is the number of elements in the list). Then, use i'th bit in the counter as boolean values to determine whether or not to include the i'th value in the list to add into a guess. I.e., for count == 1, see value[0] equals the target. For count == 2, see if value[1] equals the target. Count == 3 -> value[0] + value[1].
The algorithm I came up with used recursive subsets of the (sorted) listed, as well as pre-calculated knowledge of the sum of the first i elements. Try as I might, I could *not* get an exponential-time result from sample input. The teacher "proved" that my solution was still NP, but it was kind of brushed over. I'm not saying that I wrote a P algorithm, but I certainly never saw proof to the contrary. Is there a (friendly) group of people who would be willing to look at such things from a lowly student? I'd be perfectly willing to be proved incorrect, but neither do I want to just give up simply because I'm not a world-famous scientist.
Re:Which one to try for (Score:2)
You're correct, of course. What I meant to say was that if an algorithm with a polynomial runtime exists for a problem, then the problem can't be NP.
Can it?
We didn't go nearly as in-depth as I would have liked, so please understand that I'm approaching the discussion with an "interested amateur" point of view.
On a side note, my exposure to this kind of theory prompted me to join the ACM's [acm.org] SIGACT [acm.org]. That is, the Special Interest Group on Algorithms and Computation Theory. It's a great place to be if you like this stuff.
Re:*NEW* problems? (Score:2)
He said double the largest known prime and add two. That way the result is gauranteed not to be a prime (it's even!) and it is not the sum of two primes.
This and the original post said the sum of two primes. Otherwise we could just keep adding one to our heart's content.
What may also apply is that the primes may be positive and negative. I don't know.
Now it's just a matter of finding two prime factors which sum to a number twice the largest known prime plus two :-)
Re:wrong (Score:2)
He said double the largest known prime and add two. That way the result is garaunteed not to be a prime (it's even!) and it is not the sum of two primes.
wrong, its not going to be the sum of two known primes.
Oh that's just splitting hairs... I actually meant "the" two primes. You're absolutely correct, but I think it was quite clear that I didn't think it a solution for the problem when I said that all you had to do was calculate which two primes sum to that total.
What may also apply is that the primes may be positive and negative. I don't know.
All primes are positive by definition.
When my statement is qualified with the words "I don't know", you certainly can't fault me for claiming to be an authority on the matter :-)
But thanks for the correction.
what's the name of this math trick? (Score:2)
multiply by a number that the sum is 9 and see:
12345679 x 09 = 111111111
12345679 x 18 = 222222222
12345679 x 27 = 333333333
12345679 x 36 = 444444444
12345679 x 45 = 555555555
12345679 x 54 = 666666666
12345679 x 63 = 777777777
12345679 x 72 = 888888888
12345679 x 81 = 999999999
who discovered that? is there a name to this thing? do you know any others funny values that make the same thing? is there anything to proved in that?
--
BeDevId 15453 - Download BeOS R5 Lite [be.com] free!
Re:Most of these are much harder than they seem. (Score:2)
Ah, and the old 0.999999999... thing. Most people don't realize that it is 1 until you tell them this:
What does it mean for one number to be equal to another number? Well, if x = y, then x - y = 0. In this case, what's 1 - 0.9999999999999...? The answer is 0.000000000000....(infinite number of 0's). Since 0.000000000.... = 0, they are indeed the same number.
You are thinking Alan Turing (Score:2)
David Hilbert was a heterosexual (even went after his grad student's wives) German. I don't know whether he was a Christian or not though.
Cheers,
Ben
Irrelevant for several of these problems (Score:2)
Others can.
The Goldbach problem is an example of something which if it is undecidable, cannot be proved to be undecidable.
P=NP is something that could theoretically be undecidable and be proven undecidable.
In both cases the potential counter-examples can be enumerated (ie placed into a list). The difference is as follows. There might be an algorithm that actually works for P=NP which you cannot actually prove works. However you can always prove one way or another whether a specific integer is the sum of two primes.
Cheers,
Ben
Re:That's what I thought I remembered.... (Score:2)
No (Score:2)
If there were a largest prime number, there would be finite list of primes you could write down. If you took all of these numbers and multiplied them together, then added one, you would get a new prime number.
Form Letter from the Math Department (Score:2)
The first error in your proof occurs on page ____1____, in line _____3____.
Sincerely,
Joe
That is, you make a fundamental error about the implications of reducing a problem to another problem. If I reduce a problem to a polynomial problem using a polynomial transformation, I know I have a polynomial algorithm, but you propose doing the reverse: "reducing" the problem to an exponential problem. That proves nothing; after all, I can provide you with an exponential sort algorithm (try every permutation until you find one that puts the values in order). The problem you transform to may not be the least expensive problem.
Hence you do not prove that P != NP.
Proof for Goldbach's Conjecture (Score:2)
http://www.mathematical.com/mathgold1.html
Now I'm no mathematician, so I obviously didn't check to make sure they carried all of their ones, but at a glance, it looks ok. (How's that for an endorsement?)
Cynic
http://napalm.firest0rm.org/
Re:Goldbach *not* first order. (Score:2)
Re:Aleph1 = C? (Score:2)
Oops...it does make a difference to your system of mathematics, but either way, the system generated by either assumption cannot be shown to be inconsistent.
Re: the solution to Fermat's last theorum (Score:2)
Taniyama-Shimura conjecture.
It is about elliptic curves and modular forms (or whatever that is in englisch).
Navier Stokes Equation (Score:2)
I know a little about some of the other problems, the Poincare conjecture, P=NP, and the Riemann hypothesis. Although these problems are hard, not too many people work on them. Basically, for an untenured professor, these are career destroyers. If one works on these problems as obsessively as a solution will require, you can kiss goodbye to tenure (unless you actually solve it).
In contrast, there are many many researchers the world over working on the Navier-Stokes problem, from graduate students to top mathematicians (like Charles Fefferman who wrote on the claymath website). One may not solve the real problem, but there is progress to be made, and many other easier problems to work on. One can make a reasonable career, while still having a dream of fame.
----
Another poster said that whoever solves this problem will probably already be very rich, working for some rich institute. This really is not the case - probably the solution will come from a moderately paid university professor. The money will be very handy, although then his/her career will be so certain that he/she will be comfortable without it. In any case, the motivation will probably be prestige rather than the money, but the amount of money raises the prestige.
Another poster commented that there are no Good Will's out there. I personally did not like the movie. I think that there are unfound genius's out there - Ramanujan is an example. But noone can solve these kinds of problems without being to some extent obsessive. Good Will did math as an afterthought, and no person can do great work like that. All the great genius's of history, in all creative endeviours, were not just brilliant, but also worked extremely hard.
Didn't we see this before? (Score:2)
--
grappler
Nevermind, found it (Score:2)
It's the Goldbach Conjecture [faber.co.uk], from two months ago [slashdot.org].
--
grappler
Doh (Score:2)
Re:Most of these are much harder than they seem. (Score:2)
You seem to be laboring under the rather common misconception that infinity is a number (at least, not in the ordinare "real" number system). It is not. You cannot set x equal to infinity, so you cannot have y=infinity + 1.
If you're still having trouble, try this thought exercise: Let's construct our infinitely repeating number like this: write 0.01, then insert 0's just to the right of the decimal forever.
"Zero followed by a decimal point followed by an infinite number of zeroes followed by a one" does not represent a real number.
If you're interested in this sort of thing, I REALLY think you ought to study calculus (and I don't just mean take the class). The sorts of mathematical and logic errors that you are making peaked in the mathematical world in the 19th century and were put to rest when calculus was finally put on a mathematically rigorous foundation. I think if you understood the foundations of calculus you'd have a better idea of why you are wrong. If you don't understand those foundations, there is no way I can really describe to you why you are wrong. It'd be like trying to explain pointers to a non-programmer who's doesn't speak your language.
Re:0.9 repeating [OT] (Score:2)
I'm not a mathematician either - never finishe dup the graduate degrees. But it looks to me like his proof could easily be made rigorous in the form which he describe. Define the notation so that 0.999... and 1.000... represent the appropriate infinite series, define the procedure for subtracting and borrowing, and presto! The outline he's given becomes fairly rigorous.
Re:Most of these are much harder than they seem. (Score:2)
Which is why the principle of induction is generally introduced as a postulate in most courses that start with Peano's postulates.
Re:Hilbert's problems and undecidability (Score:2)
1. If Q is provably true, then there exists a series of statements that constitutes a proof of Q.
2. If Q is false, then there exists a counterexample.
2a (contrapositive of 2) If a counter example does NOT exist, then Q is NOT false. (ie no counterexample == true)
If Q undecidable, then there does not exist a series of statements that constitute a proof, and there does not exist a counterexample. But wait! If there's no counterexample, the conjecture must be true. Proving the conjecture's undecidability thus produces a contradiction - you have proved it true AND you have proved it undecidable. So the conjecture is not undecideable.
Either there's a flaw in my logic, or yours. Which, and where? Or were you merely being more general than I?
Re:Most of these are much harder than they seem. (Score:2)
Ummm - no, that'd be the case only if 0.999... = 0.9999...990. The sequence of nines does not terminate. The sequence of zeroes does not terminate either. Granted, the poster you are replying to is giving an intuitive demonstration rather than a rigorous proof, but you are proposing mathematical nonsense.
More true would be to say that if x=1 and as y approaches 1, x-y approaches 0 so we can select a y to get x-y arbitrarily close to 0.
This is true for a finite number of nines following the decimal point. The logic does not hold up if you make the leap to an infinite number of nines. In other words, 0.9999.... != 0.999....9990.
If I remember my infinite series correctly (it's been 10 years since calc 2 for me), 0.999 represents
oo -----> (think 8 on its side)
---
\ 9
\ -------
/ 10^(-n)
/
---
n=1
I've long since forgotten how to sum the series rigorously, but I haven't forgotten the result; 0.99... = 1.
In summary, the arithmetic of infinite series is intuitively nonobvious, and slightly different from the arithmetic of
Relevance (Score:2)
Re:Which one to try for (Score:2)
Re:Doh (Score:2)
Time to go buy that 'Dummies guide to math' book.
Ooooooh, now you've done it... IDG are gonna have to close down slashdot now... I hope you're happy!
<G>
The Infinitude of Primes (Score:2)
"Known", yes. Just plain largest, no. Proof:
Let n1, n2, n3...nx be all known prime numbers. Construct M = n1 * n2 * n3 *
Case 1: M is prime. But it must be a previously unknown prime and it is clearly larger than any previously unknown prime. Therefore there exists another largest prime.
Case 2: M is not prime, but isn't factorable by any known prime. Therefore it is factorable by some unknown prime larger than all known primes.
Since this process can be repeated indefinitely, there must be an infinitude of primes.
--
Have Exchange users? Want to run Linux? Can't afford OpenMail?
Re:Uber-Math (Score:2)
I have a math problem of my own... (Score:2)
:)
Re:My own comments (Score:2)
Yes, thank you very much, my school [www.ens.fr] (translate: college) happens to be where Bourbaki's office is (and, essentially, his "birth place"), and I've read a significant portion of his "Éléments de Mathématiques".
I fail to see how that is relevant. Bourbaki was (were?) not interested in logic. His (their?)treatment of logic and set theory in his first book ("Théorie des Ensembles" - whose publication was long delayed as it remained in the state of a "fascicule de résultats") is sketchy at best, unelegant, and, in essence, as short as he could arrange it, just enough to provide the foundations for the other books.
Anyway, that is old. Currently, there are only about two groups doing logic in France: around Krivine in Paris and around Girard in Marseille (I think). Girard is the inventor of linear logic, so that's a clame to fame, but he's more the exception than the rule: logic is held in disrepute, if not contempt, in France (and I much regret it).
Re:Andrew Wiles must be turning red.... (Score:2)
Professor Andrew Wiles was present at the meeting (he made a little speech to introduce Laurent Lafforgue and later John Tate - although the latter really needs no introduction). I can assure you he did not turn red.
Re:Uber-Math (Score:2)
These problems are _hard_.
IMHO the most notorious one is the Riemann Hypothesis. Some of the best mathematicians have been working for years on that one. It has very broad implications (but so have most of the others).
For example, one can show that there's a strip around this critical axis in which all non-trivial zeroes are located. The smaller this strip, the more accurate are our estimates on things like 'the number of primes not larger than x'.
If the Riemann hypothesis were disproved, a lot of mathematics would immediately become invalid (many papers assume the validity of the hypothesis to prove deep results). In this respect it is quite similar to the Taniyama conjecture (from which the truth of Fermat's last theorem followed, together with lots of other theorem based on this conjecture).
Should the two number-theoretic conjectures (Riemann and Birch Swinnerton-Dyer) be proven in the first half of this century, I suggest that number theorists concentrate on the abc conjecture in the 2nd half of this century.
Re:Why are these important? (Score:2)
The 7 problems at hand have similar implications. For example if we know that the Riemann Hypothesis is true, we suddenly have very precise estimates on for example the growth of the number of primes. Also, the Riemann Hypothesis has generalizations in other areas of mathematics (some of these generalizations have been proven by now).
Re:Most of these are much harder than they seem. (Score:2)
I have a solution to Fermat's problem (Score:2)
George
Re:Goldbach *not* undecideable. (Score:2)
How many left? (Score:2)
---
Re:P=NP may very well be one (Score:2)
Re:Goldbach *not* first order. (Score:2)
Re:Goldbach *not* first order. (Score:2)
post. Goldbach's conjecture is first-order, but it is a first
order sentence of a theory which cannot be given a primitive recursive
axiomatisation. A lot of people here are confused about language
vs. theory and decidability vs. completeness: back to the textbooks, I
think.
Here are the answers: (Score:2)
2. 42
3. 69 (Ooh, sexy.)
4. Both 7 and 11 (it's a quantum problem)
5. 14 cats + 1 hedgehog * Larry Storch
6. No
7. E=mc^3
Please have my check ready, I will be over to get it after "Full House".
Re:P=NP (Score:2)
You'll get the proof anyway.
--
Re:*NEW* problems? (Score:2)
Of course I'm the furthest thing from a mathematician and I was really happy when I knew the answer to "the longest side of a right triangle" on Who Wants to Be a Millionaire, so I'm probably wrong but that's what comes to mind if I recall some of the math I had way back when.
Re:Aleph1 = C? (Score:2)
[ZFC is set of axioms used as the basis for a (the?) standard formulation of set theory: you start with these 9 axioms and rules of logic and all of your set theory follows.]
Therefore CH is an axiom that is independent of ZFC -- you can choose to adjoin it to your axioms or not, and you get a different set theory depending on whether you use it or not. Some might say that you choose whether to 'believe' CH -- more accurately, you choose to use CH depending on what kind of model of the real world you want your theory to be.
[btw, one can also prove that the 8 axioms of ZF are independent of C (the axiom of choice). So as above, you can choose whether to adjoin it to your set of axioms and make ZFC or just stick with ZF.]
Re:Hilbert's problems and undecidability (Score:2)
I claim to have a proof that this situation is impossible. There could be a flaw in my logic.
suppose that the original statement is decidable. then there's a proof that it's true, or there's a counterexample. therefore its decidability is definately true (and therefore decidable).
now suppose the decidability isn't decidable. then the original statement can't be decidable (see above). therefore, the original statement is not decidable.
--
Re: |power set of integers| = |reals|? (Score:2)
We know that the reals can be mapped onto the reals from 0 to 1. So, consider the following sequence of numbers:
000000000000000...
100000000000000...
010000000000000...
110000000000000...
001000000000000...
...
Just a progression of binary integers. Okay. Now, consider these as binary expansions of a real number less than one:
0.10000000000000...
So we have a mapping from the above to all reals less than one. We can also consider this a mapping onto the power set of the integers:
010010010000000... {1, 4, 7}
So we have the same progression mapping onto both sets of interest. But, aleph0 of the reals (terminating fractions) will be encoded twice. It seems like we could in some way "subtract these out", since subtracting a lower order of infinity from a higher order should still give the higher order. Also, the diagonalization argument that Cantor used doesn't work, because the number generated is:
0.1111111111111111111111... = 1
But we said that we are limiting it to numbers less than one.
But, each of the bit sequences we are using to encode a subset or a real also encodes an integer. So the above shows that:
|reals| = |power set of integers| = |integers|
Which we know is false because everyone says so. So, where is the flaw?
--Kevin
Re:Most of these are much harder than they seem. (Score:2)
Actually, there's a much easier to understand proof that 0.999... is equal to 1. What's 1/9? 0.111111.... What's 2/9? 0.22222.... So what's 9/9? 0.999999..... Of course, 9/9 is 1.
Re:Aleph1 = C? (Score:2)
None of you could solve these things, including me (Score:2)
Re:Most of these are much harder than they seem. (Score:2)
And, actually, the Is P=NP question is vitally important to any sort of reasonable algorithms work. Travelling salesman is one problem that's easy to explain, and even easier to tie up huge amounts of resources with. But it's equivalent to natural language processing, for instance, and a lot of useful AI applications. Reducing any of those problems to polynomial time would be the same as reducing all of them, and the fact of the matter is that that is almost certainly worth far more than a measely $1e6. More like $1e(8 or 9).
So, yeah, these are incredibly hard problems. And like all of the real stumpers in math, they begin with one question: where to start?
Ushers will eat latecomers.
Re:P=NP? (Score:2)
Re:P=NP? (Score:2)
Re:*NEW* problems? (Score:2)
Let n be the largest known prime number. Now is n+2 itself prime? (You have to prove/disprove this one)If it is, (just like 5 and 7) then you've just increased the largest known prime number by 2. Then it is just another instance of Goldbach's conjuecture.
If it is not prime, things become more interesting. Is there some primes less then n, such that when you add them together, you get n+2? If you can prove that there isn't, then you have disproven Goldbach's conjecture. But chances are, there is, since we can do (for example) 3 + 3 + 3 + 3 + ... and use that hit a lot of numbers. Good luck finding that number missed by ALL such sequences ....
That's easy enough... (Score:2)
I'd pay good money for that!
Re:Add this one to the list... (Score:2)
Re:Applicability (Score:2)
P=NP (Score:2)
Why such extreme numbers? Well, basically, if the solution to this problem is found, then I can easily reduce the solution into ATM or into Turint Halting problem and by doing that I can basically solve every single protection algorithm on this planet in polynomial time (in no time - rather.)
So, if any of you out there, who wants to make 10million USD, you should solve this problem and contact me.
Re:Which one to try for (Score:2)
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)
Please excuse my ignorance on this, but this both seems easy if you can use really fsck bloated and slow moving code. I assume this won't be consider polynomial time? Could anyone explain what exact is 'polynomial time' is? How it is defined?
Re:Hilbert's problems and undecidability (Score:2)
You're conflating what's usually referred to as "Proof theory" with what's usually referred to as "Model theory". By Godel's Completeness Theorem (not Incompleteness, Completeness -- they're different), if a statement is provable in first order logic from a theory, then it is true in all models of that theory -- and vice versa. (If the statement is provable, then it's true everywhere.) 2a doesn't actually follow from 2. 2a follows (after a highly non-trivial proof!) from the stronger statement "If Q is false, then there is a counterexample in all models."
Think about the axioms for the Theory of Groups. There are perfectly good groups in which multiplication isn't commutative. That means that the Abelian axiom (for all x and y, xy == yx) isn't provable from the standard axioms of group theory. It's not a proof of a contradiction, it's just a proof that a sentence isn't decided.
A theory in which all sentences are decided is called "complete". Very few theories are complete, and, in fact, what Godel's incompleteness theorem shows is that any theory which codes up the notion of proof in a non-trivial way relative to itself -- pretty much, any interesting theory -- is, ipso facto, not complete.
They Forgot Goldbach. (Score:2)
There was a /. story a month or so back about the Goldbach conjecture being worth a million.
At least I could understand that problem. These look hopeless. What is a topological manifold anyway? Whenever I hear that, I always picture mathematicians going down to the junkyard and picking apart exhaust systems... Q: Why is that math professor making all that noise and stinking up the place? A: Sounds like he has a hole in his topological manifold. :)
Re: the solution to Fermat's last theorum (Score:2)
The Taniyama-Shimura conjecture was that every elliptic curve was a modular form. This implied that Fermat's Last Theorem was true in a roundabout way. Wiles proved Taniyama-Shimura and thus Fermat.
Re:*NEW* problems? (Score:2)
Well, there is the obvious number theory rule that odd+odd=even. Since all primes >2 are odd...
Try to read before replying....
Jeroen
Re:I have a solution to Fermat's problem (Score:2)
uh, no. Fermat's Last Theorem was solved analytically by Andrew Wiles, by hand, over a seven year period.
The problem cannot be solved empirically, and neither can any of the others above (except maybe by counter-example) as they involve absolute proof of general cases
And it was Fermat who wrote something like "I have a marvellous proof of this, which this margin is too small to contain"
Nice for a change (Score:2)
Does P=NP? (Score:2)
The night before the final I posted a message on comp.theory asking for a proof that P=NP because it would greatly help on the problem set I was working on (namely invalidating the proofs I had to do to show that several different problems were NP-Complete).
Well, Unfortunately everyone on the newsgroup took me seriously and there was some angry responses along the lines of: "Are you stupid? Your going ot fail your final tommorrow if you don't already know that this is the biggest unsolved porblem in computer science..."
The best was that a few weeks later (after the grades were turned in, thank god), my TA noticed the post and E-mailed me in disbelieve asking if I had really posted that question...
I don't kow how she knew it was me since I only signed with my initials...
Re:Relevance (Score:2)
Re:Most of these are much harder than they seem. (Score:3)
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. (Score:3)
--
It's been solved. (Score:3)
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 (Score:3)
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 (Score:3)
--
Re:Aleph1 = C? (Score:3)
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 (Score:3)
Prof. AC
another million (Score:3)
the /. story is here [slashdot.org].
the conjecture itself (for the link-following-impaired) is:
Enjoy!
--
Re:Well, the first thing... (Score:4)
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 (Score:4)
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. (Score:4)
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. (Score:4)
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... (Score:4)
NP * 0 = P * 0
0 = 0
q.e.d.
Gimmie my million!
Most of these are much harder than they seem. (Score:5)
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 (Score:5)
"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 (Score:5)
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? (Score:5)
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 [mathacademy.com].
Hey wake up. We're in year 2000 (Score:5)
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 (Score:5)
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 (Score:5)
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. (Score:5)
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? (Score:5)
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.