עם ישראל חי

A major mazal tov to my co-bloggers Aaron and Steve on the birth of their sons. Other friends of mine with recent births are Anat & Oren and Tamar & Maxim. In the touchy-feely, lovey-dovey spirit of a baby post, can you guys link to some ridiculously cute baby pictures?

Breakdown of discrete intuition

Most of the classical inequalities -- Jensen, Hölder, Cauchy-Schwartz -- work for integrals just as well as for sums. In fact, it's best to think of these as integral inequalities with respect to a positive Borel measure (which includes the Lebesgue and the counting measures as special cases, and subsumes both sums and integrals). This can keep our intuition from being excessively taxed; I, for one, prefer to reason about sums and carry that intuition over to integrals. Are there instances where that intuition can fail?

Indeed there are, as Michael Steele shows us in Exercise 8.3 of his book. In part (a), we're asked to show that for all nonnegative sequences , we have

(the solution is given in the book, but readers are invited to attempt this one cold). In part (b), we're admonished against the careless conclusion that for (integrable) , we have

-- does anyone have an example where the latter fails?

A heuristic to guide one's intuition is the following principle of Hardy, Littlewood, and Pólya, called "homogeneity in ." That is, one considers as a formal symbol and checks the order to which an expression is "homogeneous in ." In this case, the lhs is homogeneous of order 2 while the rhs is homogeneous of order 3. According to the heuristic, this incompatibility destroys the integral analog. Anyone have more such examples where the integral analog fails? Could there be a general theorem lurking around?

I wasn't going to

touch the tragic events at Virginia Tech with a ten-foot pole. People much better informed and more articulate than I are all over this; go to Instapundit for updates and spot-on commentary. However, being in the academia, I feel an obligation to occasionally shout out against the insanity that has become ivory tower conventional wisdom.

Just yesterday someone was in my office telling me how it's impossible to get guns in Japan, and how even the criminal gangs have to manufacture special-purpose bats. So much for that tripe.

I have no desire to turn this into a gun control flamewar; if you're going to comment to the effect that more gun control could've prevented this tragedy, at least entertain me by explaining how it's Bush's fault (and bonus points if you manage to link this to the Israel lobby).

I'm writing about the general powerlessness and impotence fostered by a paternalistic government and eagerly accepted by the cud-chewing masses. Read this article by a Virginia Tech grad student. Money quote:

I am licensed to carry a concealed handgun in the commonwealth of Virginia, and do so on a regular basis. However, because I am a Virginia Tech student, I am prohibited from carrying at school because of Virginia Tech's student policy, which makes possession of a handgun an expellable offense

I am in the same boat. I have a concealed carry permit, have had extensive safety and tactical training, and am even an instructor. Not that this is of any use on campus, where firearms are limited to the omnipresent and omnipotent police. Every time a student gets mugged or assaulted (every month or so, on average), campus police send out a report, with the helpful advice "If confronted by an assailant, don't resist. If he wants your wallet, purse or backpack, give it up." Not a word about carrying even a sub-lethal weapon such as pepper spray. Just give the bad guy what he wants and hope for the best.

Tragedies like this can be prevented if ordinary citizens are allowed to defend themselves instead of being infantilized. A Virginia Tech professor told that student whose article I linked to, "I would feel safer if you had your gun." In a similar vein, my Rabbi has specifically allowed me to carry my pistol in his house, even on Shabbat (when ordinarily carrying items like keys and a wallet is prohibited). As long as idiots like this continue to be the voice of campus officials, we can expect more attacks on soft targets such as schools -- whether isolated acts of insane individuals, or planned terrorist attacks.

[Update May 11, 2007] At least I wasn't kicked out of my school for expressing these views...

Fear and (self) loathing in Pittsburgh

... and I'm not even talking about my thesis-writing, which is somewhat behind. I am talking about J. Michael Steele's book, The Cauchy-Schwarz Master Class: An Introduction to the Art of Mathematical Inequalities. As someone who's made inequalities his bread and butter over the past couple of years, I figured this would be mandatory reading. Even with Steele's enlightening (and wryly humorous) explanations, this is definitely not light reading. Many of the challenges -- even with the hints -- are pretty darn hard, and I'm terrified to think how I'd approach these without the hints. Then again, there's a reason why some of these inequalities have names like Cauchy, Schwartz, and Hilbert attached to them... In the words of my officemate, "I'll become a better person after working through this book." Probably true for most of us.

A clique bound on coloring numbers?

We assigned the problem of showing that 3COLOR is NP-complete, meaning that unless P=NP, there is no polynomial time algorithm to determine whether a given graph is 3-colorable. The classical reduction is from 3-SAT, via some clever gadgets.

One student had the idea that clique numbers could be used to resolve graph coloring questions. This is partly right: if a graph contains a K4 (a 4-clique), it is certainly not 3-colorable. What about the other direction?

Well, let's put it this way: testing whether a graph contains a K4 is a polynomial-time procedure (the brute-force search is O(n^4)). So either we've just proved P=NP, or... there exist graphs that don't contain a K4, yet are not 3-colorable. Can anyone exhibit one?

A neat analysis problem

I'm in thesis-writing crunch-mode, and though there's lots I could blog about, I simply don't have time. Take a look at this problem posted by Guy Gur-Ari, a student at the Hebrew University in Jerusalem:

Let f:[0,1]->R be a real function such that f has a limit at each point.
Does f have at least one continuity point?

It's definitely a good one to work out (try it before you go to his blog for the solution), and check out the rest of his blog while you're at it!

Update: on the topic of analysis, I ordered and am skimming Counterexamples in Analysis -- a must-read for any student of mathematics, though to my relief I seem to already be familiar with most of these. Here's a good one: give an example of a nonconstant function f:R->R that is periodic but has no smallest period. Anyone?

חג כשר ושמח

No need to be alarmed -- just a standard Passover greeting. Blogging will continue with absolute regularity.

Contraction bounds spectral gap?

Let A be a column-stochastic matrix. Compute its (complex) eigenvalues, take absolute values, sort in decreasing order, and let lambda2 be the second value on the list (the first is always 1, by Perron's theorem). Lambda2 is (closely related to) the spectral gap of the Markov kernel corresponding to A.

Let theta be max TV(x,y), where x and y range over the columns of A and TV(x,y) is 1/2 the L1 distance of the two vectors x and y. Theta is also called the (Doeblin) contraction coefficient of the Markov operator induced by A.

It's easy to see that lambda2 and theta are numbers between 0 and 1. Here is a simple example where lambda2=0 while theta=1:

0 0 0
0 1 1
1 0 0

It seems that we always have lambda2 <= theta, but I don't have a proof of this. I also can't imagine that I'm the first to observe this -- can someone point me to a reference? Maybe suggest a proof?

Update: thanks to David Aldous and Cristopher Moore for telling me how to prove this (well-known) fact. I won't elaborate, since nobody else seems to care, but if anyone does, let me know and I'll post a proof. I'd be thrilled to see an elementary proof (i.e., one not relying on Perron-Frobenius), so consider that a challenge!