Cauchy-Schwarz y el encasillamiento

Question

En ocasiones he oído decir (sobre todo en el blog de Terry Tao) que "la desigualdad de Cauchy-Schwarz puede considerarse un refuerzo cuantitativo del principio de encasillamiento". Ciertamente he visto un buen uso de la desigualdad, pero no he visto nada que me haga creer esa afirmación al mismo nivel que creo que el método probabilístico puede usarse como un (vasto) refuerzo del pigeonhole.

Así que.., cómo ¿se puede considerar exactamente a Cauchy-Schwarz como una versión cuantitativa del principio de encasillamiento? Y para más bondad palomera, ¿existen versiones igualmente potenciadas de otras generalizaciones del principio? (Argumentos de álgebra lineal [en particular argumentos de dimensión], el método probabilístico, etc.)

Answer 1

Mi propia interpretación (que supongo que es bastante similar a la anterior):

Suponga que tiene $r$ palomas y $n$ agujeros, y quieren minimizar el número de parejas de palomas en el mismo agujero. Esto puede verse fácilmente como equivalente a minimizar la suma de los cuadrados del número de palomas en cada agujero.

Cauchy Schwarz clásico: $x_1^2+...+x_n^2 \ge\displaystyle\frac1n(x_1+...+x_n)^2$ .

Cauchy Schwarz discreto: Si debe colocar un número entero de palomas en cada agujero, el número de pares de palomas del mismo agujero se minimiza cuando distribuye las palomas de la forma más uniforme posible sujeto a esta restricción.

Encasillamiento: En el caso $r=m+1$ el reparto más equitativo es $(2,1,1,...,1)$ que tiene un par de palomas en el mismo agujero.

Answer 2

Hace poco me enteré de una buena formulación de esta conexión a partir de una versión de la desigualdad de Cauchy-Schwarz enunciada en el artículo de Bateman y Katz [1, página 588 Lemma 2.1].

Imagino que esta versión probablemente forme parte del folclore combinatorio apropiado. Además, es esencialmente la interpretación dada en Respuesta de Kevin .

Proposición. Sea $X$ y $Y$ sean ambos conjuntos finitos y sea $f \colon X \to Y$ sea una función.

• $\#(\ker f) \cdot \#(Y) \ge \#(X)^2$ . (Donde $\ker f$ es el núcleo de una función $f$ .)
• La igualdad se mantiene si y sólo si cada fibra tiene el mismo número de elementos.

Referencia

[1] Bateman, Michael; Katz, Nets Hawk. Nuevos límites para los conjuntos de tapas . J. Amer. Math. Soc. 25 (2012), nº 2., 585-613. MR2869028

Answer 3

Muy interesante. Aquí hay un intente a una respuesta:

Supongamos que hay $n$ casilleros, con agujero $k$ que contiene $f(k)$ palomas, para $k = 1, ..., n$ . El número total de palomas es $m=\sum^n_{k=1} f(k)=f\cdot u$ en el producto interior estándar, donde $u(k) = 1$ para todos $k$ . La desigualdad de Cauchy-Schwarz implica que $\|f\| \|u\| \ge |f\cdot u| = m$ Así que $\|f\| \ge m/\|u\| = m/\sqrt{n}$ . Por otra parte, si $r$ es el máximo de $f(k)$ para $k = 1, ..., n$ alors $\|f\| = \sqrt{\sum^n_{k=1} f(k)^2} \le \sqrt{\sum^n_{k=1} r^2} =r \cdot \sqrt n$ . Juntando todo esto, tenemos $r \sqrt n \ge \|f\| \ge m/\sqrt n$ Así que $r \ge m/n$ . Es el principio del encasillamiento: si hay $m$ palomas en $n$ agujeros, entonces algún agujero tiene al menos $m/n$ palomas, que se convierte en $\lceil m/n\rceil$ si las palomas no se pueden dividir.

Eso parece un très caso especial de la desigualdad de Cauchy-Schwarz, lo que la hace algo insatisfactoria. Probablemente no es exactamente lo que Terry Tao tenía en mente, pero tampoco es completamente falso.

Answer 4

La relación entre la desigualdad de Cauchy-Schwarz y la versión teórica de la medida del principio de encasillamiento puede ilustrarse con el siguiente ejercicio.

${\bf Exercise.}$ Sea $A_1$ ,... $A_n$ sean subconjuntos medibles de un espacio de probabilidad. Suponemos que existe $c>0$ tal que $\mu(A_i)\geq c$ para todos $i$ . Demuestre que existe $i,j,\ i\not= j$ tal que $$ \mu(A_i\cap A_j)\geq {nc^2-c \over n-1}.$$

Es una versión cuantitativa del principio del casillero. Si ponemos demasiados enchufes en el cajón, dos deben solaparse.

He aquí la prueba. Definamos $f = \sum_i {\bf 1}_{A_i}$ para que $\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. $$ Ahora utilizamos la desigualdad de Cauchy-Schwarz: $\int f^2 d\mu \geq (\int f d\mu)^2$ . Obtenemos $$\int f^2-f \ d\mu \geq \Bigl(\int f d\mu -1\Bigr) \int f d\mu \geq (nc -1)nc. $$ Así pues, el principio de encasillamiento teórico de la medida se obtiene aplicando la desigualdad de Cauchy-Schwarz a la función de multiplicidad.

Answer 5

El contrapositivo de PH es: Si pones como máximo una paloma por agujero, entonces tienes como máximo $n$ palomas. Dejar $a = (1,\dots,1)$ y $b_i$ sea el número de palomas en el agujero $i$ con $b_i \in \{0,1\}$ entonces Cauchy-Schwarz es

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

Tenemos $\|b\| \leq \sqrt{n}$ así que esto se relaja para decir que hay como mucho $n$ palomas. Por lo tanto, tal vez esta es una buena generalización de PH:

Teorema. Supongamos que las especies de palomas $i$ pesa $a_i$ libras. Si el peso total de sus palomas supera las $\|a\| \|B\|$ donde $B \geq \vec{0}$ entonces existe una especie $i$ para el que tiene más de $B_i$ palomas.

Prueba. Por contrapositivo, si se tiene $b_i \in [0,B_i]$ palomas de cada especie, entonces el peso total es $\sum_i a_i b_i \leq \|a\| \|b\| \leq \|a\| \|B\|$ .