show this nice and hard inequality with $ \prod_{i=1}^{n}|x_{i}-y_{i}|<e^{\frac{n}{2}}$

Question

I saw the following results in a book. The author said it was not difficult to prove how I felt it was difficult to prove, so I asked here. The result comes from a book that has no electronic version.Here's what I'm trying to prove.

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}$$ so let $$x=\sum_{i\in A}x_{i},y=\sum_{i\in A}y_{i},t=|A|$$ then we have $$\prod_{i=1}^{n}|x_{i}-y_{i}|\le \left(\dfrac{x-y}{t}\right)^t\left(\dfrac{(n-y)-(n-x)}{n-t}\right)^{n-t}=\dfrac{(x-y)^n}{t^t(n-t)^{n-t}}$$

Answer 1

Let $x:=(x_1,\dots,x_n)$ and $y:=(y_1,\dots,y_n)$; we identify $x$ and $y$ with the corresponding functions on the set $[n]:=\{1,\dots,n\}$. Take any real $S,T\ge0$ and nonnegative integers $n_-$ and $n_+$ such that $n_-+n_+\le n$. Let $Z=Z(n,n_-,n_+,S,T)$ denote the set of all pairs $(x,y)\in[0,\infty)^n\times[0,\infty)^n$ such that $x_1\le\dots\le x_n$, $y_1\le\dots\le y_n$, $x_1+\dots+x_n\le S$, $y_1+\dots+y_n\le T$, the cardinality of the set $\{i\in[n]\colon y_i\le x_i\}$ is $\ge n_-$, and the cardinality of the set $\{i\in[n]\colon y_i\ge x_i\}$ is $\ge n_+$.

Consider the problem of maximizing $\|x-y\|:=\sum_1^n|x_i-y_i|$ over $(x,y)\in Z$.

Claim: The maximum of $\|x-y\|$ over $(x,y)\in Z$ is attained when one of the functions $x,y$ is constant while the other one takes at most two values, one of which is $0$.

Proof. By compactness and continuity, the maximum is attained. In the sequel, let $(x,y)$ be a point of attainment of this maximum. If $x_i=y_i$ for some $i\in[n]$, then we can remove this $i$, re-enumerate the coordinates of $x$ and $y$, and use induction on $n$. So, without loss of generality (wlog) $x_i\ne y_i$ for all $i$.

Let us say that a subset $J$ of the set $[n]$ is connected if it is the intersection of $[n]$ with an interval. An $x$-run is a maximal connected nonempty set of constancy of the function $x\colon i\mapsto x_i$. An $(y<x)$-run is a maximal connected nonempty subset $J$ of $[n]$ such that $y_i<x_i$ for all $i\in J$. Similarly defined are the $y$-runs and $(y>x)$-runs. Replacing the $x$- and $y$-values in each $(y<x)$-run and in each $(y>x)$-run by the corresponding arithmetic means, wlog we have that $x$ and $y$ are constant in each such run; that is, each such run is contained in an $x$-run and in a $y$-run; this condition will be assumed in the rest of this proof.

Consider any two adjacent $(y<x)$- and $(y>x)$-runs. Wlog, we have here an $(y<x)$-run $K_1$ followed (to the right of $K_1$) by a $(y>x)$-run $K_2$, of cardinalities $k_1$ and $k_2$, respectively (resp.). For each $j=1,2$, let $a_j$ and $b_j$ be the constant values of $x$ and $y$, resp., in the run $K_j$, so that $b_1<a_1\le a_2<b_2$. To obtain a contradiction, suppose that, moreover, $a_1<a_2$. Let us change/vary $a_1,a_2,b_1,b_2$ by small amounts $da_1,da_2,db_1,db_2$, resp., such that $k_1 da_1+k_2 da_2=0$ and $k_1 db_1+k_2 db_2=0$, so that the sums $x_1+\dots+x_n$ and $y_1+\dots+y_n$ are unchanged. Then the change $d\|x-y\|$ of $\|x-y\|$ will be the same as the change of $k_1(a_1-b_1)+k_2(b_2-a_2)$, which is $k_1(da_1-db_1)+k_2(db_2-da_2)=2k_2(db_2-da_2)$. If we now take any small enough (in absolute value) $da_2,db_2$ such that $da_2<db_2<0$ (and choose $da_1$ and $db_1$ so as to satisfy the conditions $k_1 da_1+k_2 da_2=0$ and $k_1 db_1+k_2 db_2=0$), then the resulting pair $(x+dx,y+dy)$ will satisfy the condition $b_1+db_1<a_1+da_1<a_2+da_2<b_2+db_2$ and will still be in the set $Z$ (in particular, we will have $db_1>0$ and hence $b_1+db_1>0$). But then $d\|x-y\|=2k_2(db_2-da_2)>0$, which is the desired contradiction. Thus, $b_1<a_1=a_2<b_2$, that is, wlog at least one of the functions $x,y$ is constant on any two adjacent $(y<x)$- and $(y>x)$-runs.

Suppose now that there are at least three $(y<x)$- and/or $(y>x)$-runs. Then wlog there are three adjacent runs $K_1,K_2,K_3$, of which $K_1$ is the leftmost one and $K_3$ is the rightmost one, and, moreover, $K_1$ and $K_3$ are $(y<x)$-runs, whereas $K_2$ is a $(y>x)$-run. For each $j=1,2,3$, let $a_j$ and $b_j$ be the constant values of $x$ and $y$, resp., in the run $K_j$ and let $k_j$ be the cardinality of $K_j$, so that, in view of the above consideration of any two adjacent $(y<x)$- and $(y>x)$-runs, we have here $B_1:=b_1<A_1:=a_1=a_2<B_2:=b_2=b_3<A_2:=a_3$. Let us change/vary $A_1,A_2,B_1,B_2$ by small amounts $dA_1,dA_2,dB_1,dB_2$, resp., such that $(k_1+k_2) dA_1+k_3 dA_2=0$ and $k_1 dB_1+(k_2+k_3) dB_2=0$, so that the sums $x_1+\dots+x_n$ and $y_1+\dots+y_n$ are unchanged. Then the change $d\|x-y\|$ of $\|x-y\|$ will be the same as the change of $k_1(A_1-B_1)+k_2(B_2-A_1)+k_3(A_2-B_2)$, which is $k_1(dA_1-dB_1)+k_2(dB_2-dA_1)+k_3(dA_2-dB_2)=2k_2(dB_2-dA_1)$. If we now take any small enough (in absolute value) $dA_1,dB_2$ such that $dA_1<dB_2<0$ (and choose $dA_2$ and $dB_1$ so as to satisfy the conditions $(k_1+k_2) dA_1+k_2 dA_2=0$ and $k_1 dB_1+(k_2+k_3) dB_2=0$), then the resulting pair $(x+dx,y+dy)$ will satisfy the condition $B_1+dB_1<A_1+dA_1<B_2+dB_2<A_2+dA_2$ and will still be in the set $Z$ (in particular, we will have $dB_1>0$ and hence $B_1+dB_1>0$). But then $d\|x-y\|=2k_2(dB_2-dA_1)>0$, which is the desired contradiction.

Thus, there are at most two $(y<x)$- and/or $(y>x)$-runs, and, by the above consideration of any two adjacent $(y<x)$- and $(y>x)$-runs, wlog the function $x$ is a constant (say $a\ge0$), whereas $y$ takes at most two values $b_1,b_2$ such that $0\le b_1\le b_2$. If $b_1=b_2=b$, then the maximum of $\|x-y\|$ over $(x,y)\in Z$ is $c:=S\vee T$, attained when one of the functions $x,y$ is the constant $c$ while the other one is $0$.

So, wlog $0\le y_1=\dots=y_k=b_1<b_2=y_{k+1}=\dots=y_n$ for some $k=1,\dots,n-1$ and some $b_1,b_2$, and $x_1=\dots=x_n=a\ge0$ for some $a\in(b_1,b_2)$. If $b_1>0$, then, replacing $y_1$ and $y_n$ respectively by $y_1-h$ and $y_n+h$ with any $h\in(0,b_1]$ results in a greater value of $\|x-y\|$, which contradicts the maximality of $(x,y)$. So, $b_1=0$, and the Claim is completely proved. $\Box$

In the OP conditions, we have $S=T=n$, so that, by the Claim, the maximum of $\|x-y\|$ is attained when $x_1=\dots=x_n=1$ and $0=y_1=\dots=y_t<y_{t+1}=\dots=y_n=\frac n{n-t}$, where $t\in[n-1]$ is as in the OP. So, \begin{equation} \|x-y\|\le t(1-0)+(n-t)(\frac n{n-t}-1)=2t. \end{equation} So, the AM-GM reasoning in the OP yields \begin{equation} \prod_1^n|y_i-x_i|\le \frac{(\|x-y\|/2)^n}{t^t(n-t)^{n-t}}\le \frac{t^n}{t^t(n-t)^{n-t}} =f(s)^n, \end{equation} where $s:=t/n$ and \begin{equation} f(s):=(\frac{s}{1-s})^{1-s}\le e^c \end{equation} for $s\in(0,1)$, where $c=0.278\ldots<1/2$, as desired.

Answer 2

Let me make the question more general: given a probability space $(X,d\mu)$ and two functions $f,g:X\rightarrow R_+$ such that $\int_Xfd\mu=\int_Xgd\mu=1$, find an upper bound of $$\int_X\log|g-f|d\mu.$$

Because $\log$ is concave, the Jensen Inequality gives $$\int_X\log|g-f|d\mu\le\log\int_X|g-f|d\mu=\log\left(2\int_X(g-f)_+d\mu\right)\le\log2.$$ Whence $$\prod_1^n|y_i-x_i|\le2^n.$$

The bound $\log2$ is not optimal in this calculation. But it has a flaw: $X$ should be an interval and I should use the monotonicity of $f$ and $g$. This could be the reason of the better bound $e^{n/2}$.

Answer 3

Using your notation, one can work explicitly as follows. Let $s_A = \sum_{i \in A} |x_i - y_i|$ and $s_B = \sum_{i \in B} |x_i - y_i|$. Then

$$\displaystyle s_A - s_B = \sum_{i \in A} (x_i - y_i) - \sum_{i \in B} (y_i - x_i) = n - n = 0,$$

hence $s_A = s_B = s$. Note that $s \leq n$ (this cannot be improved by much in general: say $x_1 = n, x_i = 0$ for $i = 2, \cdots, n$ and $y_i = 1$ for $i = 1, \cdots, n$). Thus by your AM-GM argument one gets

$$\displaystyle \prod_{i = 1}^n |x_i - y_i| \leq s^n (n-x)^{x-n} x^{-x}$$

for $x = |A|$. The latter function can be optimized to give an upper bound of $(2s/n)^n$. This is slightly better than the bound given by Denis Serre, which takes the value $s = n$.

Edit: I believe the following almost solves the problem. Note that the problem is trivial if $x_i = y_i$ for some $i$, so we assume that this is not the case. Without loss of generality, we suppose $x_1 > y_1$ and let $1, \cdots, m_1$ be the longest consecutive string containing 1 which lies in $A$. Then by AM-GM, we have

$$\displaystyle \prod_{i=1}^{m_1} (x_i - y_i) \leq \left(\frac{\sum_{i=1}^{m_1} (x_i - y_i)}{m_1}\right)^{m_1}.$$

Now replace $x_i, 1 \leq i \leq m_1$ by $u_1 = m_1^{-1} \sum_{i=1}^{m_1} x_i$ and likewise replace $y_i$ with the average of the first $m_1$ $y_i$'s. Note that the new sequence still satisfies the condition of the original problem, but the product is now larger. We do the same thing for the string $m_1 + 1, \cdots, m_2$, the longest consecutive string in $B$ containing $m_1 + 1$. Having done so, we now obtain a new sequence as follows:

$$u^{(1)} = u_1 = u_2 = \cdots = u_{m_1}, u^{(2)} = u_{m_1 + 1} = \cdots = u_{m_2}, \cdots,$$ $$v^{(1)} = v_1 = v_2 = \cdots = v_{m_1}, v^{(2)} = v_{m_1 + 1} = \cdots = v_{m_2}, \cdots$$

with the property that the sets of indices $A,B$ remain the same. Now we glue together consecutive blocks as follows. Take the first two blocks and replace each $v_i$ by the average of $v_1, \cdots, v_{m_2}$. Thus, we have replaced the values $v^{(1)}, v^{(2)}$ by their average. Indeed, this continues to preserve the conditions of the problem but enlarging each $|u_i - v_i|$. Do so with each pair of subsequent consecutive blocks.

Now this part I am not sure how to write up properly, so I will just sketch the idea. One observes that for small $i$ the terms $x_i, y_i$ contribute disproportionately to the total sum (due to the monotonicity), so one wants to lower/narrow the left most blocks with large height; likewise the rightmost blocks with small height. Doing so one eventually concludes that the optimal configuration consists of just two blocks. Then our construction tells us that $y_1 = \cdots = y_n = 1$. Let $k = m_1$ (and $m_2 = n$). We can assume that $x_i = 0$ for $i > k$; otherwise the right blocks make the product smaller. Thus our construction yields that $x_1 = \cdots = x_k = n/k$. It then follows that our product is equal to

$$\displaystyle P(n,k) = \left(\frac{n}{k} - 1\right)^k.$$

The inequality $P(n,k) < e^{n/2}$ is equivalent to

$$\displaystyle \log\left(\frac{n}{k} - 1\right) < \frac{n}{2k}.$$

Put $s = n/k - 1$. We are then left to consider $\log(s) < (s+1)/2$. This inequality is immediately verified by calculus.

Answer 4

Here's a proof I like but with an exercise left in it for the reader. Let $c_i = |x_i-y_i|$, let $A = \{i : x_i \geq y_i\}$ and $B$ the remainders, and let $c = \sum_{i \in A} c_i = \sum_{i \in B} c_i$. Under the constraints that $c_i \geq 0$ and these sums hold, we have \begin{align} \prod_{i=1}^n |x_i - y_i| &= \prod_{i\in A} c_i \prod_{j\in B} c_j \\ &\leq \left(\frac{c}{|A|}\right)^{|A|} \left(\frac{c}{|B|}\right)^{|B|} \\ &= c^n \frac{1}{|A|^{|A|}} \frac{1}{(n-|A|)^{n-|A|}} \\ &= \left(\frac{c}{n ~ \alpha^{\alpha} (1-\alpha)^{1-\alpha}}\right)^n \end{align} where $|A| = \alpha n$.

Now if we take the bound $c \leq n$ then we can optimize at $\alpha=1/2$ and recover the bound $2^n \approx e^{0.69 n}$. But I claim

Lemma. $c \leq \max\{|A|,|B|\}$. (Since writing the rest of this proof I have not been able to prove the lemma. It follows from Iosof Pinelis' claim which has been posted meanwhile, so I leave it as an exercise -- I would love to have an elementary short proof. An equivalent statement is $\sum_{i=1}^n \min\{x_i,y_i\} \geq \min\{|A|,|B|\}$.)

Given the lemma, suppose WLOG that $\alpha \leq \frac{n}{2}$ so $c = (1-\alpha)n$, then we have \begin{align} \left(\frac{c}{n ~ \alpha^{\alpha} (1-\alpha)^{1-\alpha}}\right)^n &= \left(\left(\frac{1-\alpha}{\alpha}\right)^{\alpha}\right)^n \\ &= \exp\left(n ~ \alpha \ln\frac{1-\alpha}{\alpha}\right) \\ &\leq \exp\left(n ~ \alpha \ln\frac{1}{\alpha}\right) \\ &\leq e^{n/e} \\ &\approx e^{0.37 n} \end{align} although bounding $1-\alpha$ by $1$ is clearly loose. Numerically it looks like $\approx e^{0.28 n}$.