Box norm ($\Vert f{\Vert }_{\square }$)

For nonempty finite sets $X,Y$ and a real-valued function $f$ on their Cartesian product, using uniform expectations, defineThis equals ${\mathbb{E}}_{y,y^{\prime }}({\mathbb{E}}_{x}f(x,y)f(x,y^{\prime }){)}^2$. Hence it is nonnegative, and vanishing forces $f=0$ by taking $y=y^{\prime }$. Absolute homogeneity and the box Cauchy-Schwarz inequality establish that it is a norm. This formula concerns real-valued functions; complex functions require appropriate complex conjugates in the definition.

With uniform expectations and real-valued functions,Apply the Cauchy-Schwarz inequality first in $y$. Expand the remaining square, and apply the Cauchy-Schwarz inequality in $(x,x^{\prime })$ to $u(x)u(x^{\prime })$ and ${\mathbb{E}}_{y}f(x,y)f(x^{\prime },y)$. Their squared averages are $\Vert u{\Vert }_2^4$ and $\Vert f{\Vert }_{\square }^4$, respectively.

Let a tripartite graph have nonempty parts $X,Y,Z$, pair edge density of a bipartite graph values $\alpha ,\beta ,\gamma$ on $XY,YZ,XZ$, and $\Vert G(X,Y)-\alpha {\Vert }_{\square }\le c$. If every $z\in Z$ has exactly $\beta |Y|$ neighbors in $Y$, its normalized triangle count $\tau$ obeysThe constant-degree assumption makes the contribution of the constant $\alpha$ exactly $\alpha \beta \gamma$. For each fixed $z$, apply the bilinear correlation bound for the box norm to the indicator functions of its two vertex neighbourhoods. Their squared $L^2$ norms are $\beta$ and the relative $X$-degree of $z$. Average over $z$ and use the Cauchy-Schwarz inequality to bound the mean square root of that degree by $\sqrt{\gamma }$.

For four real-valued functions on a finite Cartesian product, let $\Lambda (f_{00},f_{01},f_{10},f_{11})={\mathbb{E}}_{x_0,x_1,y_0,y_1}{\prod }_{i,j=0}^1{f}_{ij}(x_i,y_j)$. Repeated Cauchy-Schwarz inequalities giveFirst separate the two $y$ averages and apply Cauchy-Schwarz inequality in $(x_0,x_1)$. Each resulting squared factor is ${\mathbb{E}}_{y,y^{\prime }}({\mathbb{E}}_{x}f(x,y)f(x,y^{\prime }))({\mathbb{E}}_{x}g(x,y)g(x,y^{\prime }))$, bounded by $\Vert f{\Vert }_{\square }^2\Vert g{\Vert }_{\square }^2$ by another Cauchy-Schwarz inequality. Expanding the four factors of $f+g$ and applying this inequality to each of the sixteen terms gives the triangle inequality for the box norm.