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

My question is to find the minimum of the following expression: $$A(x,y) = \sum_{1\leq i 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.

• Try lagrange multipliers? Doesn't look too hard – AlexArvanitakis Oct 7 '18 at 13:59
• @AlexArvanitakis the objective is not differentiable, so you cannot immediately use Lagrange multipliers. You will need to mix in some combinatorial considerations about the order of the variables. – Neil Strickland Oct 7 '18 at 14:46
• ah misread the bars – AlexArvanitakis Oct 7 '18 at 22:04
• What is the motivation? – Alexander Chervov Oct 9 '18 at 18:03
• @AlexanderChervov It's a consequence of a conjecture on the eigenvalues of the Laplacian operators on graphs. I know that this is true for all $n$ less than 10. – Mostafa Oct 9 '18 at 18:30

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 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 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 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

• I like the homogenization idea, as well as the idea of fixing an order of the coordinates. However, it is unclear to me how and why "[s]uch a choice limits each of $x$ and $y$ to a cone whose extreme rays are generated by $(1,\ldots,1,1-n)$, $(2,\ldots,2,2-n,2-n)$, etc."; for any choice of "one of the $n!^2$ possible orders of the coordinates of $x$ and $y$"? In particular, the vectors $(1,\ldots,1,1-n)$, $(2,\ldots,2,2-n,2-n)$, etc. are compatible only with some of the $n!^2$ possible orders. Can you provide details on this? – Iosif Pinelis Oct 10 '18 at 15:53
• Sorry, I meant the image of those vectors $(1,\ldots,1,1-n)$ etc. under the appropriate permutation. If $x_1 \geq x_2 \geq \ldots \geq x_n$ then the map taking $x$ to $(x_1-x_2,x_2-x_3,\ldots,x_{n-1}-x_n)$ identifies the this cone with the closed positive orthant, and those extreme rays with the coordinate axes. – Noam D. Elkies Oct 10 '18 at 16:10
• Very nice, thank you for this detail! – Iosif Pinelis Oct 10 '18 at 16:16
• Thanks / you're welcome. I've now incorporated some of the explanation into my answer. – Noam D. Elkies Oct 10 '18 at 17:34
• Thanks Noam, I learnt so much from your answer! – Mostafa Oct 11 '18 at 20:33

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*}

• It seems that this number is actually the minimum, but I'm interested more in a verification of a good lower bound. – Mostafa Oct 9 '18 at 16:52

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.

• Thanks for this nice and detailed computations! – Mostafa Oct 11 '18 at 20:29

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}$$