Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I've occasionally heard it stated (most notably on Terry Tao's blog) that "the Cauchy-Schwarz inequality can be viewed as a quantitative strengthening of the pigeonhole principle." I've certainly seen the inequality put to good use, but I haven't seen anything to make me believe that statement on the same level that I believe that the probabilistic method can be used as a (vast) strengthening of pigeonhole.

So, how exactly can Cauchy-Schwarz be seen as a quantitative version of the pigeonhole principle? And for extra pigeonholey goodness, are there similarly powered-up versions of the principle's other generalizations? (Linear algebra arguments [particularly dimension arguments], the probabilistic method, etc.)

share|improve this question
add comment

2 Answers

up vote 12 down vote accepted

My own interpretation (which I guess is pretty similar to the one above):

Suppose you have r pigeons and n holes, and want to minimize the number of pairs of pigeons in the same hole. This can easily be seen as equivalent to minimizing the sum of the squares of the number of pigeons in each hole.

Classical Cauchy Schwartz: x_1^2+...+x_n^2 >= [(x_1+...+x_n)^2]/n.

Discrete Cauchy Schwartz: If you must place an integer number of pigeons in each hole, the number of pairs of same-hole pigeons is minimized when you distribute the pigeons as close to evenly as possible subject to this constraint.

Pigeonhole: In the case r=m+1, the most even split is (2,1,1,...,1), which has a pair of pigeons in the same hole.

share|improve this answer
add comment

Very interesting. Here's an attempt at an answer:

Suppose there are n pigeonholes, with hole k containing f(k) pigeons, for k = 1, ..., n. The total number of pigeons is m = Σnk=1 f(k) = f.u in the standard inner product, where u(k) = 1 for all k. The Cauchy-Schwarz inequality implies that ||f|| ||u|| >= |f.u| = m, so ||f|| >= m/||u|| = m/sqrt(n). On the other hand, if r is the maximum of f(k) for k = 1, ..., n, then ||f|| = sqrt(Σnk=1 f(k)2) <= sqrt(Σnk=1 r2) = r * sqrt(n). Putting these together, we have r * sqrt(n) >= ||f|| >= m/sqrt(n), so r >= m/n. That's the pigeonhole principle: if there are m pigeons in n holes, then some hole has at least m/n pigeons, which becomes ceiling(m/n) if pigeons can't be divided.

That does seem like a very special case of the Cauchy-Schwarz inequality, which makes it somewhat unsatisfying. It's probably not exactly what Terry Tao had in mind, but it's not completely bogus, either.

share|improve this answer
    
This certainly does answer the letter of my question, but I agree that it's not all that satisfying. In particular we can prove pigeonhole using just the second inequality in the L^1 norm, so Cauchy-Schwarz seems less like a strengthening of pigeonhole in itself and more like a technical tool needed to pass from L^1 to L^2. –  Harrison Brown Oct 15 '09 at 17:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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