¿Cuál es el mínimo de esta cantidad en $S^{n-2}\times S^{n-2}$ ?

Question

Mi pregunta es encontrar el mínimo de la siguiente expresión: $$A(x,y) = \sum_{1\leq i<j\leq n} |x_i-x_j|\ |y_i-y_j|,$$ sobre el conjunto de pares de vectores reales $x=(x_1,\dots,x_n),y=(y_1,\dots,y_n)$ con las siguientes condiciones: $$\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.$$

Parece que $1$ es menor o igual que el mínimo, pero no tienen una prueba.

Answer 1

La investigación experimental sugiere que el mínimo es $n/(n-1)$ , que se alcanza cuando \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 2

Utilizando la respuesta de Noam Elkies, podemos wlog asumir que las entradas de $x$ son:

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

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

y de la misma manera que las entradas de $y$ son:

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

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

donde wlog $1 \leq k, l \leq \frac{n}{2}$ (si no, toma complementos).

Denotaremos los conjuntos de coordenadas negativas de $x$ y $y$ respectivamente, por $K$ y $L$ (así $|K| = k$ y $|L| = l$ ). Que sus complementos sean $K'$ y $L'$ .

Ahora, un par de índices $i, j$ contribuye con un término no nulo al objetivo si y sólo si exactamente uno de $i, j$ está en $K$ y exactamente uno de $i, j$ está en $L$ .

El número total de estos pares (que podemos ver como aristas en la intersección de dos grafos bipartitos completos) viene dado por:

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

Si dejamos que $m := | K \cap L |$ esto es justo:

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

Se trata de una función cuadrática de $m$ con minimizador $\frac{1}{4}(2k + 2l - n)$ .

---

Caso 1: Si $2k + 2l \leq n$ se minimiza en la frontera cuando $m = 0$ . Podemos tomar $K$ y $L$ para ser disjuntos y todo es mucho más sencillo. El número de términos no nulos es $kl$ y el tamaño de cada término es:

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

por lo que el valor total de la función objetivo es:

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

Ahora es sencillo ver que queremos $l$ y $k$ para ser lo más pequeño posible, es decir $1$ dando la solución de Strickland como el único óptimo.

---

Caso 2: Si $n < 2k + 2l$ entonces el óptimo $m = \lfloor \frac{1}{4}(2k + 2l - n) \rfloor$ es todavía pequeño, ya que tenemos $m \leq \frac{k}{2}$ y $m \leq \frac{l}{2}$ . Esto implica que el número de pares no nulos sigue siendo al menos $\frac{1}{4} k l$ Así que si $kl \geq 4$ entonces nos va peor que la solución de Strickland en el caso 1.

En el subcaso restante, en el que $kl < 4$ y $n < 2k + 2l$ necesariamente tenemos $n \leq 7$ . Pero todos estos pequeños casos han sido comprobados por la OP, por lo que el resultado se mantiene en general.

Answer 3

El límite inferior $1$ fácilmente se podría obtener. En efecto, para cada dos vectores de suma cero $x,y \in \mathbb{R}^n$ tenemos

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