7

let $x_{1}\ge x_{2}\ge\cdots\ge x_{n}\ge 0,y_{1}\ge y_{2}\ge\cdots\ge y_{n}\ge 0$,and such $$\sum_{i=1}^{n}x_{i}=\sum_{i=1}^{n}y_{i}=n$$ show that $$ \prod_{i=1}^{n}|x_{i}-y_{i}|<e^{\frac{n}{2}}$$

I try let$$A=\{i|x_{i}\ge y_{i}\},B=\{i|x_{i}<y_{i}\}$$ so $$\prod_{i=1}^{n}|x_{i}-y_{i}|=\prod_{i\in A}(x_{i}-y_{i})\prod_{i\in B}(y_{i}-x_{i})$$ and use AM-GM inequality we have $$\prod_{i\in A}(x_{i}-y_{i})\le\left(\dfrac{\sum_{i\in A}(x_{i}-y_{i})}{|A|}\right)^{|A|}$$and $$\prod_{i\in B}(y_{i}-x_{i})\le\left(\dfrac{\sum_{i\in B}(y_{i}-x_{i})}{|B|}\right)^{|B|}$$ where $$|A|+|B|=n,\sum_{i\in B}x_{i}=n-\sum_{i\in A}x_{i},\sum_{i\in B}y_{i}=n-\sum_{i\in A}y_{i}$$

math110
  • 93,304
  • Simple AM-GM won't work: instead of $\prod_{i=1}^{n}|x_{i}-y_{i}|<e^{\frac{n}{2}}$, by AM-GM it suffices to show $\sum_{i=1}^{n}|x_{i}-y_{i}|< n e^{\frac{1}{2}}$ . Observe the following case. Let $y_1 = n$ and all other $y_i = 0$. Choose some $x_1\ge1 $. Then - and only then - we can always construct the other $x_i\le x_1$ such that $\sum x_i = n$. We have $\sum_{i=1}^{n} |x_{i}-y_{i}| = 2(n - x_1)$ and we need to show the worst case for $x_1=1$, i.e. $2(n -1) <n e^{\frac{1}{2}} \simeq 1.64 e$ so this won't hold. – Andreas Oct 11 '18 at 17:18
  • Here is a case which has the exponential behaviour with $n$. Let all $y_i = 1$. Choose some $a$ with $1<a<n$ and $x_1 = \cdots = x_k = a$ for $k = n/a$, and all other $x_i=0$. Then we have $P = \prod_{i=1}^{n}|x_{i}-y_{i}| = (a-1)^{n/a} = e^{\frac{n}a \ln(a-1)} $ . So we require $\frac{\ln(a-1)}a < \frac12$. The maximum of the LHS occurs at $a/(a-1) = \ln(a-1)$ or $a \simeq 4.6$ where $P \simeq e^{0.28 n} < e^{0.5 n }$. – Andreas Oct 11 '18 at 21:38

1 Answers1

2

Observe the behavior of $x_{1}\ge x_{2}\ge\cdots\ge x_{n}\ge 0$ under the restriction $\sum_{i=1}^{n}x_{i}=n$. The $x_1$ can take values $1 \cdots n$. Further $x_2 \le n/2$. For if we had $x_2 > n/2$ we must also have $x_1 \ge x_2 > n/2$ and then $\sum_{i=1}^{n}x_{i} > n$. By repeating this argument, we have $x_i \le n/i$. The same holds for the $y_i$.

So each of the factors will have maximum value $n/i$, where we can omit the $y_i$ after observing $|x_i - y_i| \le \max \{x_i, y_i\} \le n/i$.

Thus we have as an upper bound the "envelope" $$P = \prod_{i=1}^{n}|x_{i}-y_{i}| \le \prod_{i=1}^{n}\frac{n}{i} = \frac{n^n}{n!}$$ For large $n$, there exists the well known limt behavior $\log n! \simeq n \log(n) - n$ so we obtain $P \le \frac{n^n}{n!} \to e^n$ so this limit is not good enough, given that we are supposed to show $P \le e^{n/2}$. However, the same train of thought can be extended.

Start w.l.o.g. by choosing an arbitrary $x_1 > y_1$. Then for the remaining values, we have that all $x_i < \min \{x_1,n-x_1\}$. This is being derived from two facts: 1. Since $\sum_{i=1}^{n}x_{i} = n$, we have $\sum_{i=2}^{n}x_{i} = n - x_1$, and so the largest value that any further $x_i$ can attain is $n-x_1$. 2. Since $x_2 \le x_1$, we must further obey $x_i \le x_1$. The same conditions hold for $y_i$.

The envelope of the remaining values $x_2 \cdots x_n$ will therefore obey the upper bounds $x_i \le \frac{\min \{x_1,n-x_1\}}{i}$ and we have $$ P \le x_1 \frac{(\min \{x_1,n-x_1\})^{n-1}}{(n-1)!} $$ This can again be bounded with $x_1 = \frac{n}{2}$ so we obtain $$ P \le \frac{n}{2} \frac{(\frac{n}{2})^{n-1}}{(n-1)!} = \frac{(\frac{n}{2})^{n}}{(n-1)!} $$ and for large $n$, using the approximate factorial expression given above,
$$ P \le \frac{(\frac{n}{2})^{n}}{(n-1)!} \simeq \frac{e^n}{2^n} = e^{n(1-\log 2)} \simeq e^{0.31 n } \le e^{n/2 } $$ Small-$n$-details on the approximations will lead to rigorous bounds, which finalizes the proof of the claim.

Andreas
  • 15,175