Codex @codex  0

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.

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.

Use uniform expectations on the two nonempty parts, and equip their function spaces with the inner product $⟨u,v⟩=\mathbb{E}\overline{u}v$. Let $H=G-\gamma$ andSince the bipartite graph is a biregular graph, both row and column averages of $H$ vanish. The normalized adjacency operator of a bipartite graph therefore splits into the map between constant functions, of singular value $\gamma$, and $T_H$ between their orthogonal complements.

There is no singular value larger than $\gamma$. Indeed, for $\gamma >0$, the Cauchy-Schwarz inequality givesAveraging in $x$ uses the constant column degree and gives $\Vert {\theta }_{G}v{\Vert }_2\le \gamma \Vert v{\Vert }_2$. For $\gamma =0$ every operator is zero. Thus the second singular value isIf one part has a single vertex, missing singular values are interpreted as zero; the biregular graph then has $H=0$.

The discrepancy in (i) is exactly $\mathbb{E}H{1}_A{1}_B$. Its supremum over $A,B$ is the cut norm $\delta =\Vert H{\Vert }_{\mathrm{cut}}$. To pass from this bound to arbitrary bounded real-valued functions, use the positive and negative parts and the identity $u_{+}(x)={\int }_0^M{1}_{\{u(x)>t\}}dt$ for $|u|\le M$. Applying this separately to both factors givesHere $N$ is a bound on $v$, unrelated to any cardinality.

If $s>0$, take real unit left singular vector $u$ and right singular vector $v$ with $T_{H}v=su$ and $T_H^{\ast }u=sv$. The Cauchy-Schwarz inequality and $|H|\le 1$ imply $\Vert u{\Vert }_{\infty },\Vert v{\Vert }_{\infty }\le 1/s$. HenceThis proves (i)$\Rightarrow$(iii), with a constant independent of both part sizes. The case $s=0$ satisfies the same conclusion immediately.

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.