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

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

  • 1
    $\begingroup$ 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}$$ $\endgroup$ – 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}$.

  • $\begingroup$ 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) $\endgroup$ – Carlo Beenakker Oct 11 '18 at 13:46
  • $\begingroup$ @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? $\endgroup$ – Anthony Quas Oct 11 '18 at 16:29
  • $\begingroup$ 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. $\endgroup$ – usul Oct 11 '18 at 19:20
  • $\begingroup$ @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$. $\endgroup$ – 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}$.


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.