Friday, February 06, 2009

The Ugly Proof

Alice: Does Carol's proof solve your big open problem?
Bob: Yes, but it's an ugly proof so it doesn't count.

A beautiful proof—a proof from "The Book"—is a piece of art. You take a look at it and just say "Wow!"

But what about the ugly proof. A boring case analysis that doesn't generalize and gives little to no insight as to why the theorem is true. A colleague, who for some reason wants to remain anonymous on this issue, has strong opinions about ugly proofs.

I guess the question is if there is a nicer proof or not. If there turns out to be, well and good. If not, probably it wasn't a very nice question. Nice questions have pretty answers.

I'm all for banning ugly proofs, except that there's likely to be a lack of agreement on what constitutes ugliness. The one positive aspect of an ugly proof is that it might lead to a nicer one. If not, it's worse than no proof at all.

I'm all for pretty proofs but if you have an open problem you care about, a need to get from point A to point B, while it is nicer to fly first class, getting to point B by driving a bumpy road still gets you to point B.

An ugly proof has the same logically correctness as a pretty one. Does the truth lack interest just because we had to take a painful path to get there?

15 comments:

  1. A boring case analysis sounds like something that can be automated, and that may be fun.

    I know of two areas that take this approach: software verification (e.g., Spec#) and computer algebra systems (e.g., A=B).

    ReplyDelete
  2. Is the proof of the Robertson-Seymour theorem on graph minors ugly or beautiful?

    ReplyDelete
  3. My "math camp" instructor insisted, "We don't prove things to establish truth." (The implication was that we prove to understand, not to get from point A to point B.)

    ReplyDelete
  4. Nice questions have pretty answers.

    I don't think that opinion is supported by the facts.

    Thanks to Robertson and Seymour, we now know of a vast class of problems (predicates over graphs closed under minors) which are interesting (say four coloring of planar graphs) and have no pretty answers.

    Similarly, the breakthrough algorithm of Bender and Farach-Colton for LCA also has a case analysis component which while not particularly ugly it is certainly not common. In my opinion, this makes their result all the more remarkable. It is a heavily cited paper, so clearly the result is considered important.

    ReplyDelete
  5. I believe that an ugly proof can open the way to the discoverty of a really marvelous proof, one that deserves its place in "the book". This is especially important when whe do not know the answer of a big open question and an ugly proof finally asserts it.

    ReplyDelete
  6. I think that it often goes the other way. Given:

    (1) a simple and beautiful non-constructive proof of the existence of an object, or

    (2) an ugly constructive one that shows very precisely what such an object must be like,

    which is better? I'd say that the latter gives much more insight - the exact opposite of your claim.

    ReplyDelete
  7. When you actually care about the question, the ugliness of the proof doesn't matter (unless you need to implement it, and the algorithm itself is ugly).

    When you care about the answer more than the question, then an ugly proof can be dismissed more easily. Of course, people will disagree about whether a proof is ugly or not.

    For example, I consider Ladner's proof that there are languages in NP that are not NP-complete to be ugly and unsatisfying. I guess I don't care whether such languages exist but would be more interested to know of "interesting" examples of such languages.

    ReplyDelete
  8. A proof is a proof is a proof. Its primary purpose is to establish the truth of a statement. One can say that there is a certain beauty in truth itself.

    Mathematics is not about the subjectivity of something as imprecise as "beauty," although most good mathematicians would recognize it when they see it. Ugly proofs should not be banned because oftentimes they can serve as "shoulders" for the giant, beautiful proofs to stand on.

    ReplyDelete
  9. I think that whether or not I'd value an ugly proof depends on what I'd conjectured before the proof was known. If the result is surprising, I don't care if the proof is nice. The (ugly) proof has thus changed my perception of the world.

    On the other hand, if the ugly proof is of something I (and many others) believe to be true, then the ugly proof still hasn't answered the intuitive question of why is the result true, which is really motivating the need to prove it. Furthermore, the ugly proof is probably of little use in generalizations.

    ReplyDelete
  10. Mathematics is not about the subjectivity of something as imprecise as "beauty"

    But the point of a proof isn't to convince us that a statement is true; for most major open problems, mathematicians developed a collective intuition about the truth of a statement long before a formal proof came. The point is to give us some insight into why it's true, so we can use that insight to investigate other, similar (or not so similar) problems. And that's one of the yardsticks of mathematical beauty (though by no means the only one).

    ReplyDelete
  11. Ugly proof is like ugly code.
    Should be discouraged in general.
    Ugly proofs only for long standing open problems.

    ReplyDelete
  12. I thought beauty, like happiness, cannot be sought directly on purpose.

    ReplyDelete
  13. The total number of beautiful proofs may be much less than the total number of ugly proofs.
    I conjecture that if N is the total number of proofs in this universe, then only O(log(N)) proofs would be considered beautiful.
    This conjecture is probably supported by currently known proofs (which should make a resonable random sample)

    ReplyDelete
  14. This comment has been removed by the author.

    ReplyDelete
  15. Doron Zeilberger has a lot of rants in favor of ugly proofs. Here is one giving the general idea:

    http://www.math.rutgers.edu/~zeilberg/Opinion90.html

    ReplyDelete