Desigualdad de reordenamiento para múltiples secuencias.

Question

La desigualdad de reordenamiento es bien conocida para dos secuencias $\{a_i\}_{i=1}^n$ y $\{b_i\}_{i=1}^n$ donde cada secuencia es no decreciente $a_1\le a_2\le \cdots \le a_n$ y $b_1 \le b_2 \le \cdots \le b_n$. La desigualdad establece $$\sum_{i=1}^n a_i\cdot b_i\ge\sum_{i=1}^n a_i\cdot b_{\sigma(i)} \ge \sum_{i=1}^n a_i\cdot b_{n+1-i}$$ Nunca he visto una generalización de esta desigualdad en múltiples secuencias, es decir, dado $k$ secuencias no decrecientes $\{a_{1,i}\}_{i=1}^n, \cdots, \{a_{k,i}\}_{i=1}^n$, ¿existe alguna generalización de la desigualdad de reordenamiento? Mi suposición probablemente sería algo de la forma $$\sum_{i=1}^n\prod_{j=1}^k a_{j,i}\ge\sum_{i=1}^n a_{1,i}\prod_{j=2}^ka_{j,\sigma_{j}(i)}$$ para permutaciones $\sigma_j$.

Answer 1

Esta es una prueba que se me ocurrió después de mirar algunas sugerencias. Espero que esté completa.

Procedamos por inducción. Primero consideremos $k$ secuencias de dos términos cada una, $\{a_{i}^1\}_{i=1}^2,\ \{a_{i}^2\}_{i=1}^2, \ldots, \{a_{i}^k\}_{i=1}^2$. Cada secuencia en la siguiente discusión será positiva y no creciente.

Supongamos, para llegar a una contradicción, que la suma máxima es producida por una permutación donde los elementos máximos no están juntos. Sin pérdida de generalidad, supongamos que $a^1_1$ y $a^2_1$ están separados: $$a_1^1\cdot a^2_2\cdot\prod_{i=3}^k a^i_{\sigma_{i}(1)} + a_2^1\cdot a^2_1\cdot\prod_{i=3}^k a^i_{\sigma_{i}(2)}$$ Podemos asumir que $a^j_1 \neq a^j_2$ para todas las secuencias, de lo contrario simplemente factorizamos el término y continuamos. Dividamos cada sumando en dos productos más pequeños.

Primero, $b_1$, contendrá todos los términos en el primer sumando tal que $a_{\sigma_{i}(1)} > a_{\sigma_{i}(2)}$ mientras que $s_1$ contendrá todos los términos en el primer sumando tal que $a_{\sigma_{i}(1)} < a_{\sigma_{i}(2)}$. De manera similar, dividimos el segundo sumando en $b_2$ que contiene los términos $a_{\sigma_{i}(1)} < a_{\sigma_{i}(2)}$ y $s_2$ que contiene los términos $a_{\sigma_{i}(1)} > a_{\sigma_{i}(2)}$.

Esto da la suma como $$a_1^1 \cdot a_2^2 \cdot s_1 \cdot b_1 + a_2^1 \cdot a_1^2 \cdot s_2 \cdot b_2$$ por construcción, tenemos $$a_2^2\cdot s_1 < a^2_1\cdot b_2,\ \ a_2^1\cdot s_2 < a_1^1\cdot b_1$$ y así, por la desigualdad de reordenamiento, tenemos $$a_1^1\cdot a_1^2 \cdot b_1 \cdot b_2 + a_2^1 \cdot a_2^2 \cdot s_1 \cdot s_2 \ge a_1^1\cdot a^2_2\cdot\prod_{i=2}^k a^i_{\sigma_{i}(1)} + a_2^1\cdot a^2_1\cdot\prod_{i=2}^k a^i_{\sigma_{i}(2)}$$ con igualdad si y solo si $a_1^j = a_2^j$ para todas las secuencias excepto $a^1$ o $a^2$. El proceso puede repetirse para juntar todos los elementos máximos. Esto contradice el hecho de que la suma máxima se produce cuando los elementos máximos están separados. Esto maneja el caso de dos términos.

Ahora supongamos que la desigualdad se cumple para secuencias de longitud $n$ y veamos la desigualdad para secuencias de longitud $n+1$. Hay dos casos que manejar. Si los elementos máximos están todos juntos, entonces simplemente eliminamos el término y aplicamos inmediatamente la hipótesis inductiva. Si los elementos máximos no están juntos, podemos usar el procedimiento en el caso base repetidamente para juntarlos, momento en el cual eliminamos el término y aplicamos la hipótesis inductiva.

Answer 2

Creo que hay problemas si hay números negativos. Digo que las secuencias son $-5,1$; $-5,1$; y $1,2$. Mantenerlas en orden te da $27$, pero puedes reorganizar para obtener $51$. Si no hay términos negativos, ¿no funciona la inducción?

Answer 3

Al tratar con la condición de monotonicidad, lo natural es hacer la transformada de Abel (que transforma la monotonicidad en positividad).

Es decir, la secuencia no decreciente no negativa $a_{s,1},a_{s,2}, \dots, a_{s,n}$ puede escribirse como $$a_{s,i}=b_{s,1}+b_{s,2}+\dots+b_{s,i}$$ para $b_{s,1},b_{s,2},\dots,b_{s,n}$ no negativos. Ahora, para una permutación fija $\pi_1,\pi_2,\dots,\pi_k\in S_n$, la suma $$S(\pi_1,\dots,\pi_k):=\sum_{i=1}^n a_{1,\pi_1(i)}a_{2,\pi_2(i)}\ldots a_{k,\pi_k(i)}$$ es una función multilineal de los vectores $b_1,b_2,\dots,b_k$ (donde $b_s=(b_{s,1},b_{s,2},\dots,b_{s,n})$. Observa cada coeficiente específico $$[b_{i,i_1}\cdot b_{2,i_2}\cdot \ldots \cdot b_{k,i_k}]S(\pi_1,\dots,\pi_k).$$ Si $\pi_1=\pi_2=\dots =\pi_k=id$, este coeficiente es igual a $n+1-\max(i_1,\dots,i_k)$. En todos los demás casos, no excede $n+1-\max(i_1,\dots,i_k)$. De hecho, si $\max(i_1,\dots,i_k)=i_r$, para todos los $i_r-1$ valores del índice $j$ tales que $\pi_r(j) el producto $a_{1,\pi_1(i)}a_{2,\pi_2(i)}\ldots a_{k,\pi_k(i)}$ no contiene nuestro monomio $b_{i,i_1}\cdot b_{2,i_2}\cdot \ldots \cdot b_{k,i_k}$. Por lo tanto, la suma de productos igualmente ordenada es mayor o igual que cualquier otra suma de productos.

La siguiente versión de este argumento utiliza menos cantidad de notaciones. Cualquier secuencia no negativa no decreciente de longitud $n$ es una combinación lineal de secuencias de la forma $(0,0,\dots,0,1,1,\dots,1)$ con coeficientes no negativos. Entonces, por multilinealidad, basta verificar la desigualdad $S(\pi_1,\dots,\pi_k)\leqslant S(id,id,\dots,id)$ cuando cada $a_1,\dots,a_k$ es una de esas secuencias. Esto es obvio: el lado derecho es igual al mínimo de $|a_1|,|a_2|,\dots,|a_k|$ (aquí $|a_i|$ denota el número de 1's en la secuencia $a_i$), y el lado izquierdo no excede este mínimo.