The best performance improvement is the transition from the nonworking state to the working state. (John Ousterhout)

Writing down an argument formally can be a daunting task, especially if the argument is lengthy and is not modeled on an existing one in the literature. While every individual detail of the argument may be clear to the author, the overall structure of the argument may not be immediately obvious. In particular, it is often difficult to make the (important) decisions about the organisation of the argument, and selection of good notation, until a large part of the paper is already written, at which point any changes in the organisation or in the notation often become painful to implement. (Many times in the past, I have started to write a paper without devoting enough thought to the overall structure, and spent a lot of time establishing some lemmas which I thought were important, only to realise later that one did not actually need the lemma, thus wasting quite a lot of time.)

I found that the technique of rapid prototyping from software engineering is useful in ameliorating these difficulties. According to this technique, one does not write the paper in linear order, and one also refrains from the temptation of writing the easiest or most straightforward portions first. Instead, one writes the paper in the following order.

  1. First, one writes a bare-bones “skeleton” or “prototype” of the paper as quickly as possible; this prototype has the (approximate) statements of all the key lemmas, propositions, and theorems, as well as all key definitions, but all the proofs are omitted, or sketched in very informal “notes to self”. At this primary stage of the writing process, the priority is to get the “big picture” right – the logical organisation of the paper, and some semi-precise descriptions of each important proposition or piece of notation. The fuzzy nature of these descriptions will allow one to easily move parts of the argument around to improve this big picture.
  2. After the organisation is completed to one’s satisfaction, the second objective is to write down just enough of the proof so that one can make the statements of all the lemmas, propositions, theorems and definitions precise.
  3. Once this is done, the third objective is to carefully write the key portions of the argument, for instance deducing one key proposition from two previous key lemmas, to make sure that the structure actually works as expected.
  4. Finally, one fills in all the “routine” aspects of the paper, such as proofs of standard lemmas, or a quick application of the main theorem. Usually, by this stage, the remaining gaps in the paper are so disconnected that they can be filled out in basically whatever order one pleases. This is also a good time to write the introduction and similar motivational sections.

Any decisions which do not impact the big picture should be deferred until late in this process. For instance, if you have a small quantity which is probably going to equal \varepsilon/2 or maybe \varepsilon/3, but do not know exactly which it is yet, you could write “let \delta := ???” for now, and use \delta as a placeholder for this quantity until you get to the point in the proof where you figure it out exactly what ??? should be, and which point you can edit a single line to complete the proof. (Contrast this with writing \varepsilon/2 in two dozen places in the proof, then discovering much later in the writing process that you have to go back and change \varepsilon/2 to \varepsilon/3 (and \varepsilon^2/4 to \varepsilon^2/9, etc.) in those two dozen places. Even with modern search-and-replace tools, this can be an irritatingly time-consuming task.)

One nice feature of this approach is that it can be divided with a coauthor. For instance one author may write an informal sketch of the proof, with many details omitted, then the other coauthor may tweak the organisation and notation, and then fill in the details, and then the first author might then review the paper and add in some remarks and write the introduction. Many other permutations are possible; it depends very much on the nature of the collaboration.

While one is writing one part of the paper, one often gets some good ideas regarding what to do for another part of the paper; e.g. when writing down a lemma, one may have an idea for an example or remark which will illuminate that lemma. When that happens, I do not recommend ignoring that idea, nor do I recommend dropping what you are currently doing to fully flesh out that idea; instead, devote a minute to write down a “stub” for that idea in the relevant location of your paper (just enough to jog your memory when you return to that location), and then return to what you were doing before, so as not to break your concentration or momentum. That idea can then be safely forgotten about for the moment, and revisited at one’s leisure, at a more appropriate stage of the writing process.

The rapid prototyping strategy is often hard to adhere to perfectly, and I must admit that sometimes (especially for shorter papers) I take a very different approach, writing the “easy” and “fun” parts of the paper first (e.g. the introduction, or some simple lemmas), and try to use the momentum generated to then write the rest of the paper quickly. This tends to work well if one is very confident as to how the large-scale structure of the paper will be arranged, but I have regretted using this hastier approach when I found, halfway through the writing process, that a radically different organisation would have been much better.