8
$\begingroup$

Let $x, y \in \mathbb{R}^{n}_{\geq 0}$ satisfy $\sum_i x_i = \sum_i y_i = 1$ and let $c \geq 1$. I am trying to find out whether the following inequality holds:

\begin{equation} \left(\sum_i x_i y_i\right)^{2c-1} \leq \sum_i(x_i y_i)^c \end{equation}

It seems like there should be a simple proof using standard inequalities, but it eludes me. I need the inequality to hold as part of a larger proof dealing with isoperimetric properties of the boolean hypercube. A proof or a counterexample would be much appreciated!

$\endgroup$
2
  • $\begingroup$ Hint: Hoelder's inequality. $\endgroup$ Mar 23, 2018 at 20:45
  • $\begingroup$ One idea: Jensen says that the LHS is bounded by $\sum x_i^{2c-1} y_i$ and by $\sum x_i y_i^{2c-1}$. Averaging these, we get the bound $\sum \frac{1}{2}(x_i^{2c-1} y_i + x_i y_i^{2c-1})$. If we could sharpen the arithmetic mean to the geometric mean, we would be done, but I don't quite see how to do that. $\endgroup$ Mar 24, 2018 at 0:46

3 Answers 3

10
$\begingroup$

It seems like there should be a simple proof using standard inequalities

Most certainly, most certainly. Nate essentially had it though he was doing Jensen on the wrong side.

We have $z\mapsto z^{2c-1}$ convex, so by Jensen $$ \sum(x_iy_i)^c=\sum x_i(x_i^{\frac{c-1}{2c-1}}y_i^{\frac{c}{2c-1}})^{2c-1}\ge\left(\sum x_ix_i^{\frac{c-1}{2c-1}}y_i^{\frac{c}{2c-1}}\right)^{2c-1}=\left(\sum x_i^{\frac{3c-2}{2c-1}}y_i^{\frac{c}{2c-1}}\right)^{2c-1} $$ Similarly, we get $$ \sum(x_iy_i)^c\ge \left(\sum x_i^{\frac{c}{2c-1}}y_i^{\frac{3c-2}{2c-1}}\right)^{2c-1} $$ So, $$ \sum(x_iy_i)^c\ge \sqrt{\left(\sum x_i^{\frac{3c-2}{2c-1}}y_i^{\frac{c}{2c-1}}\right)\left(\sum x_i^{\frac{c}{2c-1}}y_i^{\frac{3c-2}{2c-1}}\right)}^{2c-1} \ge \left(\sum x_iy_i\right)^{2c-1} $$ by Cauchy-Schwarz.

$\endgroup$
7
$\begingroup$

Let me explain how this may be solved without tricks, this may help for other similar issues.

1) The inequality must hold true for $\sum x_i\leqslant 1$, $\sum y_i\leqslant 1$ (instead of equalities). Indeed, if we replace $x_i$ to $tx_i$, $t>1$, we get a stronger inequality, and this reduces to the case $\sum x_i=1$, analogously to $\sum y_i=1$.

2) Denote $z_i=x_iy_i$. What can be said about these numbers if we know only that $\sum x_i\leqslant 1,\sum y_i\leqslant 1$? For sure, we know that $\sum \sqrt{z_i}=\sum\sqrt{x_iy_i}\leqslant \sum \frac{x_i+y_i}2=1$, but actually nothing more: if $\sum \sqrt{z_i}\leqslant 1$, then it may occur $x_i=y_i=\sqrt{z_i}$. Note that even when we do not see an inequality for $z$'s immediately, we could come to it by minimizing $\sum y_i=\sum z_i/x_i$ subject to $\sum x_i\leqslant 1$.

3) Thus the problem restates as $\sum \sqrt{z_i}\leqslant 1$, we need to prove $(\sum z_i)^{2c-1}\leqslant \sum z_i^c$. Now make the inequality homogeneous, that is, write a (stronger) homogeneous in $z$'s inequality $$\left(\sum z_i\right)^{2c-1}\leqslant \left(\sum z_i^c\right)\left(\sum \sqrt{z_i}\right)^{2c-2}.$$

Ok, after this standard preparation we get a pure Hölder inequality $$\left(\sum a_i\right)^\alpha\left(\sum b_i\right)^\beta\geqslant \left(\sum a_i^{\frac{\alpha}{\alpha+\beta}} b_i^{\frac{\beta}{\alpha+\beta}}\right)^{\alpha+\beta} $$ for $\alpha=1,\beta=2c-2$, $a_i=z_i^c,b_i=\sqrt{z_i}$.

$\endgroup$
2
$\begingroup$

$\newcommand{\ep}{\epsilon} \newcommand{\ga}{\gamma} \newcommand{\la}{\lambda} \newcommand{\Si}{\Sigma} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\operatorname{\mathsf E}} \newcommand{\PP}{\operatorname{\mathsf P}}$

Without loss of generality (wlog), $c>1$. Let us show a bit more: \begin{equation} M_{n,w}:=\inf\{\sum_1^n(x_i y_i)^c\colon (x,y)\in S_{n,w}\}\ge w^{2c-1} \tag{1} \end{equation} where \begin{multline*} S_{n,w}:=\{(x,y)\colon x=(x_1,\dots,x_n),\ y=(y_1,\dots,y_n),\ x_i\ge0,\ y_i\ge0\ \forall i,\ \\ \sum_1^n x_i\le1,\ \sum_1^n y_i\le1,\ \sum_1^n x_i y_i=w\}. \end{multline*} Let $W_n:=\{w\ge0\colon S_{n,w}\ne\emptyset\}$. Clearly, the inf in (1) is attained for all $w\in W_n$, and that inf equals $\infty$ if $w\notin W_n$ -- in which case (1) is trivial.

Let us prove (1) by induction in $n$. For $n=1$, (1) is obvious. Let $n\ge2$. If $M_n$ is attained at some $x,y$ such that $x_jy_j=0$, then wlog $j=n$ and we may remove the $n$th coordinate from both $x$ and $y$ and thus reduce the problem to showing that $M_{n-1,w}\ge0$. So, by induction, wlog \begin{equation} x_iy_i>0\tag{2} \end{equation} for all $i=1,\dots,n$. So, wlog the minimizer $(x,y)$ satisfies the Lagrange equations \begin{equation} (x_i y_i)^{c-1}y_i=\la y_i+\mu,\quad (x_i y_i)^{c-1}x_i=\la x_i+\nu \tag{3} \end{equation} for some real $\la,\mu,\nu$ and all $i$. Multiplying $(x_i y_i)^{c-1}y_i=\la y_i+\mu$ by $x_i$ amd $(x_i y_i)^{c-1}x_i=\la x_i+\nu$ by $y_i$, and then subtracting the results, we get \begin{equation} \mu x_i=\nu y_i \tag{4} \end{equation} for all $i$.

If $\mu=\nu=0$, then (2) and (3) yield $x_iy_i=w/n$ for all $i$. By Cauchy--Schwarz, $\sqrt{nw}=\sum_1^n\sqrt{x_iy_i}\le\sqrt{\sum x_i\,\sum y_i}\le1$, so that $nw\le1$. So, $M_{n,w}=\sum_1^n(x_i y_i)^c=w^c/n^{c-1}\ge w^{2c-1}$, as desired.

It remains to consider the case when it is not true that $\mu=\nu=0$. Then, by (4), wlog $y_i=tx_i$ for some $t\in(0,1]$ and all $i$. In this case, inequality (1) follows by H\"older's inequality for the sub-probability measure $\ga$ on the set $\{1,\dots,n\}$, defined by the formula $\ga(\{i\})=x_i$ for all $i$, with $x(i):=x_i$ and $y(i):=y_i=tx_i$: \begin{multline*} \sum_1^n x_i y_i=t\int x\,d\ga\le t\Big(\int x^{2c-1}d\ga\Big)^{\frac1{2c-1}} \Big(\int d\ga\Big)^{\frac{2c-2}{2c-1}} \\ \le t\Big(\int x^{2c-1}d\ga\Big)^{\frac1{2c-1}} =t\Big(\sum_i x_i^{2c}\Big)^{\frac1{2c-1}} \\ =t^{\frac{c-1}{2c-1}}\Big(\sum_i (x_i y_i)^c\Big)^{\frac1{2c-1}} \le\Big(\sum_i (x_i y_i)^c\Big)^{\frac1{2c-1}}, \end{multline*} as desired.

As is oftentimes the case in such situations, it may be possible to distill this proof to get rid of using Lagrange multipliers. On the other hand, using Lagrange multipliers one can basically just compute the answer, with no ingenuity required.

$\endgroup$
1
  • $\begingroup$ I have added the little remaining details. $\endgroup$ Mar 25, 2018 at 0:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.