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

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?

• .- You do have, dear friend, to change in your product $\prod_{\substack{i=1\\i\neq j}}^{n+1}\left |x_j-x_i\right|$ the value $n+1$ by $n$. – Piquito Feb 10 at 15:56
• I am afraid, dear friend, your inequality is wrong. Take seven points equally distributed in $[-1,1]$. The minimal product I have got is $(2/3)^2=0.4444...$ and your quotient $\dfrac{n+1}{2^{n-1}}$ should be $\dfrac{7}{2^5}=0.21875$. Am I wrong?. – Piquito Feb 10 at 16:27
• Oh, I see... I think I should add more hypotheses on my points (I am working with very specific points but I conjectured that it would work for any choice of them). Thank you! I will edit my post. – armand trepy Feb 10 at 16:37
• Yes, rewrite your problem that I see has been very well received by MSE users and has even been the subject of a bounty. Good luck. – Piquito Feb 10 at 17:03
• I'm not convinced that Piquito's counterexample is a valid one. For seven equidistant points, taking $j$ as the one verifying $x_j = 0$, the product I get is $2^2/3^4$. – user3733558 Feb 11 at 9:44

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.

• nice! I got stuck after the Chebyshev polynomial part but apparently the residue theorem was the answer. – dezdichado Feb 19 at 17:26

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)$$