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

For nonempty finite sets $X,Y$ and a function $f:X\times Y\to \mathbb{C}$ on their Cartesian product, using uniform expectations, defineThis equals ${\mathbb{E}}_{y,y^{\prime }}|{\mathbb{E}}_{x}f(x,y)\overline{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. For a real-valued function the complex conjugates can be omitted. The bilinear correlation bound for the box norm also holds for complex functions.

Give every entry of an $m$ by $n$ matrix an independent uniformly random sign. A four-entry rectangle product has expectation zero unless its two row indices coincide or its two column indices coincide; in those cases it is one. Counting the union of these diagonal cases gives $m{n}^2+m^{2}n-mn$ before normalization. Thus some sign matrix has box norm fourth power at most the displayed expectation, and its cut norm tends to zero when both dimensions tend to infinity.

For a real function $f$ bounded by one on a finite Cartesian product, the fourth power of its box norm is the mean of $f(x,y)f(x,y^{\prime })f(x^{\prime },y)f(x^{\prime },y^{\prime })$. Two applications of the Cauchy-Schwarz inequality bound every rectangular discrepancy by the box norm. Conversely, decompose each bounded real test function into positive and negative parts and use the layer cake representation. Its bilinear pairing with $f$ is at most four times the cut norm. Applying this to the row and column tests furnished by fixed $x^{\prime },y^{\prime }$ bounds the fourth moment by four times the cut norm. These dimension-independent estimates make the two notions of small discrepancy equivalent.

For a complex function on $X_1\times X_2\times X_3$, its eighth power is the average of the conjugated product over the eight vertices of a coordinate cube. Three successive applications of the Cauchy-Schwarz inequality show that it bounds correlation with a product of three bounded functions, each omitting one coordinate. This is the analytic estimate behind the tetrahedron counting lemma.

For a real function $g$ on $X\times Y\times Z$ and functions $a(y,z),b(x,z),c(x,y)$ bounded in absolute value by one,First apply Cauchy-Schwarz inequality in $(y,z)$ to remove $a$, duplicating $x$. Apply it in $(x_0,x_1,z)$ to remove $b(x_0,z)b(x_1,z)$, duplicating $y$. Finally apply it in $(x_0,x_1,y_0,y_1)$ to remove the four $c$ factors, duplicating $z$. The resulting eighth-power bound is exactly the eight-factor average defining the three-dimensional box norm. Functions depending on just one coordinate, or constants, can be incorporated in any of the three pair factors.

For a real-valued function $H$ on a nonempty finite Cartesian product, let $T_{H}v(x)={\mathbb{E}}_{y}H(x,y)v(y)$ with uniform inner products. The box norm obeys $\Vert H{\Vert }_{\square }^4=\mathrm{Tr}((T_H{T}_H^{\ast }{)}^2)={\sum }_j{\sigma }_j^4$, where ${\sigma }_j$ are its singular values. For a biregular graph this separates the constant component ${\gamma }^4$ from the other fourth powers.

With uniform expectations and real or complex 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.