Given $n+1$ points, bound the product of the distances from one of them

Question

We have $n+1$ real numbers $x_1,\cdots,x_{n+1}$ such that $-1\leq x_i\leq 1$ for all $1\leq i\leq n+1$.

I am wondering whether the following fact is true:

There exists some $j$ such that $\prod_{\substack{i=1\\i\neq j}}^{n+1}\left |x_j-x_i\right |\leq \frac{n+1}{2^{n-1}}$.

Some base steps are easy. Assume that this holds for $n-1$.

Applying this inductive hypothesis to $\left\{x_i:i\in\mathbb{N}_{\leq n+1}\right\}\setminus\left\{x_j\right\}$ for each $j\in\mathbb{N}_{\leq n+1}$, we conclude that for each $j\in\mathbb{N}_{\leq n+1}$ there exists $h\left(j\right)\in\mathbb{N}_{\leq n+1}\setminus\left\{j\right\}$ such that $\prod_{\substack{i=1\\i\neq j\\i\neq h\left(j\right)}}^{n+1}\left |x_{h\left(j\right)}-x_i\right |\leq\frac{n}{2^{n-2}}$.

Now, if for some $j\in\mathbb{N}_{\leq n+1}$ we have $\left |x_{h\left(j\right)}-x_j\right |\leq \frac{1}{2}$, then $\prod_{\substack{i=1\\i\neq h\left(j\right)}}^{n+1}\left |x_{h\left(j\right)}-x_i\right |\leq \frac{1}{2}\cdot\frac{n}{2^{n-2}}\leq \frac{1+\frac{1}{n}}{2}\frac{n}{2^{n-2}}=\frac{n+1}{2^{n-1}}$, which gives what we want. But what about the case in which $\left |x_{h\left(j\right)}-x_j\right |>\frac{1}{2}$ for all $j\in\mathbb{N}_{\leq n+1}$?

Is there any other way?

Answer 1

Yes, it is true. Consider the polynomial $p(x)=\prod_{i=1}^{n+1}(x-x_i)$ and the monic Chebyshev polynomial $T_n(x)=x^n+\dots$ of degree $n$, so $|T_n|\le 2^{-(n-1)}$ on $[-1,1]$. Now apply the residue theorem to the integral of the rational function $Q(z)=\frac{T_n(z)}{p(z)}$ in a huge disk centered at $0$. On the one hand $$ \oint_{|z|=R}Q(z)\,dz\approx \oint_{|z|=R}\frac{dz}{z}=2\pi i $$ as $R\to\infty$ because $Q(z)=\frac 1z+O(|z|^{-2})$ as $z\to\infty$.

On the other hand, it is $$2\pi i\sum_j{\rm Res}_{x_j}Q=2\pi i\sum_j\frac{T_n(x_j)}{p'(x_j)}\,.$$ Since $|T_n(x_j)|\le 2^{-(n-1)}$, we conclude that $$\sum_j\frac{1}{|p'(x_j)|}\ge 2^{n-1}\,,$$ so there must exist $j$ with $|p'(x_j)|\le \frac{n+1}{2^{n-1}}$. But $|p'(x_j)|$ are exactly the products you are interested in.

Answer 2

The following should allow to conclude, although the end is sketchy.

Since we are considering "relative positions"/differences $|x_j-x_i|$ the "origin" has in fact no importance and we can multiply the inequality by $2^n$ $$ 2^n \prod_{\genfrac{}{}{0pt}{}{1\leq i\leq n+1 }{i\neq j}} |x_i-x_j| \leq 2(n+1)$$ "Shifting" everything by $+1$ and "absorbing" this $2^n$ factor, the problem is equivalent to having $(n+1)$ points $$\left\lbrace x_i \in [0, 4],\ i=1, \cdots, n+1\right\rbrace \qquad \Big(4= \big(1-(-1)\big)\times 2 \Big)$$

Now because $\mathbb{R}$ is totally ordered, one can assume that $x_i \leq x_j$ when $i\leq j$ (relabelling if necessary) and the data of these points is thus equivalent to that of $x_1$ together with $n$ "increments": $u_i:= x_{i+1}-x_i$.

Remark: Yet another equivalent data is that of $x_1$ and $v_i:= x_i - x_1,\ i> 1$ and the maximum of the products $\displaystyle \left\lbrace\prod_{\genfrac{}{}{0pt}{}{1\leq i\leq n+1 }{i\neq j}} |x_i-x_j|,\ j=1,\cdots , n+1 \right\rbrace $ (I didn't look for a formal proof but a drawing gives the idea) is reached (once we have totally ordered the $(x_i)_{1\leq i\leq n+1}$) for $x_j$ on the boundary, i.e. either $x_1$ or $x_{n+1}$. For $j=1$ it has value $\prod_{i=2}^n v_i$.

Instead of looking for a minimum, let us in fact make the product of all $\displaystyle \prod_{j=1}^{n+1}\prod_{\genfrac{}{}{0pt}{}{1\leq i\leq n+1 }{i\neq j}} |x_i-x_j|$ and compare it to $2^{n+1} (n+1)^{n+1}$, noticing that the factor $|x_i-x_j|$ appears only twice for each pair $(i,j),\ i\neq j$ (${n+1 \choose 2}$ possibilities.). The set of possible values for $|x_i-x_j|$ is $\left\lbrace \sum_{k=i}^{j-1} u_k,\ 1\leq i< j\leq n\right\rbrace$. Hence $$\prod_{j=1}^{n+1}\prod_{\genfrac{}{}{0pt}{}{1\leq i\leq n+1 }{i\neq j}} |x_i-x_j| = \prod_{i\neq j} |x_i-x_j| = \prod_{i< j} |x_i-x_j|^2 = \prod_{i< j} \left(\sum_{k=i}^{j-1} u_k\right)^2 = \left(\prod_{i< j} \left(\sum_{k=i}^{j-1} u_k\right)\right)^2 $$ Let us now regroup the sums by number of summands: $$\prod_{i< j}\left(\sum_{k=i}^{j-1} u_k\right)= \left(\prod_{i=1}^{n} u_i \right) \left(\prod_{i=1}^{n-1} (u_i+u_{i+1}) \right)\times \cdots \times \left(\sum_{i=1}^n u_i \right)$$ Considering this last expression as a function of $(u_i)_{1\leq i\leq n}\in \mathbb{R}_+^{n}$, we should take the gradient in order to find an extremum. It is a polynomial function (continuous in particular) and for fixed $n\in \mathbb{N}$, the variables belong to a compact subset $K$ so it does reach a minimum and a maximum (The function $f:u_i \longmapsto \sum_{i=1}^n u_i$ is continuous and the $(u_i)$ belong to $K:=f^{-1}([0,4])$ closed. Moreover each $u_i$ is bounded by $4$.)

The gradient only vanishes at $(0,\cdots ,0)$ which corresponds to a minimum. The maximum must then lie on the boundary of $K$ (e.g. the function $\mathrm{id}:[0,1]\to [0,1]$ has non vanishing derivative, so the extremum are on the boundaries). The subsets of the boundary on which one of the $u_i=0$ all correpond to minimum, so if we represent ourselves $K$ as the "$(0, \cdots 0)$ corner" of $\mathbb{R}_+^n$, the maximum must be reached on the "triangle"/"simplex" part and not the "wall" part of the corner. Let us call $S:= f^{-1}(\{4\})$ this "side" of $K$ which is also compact. This time we should be able to find the maximum by looking at the locus where the gradient vanishes: either by brute force, by looking at the function of $\big(u_1,\cdots, u_{n-1}, 4-(u_1+\cdots+ u_{n-1})\big)$ or by use of Lagrange multiplier.

I would just guess that the maximum is reached for all $u_i= \frac{4}{n}$ (the projection of the gradient of the function of $n$ variables on $S$ (kind of locally coincide with the tangent space) vanishes at this point), in which case $$ \prod_{i< j} |x_i-x_j| =\left(\frac{4}{n} \right)^n \left( 2\cdot \frac{4}{n} \right)^{n-1}\times \cdots \times \left(n\cdot \frac{4}{n}\right)^1 = \left( \frac{4}{n}\right)^{\frac{n(n+1)}{2}} n!\cdot (n-1)! \cdot (n-2)! \cdots 2! \label{Eq}\tag{Eq}$$ There may be a discussion on the cases $n$ small vs. $n$ large enough... This clearly goes to $0$ when $n$ is big, so if we compare its square with $\big(2\,(n+1) \big)^{n+1}$ it will be smaller, thus the statment of the OP is true (for $n$ big enough).

Let me clarify a crucial point by transforming products in to sums, taking logarithm of each member of the inequality: ($\ln$ increasing, preserves order) $$ \text{L.h.s.}= \ln\left( \prod_{j=1}^{n+1}\prod_{\genfrac{}{}{0pt}{}{1\leq i\leq n+1 }{i\neq j}} |x_i-x_j|\right) = \sum_{j=1}^{n+1} \ln\left( \prod_{\genfrac{}{}{0pt}{}{1\leq i\leq n+1 }{i\neq j}} |x_i-x_j|\right)$$

$$\text{R.h.s.} =\ln\left( 2^{n+1} (n+1)^{n+1}\right) = (n+1)\big( \ln(2) + \ln(n+1) \big)$$

If each summand $\ln\left( \prod_{\genfrac{}{}{0pt}{}{1\leq i\leq n+1 }{i\neq j}} |x_i-x_j|\right)$ were bigger than $\big( \ln(2) + \ln(n+1) \big)$ then $$\text{L.h.s.} > \text{R.h.s.}$$ By contraposition, since (\ref{Eq}) seems to suggest that $\text{L.h.s.} \leq \text{R.h.s.}$ (for $n$ large enough), there must exist a $j$ such that $$\ln\left( \prod_{\genfrac{}{}{0pt}{}{1\leq i\leq n+1 }{i\neq j}} |x_i-x_j|\right) \leq \big( \ln(2) + \ln(n+1) \big)\quad \Longleftrightarrow\quad \prod_{\genfrac{}{}{0pt}{}{1\leq i\leq n+1 }{i\neq j}} |x_i-x_j| \leq 2\, (n+1)$$