Is there a "Cauchy-Schwarz proof" of the following inequality?

Theorem. Given $f \colon [0,1]^2 \to [0,1]$, one has $$ \int_{[0,1]^4} f(x,y)f(z,y)f(z,w) \, dxdydzdw \geq \left(\int_{[0,1]^2} f(x,y) \, dxdy\right)^3. $$

Background. This inequality is due to Blakley and Roy (1965). In fact, they proved even more, namely when the LHS corresponds to a path of length $k$ (above $k=3$) and the RHS is $(\int f)^k$.

This is a special case of a more general Sidorenko's conjecture, which claims that $t(H,W) \geq (\int W)^{e(H)}$ for any bipartite graph $H$. The general case of Sidorenko's conjecture is still open. See, e.g., this note by Conlon, Fox, and Sudakov (although there has been some other progress since then).

Szegedy and Li gives a different proof of the above inequality, using convexity of the logarithm function.

Also see the paper of Kim, Lee, and Lee for another approach.

On page 28 of Lovasz' book on graph limits, it states this inequality without proof, and then says

... and this is already quite hard, although short proofs with a tricky application of the Cauchy–Schwarz inequality are known.

So my question is: how does one prove the inequality above using Cauchy-Schwarz?

Update: It has been shown that there is no vanilla sum-of-squares proof of the inequality https://arxiv.org/abs/1812.08820


Before giving a very short Cauchy-Schwarz inequality proof for the 3-edge path (can be done in a similar fashion for any tree), let me comment on the authorship of the inequality in question.

In 1959, Mulholland and Smith https://doi.org/10.2307/2309342 proved that for any symmetric non-negative matrix $A$ and any non-negative vector $z$ of the same order $$ (z^{*} A^k z) \cdot (z^{*} z)^{k-1} \; \geq \; (z^{*} A z)^k \; , $$ where equality takes place if and only if $z$ is an eigenvector of $A$ or a zero vector.

Almost at the same time, Atkinson, Watterson and Moran https://doi.org/10.1093/qmath/11.1.137 proved $ nm \cdot s(A A^{*} A) \; \geq \; s(A)^3 $ for an asymmetric non-negative $(n \times m)$-matrix $A$, and conjectured that a similar inequality holds for a $k$-edge path with $k>3$. (Here $s(A)$ denotes the sum of entries of $A$). They presented this inequality in both matrix and integral form.

Being unaware of these results, Blakley and Roy in 1965 published theirs: https://doi.org/10.1090/S0002-9939-1965-0184950-9.

Here is my favorite proof of the "Mulholland-Smith / Atkinson-Watterson-Moran / Blakley-Roy inequality". Let $g(x) = \int f(x,y) \: dy$. Then \begin{multline*} \int\int\int\int f(x_1,y_1) \; f(x_2,y_1) \; f(x_2,y_2) \; dx_1 \; dx_2 \; dy_1 \; dy_2 \\ \shoveleft = \int\int\int f(x_1,y_1) \; f(x_2,y_1) \; g(x_2) \; dx_1 \; dx_2 \; dy_1 \\ \shoveleft \geq`\int\int\int g^{1/2}(x_1) \; f(x_1,y_1) \; f(x_2,y_1) \; g^{1/2}(x_2) \; dx_1 \; dx_2 \; dy_1 \\ \shoveleft = \int \left( \int g^{1/2}(x) \; f(x,y) \; dx \right)^2 \; dy \\ \shoveleft \geq \left( \int\int g^{1/2}(x) \; f(x,y) \; dx \; dy \right)^2 \; = \; \left( \int g^{1/2}(x) \; g(x) \; dx \right)^2 \\ \shoveleft \geq \left( \int g(x) \; dx \right)^3 \; = \; \left( \int f(x,y) \; dx \; dy \right)^3 \; . \\ \end{multline*}


although short proofs with a tricky application of the Cauchy–Schwarz inequality are known.

Erm... What's the point of using such high-tech as Cauchy-Schwarz on an elementary algebra problem?

WLOG $\iint f(x,y)dxdy=1$. Put $A(x)=\int f(x,y)dy-1$, $B(y)=\int f(x,y)dx-1$, $C(x,y)=f(x,y)-A(x)-B(y)-1$. Then $\int A(x)dx=0$, $\int B(y)dy=0$ and $C$ integrates to $0$ in each variable with the other one fixed (this is, probably, the first decomposition one should try in multilinear double integral inequalities).

Now $f(x,y)f(z,y)f(z,w)=(1+A(x)+B(y)+C(x,y))(1+A(z)+B(y)+C(z,y))(1+A(z)+B(w)+C(z,w))$. Integrating by Fubini as much as possible, we see that we just need to show that
$$ \int A(x)^2dx+\int B(y)^2dy+\iint A(x)C(x,y)B(y)dxdy\ge 0 $$ Of course, we want to get an integral of a non-negative quantity here. The ranges are $A,B\ge -1$, $C\ge -1-A-B$. Note that we can add terms of the kind $C H(A)$, $C H(B)$ any time we want because they'll integrate to $0$ anyway. Our expression is linear in $C$. Thus, we need to find a function $H$ such that $H(A)+H(B)+ AB\ge 0$ (so the $+\infty$ end is OK) and $A^2+B^2+(-1-A-B)(H(A)+H(B)+AB)\ge 0$ up to something that integrates to $0$, so we can ignore $(1+A+B)AB$, $AH(B)$ and $BH(A)$ too. Thus, we need $(1+x)H(x)\le x^2$ anyway ($A=B=x$), so the best we can hope for is $H(x)=\frac{x^2}{1+x}$. Now we are lucky if
$$ \frac{A^2}{1+A}+\frac{B^2}{1+B}+AB\ge 0 $$ when $a=1+A,b=1+B\ge 0$. This suggests an obvious change of variable and we get $$ a-2+\frac 1a+b-2+\frac 1b+ab-a-b+1\ge 0\, $$ so $$ \frac 1a+\frac 1b+ab\ge 3\, $$ which is AM-GM for three variables (I also find it slightly more natural than C-S, which is AM-GM for 2 variables, because, after all, we have a trilinear integral).

  • $\begingroup$ Actually, after routine modifications, that works on every tree and some (but not yet all) bipartite graphs with cycles as well. $\endgroup$ – fedja Dec 10 '14 at 16:43

Let me add a possibly shortest proof of the inequality you asked, although not by Cauchy-Schwarz. Following Sasha's notation, let $g(x)=\int f(x,y) dy$. Then by Holder's inequality, \begin{align*} \int f(x,y)f(y,z)f(z,w) &= \int g(y)f(y,z)g(z)\\ &=\int g(y)f(y,z)g(z) \int \frac{f(y,z)}{g(y)} \int \frac{f(y,z)}{g(z)}\\ &\geq \left(\int f(y,z) \right)^3. \end{align*}

As both of us already knew, it is proved that the flag algebra caculus does not give the answer for this inequality. Let me also add the reference for those readers who didn't know the recent result by Blekherman, Raymond, Singh, and Thomas: https://arxiv.org/pdf/1812.08820.pdf


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.