§ Combinatorial Cauchy Schwarz

§ Version 1

• 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: $\min_{h: i > j} (h[i] - h[j])^2$ where $h[i]$ is the hole of the $i$th pigeon.
• Classical cauchy schwarz: $x_1^2 + x_2^2 + x_3^2 \geq 1/2(x_1 + x_2 + x_3)^2$
• Discrete cauchy schwarz: On placing a natural number of pigeons in each hole, The number of pairs of pigeons in the same hole is minimized iff pigeons are distributed as evenly as possible.
• Pigeonhole principle: When $r = m + 1$, the best split possible is $(2, 1, 1, \dots)$.

§ Version 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.
• Proposition: Let $X$ and $Y$ both be finite sets and let f:X→Y be a function.
• $|ker f| \cdot |Y| \geq |X|^2$. (Where ker f is the kernel of f, given as the equalizer of X*X-f*f-> X. More explicitly, it is the subset of X*X ker(f) := { (x, x') : f(x) = f(x') }).
• Equality holds if and only if every fiber has the same number of elements.
• This is the same as the version 1, when we consider $f$ to be the function $h$ which assigns pigeons to holes. Every fiber having the same number of elements is the same as asking for the pigeons to be evenly distributed.
• Compare: $|ker(f)| \cdot |Y| \geq |X|^2$ with $(x_1^2 + x_2^2 + x_3^2) \cdot n \geq (x_1 + x_2 + x_3)^2$. Cardinality replaces the action of adding things up, and $|X|^2$ is the right hand side, $|ker(f)|$ is the left hand side, which is the sum of squares.