Log in

No account? Create an account
On proof - Arvind Narayanan's journal [entries|archive|friends|userinfo]

On proof [Apr. 9th, 2006|04:00 pm]
Arvind Narayanan

If you're the sort of person who occasionally reads math papers but are not a mathematician yourself, you might wonder why mathematicians write horribly abstruse papers, vapid and rigorous. Let me attempt to explain why we do so, at least in the small subfield that I inhabit (although I suspect that my reasoning is generally true).

First, let's clear away a misconception. It is only the proofs in math papers that are vapid and abstruse. If we're introducing a new idea or a new problem, we will go to great lengths to explain its meaning, formulation and significance.

Now, it turns out that the world of proofs can be divided into Proofs You Care About and Proofs You Don't Care About. The latter type are in the majority. You are interested in the proof simply to make sure that the theorem it proves is true, so that you can go ahead and use the theorem to prove more important things. Often times, if you can't get one of these proofs to work it says more about the power of your axiom system and proof techniques than it does about the truth of the theorem itself.

Here's how Proofs You Don't Care About are done. When you're trying to prove a theorem of this type, you build up a lot of intuition, learning more and more about the statement of the theorem until you can finally prove it. However, your first attempt at writing down the proof will be horribly messy -- since you only understand the proof at an intuitive level, it is extremely hard to translate to symbols. So you begin a process of "cleaning up" the proof. You simplify and simplify and reformulate and reformulate until the proof becomes a relatively short sequence of formal deductions.

When reading such a proof in someone else's paper, you first stare at it and see if you "believe" the statement of the theorem. If you do, that is, you kinda sorta vaguely intuitively see why the theorem should be true, you just skip the proof and move on. You trust the author and respect their intelligence. Naturally, the author has a responsibility to fact check their ass really really thoroughly. If you don't believe the theorem, on the other hand, you go through the proof, and mechanically check if each step is true. The author has optimized the writing of the proof to make this checking process mechanical and straightforward. At the end of it, you the reader might be convinced that the theorem is true, but might still not "believe" it, i.e, no intuition for why it's true. But that's OK, because this is a Proof You Don't Care About -- it doesn't matter why it's true, just the fact that it's true.

Now let's turn to Proofs You Care About. When writing these proofs, you make it abundantly clear that the proof is interesting. The proof tells you more about the state of the universe than the theorem itself does. Often it is because you introduce a new proof technique. Whatever the reason, you make sure you explain the intuition behind the proof. It is not uncommon to prove a special case first or to give examples, to make really sure the reader is on board. If you write a paper in which a Proof You Care About is not sufficiently clearly explained, then that's grounds for rejection. You even write whole papers about important proofs, and give easier to understand proofs for already proved theorems. For example, the Prime Number Theorem was proved in 1896, but a new proof in 1949 of the same theorem without using analytical techniques was regarded as a landmark. There are theorems for which lists of 350 distinct proofs have been compiled.

Most of the time, this works great. There are, of course, bad mathematicians who will fail to give sufficient intuition for new concepts, or write obscure proofs even when the proofs is important. Then there are the plain dishonest ones who deliberately obfuscate their writing. The existence of bad apples cannot be considered a failing of the method.

Rarely, you think you don't care about a proof but it turns out you do. Most famously, Archimedes invented a heuristic form of infinitesimal analysis for computing volumes of solids, which would come to be rediscovered as integral calculus 1900 years later. However, Archimedes felt that his proof was not rigorous enough to be published, and instead gave alternate proofs of all the results he arrived at using infinitesimals. A grave error -- who knows how the world might have turned out if the ancients had grasped the full power of calculus? His work "On the Method of Mechanical Theorems", a.k.a the "Archimedes Palimpsest", in which he describes how he actually did the proofs, was discovered in 1906 and sold for $2 million in 1998.

I will stop now, for I have work to do. A Proof You Don't Care about, if you're curious.

x-posted to mathematics

[User Picture]From: vinodv
2006-04-09 10:43 pm (UTC)
I see at least two distinct kind of proofs.

(1) one where you "know" that the theorem you prove is true, mostly because of evidence accumulated over years and "collective intuition". I would bunch Fermat's Last theorem (also P\neq NP ?) into this category. In such cases, it is the proof (or the path from axioms to the theorem itself) that is interesting. For instance, the attempt to discover this path, in the case of FLT, gave birth to entire branches of mathematics !

(2) one where the truth of the theorem itself is unclear (perhaps not to the prover, but certainly to a layman). In such cases, the ultimate statement of the theorem might be more interesting than the way it is proven.

I would guess that the former is what they call (or what leads to) 'theory-building' and the latter is what (some) pure mathematicians (at least the small number of them i know) despise as 'problem-solving'.
(Reply) (Thread)
From: vmuthu
2006-04-13 10:52 am (UTC)
I see your dichotomy in computer science literature more often than in math. I say this because in math, elegance is thought to be compromised if intuition is given. For instance, a BJV proof with 3 as the constant required to satisfy the inequality is more elegant than deriving the intuition as to why it must be close to e and 3 works.

In computability theory, there is a proof technique called the priority argument which fall under another category. As such they are Proof Your Care About, but I have not seen any intuition given to the proof technique. Some theorems are true intuitively but the proofs are not intuitive like fixed point theorems, recursion theorem,...
(Reply) (Thread)