Friday, December 17, 2010

Writing proofs: avoiding case analysis

As a student I learned a number of ways to prove lemmas: contradiction, induction, case analysis, etc.

Case analysis, when there are more than two cases, tends to make me feel like a mindless computer. It is more like checking than like understanding, and for me it is not a good way to get insight.

The direct proof is my favorite proof organization for short pieces of argument: assumption A implies B, B implies C, C implies D, D implies the final statement E. The proof should give a brief justification for each implication. With this kind of proof it is easier for me to get insight.

For example, in Trevisan's 2005 SDP algorithm for unique games, one small piece of the analysis is proved by doing a separation into three cases.

The claim: if three vectors r,u,v are such that u.v=0, (r-u)2>(r-v)2, and the vectors satisfy a "triangle inequality" constraint, then (r-u)2 > (1/2) (r)2.

The proof has three cases:
- either (Case 1) (u)2 < (1/2) (r)2,
- or (Case 2) (v)2<(1/2)(r)2,
- or (Case 3) (u)2 and (v)2 are both > (1/2) (r)2.
Each case is short, but it feels a little bit redundant and dissatisfying.

Instead, here is a direct proof (how does one do math in html, I wonder.):
- By the triangle inequality constraints,
(A1) (r)2 < (u-v)2+(v)2 and (A2) (r)2<(r-u)2+(u)2.
-Summing, (B) 2 (r)2 < (r-u)2+(r-v)2+(u)2+(v)2.
-Since u.v=0, we have (C) (u)2+(v)2=(u-v)2.
-By the triangle inequality constraints again, (D) (u-v)2<(u-w)2+(w-v)2.
-Substituting that in (B) gives (E) 2 (r)2 < 2(r-u)2 + 2(r-v)2.
-By assumption (r-u)2>(r-v)2, so (F) 2(r)2<4(r-u)2, hence the result.

The proof is essentially the same, but it is organized differently, and I like this presentation better.

3 comments:

  1. For enable Latex support, you can put the code snippet from http://pastebin.ca/2023123 right after <head> tag in your blog template (under "Design"/"Edit HTML")

    This will render anything between $..$ as latex

    ReplyDelete
  2. \(\sum_{k=0}^{n} {n \choose k} = 2^n\)

    ReplyDelete
  3. i came across this post of yours while i was searching information about Signature forgery . i found this very informative. I enjoyed reading i t seems some interesting stuff about Handwriting expert . I'm supposed to be somewhere else in a minute but I stuck to reading the story. I like the quality of your blog :D.Thank you for this article.

    ReplyDelete

Note: Only a member of this blog may post a comment.