What is the minimum of this quantity on $S^{n-2}\times S^{n-2}$?

Question

My question is to find the minimum of the following expression: $$A(x,y) = \sum_{1\leq i<j\leq n} |x_i-x_j|\ |y_i-y_j|,$$ over the set of pairs of real vectors $x=(x_1,\dots,x_n),y=(y_1,\dots,y_n)$ subject to the following conditions: $$\sum_{i=1}^n x_i^2 =\sum_{i=1}^n y_i^2 = 1, \sum_{i=1}^n x_i=\sum_{i=1}^n y_i=0.$$

It seems that $1$ is less or equal to the minimum, but don't have a proof.

Answer 1

The minimum must occur at vectors $x,y$ where $x_i$ and $y_i$ take only two values each. This should make it easy to check Neil Strickland's experimental result (where $x$ and $y$ are indeed of this form). [EDIT: see the answer by Adam P. Goucher for this check.]

It is convenient to extend $A$ homogeneously to all nonzero $x,y$ in the zero-sum hyperplane: $$ A(x,y) = \frac1{\| x \| \, \|y\|} \sum_{1\leq i<j\leq n} |x_i-x_j|\ |y_i-y_j| $$ where $\|x\| = (x_1^2 + \cdots + x_n^2)^{1/2}$ and likewise $\|y\|$. So we seek the largest $a$ such that $$ (1)\qquad\qquad\qquad \sum_{1\leq i<j\leq n} |x_i-x_j|\ |y_i-y_j| \geq a \, \|x\| \, \|y\| \qquad\qquad\qquad\phantom{(1)} $$ for all $x,y$ such that $\sum_{i=1}^n x_i = \sum_{i=1}^n y_i = 0$.

Fix one of the $n!^2$ possible orders of the coordinates of $x$ and $y$. Such a choice limits each of $x$ and $y$ to a cone. For the order $x_1 \geq x_2 \geq \ldots \geq x_n$, the cone's extreme rays are generated by $(1,\ldots,1,1-n)$, $(2,\ldots,2,2-n,2-n)$, etc., all with $x_i$ or $y_j$ taking only two values each. In general we have the image of these generators under some coordinate permutation, so still with $x_i$ or $y_j$ taking only two values each.

Given that choice of order, $\sum_{1\leq i<j\leq n} |x_i-x_j| |y_i-y_j|$ is a bilinear form in $x,y$ because the signs of $x_i-x_j$ and $y_i-y_j$ are constant. The claim then follows by a convexity argument (so ultimately by the triangle inequality). Indeed if we fix $x$, and (1) holds for $(x,y)$ and $(x,y')$ for some $y,y'$ in the same cone, then it also holds for $(x, ty+(1-t)y')$ for all $t \in [0,1]$. So it is enough to check (1) for $y$ on an extreme ray of the cone. Likewise we can fix $y$ and reduce to the case where $x$ is on an extreme ray. QED

Answer 2

Experimental investigation suggests that the minimum is $n/(n-1)$, attained when \begin{align*} x &= (1-n,1,1,\dotsc,1)/\sqrt{n^2-n} \\ y &= (1,1-n,1,\dotsc,1)/\sqrt{n^2-n} \\ \end{align*}

Answer 3

Using Noam Elkies' answer, we can wlog assume that the entries of $x$ are:

$$ k \textrm{ copies of } \dfrac{k - n}{\sqrt{kn(n-k)}} $$

$$ n - k \textrm{ copies of } \dfrac{k}{\sqrt{kn(n-k)}} $$

and similarly that the entries of $y$ are:

$$ l \textrm{ copies of } \dfrac{l - n}{\sqrt{ln(n-l)}} $$

$$ n - l \textrm{ copies of } \dfrac{l}{\sqrt{ln(n-l)}} $$

where wlog $1 \leq k, l \leq \frac{n}{2}$ (otherwise take complements).

We shall denote the sets of negative coordinates of $x$ and $y$, respectively, by $K$ and $L$ (so $|K| = k$ and $|L| = l$). Let their complements be $K'$ and $L'$.

Now, a pair of indices $i, j$ contributes a nonzero term to the objective if and only if exactly one of $i, j$ is in $K$, and exactly one of $i, j$ is in $L$.

The total number of such pairs (which we can view as edges in the intersection of two complete bipartite graphs) is given by:

$$ | K \cap L | | K' \cap L' | + | K \cap L' | | K' \cap L | $$

If we let $m := | K \cap L |$, this is just:

$$ m (n + m - k - l) + (k - m)(l - m) $$

This is a quadratic function of $m$ with minimiser $\frac{1}{4}(2k + 2l - n)$.

---

Case 1: If $2k + 2l \leq n$, this is minimised on the boundary when $m = 0$. We can take $K$ and $L$ to be disjoint and everything is much simpler. The number of nonzero terms is $kl$, and the size of each term is:

$$ \dfrac{n^2}{\sqrt{lkn^2(n-l)(n-k)}} $$

so the total value of the objective function is:

$$ n \sqrt{\dfrac{kl}{(n - l)(n - k)}} $$

It is now straightforward to see that we want $l$ and $k$ to be as small as possible, namely $1$, giving Strickland's solution as the unique optimum.

---

Case 2: If $n < 2k + 2l$, then the optimum $m = \lfloor \frac{1}{4}(2k + 2l - n) \rfloor$ is still small, in that we have $m \leq \frac{k}{2}$ and $m \leq \frac{l}{2}$. This implies that the number of nonzero pairs is still at least $\frac{1}{4} k l$, so if $kl \geq 4$ then we do worse than Strickland's solution in Case 1.

In the remaining subcase where $kl < 4$ and $n < 2k + 2l$, we necessarily have $n \leq 7$. But all of these small cases have been checked by the OP, so the result holds in general.

Answer 4

The lower bound $1$ easily could be obtain. Indeed, for every two zero-sum vectors $x,y \in \mathbb{R}^n$, we have

$$ \begin{eqnarray} \left(\sum_{i\leq j} |x_i-x_j||y_i - y_j|\right)^2 & \geq & \frac 12\sum_{i,j}|x_i -x_j|^2|y_i -y_j|^2 \\ & = & \frac 12\sum_{i,j} (x_i^2 -2x_i x_j+x_j^2)(y_i^2-2y_i y_j+y_j^2)\\ & = & n \sum_i (x_i y_i)^2 +2 \Big(\sum_i x_i y_i\Big)^2 + \sum_i x_i^2\sum _i y_i^2 \\ & \geq & \|x\|^2 \|y\|^2 \end{eqnarray} $$