Deciphering Black Magic in Mathematics
How inexplicable proofs sometimes find explanations
This post is based on something I wrote in 2018, but I have decided to rewrite it almost from scratch. To be a bit more specific, it was an answer to “What is the closest thing to magic that actually exists?”, in which I argued that certain kinds of mathematical proofs should certainly qualify, as satirized by Randall Monroe.
A black magic proof isn’t necessarily difficult to follow—indeed, in the best examples, every step is simple and evident. What truly sets a black magic proof apart is that once you have read through it, even though you understand every step and know logically that it is correct, you still feel a sense of disbelief that this has actually worked. And then you also start wondering how the hell anyone came up with this in the first place?
Proofs that strongly rely on mathematical logic usually feel like black magic to me—I had an example using the compactness theorem in an earlier post.
But logicians and model theorists do not have a monopoly on black magic. One of my favorite examples of a black magic proof comes from elementary number theory and doesn’t use any complicated techniques. It also has the unusual distinction of being later transmuted into an intuitive, visual proof.
Allow me to introduce you to Zagier’s one-sentence proof of Fermat’s observation (relayed in a letter to Mersenne in 1640) that an odd prime number p is a sum of two squares if and only if p=4n+1 for some integer n—this is usually known as Fermat’s theorem on sums of two squares1. For example:
On the other hand, you can check that there is no way to write 3, 7, or 11 as a sum of two squares.
It is simple—particularly if you know a bit of modular arithmetic—to prove that if an odd prime number p is a sum of two squares, then it must be of the form p=4n+1. The reason is this: if it isn’t, then it must be of the form 4n+3. But you can check that a sum of two squares is either of the form 4n (if both are even), 4n+1 (if one is even and the other odd), or 4n+2 (if both are odd)—never 4n+3.
The harder part is to go the other way: prove that if p=4n+1 then there must be some way to write p as a sum of squares. Euler had a clever proof based on infinite descent and an old identity due to Diophantus; Lagrange gave a wonderful proof based on his theory of binary quadratic forms; Dedekind gave a couple of proofs using the properties of Gaussian integers; and so on. Each of these proofs takes at least a page or two of work.
And then, in 1990, Zagier found a proof that could be written down in a single sentence. Here is the paper, reproduced in its entirety.
Let me give a more gentle run-down of this bizarre proof and the logic behind it. We want to find non-negative integers x,y such that p=x2+(2y)2=x2+4y2, but since this is difficult, we instead try finding non-negative integers x,y,z such that p=x2+4yz. Since we know that p=1+4n, this is definitely possible: take x=1, y=1, z=n, for instance. So, let’s consider the entire collection of triples of non-negative integers (x,y,z) such that p=x2+4yz; we will call this S. As we have already shown, it is non-empty; it is also finite, since 0≤x,y,z≤p. What we want to prove is that S contains some triple with y=z—if we do that, then we have expressed p as a sum of two squares.
How to do that? Well, observe that if (x,y,z) is in S, then so is (x,z,y)—so we have an involution (a function that is its own inverse) defined on S that allows us to pair up solutions. Well, I say pair up, but in principle, an element can be paired up with itself: precisely, when (x,y,z)=(x,z,y) (that is, we say that this involution has a fixed point). So let’s suppose that never happens. Then S can be cleanly split into two equal pieces—that is, S has an even number of elements.
Ah ha! If we can prove that S has an odd number of elements, then we will have proved that (x,y,z)=(x,z,y) for some triple. But how can we do that? Easily enough: find some other involution of S that has exactly one fixed point. Then this involution will divide S into two equal pieces minus this one fixed point—that is, S must then have an odd number of elements.
Up to this point, the proof has been completely reasonable, and one can even imagine how the author could have come up with it. But in the next step, Zagier heads in a seemingly gonzo direction by defining the following function on S:
It isn’t hard to prove that I is a well-defined function on S—it is just a bit of algebra. It also isn’t so hard to prove that I has exactly one fixed point: namely, (1,1,(p-1)/4). And putting all of that together, we finally have a proof of our desired result.
But, um… why?! Where did this function come from? This is the black magic part: one wonders where Zagier could have summoned this beast from, and what part of his soul he must have sacrificed to do it. He gives few hints: only that this proof was based on a proof of Heath-Brown, which was in turn based on a proof of Liouville. Evidently, distilling the ideas of past mathematicians left an inexplicable residue.
Now, that in itself is, to me, a great story. But it gets better, because there is an intuitive explanation for Zagier’s proof—it just wasn’t found until years after he published it. This is completely backwards to the usual progression of mathematics: usually, the intuitive idea comes first, and then the formal proof!
It isn’t totally clear who came up with this intuitive idea—the best guess seems to be Alexander Spivak, who wrote it up as part of lecture notes at Moscow State University in 2007. But it is gorgeous, and I will share it with you now.
We’re going to give a geometric description for the triples (x,y,z) in S, as follows: define the corresponding windmill to be the geometric figure that you get by starting with a square with side length x and then attaching four rectangular “spokes” with side lengths y and z at the corners.
What is the area of such a windmill? It is exactly x2+4yz. Ah, this means that S is just the collection of all triples (x,y,z) that correspond to windmills of area p. But it gets better: let’s draw our windmills all in one solid color.
Do you see what has happened? The windmill that is just a unit square with four thin spokes coming out of the sides is all by itself, but all of the other windmills come in pairs!
What is this matching between windmills? If you run through the details, it is exactly the involution that Zagier wrote down! We get one fixed point: (1,1,(p-1)/4), corresponding to the windmill that looks like a cross. All other windmills come in pairs, coming from the two ways to decompose any such shape: you can have a large square at the center and shorter spokes, or a small square and longer spokes.
Black magic turned into proof-by-picture—a magnificent transformation!
We don’t know for sure that Fermat had a proof—he claimed that he did, but he seldom wrote down any of his proofs. The first documented proof was due to Euler in 1749, over a hundred years later.
Beautiful!
Good post