The late great Paul Erdös was not a religious man (his take on religion seems to have been fairly ironic, referring for example to God as “The Supreme Fascist”), except of course when it came to mathematics. Ever the Platonist, he considered that when he died, he might finally get a chance to gaze upon “The Book” which, as if written by God, contains the most beautiful and enlightening proofs of all theorems. The highest form of praise from Erdös for a proof was, “It’s straight from The Book!” He also said, “You don’t have to believe in God, but you should believe in The Book!”

Do you believe in The Book? I’m not sure I do!

In fact, there is this book by Aigner and Ziegler, “Proofs from The Book”. In it they include the following one-sentence proof by Don Zagier on Fermat’s two square theorem (that a prime congruent to 1 \pmod 4 is a sum of two squares):

A One-Sentence Proof That Every Prime p congruent to 1 modulo 4 Is a Sum of Two Squares

                                        D. Zagier

      Department of Mathematics, University of Maryland, College Park, MD 20742

The involution on a finite set S = {(x,y,z) \in N^3 : x^2 +4yz = p } defined by

                      ( x+2z, z, y-x-z )  if   x < y-z
       (x,y,z) ---> { ( 2y-x, y, x-y+z )  if y-z < x < 2y
                      ( x-2y, x-y+z, y )  if   x > 2y

has exactly one fixed point, so |S| is odd and the involution defined by 

       (x,y,z) ---> (x,z,y)

also has a fixed point.

I plucked this off the Web from here; the author of the page prefaces it with a comment:

The following constitutes the essential text of a complete research article; I have
omitted only some comments at the end concerning the history of this type of argument.
The author reproves a famous result.  He builds his proof into a single sentence
as simply a tour-de-force.  In fact, he has left many straightforward steps for
the reader to verify.

1.  As an exercise in critical reading, list all the implicit claims that the
reader must verify in order to accept this argument as a proof.

2.  As an exercise in logic and algebra, supply all the details necessary to
support these claims.   Package all this as a long-winded rewrite of Zagier's
article written so that any high school algebra student could easily read it
with comprehension.

You should expect to expand Zagier's single sentence to a full page or more.

Um, yeah.

My own reaction to this proof: it is surely dazzling in its compression, although one’s first reaction is likely to be “WTF?!?” — what just happened here? The underlying idea is that the number of fixed points of an involution f: S \to S on a finite set S (i.e., a function f equal to its own inverse) has the same parity as S itself; it follows that if S has odd parity, then any involution on S has at least one fixed point; such a fixed point of the involution (x, y, z) \leftrightarrow (x, z, y) on Zagier’s set S yields a solution (x, y) to x^2 + 4y^2 = p, whence the theorem. So the bulk of the proof is in showing that S has odd parity, by showing that his nontrivial involution has exactly one fixed point.

And I guess you can see, by staring at his casewise-defined involution for a while, that its only fixed point is (x, y, z) = (1, 1, n) where p = 4n+1. It then remains to check that this really is a well-defined function from S to S, and it really is an involution. The full verification probably does take up at least a page.

It truly is a jaw-dropping proof. My problem though is that it looks like black magic. I mean, I can construct a line-by-line verification that the proof does what it purports to do, but in a deeper sense I still don’t get it. How Zagier cooked up this involution is a mystery to me, and unless I made a concerted effort to memorize it, it would remain unmemorable to me (that is, unless someone were to reveal the underlying mystery to me — I suspect that that would take a few sentences or more! Can anyone help me?).

What do you think — does it qualify as a Book proof? Me personally, I prefer proofs which are enlightening — arguments that I can really understand, proofs that stick, proofs I can take with me to the grave. Put it this way: if God were to write a proof which consumed an absolute minimum number of bytes in some optimal language, it still wouldn’t be much of a Book proof to me unless I (a limited human) could really understand it, and if it were really better in that sense than its closest competitors.

I don’t think I believe too strongly in the reality of “Book proofs”, or at least I’m skeptical that every theorem can be said to have a Book proof. Every mathematical statement and proof is embodied in some larger context or matrix of ideas, many requiring patient assimilation before a light suddenly flashes on. I tend to believe that’s the rule rather than the exception, and the idea that we should believe in a Book proof for every theorem, possessing a snappy immediacy which cries “Behold!”, is based on a dangerous and even crazy fallacy concerning the nature of mathematics.

[At the same time: we can all agree that Erdös was an absolute genius at finding Book proofs! :-) ]

About these ads