16
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ .- 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$. $\endgroup$ – Piquito Feb 10 at 15:56
  • 1
    $\begingroup$ 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?. $\endgroup$ – Piquito Feb 10 at 16:27
  • $\begingroup$ 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. $\endgroup$ – armand trepy Feb 10 at 16:37
  • $\begingroup$ 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. $\endgroup$ – Piquito Feb 10 at 17:03
  • 1
    $\begingroup$ 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$. $\endgroup$ – user3733558 Feb 11 at 9:44
9
+150
$\begingroup$

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.

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

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

$\endgroup$
0

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.