Problem 1891

*Proof.* First, let's point out a situation where the equality holds, which will help us understand the problem. Let $0 = y_1 = \cdots = y_{\lfloor \frac{n}{2} \rfloor} < y_{\lfloor \frac{n}{2} \rfloor+1} = \cdots = y_n = 1$, and take $x_{i,j} = y_j - y_i$ for $1 \le i < j \le n$. In this case, $x_{i,j} + x_{j,k} = x_{i,k}$, and
$$\sum_{1 \le i < j \le n} x_{i,j}^4 = \sum_{1 \le i < j \le n} x_{i,j}^2 = \left\lfloor \frac{n}{2} \right\rfloor \cdot \left\lfloor \frac{n}{2} \right\rfloor = \left\lfloor \frac{n^2}{4} \right\rfloor,$$
showing that the inequality holds with equality in this case.

Now, let's prove the inequality. We start with the following lemma.

Lemma: Let $m \ge 2$ be a positive integer and $x_1, x_2, \dots, x_m \ge 0$. Let $\lambda_m = \left\lfloor \frac{m^2}{4} \right\rfloor$. Then,
$$\lambda_m \sum_{i=1}^{m} x_i^3 \ge \left( m \sum_{i=1}^{m} x_i^2 - \left( \sum_{i=1}^{m} x_i \right)^2 \right) \sum_{i=1}^{m} x_i.$$

Proof of Lemma: Without loss of generality, assume $\sum_{i=1}^m x_i = 1$. For fixed $x_1, x_2, \dots, x_m$, assume $x_1 \ge x_2 \ge \dots \ge x_k > 0$ and $x_i = 0$ for $i > k$. Let $s = \frac{1}{k} \sum_{i=1}^k x_i = \frac{1}{k}$, and define
$$F(x_1, x_k) := \lambda_m \sum_{i=1}^{m} x_i^3 - \left( m \sum_{i=1}^{m} x_i^2 - \left( \sum_{i=1}^{m} x_i \right)^2 \right) \sum_{i=1}^{m} x_i.$$
When $x_1 + x_k$ is fixed and $x_2, x_3, \dots, x_{k-1}, x_{k+1}, \dots, x_m$ are fixed, $F$ is a linear function of $x_1x_k$. Hence, $F$ achieves its minimum value when $x_1x_k$ is minimized. Notice that
$$s(x_1 + x_k - s) \ge x_1 x_k \ge (x_1 + x_k) \cdot 0 = 0,$$
therefore,
$$F(x_1, x_k) \ge \min \{F(x_1 + x_k, 0), F(s, x_1 + x_k - s)\}.$$
This means that we can always adjust the values such that one variable becomes zero or one variable becomes the arithmetic mean of all positive variables. This adjustment process will terminate in finite steps, leaving all positive variables equal. Assume $x_1 = x_2 = \dots = x_u > x_{u+1} = x_{u+2} = \dots = x_m = 0$. We need to prove that for any $1 \le u \le m$,
$$\lambda_m u \ge (mu - u^2)u \iff \lambda_m \ge u(m - u).$$
This inequality is true by the AM-GM inequality. $\square$

Returning to the original problem, let $\lambda_n = \left\lfloor \frac{n^2}{4} \right\rfloor$. We will use induction to prove a stronger statement: for any positive integers $n \ge 2$ and $\ell$, the following holds:
$$P(n, \ell) := \lambda_{n+\ell-1} \left( \sum_{1 \le i < j < n} x_{i,j}^4 + \ell \sum_{i=1}^{n-1} x_{i,n}^4 \right) - \left( \sum_{1 \le i < j < n} x_{i,j}^2 + \ell \sum_{i=1}^{n-1} x_{i,n}^2 \right)^2 \ge 0. \quad (12)$$
When $\ell = 1$, this is the desired inequality.

We use induction on $n$. For $n = 2$, (12) is equivalent to
$$\lambda_{\ell+1} \ell x_{12}^4 \ge \ell^2 x_{12}^4 \iff \lambda_{\ell+1} \ge \ell,$$
which holds. For $n \ge 3$, fix $n, \ell, x_{i,j}$ for $1 \le i < j < n$, and let
$$f(x_1, x_2, \dots, x_{n-1}) := \lambda_{n+\ell-1} \left( \sum_{1 \le i < j < n} x_{i,j}^4 + \ell \sum_{i=1}^{n-1} x_i^4 \right) - \left( \sum_{1 \le i < j < n} x_{i,j}^2 + \ell \sum_{i=1}^{n-1} x_i^2 \right)^2.$$
If $x_j + x_{i,j} \le x_i$ for $1 \le i < j < n$, then
$$\sum_{1 \le i < j < n} x_{i,j}^2 \le \sum_{1 \le i < j < n} (x_i - x_j)^2 = (n-1) \sum_{i=1}^{n-1} x_i^2 - \left( \sum_{i=1}^{n-1} x_i \right)^2. \quad (13)$$
Using (13) and applying the lemma with $m = n + \ell - 1$, $x_i = 0$ for $n \le i \le n + \ell - 1$, we have
$$\begin{aligned} \sum_{i=1}^{n-1} \frac{\partial f}{\partial x_i} &= 4\ell\lambda_{n+\ell-1} \sum_{i=1}^{n-1} x_i^3 - 4\ell \left( \sum_{1 \le i < j < n} x_{i,j}^2 + \ell \sum_{i=1}^{n-1} x_i^2 \right) \sum_{i=1}^{n-1} x_i \\ &\ge 4\ell\lambda_{n+\ell-1} \sum_{i=1}^{n-1} x_i^3 - 4\ell \left( (n+\ell-1) \sum_{i=1}^{n-1} x_i^2 - \left( \sum_{i=1}^{n-1} x_i \right)^2 \right) \sum_{i=1}^{n-1} x_i \ge 0. \end{aligned}$$
Let $g(y) = f(x_{1,n} + y, \dots, x_{n-1,n} + y)$. For $y \ge -x_{n-1,n}$, $g'(y) \ge 0$. Therefore, $g(0) \ge g(-x_{n-1,n})$. We only need to consider the case where $x_{n-1,n} = 0$.

When $x_{n-1,n} = 0$, let
$$A_p := \sum_{1 \le i < j < n-1} x_{i,j}^p, \quad B_p := \sum_{i=1}^{n-2} x_{i,n-1}^p, \quad C_p := \sum_{i=1}^{n-2} x_{i,n}^p, \quad p \in \{2, 4\}.$$
Then, (12) is equivalent to
$$\lambda_{n+\ell-1}(A_4 + B_4 + \ell C_4) \ge (A_2 + B_2 + \ell C_2)^2. \quad (14)$$
By the induction hypothesis, $P(n-1, \ell+1) \ge 0$, so
$$\begin{aligned} \lambda_{n+\ell-1}(A_4 + (\ell+1)B_4) &\ge (A_2 + (\ell+1)B_2)^2, \\ \lambda_{n+\ell-1}(A_4 + (\ell+1)C_4) &\ge (A_2 + (\ell+1)C_2)^2. \end{aligned}$$
Using these and the Cauchy-Schwarz inequality, we have
$$\begin{aligned} (A_2 + B_2 + \ell C_2)^2 &= \frac{1}{(\ell+1)^2} (A_2 + (\ell+1)B_2 + \ell(A_2 + (\ell+1)C_2))^2 \\ &\le \frac{1}{\ell+1} ((A_2 + (\ell+1)B_2)^2 + \ell(A_2 + (\ell+1)C_2)^2) \\ &\le \frac{1}{\ell+1} (\lambda_{n+\ell-1}(A_4 + (\ell+1)B_4) + \ell\lambda_{n+\ell-1}(A_4 + (\ell+1)C_4)) \\ &= \lambda_{n+\ell-1}(A_4 + B_4 + \ell C_4). \end{aligned}$$
Thus, (14) holds, completing the induction. $\square$