Desigualdad de Karamata

Teoría

La desigualdad de Karamata es una herramienta súper potente que lleva la desigualdad de Jensen al siguiente nivel. Mientras que Jensen te sirve para comparar el promedio de una función con la función del promedio, Karamata te permite comparar sumas de funciones aplicadas a dos conjuntos de números distintos. La clave para usarla es un concepto llamado "mayorización", que básicamente es una forma matemática de decir que un conjunto de números está más "disperso" o "alejado del centro" que otro, aunque ambos sumen lo mismo.

Esta técnica es fundamental en problemas de olimpiada de alto nivel, como el USAMO o la IMO, porque te da mucha flexibilidad. Imagina que tienes una expresión de la forma $\sum f(x_i)$ y quieres demostrar que es mayor o igual a $\sum f(y_i)$. Si logras probar que el conjunto de las $x$ mayoriza al de las $y$ y que la función $f$ es convexa, el problema está prácticamente resuelto. La intuición clave es que las funciones convexas "premian" la dispersión: entre más alejados estén los puntos entre sí, más grande será la suma de sus imágenes.

Fórmulas Clave

Para aplicar Karamata, primero necesitas ordenar tus variables. Considera dos secuencias de números reales $x_1, x_2, \dots, x_n$ y $y_1, y_2, \dots, y_n$ ordenadas de forma no creciente: $$x_1 \ge x_2 \ge \dots \ge x_n \quad \text{y} \quad y_1 \ge y_2 \ge \dots \ge y_n$$

Dices que la secuencia $x$ mayoriza a la secuencia $y$ (y lo escribes como $x \succ y$) si se cumplen las siguientes $n$ condiciones:

1. $x_1 \ge y_1$
2. $x_1 + x_2 \ge y_1 + y_2$
3. $x_1 + x_2 + \dots + x_k \ge y_1 + y_2 + \dots + y_k$ para toda $k < n$
4. $x_1 + x_2 + \dots + x_n = y_1 + y_2 + \dots + y_n$ (la suma total debe ser igual)

El Teorema de Karamata: Si $f: I \to \mathbb{R}$ es una función convexa en un intervalo $I$ y $x, y \in I$ son tales que $x \succ y$, entonces: $$\sum_{i=1}^n f(x_i) \ge \sum_{i=1}^n f(y_i)$$

Si la función $f$ es cóncava, la desigualdad simplemente se voltea: $$\sum_{i=1}^n f(x_i) \le \sum_{i=1}^n f(y_i)$$

Demostración

Para demostrar este teorema, puedes usar la propiedad de las pendientes de las funciones convexas. Supón que $f$ es derivable (si no lo es, el argumento funciona igual usando derivadas laterales).

1. Define $c_i$ como el cociente de la diferencia: $$c_i = \frac{f(x_i) - f(y_i)}{x_i - y_i}$$ Si $x_i = y_i$, puedes tomar $c_i = f'(x_i)$. Como $f$ es convexa, su derivada $f'$ es no decreciente. Nota que como $x_1 \ge y_1$ y las secuencias están ordenadas, las pendientes $c_i$ también siguen un orden no creciente: $c_1 \ge c_2 \ge \dots \ge c_n$.

2. Escribe la diferencia que quieres analizar como una suma: $$D = \sum_{i=1}^n f(x_i) - \sum_{i=1}^n f(y_i) = \sum_{i=1}^n (f(x_i) - f(y_i)) = \sum_{i=1}^n c_i(x_i - y_i)$$

3. Ahora, define $A_k = \sum_{i=1}^k (x_i - y_i)$ para cada $k=1, \dots, n$. Por la definición de mayorización, sabes que $A_k \ge 0$ para todo $k < n$ y que $A_n = 0$. También nota que $x_i - y_i = A_i - A_{i-1}$ (donde $A_0 = 0$).

4. Sustituye esto en la suma y aplica un truco de suma por partes (Abel): $$D = \sum_{i=1}^n c_i(A_i - A_{i-1}) = c_1 A_1 + c_2(A_2 - A_1) + \dots + c_n(A_n - A_{n-1})$$ Reagrupando los términos según cada $A_i$, obtienes: $$D = (c_1 - c_2)A_1 + (c_2 - c_3)A_2 + \dots + (c_{n-1} - c_n)A_{n-1} + c_n A_n$$

5. Analiza cada término:

• Como $f$ es convexa y las secuencias están ordenadas, $c_i \ge c_{i+1}$, por lo que $(c_i - c_{i+1}) \ge 0$.
• Por la condición de mayorización, $A_i \ge 0$ para todo $i$.
• El último término $c_n A_n$ es cero porque $A_n = 0$.

Como todos los términos de la suma son productos de números no negativos, la suma total $D$ debe ser mayor o igual a cero. Por lo tanto: $$\sum_{i=1}^n f(x_i) \ge \sum_{i=1}^n f(y_i)$$ $\square$