$2\sum_{i,j} |x_i-y_j| \geq \sum_{i,j} (|x_i-x_j| + |y_i-y_j|)$ ?

Question

Dejemos que $x_1, \ldots, x_n$ y $y_1, \ldots, y_n$ sean números reales.

Pregunta: ¿Es $$2\sum_{i,j=1}^n |x_i-y_j| \geq \sum_{i,j=1}^n (|x_i-x_j| + |y_i-y_j|)$$ ¿Es cierto?

Motivación: Esto está motivado por un problema físico. Si la desigualdad anterior se cumple, entonces se puede obtener que ciertos términos se suprimen exponencialmente.

Mi juicio:

1. Para los pequeños $n$ He generado aleatoriamente $x_i, y_i$ muchas veces y comprobar que la desigualdad se mantiene.

2. Si el prefactor en el LHS es 4, entonces puedo demostrar la desigualdad como sigue. Para $k=1, \ldots, n$ tenemos $$|x_i-x_j| \leq |x_i-y_k| + |y_k-x_j|$$ y análogamente $$|y_i-y_j| \leq |y_i-x_k| + |x_k - y_j|.$$ Promediando las desigualdades anteriores sobre todos los $k$ y sumando sobre $i,j$ da $$\sum_{i,j=1}^n (|x_i-x_j| + |y_i-y_j|) \leq 4 \sum_{i,j=1}^n |x_i-y_j|.$$

Answer 1

Podemos reescribir la RHS como sigue:

$$2 \sum_{0<i<j\leq n}(|x_i-x_j|+|y_i-y_j|) $$

Ahora, sin pérdida de generalidad, podemos reordenar cada vector de manera que todos los diferencias sean no negativas (es decir, en orden descendente)

$$2 \sum_{0<i<j\leq n}(x_i-x_j+y_i-y_j) = 2\sum_{0<i<j\leq n}((x_i-y_j)-(x_j-y_i))\\ =\sum_{i,j=1\leq n}(x_i-y_j)-\sum_{i,j=1\leq n}(x_j-y_i)$$

$$\sum_{i,j=1\leq n}(x_i-y_j)-\sum_{i,j=1\leq n}(x_j-y_i) \leq \sum_{i,j=1\leq n}|x_i-y_j| +\sum_{i,j=1\leq n}|x_j-y_i| = 2\sum_{i,j=1\leq n}|x_j-y_i|$$