Skip to content

Great Proofs as Great Art

April 14, 2010


Can we view and appreciate great proofs as great art?

Leonardo da Vinci was not a complexity theorist, but according to our friends at Wikipedia he was just about everything else: a painter, a sculptor, an architect, a musician, a scientist, a mathematician, an engineer, an inventor, an anatomist, a geologist, a cartographer, a botanist and a writer. If he was alive now, I wonder what brilliant things he would be doing.

Today I want to discuss a question related to Leonardo as an artist: can we view great proofs as great art? I think we can, and I would like to explain why.

Connecting proofs and art reminds me of a legend I heard at Yale, many years ago, concerning the beginning programming class, CS 101. I do not believe the legend, but this will not stop me from repeating it. The legend goes there was once an exam given to a 101 class, containing the question:

Evaluate the following expression:

\displaystyle  \mathsf{E} + \mathsf{H} \times \mathsf{E}

where { \mathsf{E} = 3} and { \mathsf{H} = 4}.

The correct answer was {15 = 3 + (4 \times 3)}, not {21 =( 3 + 4) \times 3}, since the operator “{\times}” has higher precedence than the operator “{+}”. But, the legend is one student “evaluated” the expression as follows:

The expression { \ \mathsf{E} + \mathsf{H} \times \mathsf{E} \ } has a pleasing horizontal symmetry, and a near left-to-right central symmetry, and is also {\dots}

You must remember Yale was filled with very bright students, but their main interests were often in the liberal arts, not in mathematics. The student was right, the expression does have some nice symmetries {\dots}

Studying Great Art

How do we study great art? Consider Mona Lisa as an example—perhaps the best known painting in the entire world. We may, if in Paris, go to the Louvre and wait in a long line, and eventually get a glance at the famous painting. Or we may study reproductions of the Mona Lisa in art books, in other reproductions, or even on-line today.

Most of us look at the Mona Lisa and see different things. We may like it, we may love it, or we may prefer more modern paintings, but most are amazed at Leonardo’s achievement.

Our goal in looking at and studying a great work of art, like this, is not to reproduce it ourselves—that is impossible. Our goal is not to even try to understand how Leonardo achieved his great painting, how he captured her famous smile—that also is probably impossible.

Instead our goal is one of enjoyment, of pleasure, of the excitement in seeing the work of a master. We come away with a impression, a general feel, a holist view of what he did. We do not understand each brush stroke, we do not understand how he made his paints, we do not understand how he captured her look, we do not understand how he created the masterpiece. But, we do leave with something.

Studying Great Proofs

I have wondered if we could do something similar with the great proofs. Many read and study a great proof in an attempt to really understand them. If there is a masterpiece in your area of research you may need to understand the proof line for line—you may need to be able to reproduce the proof to be considered an expert in your area.

However, most of us do not even look at the masterpiece proofs, ever. We may know their statements, but most of us—I claim—have no idea of how they work. Nor do we need to understand them line for line. But my thesis is this:

We can learn from a study of the great proofs, even if we do not follow the proofs in detail.

We should study the great proofs, not to understand them completely, but in the same way people study the Mona Lisa. For enjoyment, for enrichment, for seeing a master at work, and for getting something out of the study. Not to be able to reproduce the Mona Lisa. What we learn may be intangible, but still invaluable. Again, we can leave with something.

Some Great Proofs

Here are some sample great proofs—there are many others, these are just a few to make our discussion concrete. The same comments will apply to many other of the great proofs.

One property of many of the great proofs—not all—is they are long. The opposite is not true: there are plenty of long proofs of relatively unimportant results. Length is no measure of greatness, just as the length of a book or the size of a painting is not a measure of its greatness. However, many of the great proofs are long, some are very long. One reason is: a great proof often requires several new ideas and it is reasonable to expect weaving these ideas together can be difficult to explain; hence, the great length of the great proofs.

{\bullet } Feit-Thompson’s Theorem: Walter Feit and John Thompson proved in 1962: Every group of odd order is solvable.

{\bullet } Cohen’s Theorem: Paul Cohen proved in 1962: The Axiom of Choice and the Continuum Hypothesis are independent from Zermelo–Fraenkel (ZF) set theory. Obviously, 1962 was a very good year for great proofs.

{\bullet } Szemerédi’s Theorem: Endre Szemerédi proved in 1975: Every dense enough set has arbitrary long arithmetic progressions.

{\bullet } Wiles’ Theorem: Andrew Wiles proved in 1994: Fermat’s Last Theorem.

What Can One Learn From This Study?

I would like to run a class on the study of great proofs as great art. I would have students “read” each of the great proofs, and we would have discussions about them. I would not expect, even the top students, to be able to understand the proofs fully, or even partially. I would not expect anyone to understand the proof at any deep level at all. They may, even should, understand parts of the proof completely—a lemma here, or an argument there.

I would expect students to learn some appreciation for what it takes to create a masterpiece—a great proof. I believe we can learn a great deal from reading great proofs, even without understanding them in the usual sense. Let’s look and see what we might learn from reading these proofs in this way.

Previous Work

Great proofs usually do not arise out of a complete vacuum. They are almost always based on previous work: they may extend an earlier argument, they may use techniques developed by others, they arise in a complex context.

  • Feit-Thompson: They used a great deal of machinery of group theory. One of the great previous results was due to William Burnside, who had proved every group of order {p^{a}q^{b}} with {p} and {q} both prime is solvable.
  • Cohen: He used Kurt Gödel famous proof of the relative consistency of the AC with ZF.

    Weave Many Ideas Together

    Great proofs often need to use much of the existing machinery. This is similar to the last point, but a bit different. Here the point is the creation of a great proof usually requires the mastery of many tools and techniques.

  • Feit-Thompson: They used almost all aspects of group theory: local analysis, character theory, and relation definitions of groups. They also needed to use non-trivial number theory. At the very end of their proof they could have saved a large amount of work if they could have proved this conjecture: there are no distinct primes {p} and {q} so that

    \displaystyle  \frac{p^{q}-1}{p-1} \text{ divides } \frac{q^{p}-1}{q-1}

    Since they could not, they needed to use even more group theory tricks to get the contradiction they needed.

  • Wiles: He used much of modern number theory, especially the theory of modular forms and Galois representation theory. The famous number theorist Enrico Bombieri said that he would need at least a full year to understand Wiles achievement—this is because of the diverse tools used in the proof.

    Golden Nuggets

    Great proofs often contain new ideas and methods, sometimes these can be more important than the theorem being proved. Note, I have talked all through this discussion about proofs not theorems. This is one reason for this: often the proof is much more important than the theorem itself.

  • Cohen: He created an entire new way of constructing models of set theory. This method, called forcing, is now a standard tool used by set theorists everyday. When Alfred Tarski heard about Cohen’s new method he said: They have a method, now they will get everything.
  • Szemerédi: He needed to prove a certain lemma to make his great proof work. This lemma is the now famous Regularity Lemma.

    Strategic Plan

    Great proofs almost always have a plan of attack. If someone tells you they have solved a long standing open problem by “just an induction”—it is pretty unlikely to be true. Usually, great proofs have a complex strategic plan for the attack of their proof.

  • Feit-Thompson: Their proof is divided into six chapters: each has its own abstract and they give a coherent overview of what each chapter does and how they all fit together.

  • Szemerédi: His proof had a road map: there is a figure showing the various lemmas and the inter-relationships.

    Open Problems

    What are the other great proofs that you view as a work of art? What features, other than those mentioned, do you find often in such proofs?

    Is this idea reasonable? Would you like to take such a course? Should I give this course sometime?

  • 34 Comments leave one →
    1. April 14, 2010 8:46 am

      I’d love to see more written about this! I think the great proofs should be appreciated even if they’re not fully understood.

      Any chance you could make this series available online somehow? I don’t think I’d be able to fly to the US to come to the lecture series🙂

    2. Peter permalink
      April 14, 2010 9:08 am

      Has the labor saving conjecture of Feit-Thompson been proved, and if so, when?

      • subruk permalink
        April 14, 2010 4:24 pm

        The conjecture is false. It was disproved in 1971. The counterexample is p = 17 and q = 3313. See this mathworld link for more details.

        • rjlipton permalink*
          April 14, 2010 6:40 pm

          I think this is slightly off. I may be wrong, but I think they need that X not divide Y. The counterexample is to a stronger conjecture that X,Y are relatively prime.

        • subruk permalink
          April 14, 2010 7:25 pm

          sorry, yes dick is right. this is counterexample to a stronger conjecture that x, y are rel prime.

    3. April 14, 2010 9:09 am

      Abel’s original proof of the insoluability of the quintic is well worth reading, and there’s even a book (Abel’s Proof) that would work as a class text.

      As far as short proofs go, the best I’ve seen recently is the proof that Conway’s Soldiers cannot reach the fifth row.

    4. Farbod Shokrieh permalink
      April 14, 2010 9:43 am

      Curtis T McMullen, in his general audience lecture on Poincaré Conjecture and Perelman’s proof, concludes with the following remark:

      “Dieudonné called mathematics ‘the music of reason’, and I think this is an apt metaphor if you allow that a great opera can take 100 years to write… What’s remarkable is that the end result is not a cacophony; rather, it is a masterpiece beyond the reach of any single composer “.

      (The video is available on his website.)

    5. April 14, 2010 10:05 am

      This is a very good idea, courses such as this can do a lot to develop the culture of mathematics. The metaphor of studying proofs as works of art can be extended further. In some cases what makes a proof great is not the difficulty of the ideas, but their subtlty and the impact they have.

      To start with take the classification of the regular polyhedra. As a proof this can be taught to non-mathematicians. It can even be motivated to primary school children. It is far from trivial, however, and today its impact can be felt in large areas of mathematics.

      More recently we have Cantor’s diagonal argument. This is something taught to nearly all undergraduates, but not always with the context of what a powerful idea it is, and how it lies at the start of the massive developments of Godel, Turing and of course the results of Cohen you mention.

      Euler’s characteristic is another example of an idea that goes far deeper than the difficulty of its proof. As shown for example by Conway’s use of it to classify the wallpaper groups.

      In all these cases being able to understand the proof is a first step, one then needs to step back to appreciate the power and beauty of the ideas.

    6. steve permalink
      April 14, 2010 10:05 am

      i think that the robinson-matijasevic result should be included in this list. it ties together diverse ways of thinking about the same thing and encodes them very nicely. i also think that anyone who doesn’t include julia robinson’s name in that result is committing a crime.

      i’d probably consider adding the PCP theorem as well. the structure of the (more recent) proof is really quite beautiful.

      i think that an important feature of a great theorem is that it shocks you to your core the first time that you hear it (or at least the first time that the truth of it really starts to set in). a great proof is one that makes the truth of a great theorem believable.

      s.

    7. Robert permalink
      April 14, 2010 10:10 am

      Seems like some of these “great proofs” you cited need at least 2-3 years of intense study for a non-expert to acquire the necessary background (certainly for Wile’s Theorem I think).

      This would make your proposed course very challenging – even if you just kept it a high level.

      Would be great if you could pull it off though!

    8. April 14, 2010 10:55 am

      Like gelada, I’m inclined to make a case for Cantor’s diagonalization as a canonically great proof. One of the primary reasons is that it gave us an architecture for thinking about proofs or constructions of other things; its logical toolkit had a lifespan beyond its immediate use. I think it’s quite possible to have a non-expert conversation about the aesthetics of proofs if you frame them as a series of broad logical gestures, and see arguments as wholes rather than parts, or as modules that slide neatly into place. It may benefit mathematicians as well in the form of creative inspiration about how to go about designing a proof.

      In any case, I think having a student discussion about this in the form of a course or seminar would be extremely fruitful. Please do it, and write about it too.

      As far as the literature of elegance goes, G.H. Hardy’s A Mathematician’s Apology is probably a good place to start.

    9. April 14, 2010 11:02 am

      Many readers of this blog must know this, but there is a great book called “Proofs from THE BOOK” which is full of knock-you-flat-with-their-beauty proofs of powerful results — all of which are accessible to advanced undergrads and above. (They are also quite short!) I took a seminar at MIT devoted to this book and it was a great time.

      • Anand permalink
        April 14, 2010 11:10 pm

        For people from Gatech, the book is available in the Theory Lab

    10. Varun permalink
      April 14, 2010 11:10 am

      Tomorrow (April 15th) is Leonardo da Vinci’s birthday. Nice tribute.

    11. caRh permalink
      April 14, 2010 12:11 pm

      I certainly agree that proofs can be seen as works of art. However, I am not sure we can enjoy them without understanding them. Isn’t “to enjoy a proof without understanding it” the same as “to enjoy the Mona Lisa without looking at it”?

    12. Amir Michail permalink
      April 14, 2010 12:40 pm

      It bothers me when I see computer scientists using the word “art” in relation to their work.

      And this is because art can be used to describe something quite different that has nothing to do with implementation/proofs — namely, application level creativity.

      By hijacking the word “art” for their purposes, computer scientists are actually getting in the way of the creation of a new computing field concerned with inventing novel applications.

    13. subruk permalink
      April 14, 2010 12:59 pm

      I like the post, agree that it is nice to view proofs as work of great art.

      But I also agree with caRh’s views above. You might still be able to enjoy Mona Lisa or a symphony without getting the details, but once you learn more about them, learn about the details, you begin to appreciate the little nuances that are part of the masterpiece. With greater learning, you begin to unravel the layers of beauty of the work of art.

      I think the same applies to proofs. You might be able to enjoy the outline of it, or once you learn more details you would enjoy the little tricks which play a part in it.

    14. April 14, 2010 2:19 pm

      Saunders Mac Lane’s classic (but now sadly out-of-print) Mathematics: Form and Function has a section titled IX.9: Mechanics: Tricks versus Ideas that includes the following passage: “Analysis is full of ingenious changes of coordinates, clever substitutions, and astute manipulations. In some of these cases, one can find a conceptual background. When so, the ideas so revealed help us understand what’s what. We submit that this aim of understanding is a vital aspect of mathematics.”

      Mac Lanes remark suggests a working definition of a Great Proof: a proof whose technical ingenuity is guided by a narrative that tells us “what’s what.”

      The range of of the narrative tells us whether we are doing math, science and engineering. If the narrative is entirely about the ascent, then we’re doing “yellow book” mathematics. If the ascent is followed by a survey of the summit, then the narrative is likely about mathematics *and* science. If the narrative embodies mountaineer Ed Viestur’s famous axiom that “Getting to the top is optional; getting down is mandatory”, such that the ascent and summit survey are accompanied by a descent to practical applications, then we’re doing engineering.

      Very few technical narratives cover all three aspects of ascent, summit, and descent. Feynman’s books belong to this uncommon class … in fact the above narrative classification of ascent, summit, and descent is taken straight from page 1 of Feynman’s Statistical Mechanics; a Set of Lectures.

      It seems to me that, for better or for worse, most “yellow books” are largely or entirely about the ascent, whereas great books about descent are relatively uncommon in almost any technical discipline. The few that we have are treasures: The Art of Electronics, for example.

    15. Abhay permalink
      April 14, 2010 2:49 pm

      I think that Godel’s proof of the Incompleteness theorem also presents wonderful insight into the nature of mathematical entities. Recently we did a proof of the undecidability of the Halting Problem which had a very similar idea!

      Btw it would be nice if you could dedicate one post to the Halting problem.

      • rjlipton permalink*
        April 14, 2010 6:36 pm

        Will do…great idea

    16. Someone permalink
      April 14, 2010 3:45 pm

      The graph minors project would be a Sistine Chapel.

    17. April 14, 2010 4:48 pm

      More generally, it is a good idea to study what both oneself and those more accomplished have done that worked—and to try to find out why it worked, what thought-processes took one/them there, which principles tend to lead in a fruitful direction, etc. Proofs would be one of many special cases—and, arguably, the proof it self is a lesser source of information than the road taken to the proof.

      (For lack of opportunity to actually observe the great masters, as well as obvious problems with making in-depth observations of lesser subjects, this claim is somewhat speculative; however, so far it seems to hold-up well.)

      Similarly, it can pay to try to find out why something did not work, etc.

      As an aside: If da Vinci was alive today, he would likely make a much lesser impact. It is even conceivable that he would be a broke and unknown artist, locally infamous for having excentric ideas.

    18. student permalink
      April 18, 2010 5:57 pm

      Interesting post.

      I believe there could be another similar post, which we all may very much like to hear about. How about proofs that are beautiful because of their simplicity (and/or importance of the result)?

    19. Leonardo permalink
      May 3, 2010 2:58 pm

      A clear, conceptual proof of an important result is, besides other things, a mathematical fest. It brings real fun to the profession
      and attracts young people. The long great proofs are similar to long great novels, operas etc.
      But most of people are more atuned to poetry, i.e. to short proofs. In general there is a big similarity
      between highly structural(with rhymes etc.) yet impressionist poems and good proofs, they both
      both have those amazingly non-trivial shortcuts/jumps. In a way, we owe TCS community
      many masterpieces of this genre. Perhaps, the explainations is that the most guys from TCS grew up
      not on Vagner, but rather on Charley Parker, Bob Dylan and Beatles…..

    20. May 3, 2010 11:57 pm

      A very interesting idea

    21. March 20, 2013 7:48 pm

      Very interesting post about proofs of great art. Very conceptualize ideas from the history.

    Trackbacks

    1. Art » Great Proofs as Great Art « Gödel's Lost Letter and P=NP
    2. Great Proofs as Great Art « Gödel's Lost Letter and P=NP | All Topics Blog
    3. Internet Art – The Art of O » Blog Archive » Max’s Work of Art/Max Meets Morris/Ruby’s Scavenger Hunt
    4. Great Proofs as Great Art « Gödel's Lost Letter and P=NP Mobile
    5. Top Posts — WordPress.com
    6. Suggested reading, spine-tingling edition | Nick's Café Canadien
    7. Software As Art | KnowHR Blog
    8. Mathematicians Apology

    Leave a Reply

    Fill in your details below or click an icon to log in:

    WordPress.com Logo

    You are commenting using your WordPress.com account. Log Out / Change )

    Twitter picture

    You are commenting using your Twitter account. Log Out / Change )

    Facebook photo

    You are commenting using your Facebook account. Log Out / Change )

    Google+ photo

    You are commenting using your Google+ account. Log Out / Change )

    Connecting to %s