16
$\begingroup$

Let $x_{i}$, where $i\in\{1,2,\cdots,n\}$ be distinct real numbers. Find the minimum of the value of $$\sum_{1\le i<j\le n}\left(\dfrac{1-x_{i}x_{j}}{x_{i}-x_{j}}\right)^2$$

It is clear when $n=2$ minimum of the value is $0$, when $x_{1}x_{2}=1$. But for $n\ge 3$,I can't find it.

Thanks.

$\endgroup$
  • 4
    $\begingroup$ I'm not sure how useful this is but the summand does resemble the addition/difference formula for the hyperbolic tangent: $\tanh(a-b) = \frac{\tanh (a) - \tanh (b)}{1 - \tanh(a) \tanh(b)}$. The issue for applying this directly is that it'd restrict the $x_i$ to $[-1, 1]$. Alternatively, if you let $x_i = \tan \alpha_i$, the summand becomes $\left(\frac{\cos(x_i + x_j)}{\sin(x_i - x_j)}\right)^2$. $\endgroup$ – Sirzh Jul 5 '17 at 18:05
  • $\begingroup$ What do you mean by "find minimum of the value"? If you choose a $n$, you will get one single answer right? $\endgroup$ – Agile_Eagle Jul 9 '17 at 8:57
4
$\begingroup$

This is not a full solution, but an upper bound to the minimum for given $n$ is given by: $$ M_n = \text{Minimum}(n) \leq \left\{ \begin{array}{ll} \frac{1}{2} n(n-2) & \text{for $n$ even} \\ \frac{1}{2} (n-1)^2 & \text{for $n$ odd} \end{array} \right. $$ I will first show that for a particular set of numbers $\{x_i\}$ these values would be an under limit to the sum and then give an example of such a set. I also will assume that all values are strictly positive $x_i > 0$.

As a short-hand notation let for $x \neq y$ the function $f(x,y)$ be given by $$ f(x,y) = \left( \frac{1 - x y}{x-y} \right)^2 $$ Then it follows that for $x \neq \frac{1}{y}$ $$ f(x,\frac{1}{y}) = \left( \frac{1 - \frac{x}{y}}{x-\frac{1}{y}} \right)^2 = \left( \frac{y -x}{x y-1} \right)^2 = \frac{1}{f(x,y)} $$ and hence we also have $f(x,y)=f(\frac{1}{x},\frac{1}{y})$ and $f(x,\frac{1}{y})=f(\frac{1}{x},y)$. Furthermore we have both $f(x,\frac{1}{x}) = 0$ and $f(x,1)=1$ for $x \neq 1$ as well as the inequality $f(x,y)+f(x,\frac{1}{y}) \geq 2$.

To combine the even an odd cases of $n$, I will set $n = 2 k + \sigma$, with $k \geq 1$ and $\sigma \in \{0,1\}$.

Now consider a set $\{x_i\}$ that satisfies $$ \begin{array}{ll} 1 <x_1 < x_2 < \dots < x_k \\ x_{k+i} = \frac{1}{x_i} & \text{for $1 \leq i \leq k$}\\ x_n = 1 & \text{if $n$ is odd} \end{array} $$ Then we find for the sum $$ \sum_{1\leq i<j\leq n} \left( \frac{1 - x_i x_j}{x_i-x_j} \right)^2 = \sum_{1\leq i<j\leq k} \left[ f(x_i,x_j) + f(x_i,x_{k+j}) + f(x_{k+i},x_j) + f(x_{k+i},x_{k+j})\right] \\ + \sum_{1\leq i \leq k} f(x_i,x_{k+i}) + \sigma \sum_{1 \leq i \leq n} f(x_i,1) \\ = 2 \sum_{1\leq i<j\leq k} \left[ f(x_i,x_j) + f(x_i,\frac{1}{x_j}) \right] + \sum_{1\leq i \leq k} f(x_i,\frac{1}{x_i}) + \sigma n \\ \geq 4 \binom{k}{2} + \sigma n = 2 k (k-1+\sigma) $$ which are the limits mentioned above.

As an example for such a set consider $x_i=1 + \delta^i$ for $1 \leq i \leq k$. Then all elements are distinct, in particular for $0<\delta \ll 1$.

The only contribution to the sum that we have to consider is: $$ f(x_i,x_j) + f(x_i,\frac{1}{x_j}) = 2 + {\cal O}(\delta^2) > 2 $$ and hence we can get arbitrary close to the limit obtained.

Equality only holds when these terms do not exist, which is in the case $n=2$ and $n=3$, whereas for $n>4$ this type of set can not reach the lower limit.

It might be possible that other sets of $\{x_i\}$ provide lower values for the sum, but a numerical minimisation of the sum for various $n$ did not give me any.

We can also give a lower bound for $M_n$. If we consider the same $$ S_n(\{x_i\}) = \sum_{1 \leq i<j \leq n} \left( \frac{1 - x_i x_j}{x_i-x_j} \right)^2 \geq M_n $$ we can also write this as a some over partitions of the $n$ values, in particular partitions of $n-1$ elements. $$ S_n(\{x_i\}) = \frac{1}{n-2} \sum_{k=1}^n S_{n-1}(\{x_i\}_{i\neq k}) $$ The factor $\frac{1}{n-2}$ is from over counting and follows directly from realising that each pair $(x_i,x_j)$ appears $n-2$ times in the various sums. From this it immediately follows that $$ M_n \geq \frac{n}{n-2} M_{n-1} $$ Since we already know $M_2=0$ and from Michaels result that $M_3=2$, we can by repeatedly applying this lower bound obtain $$ M_n \geq \frac{n(n-1)}{6} M_3 = \frac{n(n-1)}{3} ~~~~ \forall n \geq 4 $$ This gives $M_4 \geq 4$ and with the constructed solution above we find $$ S_4(\{x_i\}) - 4 < \delta ~~~ \forall \delta >0 $$ In all other cases $n\geq 5$ the upper and lower bound are separated.

Not a full proof, but perhaps somebody else can use this result to continue.

$\endgroup$
  • $\begingroup$ Very nice! ${}{}$ $\endgroup$ – Jyrki Lahtonen Jul 18 '17 at 20:52
  • $\begingroup$ @Ronald Blaak It remains to prove our inequality for your estimations. I think it's a hardest point! During this proof we can get that the minimal value it's something another. See please my proof for $n=3$. It's a full proof. $\endgroup$ – Michael Rozenberg Jul 21 '17 at 6:57
2
$\begingroup$

We begin with a short proof for the case $n=3$ :

We make a substitution so we put :

$\frac{\lambda_1}{2}(\frac{1+(a-b)^2}{a-b})^2=(\frac{1-xy}{x-y})^2$

$\frac{\lambda_2}{2}(\frac{1+(b-c)^2}{c-b})^2=(\frac{1-zy}{z-y})^2$

$\frac{\lambda_3}{2}(\frac{1+(a-c)^2}{a-c})^2=(\frac{1-xz}{x-z})^2$

With $a,b,c$ and the condition $a\geq b \geq c$ real numbers and $\lambda_1,\lambda_2,\lambda_3$ real positive numbers with the condition $\lambda_1+\lambda_2+\lambda_3=1$

So we have to find the minimum value of :

$$\frac{\lambda_1}{2}(\frac{1+(a-b)^2}{a-b})^2+\frac{\lambda_2}{2}(\frac{1+(b-c)^2}{c-b})^2+\frac{\lambda_3}{2}(\frac{1+(a-c)^2}{a-c})^2$$

We could apply Jensen's inequality for $f(x)=\frac{1}{2}(\frac{1+x^2}{x})^2$ it becomes :

$$\frac{1}{2}[\lambda_1(\frac{1+(a-b)^2}{a-b})^2+\lambda_2(\frac{1+(b-c)^2}{c-b})^2+\lambda_3(\frac{1+(a-c)^2}{a-c})^2]\geq \frac{1}{2}[(\frac{1+(\lambda_1(a-b)+\lambda_2(b-c)+\lambda_3(a-c))^2}{((\lambda_1(a-b)+\lambda_2(b-c)+\lambda_3(a-c))})^2]$$

But $\lambda_1(a-b)+\lambda_2(b-c)+\lambda_3(a-c)>0$

So the minimum of the function $f(x)$ is 2 .

$\endgroup$
  • $\begingroup$ I think your solution is total wrong. Because1. Why these values $a$, $b$, $c$, $\lambda_1$, $\lambda_2$ and $\lambda_3$ are exist? 2. We can not use the Jensen's inequality here because $f$ is not convex function. $\endgroup$ – Michael Rozenberg Jul 21 '17 at 4:32
1
$\begingroup$

I have found the following nice proof for $n=3$.

I believe that it will help in the general case.

Indeed, let $x_1=a$, $x_2=b$ and $x_3=c$.

Hence, $$\sum_{cyc}\left(\frac{1-ab}{a-b}\cdot\frac{1-bc}{b-c}\right)=\frac{\sum\limits_{cyc}(1-ab)(1-bc)(c-a)}{\prod\limits_{cyc}(a-b)}=$$ $$=\frac{\sum\limits_{cyc}(a^2b-a^2c)}{\prod\limits_{cyc}(a-b)}=-1.$$ Id est, $$\sum_{cyc}\frac{(1-ab)^2}{(a-b)^2}=\left(\sum_{cyc}\frac{1-ab}{a-b}\right)^2-2\sum_{cyc}\left(\frac{1-ab}{a-b}\cdot\frac{1-bc}{b-c}\right)=$$ $$=\left(\sum_{cyc}\frac{1-ab}{a-b}\right)^2+2\geq2.$$

$\endgroup$
  • $\begingroup$ That's identical to the answer you posted 2 weeks ago. Why delete that one and post it as a new one? $\endgroup$ – Martin R Jul 15 '17 at 18:43
  • $\begingroup$ @Martin I think the worth of my solution for $n=3$ is 50 points at least, but in the previous period I got nothing. It's not fair! $\endgroup$ – Michael Rozenberg Jul 15 '17 at 19:01
  • 1
    $\begingroup$ Deleting the other answer with its text defaced may amount to vandalism. I may be mistaken but I think the old posts are still eligible for bounty. For the automatic bounty, IIRC, they compete with the weight of votes earned after the bounty period started. I may be wrong though. Anyway, if I were inclined to vote here I would find antics like this off-putting. $\endgroup$ – Jyrki Lahtonen Jul 16 '17 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.