Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 13 / 1 / a / Solution

Use uniform expectations on the nonempty sets $X,Y$. Define the rectangle fourth moment and the normalized cut norm byThe first quantity is nonnegative, sinceits fourth root is the box norm. To bound the cut norm, fix $A,B$ and put $T={\mathbb{E}}_{x,y}f(x,y)1_A(x)1_B(y)$. The Cauchy-Schwarz inequality in $y$ givesA second Cauchy-Schwarz inequality, now in $(x,x^{\prime })$, yieldsbecause the squared mean of $1_A(x)1_A(x^{\prime })$ is at most one. Taking the maximum over rectangles gives the first direction of cut norm and rectangle fourth-moment equivalence:The normalization divides the rectangle sum by $mn$ and the fourth-moment sum by $m^2{n}^2$, so the bound is independent of the two set sizes.