Cauchy-Schwarz and pigeonhole

Question

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.)

Answer 1

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 Schwarz: $x_1^2+...+x_n^2 \ge\displaystyle\frac1n(x_1+...+x_n)^2$.

Discrete Cauchy Schwarz: 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.

Answer 2

I recently learned about a nice formulation of this connection from a version of the Cauchy–Schwarz inequality stated in Bateman's and Katz's article [1, page 588 Lemma 2.1].

I imagine this version is probably part of the appropriate combinatorial folklore. Also, it's essentially the interpretation given in Kevin's answer.

Proposition. Let $X$ and $Y$ both be finite sets and let $f \colon X \to Y$ be a function.

• $\#(\ker f) \cdot \#(Y) \ge \#(X)^2$. (Where $\ker f$ is the kernel of a function $f$.)
• Equality holds if and only if every fiber has the same number of elements.

Reference

[1] Bateman, Michael; Katz, Nets Hawk. New bounds on cap sets. J. Amer. Math. Soc. 25 (2012), no. 2., 585–613. MR2869028

Answer 3

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=\sum^n_{k=1} f(k)=f\cdot u$ in the standard inner product, where $u(k) = 1$ for all $k$. The Cauchy-Schwarz inequality implies that $\|f\| \|u\| \ge |f\cdot u| = m$, so $\|f\| \ge m/\|u\| = m/\sqrt{n}$. On the other hand, if $r$ is the maximum of $f(k)$ for $k = 1, ..., n$, then $\|f\| = \sqrt{\sum^n_{k=1} f(k)^2} \le \sqrt{\sum^n_{k=1} r^2} =r \cdot \sqrt n$. Putting these together, we have $r \sqrt n \ge \|f\| \ge m/\sqrt n$, so $r \ge 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 $\lceil m/n\rceil$ 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.

Answer 4

The relation between the Cauchy-Schwarz inequality and the measure theoretic version of the pigeon-hole principle can be illustrated by the following exercise.

${\bf Exercise.}$ Let $A_1$,...$A_n$ be measurable subsets of a probability space. We assume that there exists $c>0$ such that $\mu(A_i)\geq c$ for all $i$. Show that there exists $i,j,\ i\not= j$ such that $$ \mu(A_i\cap A_j)\geq {nc^2-c \over n-1}.$$

That's a quantitative version of the pigeonhole principle. If we put too many sockets in the drawer, two must overlap.

Here is the proof. Let us define $f = \sum_i {\bf 1}_{A_i}$ so that $\int f d\mu\geq nc$. $$ n(n-1)\max_{i,j} \mu(A_i\cap A_j) \geq \sum_{i\neq j} \mu(A_i\cap A_j) = \int \sum_{i\neq j} {\bf 1}_{A_i} {\bf 1}_{A_j} \ d\mu = \int (f^2-f) d\mu. $$ Now we use the Cauchy-Schwarz inequality: $\int f^2 d\mu \geq (\int f d\mu)^2$. We get $$\int f^2-f \ d\mu \geq \Bigl(\int f d\mu -1\Bigr) \int f d\mu \geq (nc -1)nc. $$ So the measure-theoretic pigeonhole principle is obtained by applying the Cauchy-Schwarz inequality to the multiplicity function.

Answer 5

The contrapositive of PH is: If you put at most one pigeon per hole, then you have at most $n$ pigeons. Letting $a = (1,\dots,1)$ and $b_i$ be the number of pigeons in hole $i$ with $b_i \in \{0,1\}$, then Cauchy-Schwarz is

$$ \text{number of pigeons} = \sum_i b_i \leq \sqrt{n} \|b\| . $$

We have $\|b\| \leq \sqrt{n}$ so this relaxes to say there are at most $n$ pigeons. So, maybe this is a good generalization of PH:

Theorem. Suppose that pigeon species $i$ weighs $a_i$ pounds. If the total weight of your pigeons exceeds $\|a\| \|B\|$ where $B \geq \vec{0}$, then there exists a species $i$ for which you have more than $B_i$ pigeons.

Proof. By contrapositive, if you have $b_i \in [0,B_i]$ pigeons of each species, then the total weight is $\sum_i a_i b_i \leq \|a\| \|b\| \leq \|a\| \|B\|$.