Muirhead y la teoría de la mayorización

La notación de sumas simétricas

Para un vector de exponentes $(\alpha,\beta,\gamma)$ con $\alpha,\beta,\gamma\in\mathbb{R}$, la suma de Muirhead se define como:

$$[\alpha,\beta,\gamma] = \sum_{\sigma\in S_3} a^{\sigma(\alpha)} b^{\sigma(\beta)} c^{\sigma(\gamma)},$$

donde la suma recorre las 6 permutaciones de $(\alpha,\beta,\gamma)$. Explícitamente:

$$[\alpha,\beta,\gamma] = a^\alpha b^\beta c^\gamma + a^\alpha b^\gamma c^\beta + a^\beta b^\alpha c^\gamma + a^\beta b^\gamma c^\alpha + a^\gamma b^\alpha c^\beta + a^\gamma b^\beta c^\alpha.$$

Ejemplos fundamentales para tres variables $a,b,c>0$:

$$[3,0,0] = 2(a^3+b^3+c^3), \quad [2,1,0] = 2(a^2b+a^2c+b^2a+b^2c+c^2a+c^2b),$$

$$[1,1,1] = 6abc, \quad [2,0,0] = 2(a^2+b^2+c^2), \quad [1,1,0] = 2(ab+bc+ca).$$

La notación $[\alpha,\beta,\gamma]$ es conveniente porque muchas desigualdades famosas se escriben de forma compacta. Por ejemplo, la desigualdad AM-GM para tres variables es $[1,0,0]\geq [1/3,1/3,1/3]$... espera: en esta notación $[1,0,0]=2(a+b+c)$ y $[1/3,1/3,1/3]=6(abc)^{1/3}$. AM-GM dice $(a+b+c)/3\geq (abc)^{1/3}$, equivalente a $2(a+b+c)\geq 6(abc)^{1/3}$, es decir $[1,0,0]\geq [1/3,1/3,1/3]$. Esto sugiere que las desigualdades de la forma $[\mathbf{x}]\geq[\mathbf{y}]$ tienen una estructura.

Mayorización: la relación de orden que unifica las desigualdades

Sean $\mathbf{x} = (x_1,x_2,x_3)$ e $\mathbf{y} = (y_1,y_2,y_3)$ con $x_1\geq x_2\geq x_3$ e $y_1\geq y_2\geq y_3$ (en orden decreciente). Decimos que **$\mathbf{x}$ mayoriza a $\mathbf{y}$**, escrito $\mathbf{x}\succ\mathbf{y}$, si:

$$x_1 \geq y_1, \quad x_1+x_2 \geq y_1+y_2, \quad x_1+x_2+x_3 = y_1+y_2+y_3.$$

La condición de igualdad en la última línea es importante: mayorización requiere que las sumas totales sean iguales. Sin ella tendríamos un preorden diferente.

Interpretación geométrica. El vector $\mathbf{x}$ "está más concentrado" que $\mathbf{y}$: toda la "masa" en $\mathbf{x}$ tiende a estar en las primeras coordenadas más que en $\mathbf{y}$. El vector más concentrado posible con suma $s$ es $(s,0,0)$; el más "disperso" es $(s/3,s/3,s/3)$. Formalmente: $(s,0,0)\succ\mathbf{y}\succ(s/3,s/3,s/3)$ para todo $\mathbf{y}$ con suma $s$ y coordenadas no negativas.

Ejemplos de comparación. Todos los vectores con suma $n$:

$(n,0,0) \succ (n-1,1,0) \succ (n-1,0,1)$... espera, aquí $(n-1,1,0)=(n-1,1,0)$ y $(n-1,0,1)=(n-1,1,0)$ en orden decreciente, son iguales. Correcto: $(n,0,0)\succ(n-1,1,0)\succ(\lceil n/2\rceil, \lfloor n/2\rfloor, 0)\succ\ldots\succ(n/3,n/3,n/3)$.

Concreto para $n=3$: $(3,0,0)\succ(2,1,0)\succ(1,1,1)$.

Teorema de Muirhead

Teorema de Muirhead. Sean $\mathbf{x}=(x_1,x_2,x_3)$ e $\mathbf{y}=(y_1,y_2,y_3)$ con $x_1\geq x_2\geq x_3\geq 0$ e $y_1\geq y_2\geq y_3\geq 0$, con $x_1+x_2+x_3=y_1+y_2+y_3$. Si $\mathbf{x}\succ\mathbf{y}$, entonces para todo $a,b,c>0$:

$$[x_1,x_2,x_3] \geq [y_1,y_2,y_3].$$

Demostración via transformadas T. Una transformada T es la operación que toma $\mathbf{y}=(y_1,y_2,y_3)$ y lo remplaza por $\mathbf{y}^* = (y_1+\epsilon, y_2, y_3-\epsilon)$ para algún $\epsilon>0$ tal que $\mathbf{y}^*$ sigue siendo ordenado. El teorema de Hardy-Littlewood-Pólya establece que $\mathbf{x}\succ\mathbf{y}$ si y solo si $\mathbf{y}$ se puede obtener de $\mathbf{x}$ mediante una secuencia finita de transformadas T inversas (que "dispersan" el vector).

Es suficiente demostrar que una sola transformada T preserva la desigualdad de sumas simétricas. Es decir, si $\alpha\geq\beta$ y $\epsilon>0$, entonces $[\alpha,\beta,\gamma]\geq[\alpha-\epsilon,\beta+\epsilon,\gamma]$ para $a,b,c>0$. Esto equivale a demostrar:

$$\sum_{\sigma\in S_3} a^{\sigma(\alpha)}b^{\sigma(\beta)}c^{\sigma(\gamma)} \geq \sum_{\sigma\in S_3} a^{\sigma(\alpha-\epsilon)}b^{\sigma(\beta+\epsilon)}c^{\sigma(\gamma)}.$$

Fijando $c$ y viendo la diferencia como función de $a,b$: la diferencia se factoriza como $(a^{\alpha-\beta}-b^{\alpha-\beta})(a^\beta-b^\beta)(\cdots)\geq 0$ por el lema algebraico $(x^p-y^p)(x^q-y^q)\geq 0$ para $x,y>0$ y $p,q$ del mismo signo. Los detalles de esta factorización son técnicos pero estándar; el resultado es que cada paso T preserva $[\cdot]\geq[\cdot]$. Iterando, se obtiene el teorema completo. $\blacksquare$

El teorema es válido para $n$ variables con la definición análoga de suma $[x_1,\ldots,x_n]$ y la relación de mayorización correspondiente.

Cuándo aplica Muirhead y cuándo no

Condición fundamental: la desigualdad debe ser simétrica. El teorema de Muirhead aplica cuando la desigualdad $[\mathbf{x}]\geq[\mathbf{y}]$ involucra sumas sobre todas las permutaciones (sumas simétricas completas $\sum_{\sigma\in S_n}$). Si la desigualdad involucra sumas cíclicas (solo $n$ términos en lugar de $n!$), Muirhead no aplica directamente.

El error más común: aplicar Muirhead a una suma cíclica. Por ejemplo, $\sum_{\mathrm{cyc}} a^2b\geq\sum_{\mathrm{cyc}} abc$ (es decir, $a^2b+b^2c+c^2a\geq 3abc$) no se puede probar por Muirhead porque las sumas cíclicas $\sum_{\mathrm{cyc}}$ no son sumas simétricas $\sum_{\sigma\in S_3}$. (En efecto, la suma simétrica $[2,1,0]=2(a^2b+a^2c+b^2a+b^2c+c^2a+c^2b)$ incluye tanto $\sum_{\mathrm{cyc}} a^2b$ como $\sum_{\mathrm{cyc}} ab^2$, y $(2,1,0)\succ(1,1,1)$ por Muirhead da $[2,1,0]\geq[1,1,1]$, que es $a^2b+a^2c+b^2a+b^2c+c^2a+c^2b\geq 6abc$, cierto. Pero $a^2b+b^2c+c^2a\geq 3abc$ es una suma cíclica, que es falsa para $a=3,b=1/3,c=1$: LHS $= 9\cdot(1/3) + (1/9)\cdot 1 + 1\cdot 3 = 3+1/9+3\approx 6.1$, RHS $=3$. Cierto en este caso, pero la desigualdad cíclica es de hecho falsa en general — tomando $a\to\infty, b\to 0$ adecuadamente se obtiene contraejemplo.)

Muirhead y el olimpismo. En algunas competencias (en particular el propio IMO), invocar "por Muirhead" sin dar la demostración explícita no se acepta como solución completa. El motivo es que Muirhead es un teorema cuya demostración requiere la teoría de majorización; simplemente citar "$[\mathbf{x}]\geq[\mathbf{y}]$ porque $\mathbf{x}\succ\mathbf{y}$" es circular si no se ha demostrado el teorema. En selectivos de alto nivel, la práctica correcta es o bien demostrar el teorema, o bien reemplazar la aplicación de Muirhead por una demostración explícita via AM-GM o SOS.

Muirhead como guía heurística. Aunque no sea siempre válido como argumento final, Muirhead es invaluable como herramienta de diagnóstico: si $[\mathbf{x}]\geq[\mathbf{y}]$ con $\mathbf{x}\succ\mathbf{y}$, sabemos que la desigualdad es verdadera y podemos buscar una demostración por AM-GM, SOS o Schur. Si $\mathbf{x}\not\succ\mathbf{y}$, la desigualdad puede ser falsa y debemos buscar contraejemplo.

Ejemplos: majorización y tablas de comparación

Para vectores con suma 3 (exponentes en tres variables, problema típico de grado 3):

$(3,0,0)\succ(2,1,0)\succ(1,1,1)$.

Luego: $[3,0,0]\geq[2,1,0]\geq[1,1,1]$.

Esto da las desigualdades: $a^3+b^3+c^3\geq a^2b+ab^2+b^2c+bc^2+c^2a+ca^2\geq 6abc$... Pero cuidado: $[3,0,0]=2(a^3+b^3+c^3)$ y $[2,1,0]=2(a^2b+\ldots)$, y $[1,1,1]=6abc$. Dividiendo: $a^3+b^3+c^3\geq a^2b+\ldots$ y $a^2b+\ldots\geq 6abc$.

La segunda es AM-GM en 6 términos. La primera es la desigualdad clásica $\sum a^3\geq\sum a^2b$ (demostrable también por SOS: $\sum a^3-\sum a^2b = \frac{1}{2}\sum_{\mathrm{cyc}}(a-b)^2(a+b-c)$... que puede ser negativo localmente — Schur dice que la suma es $\geq 0$).

Para vectores con suma 4:

$(4,0,0)\succ(3,1,0)\succ(2,2,0)\succ(2,1,1)$.

La cadena de desigualdades correspondiente incluye $\sum a^4\geq\sum a^3b\geq\sum a^2b^2\geq\sum a^2bc$ (todas con sus factores 2 correspondientes en la notación de sumas simétricas).

IMO 2000 Problema 2 via Muirhead

Problema (IMO 2000, P2). Para $a,b,c>0$ con $abc=1$, probar:

$$\left(a-1+\frac{1}{b}\right)\left(b-1+\frac{1}{c}\right)\left(c-1+\frac{1}{a}\right) \leq 1.$$

Reducción a sumas simétricas. Como $abc=1$, podemos escribir $1/b = ac$ y similarmente. Entonces $a-1+1/b = a+ac-1 = a(1+c)-1$. El producto es $\prod_{\mathrm{cyc}}(a(1+c)-1)$.

Alternativamente, la substitución $a=x/y, b=y/z, c=z/x$ (que usamos en la lección 2.1) reduce la desigualdad a $(x+z-y)(y+x-z)(z+y-x)\leq xyz$, o equivalentemente:

$$x^3+y^3+z^3+3xyz \geq x^2y+xy^2+y^2z+yz^2+z^2x+zx^2.$$

Vía Muirhead. El lado derecho $x^2y+xy^2+y^2z+yz^2+z^2x+zx^2 = [2,1,0]$ (la suma simétrica). El lado izquierdo $x^3+y^3+z^3+3xyz = \frac{1}{2}[3,0,0] + \frac{1}{6}[1,1,1]$... Hmm, calculemos: $[3,0,0]=2(x^3+y^3+z^3)$ y $[1,1,1]=6xyz$. Entonces $x^3+y^3+z^3+3xyz = \frac{1}{2}[3,0,0]+\frac{1}{2}[1,1,1]$.

La desigualdad a probar es $\frac{1}{2}[3,0,0]+\frac{1}{2}[1,1,1]\geq[2,1,0]$.

Como $(3,0,0)\succ(2,1,0)$ por Muirhead: $[3,0,0]\geq[2,1,0]$. Luego $\frac{1}{2}[3,0,0]+\frac{1}{2}[1,1,1]\geq\frac{1}{2}[2,1,0]+\frac{1}{2}[1,1,1]$.

Queda por ver que $\frac{1}{2}[2,1,0]+\frac{1}{2}[1,1,1]\geq[2,1,0]$, es decir $[1,1,1]\geq[2,1,0]$. Pero $(1,1,1)\not\succ(2,1,0)$ pues $1<2$. Esta dirección es incorrecta.

Corrección. La desigualdad $\frac{1}{2}[3,0,0]+\frac{1}{2}[1,1,1]\geq[2,1,0]$ se demuestra directamente: es equivalente a $[3,0,0]+[1,1,1]\geq 2[2,1,0]$, que se lee $2(x^3+y^3+z^3)+6xyz\geq 2(x^2y+\ldots)$, es decir la desigualdad ya demostrada. Para probarla via Muirhead puro, necesitamos escribirla como una combinación convexa de desigualdades Muirhead. Específicamente: $\frac{1}{2}([3,0,0]-[2,1,0])+\frac{1}{2}([1,1,1]-[2,1,0])\geq 0$. La primera diferencia es $\geq 0$ por $(3,0,0)\succ(2,1,0)$. La segunda diferencia $[1,1,1]-[2,1,0]\leq 0$ pues $(2,1,0)\succ(1,1,1)$. Así Muirhead solo no es suficiente; la combinación lineal particular requiere verificación adicional.

Conclusión pedagógica. Muirhead da la intuición de que la desigualdad es verdadera (ambos vectores $(3,0,0)$ e $(1,1,1)$ son "más extremos" que $(2,1,0)$ en sentidos opuestos). La prueba rigurosa usa SOS o Schur, como demostramos en la lección 2.1. Muirhead fue la brújula; SOS fue el vehículo.