Minimum of $\sum_{i=1}^n \frac{1}{\prod_{j\ne i} |x_j - x_i|}$ for $x_1,...,x_n \in \mathbb [-1, 1]$

Question

Let's consider $x_1,\cdots,x_n \in \mathbb [-1, 1]$. I want to find minimum value of:

$$\frac{1}{|x_1-x_2|\cdots|x_1 - x_{n}|} + \frac{1}{|x_2-x_1||x_2-x_3|\cdots|x_2 - x_n|}+\cdots+\frac{1}{|x_n-x_1|\cdots|x_n-x_{n - 1}|}$$

i.e. in each denominator we have a product of $n-1$ differences, where we omit the difference with the same indices i.e. $x_j - x_j$.

My work so far

Without lose of generality we can say, that $x_1>x_2>...>x_n$, and therefore:

$$\frac{1}{(x_1-x_2)\cdots(x_1-x_n)} + \frac{1}{(x_1-x_2)(x_2-x_3)\cdots(x_2 - x_n)} + \frac{1}{(x_1 - x_n)\cdots(x_{n-1}-x_n)} =:K$$

What can be noticed, is that we obtain pretty bound, when applying AM-GM inequality:

$$K \ge n \frac{1}{\sqrt{(x_1-x_2)^2(x_1 - x_3)^2\cdots(x_n-x_{n-1})^2}} $$

And now we can use fact that, since $x_1,\cdots,x_n \in [-1, 1]$, then, for $i \neq j, x_i > x_j$:

$$|x_i - x_j| \le 2 \Rightarrow \frac{1}{(x_i-x_j)^2} \ge \frac 1 4 \Rightarrow \frac{1}{\sqrt{(x_i - x_j)^2}} \ge \frac 1 2$$

The number of terms under the root equals $\frac{(n - 1) \cdot n}{2}$, because in each difference we have $(n - 1)$ expressions, and we have $n$ sums. Also each square will be present only once. So finally, we obtain the bound:

$$K\ge n \cdot \frac{1}{2^{\frac{n(n-1)}{2}}}$$

And unfortunately, this bound is too weak to be a lower bound for each $n$. For example here The smallest value of sum of reversed absolute values we can find, that the minimum for this problem, for $n = 3$, equals $2$, and my bound suggests $\frac{3}{8}$. Do you know how my solution can be repaired to be accurate for all $n \in \mathbb N$?

Answer 1

The minimum value for $n \ge 2$ distinct numbers in $[-1, 1]$ is $2^{n-2}$. This can be shown with the help of Lagrange interpolation and Chebyshev polynomials.

In order to simplify the notation a bit, I'll start the indexing with zero. Then we have the following result:

Let $x_0, x_1, \ldots, x_{n}$ be $n+1 \ge 2$ distinct real numbers in the interval $[-1, 1]$. Then $$ \sum_{i=0}^n \frac{1}{\prod\limits_{\substack{j=0 \\ j \ne i}}^n |x_i-x_j|} \ge 2^{n-1} \, . $$ The bound is best possible, equality holds if and only if $$ \{ x_0, \ldots, x_n \} = \{ \cos(i \pi/n) \mid 0 \le i \le n \} \, .$$

Proof: Without loss of generality we can assume that the $x_i$ are in decreasing order. We are looking for the minimal possible value of $$ K = \sum_{i=0}^n \frac{1}{\prod\limits_{\substack{j=0 \\ j \ne i}}^n |x_i-x_j|} = \sum_{i=0}^n \frac{(-1)^i}{\prod\limits_{\substack{j=0 \\ j \ne i}}^n (x_i-x_j)} \, . $$ Let $P$ be the (unique) interpolation polynomial of degree $n$ satisfying $P(x_i) = (-1)^i$ for $0 \le i \le n$, that is $$ P(x) = \sum_{i=0}^n \prod\limits_{\substack{j=0 \\ j \ne i}}^n \frac{x-x_j}{x_i - x_j} (-1)^i \, . $$ Note that $K$ is the leading coefficient of that polynomial: $P(x) = K x^n + \cdots$.

Now we consider the function $f(x) = P(x) - T_n(x)$, where $T_n$ is the $n$-th degree Chebyshev polynomial of the first kind. It is known that $$ T_n(x) = 2^{n-1}x^n + \ldots $$ and that $|T_n(x)| \le 1$ for $-1 \le x \le 1$. Then $$ \tag{$*$} f(x_i) = \begin{cases} 1 - T_n(x_i) \ge 0 & \text{ for even $i$} \, , \\ -1 - T_n(x_i) \le 0 & \text{ for odd $i$} \, .\\ \end{cases} $$ Using the mean-value theorem we see that there are $n$ points $y_i \in (x_{i+1}, x_i)$, $0 \le i \le n-1$, such that $f'(y_i) \ge 0$ for even $i$, and $f'(y_i) \le 0$ for odd $i$.

Using the mean-value theorem again we see that there are $n-1$ points $z_i \in (y_{i+1}, y_i)$, $0 \le i \le n-2$, such that $f''(z_i) \ge 0$ for even $i$, and $f''(z_i) \le 0$ for odd $i$.

Repeating this argument, we finally conclude that $f^{(n)}(c) \ge 0$ for some $c \in (-1, 1)$. So $$ 0 \le f^{(n)}(c) = P^{(n)}(c) - T_n^{(n)}(c) = n! (K - 2^{n-1}) $$ and this proves the desired estimate $K \ge 2^{n-1}$.

If strict inequality holds for at least one $i$ in $(*)$ then the same argument shows that $f^{(n)}(c) > 0$ for some $c \in (-1, 1)$, so that $K > 2^{n-1}$. Therefore is $K = 2^{n-1}$ if and only if $T_n(x_i) = (-1)^i$ for all $i$, and that is equivalent to $x_i = \cos(i \pi/n)$ for $0 \le i \le n$.

Answer 2

Some thoughts:

Since the expression is symmetric, WLOG, assume that $x_1 > x_2 > \cdots > x_n$.

Let $$f_i = \prod_{j\ne i} |x_j - x_i|, \, i = 1, 2, \cdots, n.$$ Using AM-GM, we have \begin{align*} \sum_{i=1}^n \frac{1}{f_i} &= \frac{1}{f_1} + \sum_{i=2}^{n-1} \left(\frac{1}{2f_i} + \frac{1}{2f_i}\right) + \frac{1}{f_n}\\ &\ge (2n - 2)\left(2^{2(n - 2)}f_1 f_n \prod_{i=2}^{n-1} f_i^2\right)^{-1/(2n - 2)}. \end{align*}

Conjecture 1: We have $$f_1 f_n \prod_{i=2}^{n-1} f_i^2 \le (n - 1)^{2n - 2}2^{-2n^2 + 6n - 2}$$ with equality if \begin{align*} f_1 &= \frac{n - 1}{2^{n - 3}}, \\ f_i &= \frac{n - 1}{2^{n - 2}}, \quad i = 2, 3, \cdots, n - 1;\\ f_n &= \frac{n - 1}{2^{n - 3}}. \end{align*}

If Conjecture 1 is true, the minimum of $\sum_{i=1}^n \frac{1}{f_i}$ is $2^{n - 2}$.

---

Remarks: I evaluated the minimum for $n=3, 4, \cdots, 9$ which is $2^{n - 2}$, and the minimizer $(x_1, x_2, \cdots, x_n) \in [-1, 1]^n$ (with $x_1 > x_2 > \cdots > x_n$) satisfies the system of equations
\begin{align*} f_1 &= \frac{n - 1}{2^{n - 3}}, \\ f_i &= \frac{n - 1}{2^{n - 2}}, \quad i = 2, 3, \cdots, n - 1;\\ f_n &= \frac{n - 1}{2^{n - 3}}. \end{align*} Also, clearly, $x_1 = 1$ and $x_n = -1$.