7
$\begingroup$

I am just beginning my second year of PhD. While my advisor is largely happy with my progress and work, there seems to be a recurring point in our discussions that I need to be more formal in my writing. Until now, he has been happy to help me formalize my arguments and proofs but this is clearly something I am struggling with.

Any advice on how to be more formal while writing papers? The obvious answer is to read a lot of papers and try to re-create proofs by writing them down. I seem to do that relatively well but the writing itself is a problem for me.

$\endgroup$
  • 7
    $\begingroup$ I am not sure this is appropriate for this forum. While it's definitely an on-topic question, it does not have a self-contained and objective answer. Still, this advice from Terry Tao may be helpful: terrytao.wordpress.com/advice-on-writing-papers $\endgroup$ – Sasho Nikolov Sep 2 '16 at 17:18
  • 6
    $\begingroup$ I'll suggest academia.stackexchange.com as an alternate forum. $\endgroup$ – cody Sep 2 '16 at 17:59
  • 1
    $\begingroup$ I don't think that academia is a suitable place to ask this question. In fact philosopher's or physician's ... answers are not suitable for computer scientists. $\endgroup$ – Saeed Sep 3 '16 at 5:12
  • $\begingroup$ @Saeed I am not sure that academia@SE is a bad idea, there are quite a few mathematicians and computer scientists who are active there, and if the question is explicit about the field, it will attract relevant answers, I think. $\endgroup$ – Sasho Nikolov Sep 3 '16 at 17:19
  • $\begingroup$ @SashoNikolov, yes there are also related scientists at academia. But here all of users are in the field and this question can be a good question for all undergrad and first year PhD students in TCS. Compare to academia I think here is a better place. We can relax a bit and allow good aubjective questions (as we had in past). $\endgroup$ – Saeed Sep 4 '16 at 8:11
8
$\begingroup$

Sure, here's a basic checklist. It would make for a very dry read to actually follow these to the letter, but maybe you should first try to write extremely formally, then see where it's reasonable to relax the writing without risk of misunderstanding or vagueness.

Preface. The high-level goal of formality is to make your proof closer to "machine-checkable". You want to allow people of a variety of different backgrounds, knowledge levels, abilities, and intuitions to be able to read your definitions, claims and proofs, understand what they say, and verify that they are correct.

Just as a computer cannot execute a program that is vague and skip steps, so it is difficult for a human to verify a proof with the same flaws.

However, a caveat is that mathematical formality is not perfectly aligned with conveying understanding. Notice I said "verify" above, not "understand". But even if the goal is to convey understanding, it is important to at least be able to formalize what one writes, since you want to convey to others the ability to formalize it.

  1. Define terminology and notation precisely. For example, this is informal:

each vertex gets a weight $w_v$ whenever it gets matched, and $W$ is the total of all the weights.

This is formal:

the graph $G$ has a set of vertices $V$. For each vertex $v \in V$, the algorithm is given its weight $w_v$. For an algorithm $A$, let $S_A \subseteq V$ be the vertices matched by $A$. $S_A$ is a random variable depending on the random choices of $A$. Let $W_A = \mathbb{E} \sum_{v \in S_A} w_v$ where the expectation is over the randomness of $A$.

Why bury ourselves in so much notation? For one thing, notice that in the formal rewrite, we realized $W$ wasn't well-defined because it depended on the algorithm (and even its randomness), so we had to introduce and define notation to capture that. We had to introduce notation $S_A$, but it will come in handy later anyway.

Try not to feel frustrated or annoyed if things that sound simple take up a lot of space and require a lot of notation when written formally. Don't think of this as dirty work, think of it as a valuable part of the process to deeply understanding what you're writing.

  1. Do not use a technical term if you have not defined it yet, and do not use nontechnical terms in a technical discussion or proof. For example, do not say "because $G$ is an expander, ..." as part of a step of a proof if a precise definition of expander has not yet appeared. But it's okay to say "intuitively, $G$ is acting like an expander". Do not say as part of a proof, "if the algorithm has made enough matches, then ..." unless you have precisely defined what that means. Better is to define a threshold $R(t)$ at each time $t$, then say "if the number of matches at time $t$ is at least $R(t)$, then...."

  2. State results precisely using a logical sentence. Any proposition / lemma / theorem should really be a logical sentence such as "For all $x$ such that $P(x)$, there exists $y$ such that $Q(x,y)$. For example, "There exists a constant $c$ such that the following holds: For all input graphs on $n$ nodes, there exists $m$ such that Algorithm 4 runs in $m$ steps and $m \leq c n^3$."

    First make sure you can write the result you are stating in this form, then see if you're willing to relax it to someting like "Algorithm 4 runs in time $O(n^3)$ on graphs of $n$ vertices". I would avoid something like "Algorithm 4 runs in cubic time" since it's unclear (cubic in what?).

  3. Understand what a "step" of a proof is and use them well. A step in the proof starts with what has already been shown so far and applies a simple, known fact, axiom, or result (properly cited/stated) to get a new statement. For example, if we have already shown that $M \leq (1+x)^n$, then we can apply the fact that $1+x \leq e^x$ for all $x$ to deduce $M \leq e^{nx}$.

    Even there I left out a step: $(e^x)^n = e^{nx}$. When in doubt, do not omit any step bigger than that. You can always cut them down later.

    Your proof should be a sequence of steps of this kind, where the first step only uses assumptions stated in the claim, each step uses only statements shown in previous steps, and the last step derives the statement in the claim.

    You should also split proofs into lemmas and so on, but that's beyond my scope.

  4. In particular, each step should be short and easy to follow. If you are trying to write formally as a beginner, don't skip a bunch of lines of calculation and expect the reader to trust you. (If for some reason you do, at least tell the reader that's what you're doing!) The reader should be able to see immediately why this step is correct.

    A big mistake beginning proof-writers make (also experienced ones) is to not bother writing why a seemingly-obvious step is true. This is a big red flag. Sit down and go through the math convincing yourself why that "obvious" step is true, then put that into the proof! Do not ever write "clearly" or "obviously". Give me the fact for why it's clear ("Because probabilities are at most $1$, $\sum p_i \leq n$").

  5. When you proofread, do so extremely slowly, carefully, and pretend you're explaining to someone who has never seen your paper. Read it out loud if you have to. If you proofread in your head fast, you're just reminding yourself of what you intended it to say. A step or definition left out of the paper won't be noticed because it will still be in your head. You want to check that each sentence makes sense given (only) what came before it.

$\endgroup$
  • 1
    $\begingroup$ How formal should one be when introducing an argument that is intuitively obvious, but seems tedious and uninstructive to formalize? As an example: I am currently working on my first paper and there are a lot of arguments that involve small quantities. I find it convenient not to derive lower bounds on each of these quantities but instead to claim that they are all bounded from below by some $c$ due to the finiteness of the objects studied. This greatly simplifies the presentation by omitting explicit calculations throughout the paper, but leaves something to be desired in terms of formalism.. $\endgroup$ – mich Sep 5 '16 at 2:22
  • $\begingroup$ @Michael, I think it's a great/hard question. I don't know. I feel comfortable giving advice on how to be formal, but I don't know if I'm experienced enough to give advice on when. :) That being said, I could suggest proof sketches in the main text and full proofs in the appendix. $\endgroup$ – usul Sep 5 '16 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.