News for hackers. Stuff that matters.
Re:An ABC proof too tough even for mathematicians by cperciva on Sunday November 25, 2012 @03:54PM (#4829253)
Proofs at this level are nowhere near formal enough for existing mechanical tools to understand. I've seen researchers cite "translated proof X into an automatically-verifiable form" as a major achievement -- even for very simple proofs.
Re:An ABC proof too tough even for mathematicians by makmanalp on Sunday November 25, 2012 @04:25PM (#4829343)
Non-math person here. Wait, so you're saying it's easier for humans to prove complex theorems than computers? That's nuts.

Doesn't that mean that verifying proofs is then based on a super handwavy process where a bunch of researchers come to a consensus and say "yes, this is correct"? Ugh!

What if they all overlook some crucial aspect because of the way they were trained, or their entrenched / ingrained assumptions?

When you describe a proof with words like you say, aren't there quibbles over semantic things? But I thought the whole point of a proof was that you leave nothing to semantics. Everything logically follows from each other.

I thought the main issue with proofs systems was that encoding the concepts into code was tedious. Could we maybe have a common database of well-known proofs, axioms, concepts etc, so that you wouldn't have to rewrite common ideas from scratch? Like a package manager with proof-libraries?

Or is this an issue with the expression power of proofs languages?

Re:An ABC proof too tough even for mathematicians by shou4577 on Sunday November 25, 2012 @05:28PM (#4829520)
Yes, it's much easier for humans to prove complex theorems than computers. Just as it is much easier for humans to build complex programs than computers.

Often times, a proof is (much) more complicated than just mixing theorems A, B, and C together to get result D. Many times proofs will require developing entirely new mathematical structures, or can be done only in steps.

As an example, a friend of mine just proved a great theorem about whether or not Hessenberg varieties can be paved by affines. Ignoring what this actually means, the proof involved firstly recognizing that a Hessenberg variety actually fits within a spectrum - it is somehow "between" other types of well- (or better-) understood varieties. These are paved by affines in (somewhat) obvious ways, and so it is natural to try to use the "between-ness" of the Hessenberg variety to construct a "between-ish" paving. This isn't a proof, but it is a direction (one that turned out to be fruitful). It would be very hard for a computer to have made this intuitive leap.

And it almost works. Except now you can't reduce things like you would like, and you need to construct multi-level fiber bundles in order to get the triviality that you want. And wait - this only works if the Hessenberg variety that we started with has such-and-such property.

So she's reduced the problem to a simpler problem. How does she know it is simpler? Intuition. A computer would have a very hard time recognizing whether or not this is actually simpler (even if it could get there). It turns out that this property holds when our Hessenberg variety is constructed from an element whose semisimple part under the Jordan decomposition is regular. So she has proved it for a huge class of varieties, but not all. Such a partial result would also be very difficult for a computer, since it isn't exactly what she set out to do. She's only partly there. But even this part is huge.

And there isn't anything hand-wavy about her argument, either. It's perfectly grounded in well-established theorems, all of which she understands the proof for. It's just that the original concept was shakey - the "between-ness". She had to work to ground it. It would have been exceptionally hard for a computer to make several of the intuitive leaps necessary to come up with the ideas for the proof in the first place.

Re:An ABC proof too tough even for mathematicians by apl on Sunday November 25, 2012 @06:42PM (#4829691)
I assume that he was going for something different, though; namely, that it's nuts that verifying proofs is simpler for humans than it is for machines.
Re:An ABC proof too tough even for mathematicians by _delirium on Sunday November 25, 2012 @07:56PM (#4829869)
Well, if the proof is first formalized, it's easier for machines to verify. But formalizing it is much harder. This is similar to the situation in software, where uptake of formal-verification tools that can prove correctness of programs is relatively low (though Agda is making some very interesting progress).
Re:An ABC proof too tough even for mathematicians by impendia on Sunday November 25, 2012 @04:47PM (#4829396)
Math person here.

>Wait, so you're saying it's easier for humans to prove complex theorems than computers?

Of course! If proving theorems could be readily automated, this would have been done already. Indeed, automation has succeeded for some kinds of problems (e.g. google Wilf and Zeilberger's "WZ method" in combinatorics for a particularly successful example)

>Doesn't that mean that verifying proofs is then based on a super handwavy process where a bunch of researchers come to a consensus and say "yes, this is correct"?

Basically, yes.

>What if they all overlook some crucial aspect because of the way they were trained, or their entrenched / ingrained assumptions?

This happens surprisingly rarely. It helps that we are trained to constantly question our entrenched assumptions.

>Could we maybe have a common database of well-known proofs, axioms, concepts etc, so that you wouldn't have to rewrite common ideas from scratch?

Various books fill this purpose. But the problem is that theorems are difficult to encapsulate. For example, a theorem will say "Assume X, Y, and Z. Then A and B are true." and you need to use it in some situation where Z isn't true, but some appropriate variant of Z is, and any expert would know how to conclude that A and B are true. This is when the handwaviness comes in.

Mistakes do happen. But surprisingly rarely.

Re:An ABC proof too tough even for mathematicians by jlouis on Sunday November 25, 2012 @05:52PM (#4829563)
Let me add to this. When you try to formalize a proof in a proof assistant, then almost all of the time, you will find numerous errors in the proof.

But - and this is key - these errors are usually fixable or the area is not understood well enough and requires more attention to detail. The human intuition is quite powerful.

Re:An ABC proof too tough even for mathematicians by scotty79 on Monday November 26, 2012 @12:57AM (#4830806)
That's similar to when you subject working software system to new batch of tests or test it in some new way.

Usually a lot of previously known errors will crop up despite that the system already works mostly as intended.

Re:An ABC proof too tough even for mathematicians by pseut on Sunday November 25, 2012 @09:35PM (#4830133)
>>What if they all overlook some crucial aspect because of the way they were trained, or their entrenched / ingrained assumptions?

>This happens surprisingly rarely. It helps that we are trained to constantly question our entrenched assumptions.

It also helps that finding a counterexample to a widely accepted proof tends to enhance one's career and reputation.

Re:An ABC proof too tough even for mathematicians by mbell on Sunday November 25, 2012 @05:07PM (#4829448)
> Of course! If proving theorems could be readily automated, this would have been done already.

It doesn't need to create the proof, just validate it. See P vs NP.

Re:An ABC proof too tough even for mathematicians by Someone on Sunday November 25, 2012 @05:43PM (#4829545)
To have an automated proof checker validate a proof, someone would have to lay out every single step in the proof in enough detail for the verifier to do its work. With current verifiers, that means 'in painstaking detail'. Only highly educated and motivated people can do that, it takes ages, and it is not very rewarding (neither financially nor otherwise). Because of that, volunteers are hard found.

In some sense we won't really know whether a proof is rock-solid until we have run it through a verifier, using a proven-correct verifier on proven-correct hardware.

If theorem provers grow to be more easy to use, we may require proofs to be verified, but we aren't there yet by a wide stretch.

For an idea about how hard this can be, check out http://www.cs.ru.nl/~freek/comparison/comparison.pdf: 

"In 1998, Tom Hales proved the Kepler Conjecture […] with a proof that is in the same category as the Four Color Theorem proof in that it relies on a large amount of computer computation. For this reason the referees of the Annals of Mathematics, where he submitted this proof, did not feel that they could check his work. And then he decided to formalize his proof to force them to admit that it was correct. He calculated that this formalization effort would take around twenty man-years"

(that effort is ongoing at http://code.google.com/p/flyspeck/wiki/FlyspeckFactSheet)

Re:An ABC proof too tough even for mathematicians by xyzzy123 on Sunday November 25, 2012 @06:21PM (#4829641)
So would it be fair to say then, that these proof checkers are missing the 'libraries' that would be needed to efficiently write verifiable proofs for modern mathematics?
Re:An ABC proof too tough even for mathematicians by cperciva on Sunday November 25, 2012 @06:35PM (#4829663)
Exactly. And this is where most of the work on proof checkers is happening -- finding ways that people can input proofs in a less formal way and have automated code fill in the formal details as a first pass before running the verification.
Re:An ABC proof too tough even for mathematicians by makmanalp on Sunday November 25, 2012 @06:42PM (#4829686)
Indeed! This is exactly what I was trying to say!
Re:An ABC proof too tough even for mathematicians by makmanalp on Sunday November 25, 2012 @06:40PM (#4829678)
Right, this was what I was going for. I can't imagine computers being imaginative enough for coming up with proofs, but verifying seems like it should be rather trivial since mathematical notation is already almost rigorous enough to be a programming language.
Re:An ABC proof too tough even for mathematicians by Evbn on Sunday November 25, 2012 @08:36PM (#4829987)
The more advanced the math gets, the more deeply ambiguous the notation gets. Everything becomes Tx, while T and x become ever more complex objects, whose definiton is implied by context.
Re:An ABC proof too tough even for mathematicians by Evbn on Sunday November 25, 2012 @08:33PM (#4829980)
Zeilberger has some nice examples of human error on his blog. He would love to see much more use of computer provers to clean up the errors made by human writers and readers.
Re:An ABC proof too tough even for mathematicians by dalke on Sunday November 25, 2012 @05:20PM (#4829487)
It's absolutely easier for humans to prove complex theorems than it is to encode it on a computer. Consider if your computer proof system only knows about finite numbers, when your proof deals with transfinite numbers. (There is a one-to-one mapping from each integer to each rational fraction, but there no such mapping exists from the integers to the reals, showing that size of the set of reals is fundamentally larger than the size of the set of integers, despite both being "infinite" in size. -- there is more than one type of infinity.) How do you encode that information

Complicated theorems, like the four-color theorem, are different point. Note there though that the original proof of the four-color theorem, which was based on a computer enumeration, was not convincing to many mathematicians when it first came out, in part because it wasn't feasible to verify manually. Researching now, I see that a proof verified by Coq now exists, which I think reduces the amount of distrust.

Yes, mathematicians "come to a consensus." And they make mistakes. Proofs are sometimes believed to be correct for several decades before being shown to be incorrect, though for important proofs - proofs that others depend on - that's extremely rare. But it isn't super handwavy. They've developed processes over time to help identify flaws. This link outlined a few of them: many people work in the same area, so they can cross-check, and workshops and other meetings serve as a way to spread knowledge and get feedback. Note how it will be a couple of years before the proof is published.

If there's a missing crucial aspect, then that may reveal new types of math. Consider the work of Cantor. Quoting Wikipedia, it was "so counter-intuitive—even shocking—that it encountered resistance from mathematical contemporaries such as Leopold Kronecker and [others], while Ludwig Wittgenstein raised philosophical objections. Some Christian theologians (particularly neo-Scholastics) saw Cantor's work as a challenge to the uniqueness of the absolute infinity in the nature of God ... The objections to his work were occasionally fierce: Poincaré referred to Cantor's ideas as a "grave disease" infecting the discipline of mathematics, and Kronecker's public opposition and personal attacks included describing Cantor as a "scientific charlatan", a "renegade" and a "corrupter of youth.""

Nowadays, Cantor's work is considered the origin for set theory.

Part of the training in math is to make those "semantic things" well-defined.

If you go further into the philosophy involved, then you start dealing with formalism, where everything is reduced to symbols manipulated by a grammar (hence how Stephenson's 'Anathem' refers to computers as 'syntactic devices'), and with Zermelo–Fraenkel set theory, which is one of the most common foundations of mathematics. However, then you have things like the continuum hypothesis and the axiom of choice which are not part of the the ZF set theory, leading to ZFC set theory. And at this point I'm well beyond what I know about the philosophy of mathematics.

Suffice it to say that a full formalist description of a theorem, such that it can be reduced to a machine proof, is hard. Take a look at "Principia Mathematica" by Whitehead and Russell. Among other things, it used logic to show that 1+1=2. (See the end of the proof at http://en.wikipedia.org/wiki/File:Principia_Mathematica_theo... - "The above proposition is occasionally useful.") That might give you a idea of what the effort looks like.

Re:An ABC proof too tough even for mathematicians by sold on Sunday November 25, 2012 @06:37PM (#4829667)
I have to strongly disagree with your first paragraph. Proofs by humans are finite objects, even if they speak about properties of infinite sets. This difference does not make proofs for computers more difficult than for humans. You can encode cardinality theorems easily in interactive theorem provers.

Formally, a proof is a sequence of assertions, where each one is an axiom or follows from previous ones. Humans are better at proofs because they have good and well-developed intuition; it's bit like coding in assembly vs coding in a high level language. The fact that you deal with infinite objects is not relevant.

Re:An ABC proof too tough even for mathematicians by dalke on Sunday November 25, 2012 @07:34PM (#4829809)
I was trying to come up with a example where a theorem prover would have to be extended or rewritten in order to handle new types of mathematics. My imaginary scenario is a theorem validator built by mathematicians from pre-Cantor days, where I conjecture that it would be hard to encode transfinite proofs. As I know nothing about how theorem provers work, this is purely conjectural.

In more concrete terms .. and I am so far outside my knowledge that I barely know what I am saying ... I read in the Coq FAQ that "The axiom of unique choice together with classical logic (e.g. excluded-middle) are inconsistent in the variant of the Calculus of Inductive Constructions where Set is impredicative. As a consequence, the functional form of the axiom of choice and excluded-middle, or any form of the axiom of choice together with predicate extensionality are inconsistent in the Set-impredicative version of the Calculus of Inductive Constructions."

In other words, proofs involving "axiom of unique choice together with classical logic" cannot be expressed in at least Coq. While it might be possible to use a machine to check tools which assume the axiom of unique choice, it would no doubt take a lot of work if one needs to build such a system from scratch.

And that is the scenario - where it's much more difficult to develop a mechanical tool than to come up with a proof that enough for humans - that I am contemplating.

Re:An ABC proof too tough even for mathematicians by sold on Monday November 26, 2012 @07:12PM (#4834774)
What do you mean by "transfinite proofs"? Let's look at Cantor's proof. It is:

For every set A and function f : A -> P(A) there exists y in P(A) such that for all x, f(x) /= y.

Proof: Define y = {a: a is not in f(a)}. If f(x) = y, then f(x) = {a: a is not in f(a)}, but this implies x is in f(x) <=> x is not in f(x), contradiction.

It does not mention infinity anywhere! It only says that there cannot be a surjection between one set and the other. We could call this situation "transfinite" but this is only a name; under the hood, this is a normal proof of properties of functions, using very natural reasoning rules. That's why I disagreed - there's nothing special in Cantor's proof from a formal viewpoint, possible concerns are of psychological/historical nature, which are not relevant to a machine.

It is true that changing foundations might require rewriting the prover. However, humans also need time to adjust to a new formal system. For example, it takes a lot of effort to get a good grasp of intuitionistic logic. This might be a concern, but ZFC is a very well-grounded common framework for mathematicians, and this is extremely unlikely to change. Perhaps calculus of constructions, as a version of lambda calculus, is closer to computation, and this is why it was chosen in Coq. I'm not sure. Mizar (another theorem-proving environment) is based on an extension of ZFC. [ZFC is untyped - everything is a set, while CoC has a rich type system.]

Small nitpick: It's not like proofs involving unique choice + excluded middle cannot be expressed in Coq; they can, but as the system is inconsistent, they have no value, as everything is provable.

Re:An ABC proof too tough even for mathematicians by leephillips on Sunday November 25, 2012 @06:48PM (#4829711)
This is related to the issue that the criteria for what constitutes a rigorous proof continually evolves, and has undergone tremendous change since Euclid. Morris Kline has a good semi-popular account of this history [http://www.amazon.com/Mathematics-Loss-Certainty-Galaxy-Book...].
Re:An ABC proof too tough even for mathematicians by duaneb on Sunday November 25, 2012 @05:25PM (#4829505)
I suspect that Godels incompleteness theorems may imply that no single algorithm can solve all proofs. This is actually the basis for Penrose's argument that the mind is non-deterministic, though his argument is deeply flawed.
Re:An ABC proof too tough even for mathematicians by leephillips on Sunday November 25, 2012 @06:56PM (#4829726)
Penrose's argument, if I remember correctly, is not that the mind is necessarily non-deterministic, but that it is not equivalent to an algorithm - that you can never program a computer to create a mind. It might also be non-deterministic, but that is not exactly the same thing. His evidence for this is indeed that we can "know" the truth of theorems whose proof can not be reduced to an algorithm.
Re:An ABC proof too tough even for mathematicians by duaneb on Sunday November 25, 2012 @07:09PM (#4829750)
Wouldn't finite, deterministic systems necessarily be able to be modeled by an algorithm? Either the human mind is infinite in some way, non-deterministic, or it must be able to be modeled by an algorithm.

NB I am a programmer and very weak in theory.

Re:An ABC proof too tough even for mathematicians by leephillips on Sunday November 25, 2012 @08:02PM (#4829884)
There is no algorithm that can determine the truth of any proposition in arithmetic (for example). It is impossible, in principle, to construct such an algorithm. But given any proposition in arithmetic, the mind can decide its truth value. It is in this sense that Penrose claims the mind can not be modeled by a computer program. It may seem odd now, but at the time there was still a school of artificial intelligence that assumed that a big computer running a really sophisticated program could be equivalent to a human mind. Penrose was trying to show that this idea is a non-starter.
Re:An ABC proof too tough even for mathematicians by cbr on Monday November 26, 2012 @08:24AM (#4831798)

    at the time there was still a school of artificial 
    intelligence that assumed that a big computer running a
    really sophisticated program could be equivalent to a
    human mind
We're talking theory, so imagine we have extremely powerful hardware, gobs of memory, understand the brain really well, and have some sort of extremely high-resolution scanning device. We could build an "emulator" that would simulate the brain's "hardware" and then load a scan of someone's brain onto it as "software". The system as a whole is just a big computer running a sophisticated program but it's equivalent to a human mind. This mind running on a computer would have the same strengths and weaknesses as the mind had when running on a biological brain when it comes to determining the truth values of propositions in arithmetic (and everywhere else).
Re:An ABC proof too tough even for mathematicians by leephillips on Monday November 26, 2012 @09:32AM (#4832049)
To say that a computer program can not, in principle, do what the mind does is not to say that the mind can not exist on a substrate other than the familiar biological one. In your thought experiment the "software" would not be a computer program as we understand it; it would not be a set of algorithms. Also, it is problematic to separate "hardware" and "software", and to define what a "scan" of the brain might be.
Re:An ABC proof too tough even for mathematicians by hackinthebochs on Sunday November 25, 2012 @10:10PM (#4830246)
>There is no algorithm that can determine the truth of any proposition in arithmetic (for example).

Currently, yes. But I don't see that this is necessarily true. Why do you think it is?

Re:An ABC proof too tough even for mathematicians by krichman on Sunday November 25, 2012 @11:47PM (#4830567)
Simply because there are some propositions that are unprovable in a consistent system with finite axioms. Having an algorithm that solves any proposition would be equivalent to having an algorithm that solves the halting problem.
Re:An ABC proof too tough even for mathematicians by hackinthebochs on Monday November 26, 2012 @12:23AM (#4830699)
>There is no algorithm that can determine the truth of any proposition in arithmetic (for example). It is impossible, in principle, to construct such an algorithm. But given any proposition in arithmetic, the mind can decide its truth value.

These two statements seem to contradict, unless you grant that the mind either fudges the proof or constructs new axioms such that the proof can be valid. Why do you assume a program can never do this?

Re:An ABC proof too tough even for mathematicians by leephillips on Monday November 26, 2012 @09:35AM (#4832062)
Because the program that does it would itself be an algorithm with its own finite set of axioms. There would be undecidable propositions unreachable by the program.
Re:An ABC proof too tough even for mathematicians by DanWaterworth on Monday November 26, 2012 @01:31AM (#4830914)
Solving the halting problem wouldn't be sufficient to tell you whether a proposition was true, but it could tell you whether a proposition is independent and if it wasn't whether it was true or false.
Re:An ABC proof too tough even for mathematicians by voyou on Monday November 26, 2012 @05:00AM (#4831337)
"Given any proposition in arithmetic, the mind can decide its truth value."

Really? I don't see what reason we have to believe that this is true.

Re:An ABC proof too tough even for mathematicians by leephillips on Monday November 26, 2012 @09:39AM (#4832075)
I guess I didn't really mean that. What I should have said was that in any system of axioms (or within any algorithmic structure) there will exist undecidable propositions (unreachable by the algorithm). The mind can determine the truth value of some of these, so the mind can not be encompassed or modeled by an algorithm.
Re:An ABC proof too tough even for mathematicians by duaneb on Monday November 26, 2012 @10:13PM (#4835429)
> The mind can determine the truth value of some of these, so the mind can not be encompassed or modeled by an algorithm.

Do you have an example of this? I have an extremely difficult time comprehending it. Also, I was under the impression that there weren't necessarily propositions that are not algorithmically possible to reach, but rather, there are always propositions a given algorithm cannot solve.

Re:An ABC proof too tough even for mathematicians by leephillips on Tuesday November 27, 2012 @12:47PM (#4837741)
> not algorithmically possible to reach

I just meant undecidable propositions.

> Do you have an example

Maybe check out the conclusion on p.76 of this book[1] by Penrose (and the argument supporting it that begins on p.72.): "Human mathematicians are not using a knowably sound algorithm in order to ascertain mathematical truth".

His example is our knowledge that a certain computation will not halt, and the impossibility of constructing an algorithm that can prove that fact.

More flippantly, you know that you can examine the soundness of your own reasoning, but no algorithm can reach conclusions about its own correctness.

[1]http://www.amazon.com/dp/0198539789

Re:An ABC proof too tough even for mathematicians by wbl on Sunday November 25, 2012 @10:31PM (#4830332)
Okay, so is the twin prime constant transcendental?
Re:An ABC proof too tough even for mathematicians by mjcohenw on Monday November 26, 2012 @01:45AM (#4830949)
Yes.
Re:An ABC proof too tough even for mathematicians by Evbn on Sunday November 25, 2012 @08:39PM (#4829995)
Gödel's theorems are about uncountable infinities of statements, and statements whose meaning proof is outside the bounds of a theory. Nothing contradicts the possibility of an algorithm as good as as any human doing formal math.
Re:An ABC proof too tough even for mathematicians by ctkrohn on Sunday November 25, 2012 @05:02PM (#4829440)
Terence Tao, one of the preeminent mathematicians working today, had a pretty good post on this exact question:

http://terrytao.wordpress.com/career-advice/there%E2%80%99s-...

Re:An ABC proof too tough even for mathematicians by kruipen on Sunday November 25, 2012 @05:22PM (#4829494)
Good read. You could change a few phrases and make it a post about learning programming rather than mathematics.
Re:An ABC proof too tough even for mathematicians by DanBC on Sunday November 25, 2012 @05:06PM (#4829446)
> Wait, so you're saying it's easier for humans to prove complex theorems than computers?

Computer proofs tend to be brute force. For example: Are all games of Freecell winnable? But a brute force run of all Freecell games just tells us that all but one game is winnable, but tells us nothing about what's happening or why.

Re:An ABC proof too tough even for mathematicians by njs12345 on Sunday November 25, 2012 @05:19PM (#4829483)
That's not true for proofs in assistants like Coq, which work by generating a program whose type can be checked to verify the statement in question.
Re:An ABC proof too tough even for mathematicians by joshmaker on Sunday November 25, 2012 @05:58PM (#4829584)
Computers may not be able to solve proofs, but they can help. In fact, there is a BOINC project aimed at finding triples for the ABC conjecture: http://en.wikipedia.org/wiki/ABC@home
Re:An ABC proof too tough even for mathematicians by Camillo on Sunday November 25, 2012 @07:35PM (#4829813)
Honestly, you sound more like a "non-science" person there. Did you think many branches of science have an epistemology founded on automatic computation? Think again!
Re:An ABC proof too tough even for mathematicians by kvb on Sunday November 25, 2012 @04:22PM (#4829332)
This seems overly pessimistic. I'm sure it'd take a lot of work, but consider results like Gonthier's proof of the Odd Order Theorem (see http://research.microsoft.com/en-us/news/features/gonthierpr...), which formalized a book-length proof.