Live data from Hacker News

Titans of Mathematics Clash Over Epic Proof of ABC Conjecture

quantamagazine.org

141–150 of 275 posts

Re: Titans of Mathematics Clash Over Epic Proof of ABC Conjecture

#141

Earlier quoted context omitted.

Who proves that the automated proof is correct. Who proves that... etc. All this is tied up in Gödel's incompleteness theorem.

Verifying proofs is a much simpler job than creating a proof. Also, you can have multiple independently implemented verifiers, which act in many ways like multiple human reviewers. That is what the metamath community does, they have 4 independently implemented verifiers that check every proof. That is very strong evidence that a proof is correct, far stronger evidence than is typically accepted now.

Yes but these will only accept proofs from within the mathematical framework of the multiple verifiers. I'm not saying that having 4 automatic independent verifications of a proof is useless, far from it! Just that, the notion you can "prove" all of mathematics is almost meaningless, or demonstrable false.

Re: Titans of Mathematics Clash Over Epic Proof of ABC Conjecture

#142

Earlier quoted context omitted.

The really interesting case here is Voevodsky, who found an error in one of his own proofs many years later and then got interested in foundations of Mathematics and automated proofs. Homotopy type theory is an interesting development, particularly if you are into programming languages.

I don't really understand why the entire known mathematics is not automatically proven yet. We, people, understand very formal proofs. Mathematics is very strict science with axioms and following theorems. It should be a perfect application for computing. I'm not talking about computer prooving theorem himself, but mathematician should write proof using some formal language and computer should be able to follow that…

> Mathematics is very strict science with axioms and following theorems. It should be a perfect application for computing.

The short answer is that mathematics is not actually a very good application for computation. It's a rather poor application for computation. Herein lies the rub and the reason why it can't be done as easily as you'd suppose. Computationally-oriented questions and theorems are a subset of all available mathematics research in the same way that computer science is only a subset of all available applied mathematics. Stated another way, imagine the massive difference of effort involved between developing an application that works and formally proving that your application works for all possible inputs. It's extremely difficult to take the set of all possible test cases and reduce them to a set of equivalence classes which can be individually proved. This is the difference between constructive and non-constructive proofs.

Most mathematics is not actually constructive, which intrinsically presents a difficulty for computational theorem proving. Furthermore a lot of mathematics (particularly in the various flavors of analysis) is continuous in nature, which is inherently difficult for a computer to correctly model. For example, computers don't actually deal with real numbers, the floating points are just a good enough practical approximation of them.

If you look at the noteworthy cases where computer-assisted theorem proving has done very well, they generally fall into one of two categories:

1. Cases where the program mechanizes a well-established theorem with a vast amount of scaffolding theory already existing around it. In this way it's relatively easier to automatically prove much of undergraduate mathematics, the bulk of which has been reduced to very succinct proofs over the past few centuries (undergraduate mathematics doesn't really make it past the late 19th century in terms of novelty).

2. Cases where a vast problem can be provably reduced to a large but finite number of special cases, each of which can then be individually proven. The four color theorem is an example of this variant of automated theorem.

To give you an idea of how monumental the gap between research mathematics theorems and computation is: in order to make as much progress as we have, we've had to develop an entirely new theory of foundational mathematics (type theory). This allows us to bridge the gap between theorems and automated proofs in a way that set theory doesn't really allow. But that's a huge undertaking and a very quickly growing field of math.

When it comes down to it, mathematicians do not tend to do research in, nor does their intuition naturally map to, a computationally rigid language. Essentially no current mathematician was taught or trained to do their research in a computational manner unless that was explicitly their field of research. Furthermore, while mathematical terminology looks formal to an outsider, there is a significant amount of symbolic overloading and notational interpretation in modern math. That doesn't mean most proofs are wrong, but it does mean that most mathematicians are informal; to the extent they write down proofs of their theorems, they've only ever needed to do so enough to get other mathematicians to say, "Yes, I see what you mean, this does logically follow from what we already both agree on."

Re: Titans of Mathematics Clash Over Epic Proof of ABC Conjecture

#143

Earlier quoted context omitted.

I don't really understand why the entire known mathematics is not automatically proven yet. We, people, understand very formal proofs. Mathematics is very strict science with axioms and following theorems. It should be a perfect application for computing. I'm not talking about computer prooving theorem himself, but mathematician should write proof using some formal language and computer should be able to follow that…

Because most mathematics is not constructive, and most automated theorem proving tools are based on constructive logic.

That doesn't sound right at all. Law of excluded middle is very easily computed with, It's a college homework exercise.

Re: Titans of Mathematics Clash Over Epic Proof of ABC Conjecture

#144
post #119

Earlier quoted context omitted.

What is the painful part? The level of detail required for it to check?

How current proof assistants work is using the Curry-Howard correspondence, [1] the gist of it is that all of first order logic can be encoded into a type. All one must do is write an expression that type checks to what one is trying to prove. That turns out to be fairly hard for reasonably complex proofs. [1]: https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...

To be only a little more precise, every proposition becomes a type of its own. The AND operator forms product types, the OR operator forms sum types, IMPLIES forms a function type... The proof of a theorem turns into an inhabitant of the theorem's type.

Re: Titans of Mathematics Clash Over Epic Proof of ABC Conjecture

#145

Earlier quoted context omitted.

I don't really understand why the entire known mathematics is not automatically proven yet. We, people, understand very formal proofs. Mathematics is very strict science with axioms and following theorems. It should be a perfect application for computing. I'm not talking about computer prooving theorem himself, but mathematician should write proof using some formal language and computer should be able to follow that…

Some mathematicians are concerned that the possibility of an error in a computer program or a run-time error in its calculations calls the validity of such computer-assisted proofs into question. (This might be one reason, from https://en.wikipedia.org/wiki/Mathematical_proof#Computer-as... )

That's silly, because humans have been repeatedly proven to be full of errors.

Re: Titans of Mathematics Clash Over Epic Proof of ABC Conjecture

#146
post #22
post #20

Earlier quoted context omitted.

True, but even then, how large do you think the field is? And how many people verify these proofs? I have a PhD in an esoteric field myself. There's literally <50 people worldwide who write/verify proofs in it. I've spotted errors in my own work or other's work that got past peer review. And I don't think I'm particularly special. There's just not enough eyeballs, time and incentives sometimes.

> True, but even then, how large do you think the field is? And how many people verify these proofs? It only takes one to break it. And, for something so fundamental, it's a big deal if you are the one. This isn't physics, where you have to rule out all manner of confounding data before you can trust your conclusion.

The point you are missing that studying a proof can't proof it correct, only fail to disprove it.

Re: Titans of Mathematics Clash Over Epic Proof of ABC Conjecture

#147

Earlier quoted context omitted.

Verifying proofs is a much simpler job than creating a proof. Also, you can have multiple independently implemented verifiers, which act in many ways like multiple human reviewers. That is what the metamath community does, they have 4 independently implemented verifiers that check every proof. That is very strong evidence that a proof is correct, far stronger evidence than is typically accepted now.

Yes but these will only accept proofs from within the mathematical framework of the multiple verifiers. I'm not saying that having 4 automatic independent verifications of a proof is useless, far from it! Just that, the notion you can "prove" all of mathematics is almost meaningless, or demonstrable false.

I'm not sure what your point is here. If the point is that the provers require a particular format, and not just English sentences, then that is true but not really a problem. Writing programs also requires that you use a particular format, AKA programming language, and that happens all the time.

It's true that some things cannot be proven, due to Goedel's incompleteness theorems... but that is a fundamental limitation of mathematics and has nothing to do with the limitations of computer tools.

You can write proof verifiers that are very generic. The metamath proof verifiers, for example, can work with arbitrary axiom systems. Most people use metamath to prove statements using classical logic with ZFC, but there are a number of other systems that are supported. Quine's New Foundationd set theory axioms and intuitionistic logic are alsk supported.

Re: Titans of Mathematics Clash Over Epic Proof of ABC Conjecture

#148
post #69

I remember an instructor explaining during the math olympiad training program: "A proof doesn't have to be in any particular format. A proof is an argument that can convince other mathematicians." At this point, it seems clear that we do not have a proof of the ABC conjecture. Perhaps someone will be able to improve this to make a real proof - after all, there were some errors in the first Wiles proof of Fermat's Las…

I think you're exactly right. Mochizuki's work may or may not turn out to be sound, but in the mean time he's failed to communicate it to other experts, even when they've met with him in person for the specific goal of understanding his reasoning. It's not sufficient to have a great idea, or even to be right about it. You have to be able to explain it thoroughly enough that other qualified peers can understand your l…

It's sufficient for Mochizuki. Everyone else can decide for themselves what is sufficient for them.

Re: Titans of Mathematics Clash Over Epic Proof of ABC Conjecture

#149

Earlier quoted context omitted.

I don't really understand why the entire known mathematics is not automatically proven yet. We, people, understand very formal proofs. Mathematics is very strict science with axioms and following theorems. It should be a perfect application for computing. I'm not talking about computer prooving theorem himself, but mathematician should write proof using some formal language and computer should be able to follow that…

> Mathematics is very strict science with axioms and following theorems. It should be a perfect application for computing. The short answer is that mathematics is not actually a very good application for computation. It's a rather poor application for computation. Herein lies the rub and the reason why it can't be done as easily as you'd suppose. Computationally-oriented questions and theorems are a subset of all ava…

> That doesn't mean most proofs are wrong, but it does mean that most mathematicians are informal; to the extent they write down proofs of their theorems, they've only ever needed to do so enough to get other mathematicians to say, "Yes, I see what you mean, this does logically follow from what we already both agree on."

THIS is the real reason more mathematics isn't computer-checked. You massively buried the lede.

> Most mathematics is not actually constructive, which intrinsically presents a difficulty for computational theorem proving

How so? There are plenty of theorem provers for classical logics.

> Furthermore a lot of mathematics (particularly in the various flavors of analysis) is continuous in nature, which is inherently difficult for a computer to correctly model.

You can do continuous mathematics in a theorem prover. E.g. much of the classical theory of ODEs has been formalized in various theorem provers. Proofs about infinite structures are still a finite sequence of axiom applications.

Furthermore, outside of theorem proving, numerical analysis and simulation of ODEs/PDEs is probably THE killer example of computers revolutionizing a field of mathematics...

> For example, computers don't actually deal with real numbers, the floating points are just a good enough practical approximation of them.

When you drill down into the model theory, you come to the amazing surprise that exactly the opposite is true.

Integers aren't decidable: https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...

Reals are deciable: https://en.wikipedia.org/wiki/Real_closed_field#Model_theory...

> To give you an idea of how monumental the gap between research mathematics theorems and computation is: in order to make as much progress as we have, we've had to develop an entirely new theory of foundational mathematics (type theory).

Again, there's nothing stopping us from doing classical mathematics in a theorem prover.

Post reply on HN