## § 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.