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

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}|

I try let$$A=\{i|x_{i}\ge y_{i}\},B=\{i|x_{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}}$$

• What is the name of the book? – Mare Oct 11 '18 at 12:37
• @PietroMajer Ah yes. I am sorry! – Ali Taghavi Oct 11 '18 at 13:20
• Looks like the Cauchy-Schwarz Master Class to me... is it? – Marty Oct 11 '18 at 15:23
• @Marty --- I checked that book, it's not there (at least I did not find it there) – Carlo Beenakker Oct 11 '18 at 21:34
• Absence of electronic version is not the reason to skip the title and author of the book. Some people still read paper books! – Alexandre Eremenko Oct 12 '18 at 0:19

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-run is a maximal connected nonempty subset $$J$$ of $$[n]$$ such that $$y_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-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- and $$(y>x)$$-runs. Wlog, we have here an $$(y-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. To obtain a contradiction, suppose that, moreover, $$a_1. 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 (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 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, that is, wlog at least one of the functions $$x,y$$ is constant on any two adjacent $$(y- and $$(y>x)$$-runs.

Suppose now that there are at least three $$(y- 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-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- and $$(y>x)$$-runs, we have here $$B_1:=b_1. 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 (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 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- and/or $$(y>x)$$-runs, and, by the above consideration of any two adjacent $$(y- 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 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, where $$t\in[n-1]$$ is as in the OP. So, $$$$\|x-y\|\le t(1-0)+(n-t)(\frac n{n-t}-1)=2t.$$$$ So, the AM-GM reasoning in the OP yields $$$$\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,$$$$ where $$s:=t/n$$ and $$$$f(s):=(\frac{s}{1-s})^{1-s}\le e^c$$$$ for $$s\in(0,1)$$, where $$c=0.278\ldots<1/2$$, as desired.

• Since the final function is maximized near $s=7/9$, this shows that a near-optimal example has $n=9$ and $$x=(1,1,1,1,1,1,1,1,1)$$ $$y=(0,0,0,0,0,0,0,\frac{9}{2},\frac{9}{2})$$ $$\Pi |y_i-x_i| = \frac{49}{4} = {\Large e}^{\Large(.278...)9}$$ – Matt F. Oct 15 '18 at 11:27

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.

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}$$.

• this $2^n$ bound is reached when you take $\{x_i,y_i\}=\{0,2\}$ for each $i=1,2,\ldots n$, right? (subject to the constraint on the sum) – Carlo Beenakker Oct 11 '18 at 13:46
• @CarloBeenakker: both sequences are supposed to be non-decreasing, so if each $x$ and $y$ is 0 or 2 and they have the same sum, they are the same sequence, right? – Anthony Quas Oct 11 '18 at 16:29
• If we take $x = (n,0,\dots,0)$ and $y=(1,\dots,1)$, then $\int_X (g-f)_+ d\mu = (n-1)/n \approx 1$ which makes the final inequality tight. So utilizing the monotonicity assumption may not push this proof approach any further. The AM-GM inequality (Jensen's) seems like the weak spot. – usul Oct 11 '18 at 19:20
• @AnthonyQuas -- certainly, the $2^n$ bound of this answer does not incorporate the requirement of non-decreasing sequences, so it allows $x_1=2, y_1=0, x_2=2, y_2=0,\ldots x_{n-1}=0,y_{n-1}=2, x_n=0,y_n=2$. – Carlo Beenakker Oct 11 '18 at 19:44

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}$$.