21
$\begingroup$

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

$\endgroup$
1

3 Answers 3

16
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Where does the first $\geq$ sign in your favorite proof come from? (I've removed a ` accent that I expect to be a fluke.) $\endgroup$ Jun 20, 2022 at 19:36
  • 1
    $\begingroup$ Ah, you replace $g\left(x_2\right)$ by $\dfrac{1}{2}\left(g\left(x_1\right) + g\left(x_2\right)\right)$ by symmetrization, then apply AM-GM. Probably worth a comment :) $\endgroup$ Jun 20, 2022 at 19:40
21
$\begingroup$

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).

$\endgroup$
1
  • $\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, 2014 at 16:43
5
$\begingroup$

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

$\endgroup$
7
  • 1
    $\begingroup$ On the 2nd line of the computation, you have three $\int$ signs but only two variables. Is there a typo? $\endgroup$ Jun 26, 2022 at 14:03
  • $\begingroup$ @darijgrinberg I confess that I am having trouble parsing these integrals, even in the first line of the computation: g is defined by integrating out the 2nd variable of f, but then where does g(y) come frome? $\endgroup$
    – Yemon Choi
    Apr 3, 2023 at 18:41
  • 1
    $\begingroup$ @YemonChoi f(x,y) is symmetric, i.e., f(x,y)=f(y,x). The function g is hence obtained by integrating f with one of the two variables. You can easily make it asymmetric though. $\endgroup$
    – Joonkyung
    Apr 5, 2023 at 6:57
  • $\begingroup$ @darijgrinberg I used single integral for averaging over all variables. $\endgroup$
    – Joonkyung
    Apr 5, 2023 at 6:57
  • $\begingroup$ In the original question it does not say that f is symmetric, and you can see in fedja's proof that he does not make this assumption. The original question is stated independently of the context of graph densities or graphons. $\endgroup$
    – Yemon Choi
    Apr 5, 2023 at 11:25

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.