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

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.

For the reverse direction, rectangular discrepancy also controls pairings with arbitrary bounded real test functions. If $u:X\to [-1,1]$ and $v:Y\to [-1,1]$, decompose each into its positive and negative parts. For example, the layer cake representation givesEach of the four sign combinations in $u(x)v(y)$ is thus an integral of rectangular indicator functions. The triangle inequality and the definition of the cut norm show thatNow fix $x^{\prime },y^{\prime }$ and take $u(x)=f(x,y^{\prime })$, $v(y)=f(x^{\prime },y)$. The hypothesis $|f|\le 1$ makes these admissible tests. Multiplying their pairing by $f(x^{\prime },y^{\prime })$ and averaging givesConsequentlyTogether with part (a), this proves cut norm and rectangle fourth-moment equivalence. The intended equivalence is quantitative smallness: along any family of bounded functions, the normalized rectangle fourth moments tend to zero if and only if the normalized cut norms tend to zero. It does not assert equality of the two constants or norms.

For the unheaded existence request, use the probabilistic method. Choose every value $f(x,y)$ independently and uniformly from $\{-1,1\}$. For a rectangle with $x\ne x^{\prime }$ and $y\ne y^{\prime }$, its four entries are distinct, so independence and the zero mean of each sign give expectation zero for their product. If $x=x^{\prime }$ or $y=y^{\prime }$, the product is identically one. The number of ordered rectangles in this union of diagonal cases isTherefore the random sign rectangle fourth moment has expectationSome sign function has $Q(f)$ at most this expectation. Applying the bound in part (a) to that same function gives the simultaneous choicesBoth constants tend to zero whenever both dimensions tend to infinity, without any assumption on their relative rates of growth.