how to write proofs

So midterms have come and gone, and now I know I need to work on mathematical exposition.

Main lesson: if you're trying to prove fact X, and facts A, B, and C imply X, then saying
"A, B, and C are true" is not a good proof (particularly if A, B, and C are out of order, and you're also assuming D, which you thought was too obvious to mention.)

Clarity is hard -- a lot harder than I gave it credit for. Bad wording can make you look confused, or worse, actually confuse you. So, some antidotes.

Leslie Lamport has an interesting article about writing structured proofs, with the large-scale points (here are my lemmas and cases) on the "coarse" level of structure, and the justifications for those points on the "fine" level.

Here's a nice article from the U. of C. about how to write proofs. It's written for beginners, but it doesn't stop being true when you're more advanced.

I had a professor once who said, "A proof is nothing more than an elaborate gesture at the truth." (I think he may have been quoting Hardy, but I can't find it anywhere.) It's just a matter of communicating what you understand explicitly enough that other people will read it, and feel they understand it too.

organization kid?

I read, at my roommate's urging, this old Atlantic Monthly article on today's Princeton kid.

Here's the article.

It's spot-on in most ways. We're supposed to be cheerful workaholics, seeking to please authority, obsessed with success and lacking a sense of sin. We're compared to the Edwardians -- and it's true that some of Kipling's short stories about young officers in the Raj sound like they could have been written about my Woody Woo classmates.

I was never an Organization Kid by temperament. But I do know people who fit the model almost perfectly -- and yet are a lot more alive and interesting than the article's generalizations. Not everyone with a busy schedule is soulless! It's always kind of sad to have your identity defined by a journalist, even when he does a better job than most.

allocation problem

The tea room is a wonderful thing. You sit and work with a cup of Constant Comment, and interesting people drift in and out and talk about interesting things. A filter-feeder lifestyle, with math taking the place of tasty plankton.

One example: on Friday there was a talk about the allocation problem with submodular utility functions. It's an economic question: given a group of people with different desires (utility functions) and a set of items they can receive, how can you allocate the resources to maximize everyone's happiness? To make life simpler, they assumed that the utility functions were submodular, that is,
w(A) + w(B) <= w(A \cup B) + w(A \cap B). This translates to decreasing marginal value, or risk aversion.

They set up a random rounding procedure that, in polynomial time, can take a given allocation and improve it until it is some fraction r of the value of the feasible solution for that instance of the problem; also, r > 1 - 1/e.

The most obvious way to set up an allocation is to allow each player to choose a "tentative set," and then resolve disputes between players who claim the same item by giving it to whoever can get the most utility from it. This winds up giving exactly a bound of 1 - 1/e, which Vondrak improves on with more sophisticated random rounding methods.

He ran through it fast, so I missed quite a few of the details; I'll have to read the paper through when (and if!) I have time. The amazing thing is that everything looks elementary.

I'm pretty blown away. It seems to me that a lot of the hard problems in the world (energy consumption comes to mind first) are essentially questions of allocating resources to people with different priorities. People call it "policy" and not math, but these guys just showed that in a specific kind of model you can always get better than 63% of the best solution.