Chess with the Devil

“As far as God goes, I am a nonbeliever. Still am. But when it comes to a devil — well, that’s something else.”

— The Exorcist (William Peter Blatty)

Sometimes a key advance is embodied in an insight that in retrospect looks simple and even obvious, and when someone shares it with us our elation is mixed with a kind of bewildered embarrassment, as seen in T. H. Huxley’s reaction to learning about Darwin’s theory of evolution through natural selection: “How extremely stupid not to have thought of that.”

This phenomenon often arises as one learns math. Mathematician Piper H writes: “The weird thing about math is you can be struggling to climb this mountain, then conquer the mountain, and look out from the top only to find you’re only a few feet from where you started.” In the same vein, mathematician David Epstein has said that learning mathematics is like climbing a cliff that’s sheer vertical in front of you and horizontal behind you. And mathematician Jules Hedges writes: “Math is like flattening mountains. It’s really hard work, and after you’ve finished you show someone and they say “What mountain?””

Drawings by Ben Orlin. Check out his webpage: https://mathwithbaddrawings.com/

These descriptions apply both to people who are learning math from books and to people working at the frontier of the known, discovering entirely new things. A lot of the work one does isn’t visible to others because sometimes you need to explore a terrain thoroughly before you can find the straight path through it. I’m reminded of the parable of the king who asked the greatest artist of the land to create for him a painting of a bird.¹ The artist said “Come back to me in a year and I will give you your painting.” When the king returned, the artist said “I am still not ready; give me another year and I will give you your painting.” This happened several times, until finally the king said “Give me the painting now, or I will have your head cut off!” Thereupon the artist whipped out a brush and, in a few quick strokes, created the most beautiful painting of a bird the king had ever seen. Astonished, the king asked “If this was so easy for you, why did you make me wait so long?” By way of answer, the artist led the king to another room containing hundreds of sketches of birds. The artist’s inspired creation only seemed to come from nowhere; it grew out of a huge mass of preparation, hidden from sight.

In math, what often happens is that we try to solve a problem using one approach, and then another, and then another, failing each time, until we finally hit on an approach that works, possibly after months or years. In a different sort of mathematical culture, researchers might be encouraged to discuss those failures and the lessons they learned from them, but in our culture, it is customary to describe only the approach that worked. This custom has the unfortunate effect of making advances seem like strokes of genius rather than fruits of effort. Then other people’s responses tend to be less like “How extremely stupid not to have thought of that” and more like “How on earth could anyone ever think of that?”²

FEFFERMAN’S DEVIL

Mathematician Charles Fefferman has an analogy for math that I like a lot (and in fact it’s the reason why I put a chessboard grid on the pseudosphere that serves as this blog’s logo); he says that doing math research is like playing chess with the Devil. Or rather, chess with a devil who, although much smarter than you, is bound by an ironclad rule: although you are allowed at any stage to take back as many moves as you like and rewind the game to an earlier stage, the devil cannot. In game after game, the devil trounces you, but if you learn from your mistakes, you can turn his intelligence against him, forcing him to become your chess tutor.  Eventually you may run out of mistakes to make and find a winning line of play. Someone who reads a record of the final version of the game (the one in which you win) may marvel at some cunning trap you set and ask “How on earth did you know that this would lead to checkmate ten moves in the future?” The answer is, you already had a chance to explore that future.³

In the same fashion, when you try to construct a proof, you often go down blind alleys, but if in the end you reach your goal, you can devise a straight path. In this way, we may see Fefferman’s Devil as unknowingly laboring in the service of Paul Erdős’ God (whom I wrote about last month): a proof that seems to exhibit godlike foresight could be the result of a devilish amount of preparatory fumbling.

Erdős lived for the moments when he caught a glimpse of God’s book and the gnomic proofs it contains, but I would prefer a book that shows the process by which mere mortals find their way to such proofs, surmounting obstacles, dismissing distractions, and maintaining hope along the way. What secrets the erasers and wastebaskets of mathematicians could tell us, if only they could talk!

If you like this drawing, you’ll like https://mathwithbaddrawings.com/2018/05/23/math-with-bad-drawings-the-book/

THE DEVIL’S BOOK

Mathematician Doron Zeilberger has noticed the mathematical community’s preference for elegant proofs over proofs that solve problems by brute force, and he’s not happy about it. As a natural contrarian he’s suspicious of consensus and believes (or is willing to pretend to believe) that the future progress of mathematics depends on ugly computer proofs, not the kind of beautiful proofs people like. In his view, the finding of beautiful proofs will become an eccentric pastime of human mathematicians, while their electronic counterparts, untrammeled by our species’ odd notions of beauty, will make the real advances. Over time, our tools may becomes our masters, and we their pets.

If Zeilberger is right, mathematical historians of the future, be they humans or computers, will view the year 1976 as pivotal. That was the year in which mathematicians Kenneth Appel and Wolfgang Haken gave the mathematical community a solution to the century-old Four Color Problem that involved a huge hunk of brute-force computation. The problem itself can be explained to a child in five minutes; the proof found by Appel, Haken, and their computer would take years of toil for a human to verify with pencil and paper. A more recent and extreme example of an unreadable proof is described by Kevin Buzzard in his essay “A computer-generated proof that nobody understands”.

Zeilberger doesn’t just predict a brave new mathematical world; he’s doing his best to bring it into being. Along with the late Herb Wilf, Zeilberger created a mathematical technology for automating the proofs of a broad class of equations (see their book “A=B” written with Marko Petkovsek), and over the course of his career he has delighted in finding brute-force approaches to problems. For instance, consider Morley’s trisector theorem, a beautiful piece of Euclidean geometry that wasn’t discovered until the 19th century. (I’ll tell you more about it next Thirdsday.) There’s a beautiful proof found by John Conway, but Zeilberger wasn’t interested in finding a beautiful proof; he wanted a proof it doesn’t take a Conway to discover. So he found the ugliest proof: a brute-force algebraic verification that gives us complete certainty that Morley’s theorem is true but zero insight into why it is true.

Zeilberger wrote that the devil, too, has a book, and he imagined that his proof of Morley’s theorem belonged there. This book would contain all the boring, inelegant proofs missing from God’s book as conceived by Erdős. Actually, Zeilberger called both books notebooks, and this idea of the two books as evolving documents fits in nicely with thoughts about ugly and beautiful mathematics voiced by mathematician G. H. Hardy. Hardy wrote “There is no permanent place in the world for ugly mathematics” while acceding that temporary ugliness is an essential feature of doing mathematics; you can’t build cathedrals without putting up scaffolds.

Haken and Appel’s proof didn’t end the story of the Four Color Theorem; their proof led to a shorter proof, and the quest for even shorter proofs continues. Meanwhile, Erdős’ love of elegance didn’t stop him from being phenomenally productive, and most of the proofs he found fell short of his high standard for “Book proofs”. So maybe we don’t have to choose between God’s book and the devil’s? Maybe we can honor both?

You’ll also like https://mathwithbaddrawings.com/2019/06/26/change-is-the-only-constant/

THE LAST LAUGH

There’s a sense in which the Devil claims the final victory. Although there is not and may never be an uncontroverted notion of what constitutes mathematical elegance, there are objective ways to measure the simplicity of a proof as a kind of surrogate for elegance, and we might imagine that for every simple problem there is a simple solution that we could discover, at least in principle, by staying at the devil’s chess-table long enough. That is, for every easy-to-state theorem we might hope that there would be a proof that isn’t necessarily easy to find but which, once found, could be verified by humans (possibly with computer assistance). And here comes the real deviltry. Thanks to the tricks discovered in the 20th century by Kurt Gödel, Alan Turing, and Gregory Chaitin, reason can be turned against itself to show that there are bound to be theorems whose proofs are all obscenely long in comparison with the length of the theorem itself. This is related to Turing’s discovery that there is no sieve to unerringly sift the provable from the disprovable, and Gödel’s discovery that in any sufficiently advanced formal system there will be propositions that are undecidable: neither provable nor disprovable.⁴

We don’t know the location of the border between the kind of math we care about and the kind Gödel et al. warned us about. Logician Harvey Friedman thinks the border may be closer than we think, and has spent the past few decades devising ever-more disquieting examples of problems that are haunted by the ghost of undecidability. We may someday find an easily-stated truth with no proof that can be uttered (let alone checked) in a lifetime, and we may never recognize the theorem as true. Our human mathematics may be a game limited to the shallows of reason; the farther out we wade, the greater the chances of being pulled out to sea by the undertow. Computers may enable us to go a little deeper, but there are limits to what beings in our universe, however they are constituted, can hope to do in the space and time allotted to us. Beyond what we can know, or ever will be able to know, there is a Void with a ragged beginning and no end. Is It laughing at us?

Thanks to Kevin Buzzard, Sandi Gubin, Piper H, Cris Moore, Ben Orlin and James Tanton.

Next month: The Square Root of Pi.

ENDNOTES

#1. I’m reconstructing this parable from memory, so I may have some details wrong. I couldn’t find this on the web, but surely one of you can find the source!

#2. I recently came across a great quote from mathematician Gian-Carlo Rota: “Philosophers and psychiatrists should explain why it is that we mathematicians are in the habit of systematically erasing our footsteps.” I discuss the phenomenon in my essay “The Genius Box”.

#3. Contrast Fefferman’s harmless devil with the villains in fantasy fiction, who can and will kill us and the people we care about. If fantasy novels were an unbiased sample of imaginary worlds, the vast majority would end mid-book, with the main character falling prey to some otherworldly peril her past experiences hadn’t prepared her for. The books we actually read are governed by a monumental amount of survivorship bias. In my zeroeth Mathematical Enchantments essay I wrote that math is my consolation for living in a world without magic, but really, I’m a big enough coward that if I were offered a passport to magical realms I’d probably turn it down. The worlds of fantasy that I like best have rules; if you run afoul of those rules, you die, and there is no reset button. Given a choice of adversaries, I’ll take Fefferman’s devil anytime.

#4. Actually, there is an escape clause from undecidability (but you won’t like it): given a formal system for proving theorems about counting-numbers-and-things-like-that, there may be an infallible way for us to recognize which theorems are provable in our system and which aren’t, but only if the task becomes trivial (all theorems are provable, none aren’t) and pointless (if all theorems are provable in our system, then provability can’t be telling us much about what’s true). That’s what happens if our formal system is inconsistent. Very few mathematicians are seriously worried that the systems that undergird mathematics (such as Peano Arithmetic or Zermelo-Fraenkel set theory) might harbor contradictions, and most of us have faith that even if these particular systems turn out to be flawed, the flaws can be fixed. But if no fix exists — if there is no way to put our mathematics on firm foundations — then I suspect the devil’s laughter fills the mathematical universe from one nonexistent end of time to the other.