(Dis)Prove $\sum_{i=1}^n\sum_{j=1}^n{(|x_{i}-x_{j}|-|y_{i}-y_{j}|)^2}\geq 4$

Question

Let $n\ge 4$ and two vectors $x$ and $y$ in $\mathbb{R}^n$ that satisfy

1. $\sum_{i=1}^{n}{x_{i}^2}=\sum_{i=1}^{n}{y_i}^2=1$
2. $\sum_{i=1}^{n}{x_{i} y_i}=0$
3. $\sum_{i=1}^{n}{x_{i}}=\sum_{i=1}^{n}{y_i}=0$

With these conditions, prove or disprove that $$\sum_{i=1}^n\sum_{j=1}^n{(|x_{i}-x_{j}|-|y_{i}-y_{j}|)^2}\geq 4$$

I have been trying to find counterexamples, but so far couldn't find any.

Edit (2019-06-18):

Indeed I have proved in the meantime the weaker inequality that $\sum_{i=1}^n\sum_{j=1}^n{(|x_{i}-x_{j}|-|y_{i}-y_{j}|)^2}\geq 1$ holds. This works as follows:

One has the equivalent formulation $$4 \leq \sum_{i=1}^n\sum_{j=1}^n{(|x_{i}-x_{j}|-|y_{i}-y_{j}|)^2}\\ = \sum_{i=1}^n\sum_{j=1}^n{(x_{i}-x_{j})^2} + \sum_{i=1}^n\sum_{j=1}^n{(y_{i}-y_{j})^2}- 2 \sum_{i=1}^n\sum_{j=1}^n{|x_{i}-x_{j}||y_{i}-y_{j}|}\\ = 4 n - 4 \sum_{i=1}^n\sum_{j>i}^n{|x_{i}-x_{j}||y_{i}-y_{j}|} $$ so the question is equivalent to asking whether $$ = \sum_{i=1}^n\sum_{j>i}^n{|x_{i}-x_{j}||y_{i}-y_{j}|} \le n - 1 $$ I have proved here that $\sum_{i=1}^n\sum_{j>i}^n{|x_{i}-x_{j}||y_{i}-y_{j}|} \le n - \frac14 $, or equivalently $\sum_{i=1}^n\sum_{j=1}^n{(|x_{i}-x_{j}|-|y_{i}-y_{j}|)^2}\geq 1$, so you might want to improve that.

Answer 1

We use the Gruss's inequality in supposing that :

$$2n \sum_{1\leq i<j\leq n}{|x_{i}-x_{j}||y_{i}-y_{j}|} \\ = n\sum_{1\leq i\leq n}\sum_{1\leq j\leq n}{|x_{i}-x_{j}||y_{i}-y_{j}|}\\\geq \left(\sum_{1\leq i\leq n}\sum_{1\leq j\leq n}{|x_{i}-x_{j}|}\right)\left(\sum_{1\leq i\leq n}\sum_{1\leq j\leq n}{|y_{i}-y_{j}|}\right)$$

Now using the inequality for $0<x_i\leq 1$:

$$\sqrt{n-1+\frac{n}{\sum_{i=1}^{n}x_{i}^{2}}}\sqrt{\sum_{i=1}^{n}x_{i}^{2}}-\left(\sum_{i=1}^{n}x_{i}\right)\geq 0$$

And the proof @Andreas(where he used Cauchy-Schwartz inequality) we have :

$$\left(\sum_{1\leq i\leq n}\sum_{1\leq j\leq n}{|x_{i}-x_{j}|}\right) \leq \sqrt{n-1+\frac{n}{2n}}\sqrt{2n}$$

So we have :

$$ \sum_{1\leq i<j\leq n}{|x_{i}-x_{j}||y_{i}-y_{j}|}\leq \left(\sqrt{n-1+\frac{n}{2n}}\right)^{2}+0.25$$

We can obviously improves it.

Answer 2

This is an answer which is missing one necessity or sufficiency argument (see at the bottom) - please add if you have it!

Motivation:
As we are looking for a minimum of $\sum_{i=1}^n\sum_{j=1}^n{(|x_{i}-x_{j}|-|y_{i}-y_{j}|)^2}$, the aim could be to actually make the sum zero which would demand all terms to be zero. We have that $|x_{i}-x_{j}|=|y_{i}-y_{j}|$ for all $\{i,j\}$, if, for all $\{i\}$, holds: $y_i = x_i + d$ with some fixed distance $d$. Likewise, the condition $y_i = - x_i + d$ could be chosen.
Trying to match the conditions, we see that this attempt fails: We need to ensure $0 = \sum_{i=1}^{n}{y_{i}}=\sum_{i=1}^{n}{(d + x_i)}= n d + \sum_{i=1}^{n}{x_i} = nd$ which gives $d=0$ and hence $x_i = y_i$. Further, we need $ 0 = \sum_{i=1}^{n}{x_{i} y_i}=\sum_{i=1}^{n}{x_{i}^2}$ but the latter is $1$ so we have a contradiction and our aim fails.
However, this motivation may still work, if modified. As observations from @Hans Engler (see comments) show, at the minimum, all but one points $(x_i, y_i)$ lie on a straight line. So let's take this as the only condition in the following.

Answer:
As laid out above in the motivation, let us suppose that, at the minimum, for all $\{i = 1 \cdots n-1\}$ holds: $y_i = x_i + d$ with some fixed distance $d$. This is actually all that is being supposed.
Define a mean $m$ of the first $(n-1)$ values $x_i$, i.e. $\sum_{i=1}^{n-1}x_i = (n-1)m$. Then the condition $0 = \sum_{i=1}^{n}x_i$ gives $x_n = -(n-1)m$. Likewise, the condition $0 = \sum_{i=1}^{n}y_i = \sum_{i=1}^{n-1}(x_i + d) + y_n= (n-1)(m+d) + y_n$ gives $y_n = -(n-1)(m+d)$.
We now consider the conditions $\sum_{i=1}^{n}{x_{i}^2}=\sum_{i=1}^{n}{y_i}^2=1$. We evaluate $$ 1 = \sum_{i=1}^{n}{y_i}^2 = \sum_{i=1}^{n-1}(x_i + d)^2 + y_n^2\\ = (n-1)d^2 + 2 d (n-1)m + \sum_{i=1}^{n-1}{x_i}^2 + y_n^2 \\ = (n-1)d^2 + 2 d (n-1)m + 1 - x_n^2 + y_n^2 \\ = 1 - n(n-1)d(d+2m) $$ which entails $d = -2m$ and hence $y_n = (n-1)m = -x_n$.
The last condition is $$ 0 = \sum_{i=1}^{n}{x_{i}y_i}=\sum_{i=1}^{n-1}(x_i + d)x_i + x_n y_n\\ = 1 - x_n^2 + d(n-1)m + x_n y_n = 1 - (n-1)^2 m^2 - 2(n-1)m^2 - (n-1)^2 m^2 \\ = 1 - 2 n(n-1)m^2 $$ which gives $m = \sqrt{\frac{1}{2 n (n-1)}}$ (or the negative). So all conditions can be satisfied with the given choices of $d$ and $m$.

Let us now compute the target sum $S = \sum_{i=1}^n\sum_{j=1}^n{(|x_{i}-x_{j}|-|y_{i}-y_{j}|)^2}$. With our supposed condition we have, at the minimum, $S_{min} = 2 \sum_{i=1}^{n-1}{(|x_{i}-x_{n}|-|x_{i}+d-y_{n}|)^2} = 2 \sum_{i=1}^{n-1}{(|x_{i} - m +nm|-|x_{i}- m - nm|)^2} \; . $ Now observe the variance sum $\sum_{i=1}^{n-1} (x_i - m)^2 = 1 - x_n^2 - (n-1)m^2 = 1 - n(n-1)m^2 = \frac12 \; .$ From this, we have $|x_i - m| \le \frac{1}{\sqrt{2}} = \sqrt{n(n-1)} m < nm $ which allows to compute, using again the variance sum,

$$ S_{min} = 2 \sum_{i=1}^{n-1}(|x_{i} - m +nm|-|x_{i}- m - nm|)^2 \\ = 2 \sum_{i=1}^{n-1}{(x_{i} - m +nm - (nm + m - x_i))^2}\\ = 2 \sum_{i=1}^{n-1}{(2 x_i- 2 m)^2} = 8 \sum_{i=1}^{n-1}{(x_i-m)^2} = 8 \cdot \frac 12 = 4$$ This establishes the claim.

Remaining work
It remains to be shown that the only supposition used, namely that, at the minimum, for all $\{i = 1 \cdots n-1\}$ holds: $y_i = x_i + d$ with some fixed distance $d$, is indeed a necessary or sufficient condition for the minimum. As said in the beginning - please add arguments if you have them!