Skip to main content
6 of 14
edited body
Iosif Pinelis
  • 127.9k
  • 8
  • 107
  • 229

$ \newcommand{\R}{\mathbb{R}} \newcommand{\la}{\lambda} \newcommand{\p}{\partial} \newcommand{\PP}{\mathcal{P}}$ Let $x:=(x_1,\dots,x_n)\in[0,1]^n$, $y:=(y_1,\dots,y_n)\in[0,1]^n$, $h:=(h_1,\dots,h_n)$, \begin{equation*} h_i:=H(x_i,y_i),\quad H(s,t):=\frac2{\frac1s+\frac1t}=\frac{2st}{s+t} \end{equation*} for $s>0$ and $t>0$, and, by continuity, $H(s,t):=0$ for $s\ge0$ and $t\ge0$ with $s t=0$. Let $Az:=\frac1n\sum_1^n z_i$ for $z:=(z_1,\dots,z_n)$. Then the result in question can written as \begin{equation*} L(x,y):=H(Ax,Ay)-Ah\le L^*_n:= \left\{ \begin{alignedat}{2} &\frac12&&\text{ if $n$ is even}\\ & \frac12-\frac1{2n^2}&&\text{ if $n$ is odd}, \end{alignedat} \right. \tag{0} \end{equation*} with equality for some $x,y$ in $[0,1]^n$.

For $n=1$, this is trivial. So, assume $n\ge2$. Let $[n]:=\{1,\dots,n\}$. The maximum of $L(x,y)$ over all $(x,y)\in[0,1]^n\times[0,1]^n$ is attained. In what follows, let $(x,y)$ be such a maximizer.

Let \begin{gather*} I_0:=\{i\in[n]\colon x_i=0\},\quad J_0:=\{i\in[n]\colon y_i=0\},\\ I:=\{i\in[n]\colon 0<x_i<1\},\quad J:=\{i\in[n]\colon 0<y_i<1\},\\ I_1:=\{i\in[n]\colon x_i=1\},\quad J_1:=\{i\in[n]\colon y_i=1\}. \end{gather*} Note that $(I_0,I,I_1)$ and $(J_0,J,J_1)$ are partitions of the set $[n]$.

Take any $i\in I_0$, so that $x_i=0$ and hence $h_i=0$. Replacing now $y_i$ by $1$ can only increase $L(x,y)$. So, without loss of generality (wlog), $I_0\subseteq J_1$. By the symmetry (that is, because $x$ and $y$ are interchangeable), wlog \begin{equation*} I_0\subseteq J_1,\quad J_0\subseteq I_1. \tag{1} \end{equation*}

Let $\p_s$ denote the partial derivative with respect to a variable $s$.

Then
\begin{equation*} \p_s H(s,t)=2\Big(\frac t{s+t}\Big)^2 \end{equation*} for $s\ge0$ and $t\ge0$ with $s+t>0$, with $\p_s H(s,t)=0$ if $s=t=0$ (at $s=0$, the right derivative is meant here). So, for any distinct $i$ and $j$ in $I$ \begin{equation*} \p_{x_i}L(x,y)-\p_{x_j}L(x,y) =2\Big(\frac{y_j}{x_j+y_j}\Big)^2-2\Big(\frac{y_i}{x_i+y_i}\Big)^2=0, \end{equation*} because $(x,y)$ is a maximizer of $L(x,y)$. So, \begin{equation*} \exists\la\in\R\ \forall i\in I\ \frac{y_i}{x_i+y_i}=\la. \tag{1.5} \end{equation*} If $\la=0$, then $y=0$ on $I$, that is, $I\subseteq J_0$. Hence, by (1), $I\subseteq I_1$, which implies $I=\emptyset$ and hence $I\cap J_0=\emptyset$.

If $\la\ne0$ then, by (1.5), $x=ay$ on $I$ for some real $a>0$ and hence, again, $I\cap J_0=\emptyset$.

So, whether $\la$ is $0$ or not, by the symmetry, \begin{gather*} I\cap J_0=\emptyset,\quad J\cap I_0=\emptyset, \tag{2a} \\ x=ay\text{ on }I,\quad y=bx\text{ on }J \tag{2b} \end{gather*} for some real $a,b>0$.

We are going to use repeatedly the following very simple

Lemma: If $k$ and $l$ are nonnegative integers such that $k+l\le n$, then \begin{equation*} H(\tfrac kn,\tfrac ln)\le H(\tfrac mn,\tfrac{n-m}n)=L^*_n, \end{equation*} where \begin{equation*} m:=\lfloor n/2\rfloor. \tag{3} \end{equation*}

(This follows because (i) $H(\tfrac kn,\tfrac ln)\le H(\tfrac kn,\tfrac{n-k}n)$ and (ii) $H(s,1-s)$ is decreasing in $|s-1/2|$ for $s\in[0,1]$.)

Further, take any $i\in I_0\cap J_0$ and $j\notin I_0\cup J_0$, so that $x_i=y_i=0$, $h_i=0$, $x_j>0$, $y_j>0$, and $h_j>0$. By swapping $x_i$ and $x_j$, we do not change $Ax$ or $Ay$, whereas the new values of $h_i$ and $h_j$ both become equal $0$, so that $Ah$ decreases and hence $L(x,y)$ increases, which contradicts the condition that $(x,y)$ is a maximizer. Thus, we have \begin{equation*} I_0\cap J_0=\emptyset\quad\text{or}\quad I_0\cup J_0=[n]. \end{equation*}

If $I_0\cup J_0=[n]$, then $h=0$ and hence $Ah=0$. Also, introducing $k:=n-|I_0|$, $l:=n-|J_0|$, and $s:=k+l$ (where $|K|$ denotes the cardinality of a set $K$), we see that the condition $I_0\cup J_0=[n]$ implies $k+l\le n$. Also, $Ax\le k/n$ and $Ay\le l/n$. So, by the Lemma, \begin{equation*} L(x,y)=H(Ax,Ay)\le L^*_n. \end{equation*}

Also, $L(x,y)=L^*_n$ if (i) $x=1$ and $y=0$ on $[m]$ and (ii) $x=0$ and $y=1$ on $[n]\setminus[m]$, where $m$ is as in (3).

It remains to prove the inequality in (0) assuming that \begin{equation*} I_0\cap J_0=\emptyset. \tag{4} \end{equation*} Then $(I_0,J_0,I\cup J,I_1\cap J_1)$ is a partition of the set $[n]$, in view of (1) and because $(I_0,I,I_1)$ and $(J_0,J,J_1)$ are partitions of $[n]$.

Here we shall distinguish the following two mutually complementary cases: \begin{equation*} \begin{aligned} &Case\ 1:\ I\cap J\ne\emptyset \text{ or } I=\emptyset \text{ or } J=\emptyset; \\ &Case\ 2:\ I\cap J=\emptyset \text{ and } I\ne\emptyset \text{ and } J\ne\emptyset. \end{aligned} \tag{5} \end{equation*}

Consider now Case 1. Then, by (2b), for some real $a>0$ we have $x=ay$ on $I\cup J$ and hence $\xi=a\eta$, where $\xi$ and $\eta[\in(0,1)]$ are the (arithmetic) means of $x$ and $y$ over $I\cup J$. We define the mean of a vector $z=(z_1,\dots,z_n)\in[0,1]^n$ over a set $K\subseteq[n]$ as $\frac1{|K|}\sum_K z_i$ if $|K|:=(\text{cardinality of $K$})\ne0$ and as $1/2$ otherwise.
Denote by $s_0,t_0,s,u$ the respective (relative) weights of the pieces of the partition $\PP:=(I_0,J_0,I\cup J,I_1\cap J_1)$ of the set $[n]$, with the weight of a set $K\subseteq[n]$ defined as $|K|/n$. The condition $x=ay$ on $I\cup J$ also implies $h=\frac{2a}{1+a}\,y$ on $I\cup J$. Thus, recalling also (1), we see that the means of $x,y,h$ over the pieces of the partition $(I_0,J_0,I\cup J,I_1\cap J_1)$ of the set $[n]$ and the (relative) weights of these pieces are given by the following table:

$$ \begin{array}{c||c|c|c|c} \text{Pieces }& I_0 & J_0 & I\cup J & I_1\cap J_1 \\ \hline \text{Means of }x & 0 & 1 & a\eta & 1 \\ \text{Means of }y & 1 & 0 & \eta & 1 \\ \text{Means of }h & 0 & 0 & \frac{2a}{1+a}\,\eta & 1 \\ \text{Weights }& s_0 & t_0 & s & u \end{array} $$

So, \begin{alignat*}{5} &Ax=&& &&t_0&&+sa\eta&&+u, \\ &Ay=&&s_0 && &&+s\eta&&+u, \\ &Ah=&& && &&s\frac{2a}{1+a}\,\eta&&+u. \end{alignat*}

If $s=0$, then $u=1-s_0-t_0$ and \begin{equation*} L(x,y)|_{s=0}=\frac{(1-s_0)s_0+(1-t_0)t_0}{2-s_0-t_0}. \end{equation*} So, \begin{equation*} (\p_{s_0}+\p_{t_0})L(x,y)|_{s=0}=\frac{4(1-s_0)(1-t_0)}{(2-s_0-t_0)^2}\ge0. \end{equation*} So, if we increase $s_0$ and $t_0$ by the same amount, while keeping $s_0+t_0\le1$, the value of $L(x,y)|_{s=0}$ may only increase. So, \begin{equation*} L(x,y)|_{s=0}\le L(x,y)|_{s=0,t_0=1-s_0}=2(1-s_0)s_0=H(1-s_0,s_0)\le L^*_n, \end{equation*} by the Lemma.

If $s_0+u=0$, then $s_0=u=0$ and \begin{equation*} L(x,y)|_{s_0=u=0}=\frac{2 s t_0\eta}{(1 + a) (t_0 + (1 + a) s\eta)}, \end{equation*} which is nonincreasing in $a\ge0$ and nondecreasing in $\eta\ge0$. So, \begin{equation*} L(x,y)|_{s_0=u=0}\le L(x,y)|_{s_0=u=0=a,\,\eta=1}=H(s,t_0)\le L^*_n, \end{equation*} again by the Lemma.

Assume now that $s>0$ and $s_0+u>0$. Let $f:=(2 + a) s_0 + t_0 + 2 (1 + a) \eta s+ (3 + a ) u$. Note that $f>0$, since $s_0,t_0,s,u$ are nonnegative, $s_0 + t_0 + s+ u=1$, and $\eta>0$. Next, \begin{equation*} (Ax+Ay)^2\frac{(1+a)^2}{2s\eta f}\,\p_a L(x,y)=a (s_0 + u)-(t_0+u)=0, \end{equation*} since $(x,y)$ is a maximizer of $L(x,y)$. So, $a=\frac{t_0+u}{s_0 + u}$ and hence \begin{equation*} L(x,y)=r:=L(x,y)|_{a=\frac{t_0+u}{s_0 + u}}=\frac{2 s_0 t_0 + (s_0 + t_0)u}{s_0 + t_0 + 2 u}. \end{equation*} Further, $\p_u r=\frac{(s_0 - t_0)^2}{(s_0 + t_0 + 2 u)^2}\ge0$. Also, obviously $r$ does not depend on $s$. Thus, if we increase $u$ and simultaneously decrease $s$ by the same amount, while keeping $s\ge0$, the value of $L(x,y)=r$ may only increase. So, wlog $s=0$, which is a subcase of Case 1 already considered.

This completes the consideration of Case 1 in (5).

It remains to consider Case 2. Here, by (2a) and (5), $I\cap(J_0\cup J)=\emptyset$, whence $I\subseteq J_1$. So, $y=1$ on $I$ and hence, by (2b), $x=a\in(0,1)$ on $I$. Similarly, $x=1$ on $J$ and $y=b\in(0,1)$ on $J$. Thus, the means of $x,y,h$ over the pieces of the partition $(I_0,J_0,I,J,I_1\cap J_1)$ of the set $[n]$ and the weights of these pieces can be given by the following table:

$$ \begin{array}{c||c|c|c|c|c} \text{Pieces }& I_0 & J_0 & I & J & I_1\cap J_1 \\ \hline \text{Means of }x & 0 & 1 & a & 1 & 1 \\ \text{Means of }y & 1 & 0 & 1 & b & 1 \\ \text{Means of }h & 0 & 0 & \frac{2a}{1+a} & \frac{2b}{1+b} & 1 \\ \text{Weights }& s_0 & t_0 & s & t & u \end{array} $$

Here, $s_0,t_0,s,t,u$ are $\ge0$, with $s_0+t_0+s+t+u=1$. So, \begin{alignat*}{6} &Ax=&& &&t_0&&+sa&&+t&&+u, \\ &Ay=&&s_0 && &&+s&&+t b&&+u, \\ &Ah=&& && &&s\frac{2a}{1+a}&&+t\frac{2b}{1+b}&&+u. \end{alignat*}

Let $f_1:=(2 + a) s_0 + t_0 + 2 (1 + a) s + (1 + 2 b + a b ) t + (3 + a) u$ and $f_2:=s_0 + (2 + b) t_0 + (1 + 2 a + a b) s + 2 (1 + b ) t + (3 + b) u$. Note that $f_1>0$ and $f_2>0$, because in Case 2 we have $I\ne\emptyset$ and $J\ne\emptyset$, whence $s>0$ and $t>0$. Next, \begin{equation*} \begin{gathered} (Ax+Ay)^2\frac{(1+a)^2}{2f_1}\,\p_a L(x,y)=[a (b t+s_0 + u)-(t+t_0+u)]s=0, \\ (Ax+Ay)^2\frac{(1+b)^2}{2f_2}\,\p_b L(x,y)=[b (a s+t_0 + u)-(s+s_0+u)]t=0, \end{gathered} \tag{6} \end{equation*} because $(x,y)$ is a maximizer of $L(x,y)$. Subtracting one of the latter two equations from the other and rearranging, we see that $(a s+t)(s_0+u)=(b t+s)(t_0+u)$, so that $s_0+u=0\iff t_0+u=0$. So, if one of the latter two equalities holds, then the first one of the two equations in (6) becomes $ab=1$, which contradicts the conditions $a\in(0,1)$ and $b\in(0,1)$. So, $s_0+u>0$ and $t_0+u>0$. Then, solving (say) the first of the two equations in (6) for $a$, then substituting the resulting expression for $a$ in terms of $b$ into the second of the two equations in (6), and then solving for $b$, we see that $a=\frac{t_0 + u}{s_0 + u}$ and $b=\frac{s_0 + u}{t_0 + u}$, so that again $ab=1$, which contradicts the conditions $a\in(0,1)$ and $b\in(0,1)$. Thus, Case 2 cannot actually occur for any maximizer $(x,y)$ of $L(x,y)$.

The entire proof is now complete.

Iosif Pinelis
  • 127.9k
  • 8
  • 107
  • 229