What makes good mathematical writing? And what do we “understand” from proofs?

Being a complexity theorist, if you ask me what a mathematical proof is, my first answer is “something that convinces a verifier of the validity of a statement,” and this is the goal that I usually have in mind when writing up a paper: to make it clear, especially to myself, that the result is indeed correct.

With the right software environment, and with the right formal language to specify proofs, it might be possible to write proofs in a format that is not only readable by humans, but by machines too, greatly increasing our confidence in the validity of what we do (and simplifying the job of referees); conceivably automated tools might also produce automated proofs of the “it is clear that” steps, and beyond, and create the formal proof in an interactive way. A recent issue of the Notices of the AMS was devoted to formal proofs and related software tools. Gowers describes here and here what such a computer-assisted theorem-proving might look like.

A proof is easier to follow if it is broken up in a “modular” way, as a series of lemmas such that each lemma can be stated, proved and understood independently, and the lemmas combine in a simple way to give the main result. Then each lemma may similarly be broken up into simpler statements and so on.

I assumed that this was all there was to mathematical writing, until I taught an undergraduate algorithms course at Berkeley (CS170), and I could not understand the explanation of Dijkstra’s algorithm in CLR. To be sure, the presentation was extremely modular, and all proofs had been broken up into entirely elementary steps, but after reading the section in question, I had no idea what was going on. (And, if you are wondering, I already knew the algorithm.)

The point is that, although we sometimes write a proof with the main goal of establishing that a certain result is true, this is hardly the reason why we read proofs, unless we are a referee. We read proofs with the hope of learning something new, a technique that can be applied elsewhere, an insight about the nature of a certain mathematical object and so on. If a proof is too detailed, and excessively broken up into little lemmas, one can get lost in the details.

If this is the case, then what makes good mathematical writing? Taking again an analogy from complexity theory, a proof is “zero-knowledge” when, after having completed the process of verifying it, the verifier is not able to do anything that he wouldn’t be able to do before. This suggest a criterion for judging good writing: that after reading a well-written piece of mathematics, we are able to do something that we weren’t able to before.

Gowers has advocated a style of mathematical writing in which a proof is presented without “magical” steps, so that every step is justified in a way that (with the hindsight of the person writing the exposition) makes it natural, and inevitable. If the most natural line of attack is wrong, then one discusses the relevant counterexamples. If a special case contains the essence of the problem but without distracting features, one looks at the special case first, and so on. (In a way, this is the opposite of the ethos of “proofs from the Book,” which emphasizes the magic and the unexplained.)

(Note also the “computational” difference: in a proof written for ease of verification, we break up the proof until each piece is easy to verify, but here we are breaking up a proof so that each piece is, by itself, easy to generate.)

Reading expositions written in this style can be hard, and the whole thing is not very useful if the writer’s idea of what is “natural” does not agree with the reader’s, but when it works, it is phenomenally rewarding.

Indeed, if we are writing with the goal of giving the reader “non-zero knowledge,” that is the ability to do something new, then presenting the proof of an actual theorem may even be besides the point. This gets to the Tricks Wiki, a repository of mathematical techniques which is coming online any day now, and which is specifically designed to extract pieces of mathematical lore that one normally learns by reading proofs (and “understanding” them), and to present them in an independent form.

It’s not clear that something like the Tricks Wiki would be needed in theoretical computer science, because I think that we do a reasonable job at making explicit the techniques that we use; as for Gowers’ notion of writing an exposition in which there is no magical step, I’d love to see some currently impenetrable piece of theoretical computer science be explained in this way.

I also wonder if it is possible to come up with precise definitions that capture (even very approximately) the notion of a proof being understandable, understood, deep, and so on, and whether philosophers have any insight into the matter.