4

Let $x_1,\ldots, x_n$ be integers that satisfies $\sum_{i=1}^n x_i = 0$. Also, let $0<L_1<\cdots<L_n$ be given.

Question: Is $\sum_{i<j} (L_j-L_i) x_ix_j \leq 0$?

Motivation: This question is motivated from physics. To show that certain two models are equivalent by "power counting" method, the problem reduces to proving the above inequality.

My trial:

  1. We have $\sum_{i\neq j} x_ix_j = -\frac12 \sum_i x_i^2 \leq 0$. However, the problem is that we have weights $L_j-L_i$, which makes the problem nontrivial.

  2. Letting $u_j = L_{j+1}-L_j$, the above inequality becomes $\sum_{i<j} (u_{i+1}+\cdots u_j) x_ix_j \leq 0$.

  3. $\sum_{i<j} (L_j-L_i) x_ix_j = \frac12 \sum_{i\neq j} |L_j-L_i| x_ix_j$.

Laplacian
  • 2,494

2 Answers2

2

Yes, this is true (and there is no need to assume that the $x_j$ are integers). This is Exmaple 3.5 in Wells, Williams. Embeddings and extensions in analysis. The proof relies on the integral representation $$ |x|=\frac{2}{\pi}\int_0^\infty\frac{\sin^2(xu)}{u^2}\,du. $$ With the trigonometric identity $$ \sin^2((L_j-L_i)u)=\sin^2(L_i u)+\sin^2(L_j u)-2\sin^2(L_i u)\sin^2(L_j u)-\frac 1 2 \sin(2L_i u)\sin(2L_j u) $$ one obtains \begin{align*} \sum_{i,j}\sin^2((L_i-L_j)u)x_i x_j&=2\sum_i\sin^2(L_i u)x_i\sum_j x_j-\left(2\sum_i\sin^2(L_i u)x_i\right)^2-\frac 12\left(\sum_i \sin(2L_i u)x_i\right)^2\\ &=-\left(2\sum_i\sin^2(L_i u)x_i\right)^2-\frac 12\left(\sum_i \sin(2L_i u)x_i\right)^2. \end{align*} Thus \begin{align*} \sum_{i,j}|L_i-L_j|x_ix_j=-\frac 2 \pi\int_0^\infty u^{-2}\left(\left(2\sum_i\sin^2(L_i u)x_i\right)^2+\frac 12\left(\sum_i \sin(2L_i u)x_i\right)^2\right)\,du\leq 0. \end{align*}

Edit: I should add that functions $\Phi\colon E\times E\to\mathbb R$ that are symmetric, vanish on the diagonal and satisfy $$ \sum_{j,k}\Phi(e_j,e_k)x_j x_k\leq 0 $$ whenever $\sum_j x_j=0$ are called conditionally negative definite. They are closely related to the question when a metric space can be isometrically embedded into a Hilbert space: A function $\Phi\colon E\times E\to\mathbb R_+$ is conditionally of negative type if and only if $\Phi^{1/2}$ is a metric and $(E,\Phi^{1/2})$ embeds isometrically into a Hilbert space. This result can be found in the book cited above.

MaoWao
  • 15,139
  • 1
  • 18
  • 36
0

I will do this for one scenario and may be someone else can generalize this. Suppose $n = 5$ and $x_1 < x_2 < x_3 < 0 < x_4 < x_5$ We will compute the sum in three parts. First with the negative x terms only $y_1$, the positive x terms only $y_2$ and then the cross term product $y_3$.

$y_1 = x_1x_2(L_2 - L_1) + x_1x_3(L_3 - L_1) + x_2x_3(L_3-L_2)$

$y_2 = x_4x_5(L_5 - L_4)$

$y_3 = x_1x_4(L_4 - L_1) + x_1x_5(L_5 - L_1) + x_2x_4(L_4 - L_1) + x_2x_5(L_5 - L_1) + x_3x_4(L_4 - L_1) + x_3x_5(L_5 - L_1)$

We will now use the fact for example: $L_3 - L_1 = L_3 - L_2 + L_2 - L_1$

Rewriting, we get

$y_1 = (x_1x_2(L_2 - L_1) + x_1x_3(L_3 - L_2) + x_1x_3(L_2 - L_1)+x_2x_3(L_3-L_2))$

$y_2 = (x_4x_5(L_5 - L_4))$

$y_3 = x_1x_4(L_4 - L_3) + x_1x_4(L_3 - L_2) + x_1x_4(L_2 - L_1) + x_1x_5(L_5 - L_4) + x_1x_5(L_4 - L_3) + x_1x_5(L_3 - L_2) + x_1x_5(L_2- L_1) + x_2x_4(L_4 - L_3) + x_2x_4(L_3 - L_2) + x_2x_4(L_2 - L_1) + x_2x_5(L_5 - L_4) + x_2x_5(L_4 - L_3) + x_2x_5(L_3 - L_2) + x_2x_5(L_2- L_1) + x_3x_4(L_4 - L_3) + x_3x_4(L_3 - L_2) + x_3x_4(L_2 - L_1) + x_3x_5(L_5 - L_4) + x_3x_5(L_4 - L_3) + x_3x_5(L_3 - L_2) + x_3x_5(L_2- L_1)$

Adding $y_1, y_2, y_3$ and grouping by $L_j - L_i$, we get:

$[(L_2-L_1)(x_1x_2 + x_1x_3 + x_1x_4 + x_1x_5 +x_2x_4 + x_2x_5 + x_3x_4 + x_3x_5)] + [(L_3-L_2)(x_1x_3 + x_2x_3 + x_1x_4 + x_1x_5 + x_2x_4 + x_2x_5 + x_3x_5 + x_4x_5] + [(L_4 - L_3)(x_1x_4 + x_1x_5 + x_2x_4 + x_2x_5 + x_3x_4 + x_3x_5] + [(L_5 - L_4)(x_4x_5 + x_1x_5 + x_2x_5 + x_3x_5)]$

$ = [(L_2-L_1)(x_1(x_2 + x_3 + x_4 + x_5) + (x_2 + x_3)(x_4 + x_5)] + [(L_3 - L_2)(x_1x_2 + x_2x_3 + (x_1+x_2+x_3)(x_4+x_5))]+ [(L_4-L_3)((x_1+x_2+x_3)(x_4+x_5))]+ [(L_5-L_4)(x_1 + x_2 + x_3 + x_4)x_5]$

$ = [(L_2-L_1)(-x_1^2 -(x_2 + x_3)(x_1+x_2+x_3)] + [(L_3 - L_2)(x_1x_2 + x_2x_3 - (x_1+x_2+x_3)^2)]+ [(L_4-L_3)(-(x_1+x_2+x_3)^2]+ [(L_5-L_4)(-x_5^2)]$

where each term is negative (and we have used $x_4 + x_5 = -(x_1 + x_2 + x_3)$). We could likely extend this logic to $n$ terms.

sku
  • 2,643