Mathematics desk
< February 11	<< Jan \| February \| Mar >>	February 13 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

February 12

Is Goldbach's conjecture harder to prove than Fermat's last theorem?

Is 1637-1742 mathematicians' failure to crack the latter worth less than 1994-2017 mathematicians' failure to crack the former? Sagittarian Milky Way (talk) 10:40, 12 February 2017 (UTC)[reply]

Yes definitely, any such proof would have a Turing-Gödel Complexity Exponent of at least 13 rather than the 8 of Wiles' proof :) How are we supposed to know? Yes I would have said it was even before the proof of Fermat's Last Theorem but there has been some quite astounding theorems proven relating to it. You might also be interested in the Collatz conjecture of which Paul Erdős said "Mathematics may not be ready for such problems" and for which it can be proven that there are related versions that are undecidable. Dmcq (talk) 11:25, 12 February 2017 (UTC)[reply]

Just to be clear on the dates: 1742-present Goldbach's conjecture unsolved, 1667-1994 FLT unsolved. (The clock on FLT starts 30 years later because it wasn't until then that the infamous marginal note was discovered.) There are a lot of things that contribute to how difficult a problem is perceived to be, but there's no way to tell how difficult it actually is until it's solved. One factor in addition to longevity is who has tried to solve it; a problem that was attempted by Euler and Gauss is perceived as more difficult than one that went unsolved because no one bothered to try. How easy the problem is to understand by a layman has a lot to do with its notoriety, for example Goldbach's conjecture is more famous but really a proof of the Riemann hypothesis would have a bigger impact mathematics. Even when a solution is found it only puts an upper limit on how difficult the problem really is, as in the four color map theorem which is pretty much accepted as proven, but a simpler proof may turn up at any time. --RDBury (talk) 22:29, 12 February 2017 (UTC)[reply]

I want to address Dmcq's remarks on problems being "undecidable", because this is a serious area of confusion, though Dmcq him(?)self may not be confused.

An undecidable problem, in the sense of Dmcq's link, is an infinite collection of problems for which there is no fixed algorithm that correctly decides each instance. For example, "given a program in your favorite programming language, running on an idealized computer, does it get into an infinite loop?". There are infinitely many possible programs, and no algorithm can correctly divide them into those that do loop forever and those that don't.

A single proposition, like Goldbach or Collatz, cannot be "undecidable" in this sense.

There is a very different notion of a single proposition being "undecidable", in the sense that whatever formal theory you have in mind can neither prove it nor disprove it. Our article on this notion is independence (mathematical logic), and I personally think it is much better to use "independent of formal theory T" for this notion, rather than "undecidable".

It would be very interesting if, say, Goldbach or Collatz were independent of, say, Peano arithmetic. But you need to specify the theory (in this case Peano arithmetic); some stronger theory could still decide them. In fact, if Goldbach is independent of Peano arithmetic, then Goldbach is true. Moreover, any (reasonable) formal theory that proves that Goldbach is independent of Peano arithmetic, also proves that Goldbach is true. --Trovatore (talk) 22:51, 12 February 2017 (UTC)[reply]

Yes I could probably phrased it better. They might be interested in Goodstein's theorem which is an example of a simple to understand theorem in arithmetic that is true - but one can't prove it using just Peano's axioms. It may be the Collatz conjecture is like that - but I'm pretty certain no-one will ever prove something like that happens. Dmcq (talk) 00:18, 13 February 2017 (UTC)[reply]

I don't really have an issue with your answer as written. I just thought it was important to head off a potential confusion on the part of some readers. --Trovatore (talk) 00:28, 13 February 2017 (UTC)[reply]