IMO 2021 Problem 2

Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 58s

Problem

Show that the inequality $$ \sum_{i=1}^n \sum_{j=1}^n \sqrt{|x_i-x_j|} \le \sum_{i=1}^n \sum_{j=1}^n \sqrt{|x_i+x_j|} $$ holds for all real numbers $x_1,x_2,\dots,x_n$.

Exploration

For small values of $n$, the inequality reduces to comparing pairwise contributions. When $n=1$, both sides are $0$. When $n=2$, the inequality becomes

$$\sqrt{|x_1-x_1|}+\sqrt{|x_1-x_2|}+\sqrt{|x_2-x_1|}+\sqrt{|x_2-x_2|} \le \sqrt{|x_1+x_1|}+\sqrt{|x_1+x_2|}+\sqrt{|x_2+x_1|}+\sqrt{|x_2+x_2|},$$

which simplifies to

$$2\sqrt{|x_1-x_2|} \le 2\sqrt{|x_1+x_2|},$$

so the claim reduces to $\sqrt{|x_1-x_2|} \le \sqrt{|x_1+x_2|}$, which is false for arbitrary real numbers, for example $x_1=1$, $x_2=-1$. Hence the inequality is not valid in that interpretation; however, the original expression includes diagonal terms, so a more careful aggregation is needed rather than isolating pairs.

The structure suggests a symmetric double sum depending only on pairwise relations. A natural idea is to compare contributions of each pair $(i,j)$ and $(i,-j)$ after some transformation or to reinterpret the inequality via convexity of $t\mapsto \sqrt{t}$ and rearrangement-type arguments. The main difficulty is that the expression is not separable into independent pairwise inequalities.

A more promising direction is to rewrite both sides as sums over $i,j$ and attempt to compare squared quantities after applying Cauchy–Schwarz or integral representations of $\sqrt{t}$, such as

$$\sqrt{t} = \frac{1}{2\sqrt{\pi}} \int_0^\infty \left(1 - e^{-t u}\right) u^{-3/2},du.$$

This converts the inequality into a comparison of exponential kernels, where positivity of quadratic forms becomes accessible.

The key expectation is that the inequality reduces to showing that a certain matrix with entries depending on $|x_i-x_j|$ is dominated, in a positive semidefinite sense, by the matrix with entries depending on $|x_i+x_j|$.

The most delicate step will be justifying interchange of summation and integral and verifying positivity of the resulting kernel difference.

Problem Understanding

This is a Type B problem: a universal inequality must be proved for all real tuples $(x_1,\dots,x_n)$.

We compare two symmetric double sums over square roots of absolute differences and absolute sums. Each side aggregates all ordered pairs, including diagonal terms. The goal is to show that the “sum-structure” always dominates the “difference-structure” under the square root.

The core difficulty is that pointwise comparison

$$\sqrt{|x_i-x_j|} \le \sqrt{|x_i+x_j|}$$

fails in general, so the inequality cannot hold term-by-term. The structure must therefore exploit global interactions across all indices rather than pairwise dominance.

The guiding intuition is that the transformation $(x_i,x_j)\mapsto (x_i+x_j)$ spreads magnitudes more than $(x_i-x_j)$ when aggregated over all pairs, and the concavity of $\sqrt{\cdot}$ interacts favorably with this spreading effect.

Proof Architecture

First, introduce the integral representation

$$\sqrt{t} = c \int_0^\infty (1-e^{-tu})u^{-3/2},du,$$

which allows conversion of both sides into integrals of double sums of exponentials.

Second, prove absolute convergence of the resulting integrals after summation over $i,j$, ensuring exchange of summation and integration is valid.

Third, reduce the inequality to proving that for every $u>0$,

$$\sum_{i,j} e^{-u|x_i+x_j|} \le \sum_{i,j} e^{-u|x_i-x_j|}.$$

This becomes the central lemma.

Fourth, establish this exponential inequality by rewriting both sides using Fourier-type representations or by expressing them as convolutions of even functions and applying positivity of definite kernels.

The hardest step is the exponential kernel comparison, where the correct structural symmetry must be exploited.

Solution

Lemma 1

For every $t\ge 0$,

$$\sqrt{t} = \frac{1}{2\sqrt{\pi}} \int_0^\infty (1-e^{-tu})u^{-3/2},du.$$

This follows from the standard identity for the Gamma function applied to $t^{1/2}$, using the substitution $s=tu$ in the integral defining $\Gamma(-1/2)$ after analytic continuation. The representation is valid because the integral converges at $0$ due to cancellation in $1-e^{-tu}$ and at infinity due to the decay of $u^{-3/2}$. This lemma provides a strictly positive kernel representation of the square root, converting nonlinear expressions into linear ones under integration.

Certification: this step converts concave power functions into exponential averages, enabling linear comparison after integration.

Lemma 2

For every $u>0$,

$$\sum_{i,j} e^{-u|x_i+x_j|} \le \sum_{i,j} e^{-u|x_i-x_j|}.$$

For real $a,b$, define

$$K_-(a,b)=e^{-u|a-b|}, \quad K_+(a,b)=e^{-u|a+b|}.$$

Let $f(t)=e^{-u|t|}$, which is an even positive definite function on $\mathbb{R}$ since its Fourier transform is proportional to $\frac{2u}{u^2+\xi^2}$, which is nonnegative.

The kernel $K_-(a,b)$ equals $f(a-b)$ and is therefore positive definite. The kernel $K_+(a,b)$ equals $f(a-(-b))$, corresponding to evaluating the same kernel on the reflected set $(-x_j)$.

Thus

$$\sum_{i,j} e^{-u|x_i+x_j|} = \sum_{i,j} f(x_i-(-x_j)).$$

Define the multisets $X={x_i}$ and $-X={-x_i}$. The right-hand side is the interaction energy between $X$ and $-X$ under kernel $f$, while the left-hand side is the interaction energy of $X$ with itself.

Because $f$ is even and positive definite, the quadratic form

$$Q(\lambda_1,\dots,\lambda_n)=\sum_{i,j}\lambda_i\lambda_j f(x_i-x_j)$$

is nonnegative for all real $\lambda_i$. Choosing $\lambda_i=1$ yields positivity of the self-interaction matrix $[f(x_i-x_j)]$, and choosing $\lambda_i=1$ on $X$ and $\lambda_i=-1$ on $-X$ shows that cross-interaction dominates self-interaction in the sense that

$$\sum_{i,j} f(x_i-(-x_j)) \le \sum_{i,j} f(x_i-x_j).$$

This establishes the lemma.

Certification: this step identifies the exponential kernel as positive definite and converts the inequality into a comparison of quadratic forms over reflected configurations.

Completion of the proof

Using Lemma 1,

$$\sum_{i,j} \sqrt{|x_i-x_j|} = \frac{1}{2\sqrt{\pi}} \int_0^\infty \sum_{i,j} (1-e^{-u|x_i-x_j|})u^{-3/2},du.$$

An analogous representation holds for the right-hand side.

Subtracting both expressions reduces the inequality to showing that for all $u>0$,

$$\sum_{i,j} e^{-u|x_i+x_j|} \le \sum_{i,j} e^{-u|x_i-x_j|},$$

which is exactly Lemma 2. Integrating preserves the inequality since $u^{-3/2}>0$.

Thus the desired inequality holds for all real $x_1,\dots,x_n$.

This completes the proof. ∎

Verification of Key Steps

The most delicate step is the transition from the square-root inequality to the exponential kernel inequality. A direct recomputation shows that the integral representation preserves ordering because it is a positive linear combination of exponential terms; any sign error would reverse the inequality after integration.

The second fragile point is the interpretation of $e^{-u|x_i+x_j|}$ as a kernel on a reflected configuration. A careless argument might assume termwise comparison with $|x_i+x_j|\ge |x_i-x_j|$, which is false; the correct comparison uses positive definiteness, not pointwise inequalities.

The third delicate step is the use of Fourier positivity of $e^{-u|t|}$; omitting verification of nonnegativity of its transform would invalidate the quadratic form argument.

Alternative Approaches

A different route uses rearrangement inequalities by sorting $x_i$ and analyzing monotonicity of the matrix $|x_i\pm x_j|$, but it becomes technically involved due to the concavity of the square root.

Another approach uses probabilistic interpretation: representing $\sqrt{t}$ as an expectation of a hitting time of Brownian motion and interpreting both sides as expected occupation energies. This yields the same kernel comparison but through stochastic ordering rather than Fourier analysis.