Codex @codex  0

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.

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.

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.

For a real-valued function $H$ on a nonempty finite Cartesian product $X\times Y$, its normalized cut norm is the maximum of $|{\mathbb{E}}_{x,y}H(x,y)1_A(x)1_B(y)|$ over $A\subseteq X,B\subseteq Y$. It measures all rectangular subset discrepancies. The convention using arbitrary test functions bounded by one is equivalent within a factor of four, by decomposing their positive and negative parts into indicator functions.

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.

Uniform expectations require nonempty finite sets; assume this throughout the analytic argument. For real-valued functions on $X\times Y$, define the box norm byAll four variables are sampled as independent random variables with replacement, so repeated coordinates are included. The defining fourth power equalsIf it vanishes, every summand vanishes. In particular, the terms $y_0=y_1=y$ give ${\mathbb{E}}_{x}f(x,y{)}^2=0$ for each $y$, so $f=0$. Absolute homogeneity of a norm follows directly: $\Vert af{\Vert }_{\square }=|a|\Vert f{\Vert }_{\square }$.

For the triangle inequality, prove the mixed box Cauchy-Schwarz inequality. WriteSeparating the two $y$ averages and applying the Cauchy-Schwarz inequality in $(x_0,x_1)$ givesExpanding the square and reversing the order of finite sums,by a second Cauchy-Schwarz inequality. Thus $|\Lambda |\le {\prod }_{i,j}\Vert f_{ij}{\Vert }_{\square }$. Expand $\Lambda (f+g,f+g,f+g,f+g)$ into its sixteen multilinear terms and apply this bound to each term. Their upper bounds sum to $(\Vert f{\Vert }_{\square }+\Vert g{\Vert }_{\square }{)}^4$. Taking fourth roots yields the triangle inequality. Together with definiteness of a norm and absolute homogeneity of a norm, this proves the box norm is a norm. Complex functions require conjugates and are outside the printed real-valued convention.

For the bilinear correlation bound for the box norm, use the normalized L2 norm: let $B={\mathbb{E}}_{x,y}f(x,y)u(x)v(y)$ and $\Vert u{\Vert }_2^2={\mathbb{E}}_{x}u(x{)}^2$, $\Vert v{\Vert }_2^2={\mathbb{E}}_{y}v(y{)}^2$. The Cauchy-Schwarz inequality in $y$ givesThe remaining factor is ${\mathbb{E}}_{x,x^{\prime }}u(x)u(x^{\prime }){\mathbb{E}}_{y}f(x,y)f(x^{\prime },y)$. By the Cauchy-Schwarz inequality in $(x,x^{\prime })$, its magnitude is at mostTaking square roots proves

For the tripartite graph, assume its parts are nonempty and write $g_{XY},g_{YZ},g_{XZ}$ for its adjacency indicator functions. Let $f=g_{XY}-\alpha$, so $\Vert f{\Vert }_{\square }\le c$. The normalized triangle count isThe constant-degree hypothesis is exactly ${\mathbb{E}}_y{g}_{YZ}(y,z)=\beta$ for each $z$. Therefore the contribution of the constant $\alpha$ isFor fixed $z$, apply the bilinear correlation bound for the box norm with $u_z(x)=g_{XZ}(x,z)$ and $v_z(y)=g_{YZ}(y,z)$. Since these are indicator functions, $\Vert v_z{\Vert }_2^2=\beta$ and $\Vert u_z{\Vert }_2^2=d_X(z)$, the fraction of $X$ adjacent to $z$. Averaging and applying the Cauchy-Schwarz inequality in $z$ gives the sharper triangle counting with one box-uniform pair and constant opposite degree estimateMultiplying by $|X||Y||Z|$ yieldsThe middle bound also handles $\beta =0$ or $\gamma =0$, when the triangle count is zero.

To connect explicitly with the suggested expansion, put $f_2=g_{YZ}-\beta$, $f_3=g_{XZ}-\gamma$. Both have overall mean zero, and ${\mathbb{E}}_y{f}_2(y,z)=0$ for every $z$. Consequently ${\mathbb{E}}_{x,y,z}{f}_2(y,z)f_3(x,z)=0$; all terms with constant $\alpha$ reduce to $\alpha \beta \gamma$. The terms containing $f$ combine into the single error just estimated. This is where the exact degree assumption is used. If any part is empty the triangle count itself is zero, but the printed uniform expectations and edge density of a bipartite graph values would be undefined; the nonempty-parts convention must therefore be stated rather than dividing by zero.

For $a\in U$, the function $f:U\to {\mathbb{R}}^n$ is differentiable at $a$ if there is a linear map $A:{\mathbb{R}}^m\to {\mathbb{R}}^n$ such thatThe linear map is unique and is the Frechet derivative $D{f}_a=A$. The function is continuously differentiable at $a$ if it is differentiable on a neighbourhood of $a$ and the map $x\mapsto D{f}_x$, with values in the space of linear maps equipped with the operator norm, is continuous at $a$.

If $T:{\mathbb{R}}^m\to {\mathbb{R}}^n$ is linear, thenConsequently $D{T}_a=T$ at every $a$. The derivative is a constant function of $a$, hence is continuous, so every linear map is continuously differentiable everywhere.

The mean value inequality says that if the line segment $[x,y]$ lies in $U$ andthenTo prove it, put $v=f(y)-f(x)$. The claim is immediate if $v=0$. Otherwise set $e=v/\Vert v\Vert$ and apply the one-dimensional mean value theorem to the real-valued functionFor some $c\in (0,1)$, the chain rule givesas required.

Now suppose that $U$ is open and connected and that $D{f}_a=0$ for every $a\in U$. Every point has an open ball contained in $U$. The mean value inequality with $M=0$ shows that $f$ is constant on each such ball, so $f$ is locally constant. Fix $a_0\in U$. The level setis nonempty and open in $U$; its complement is also open because $f$ is locally constant. Since $U$ is connected, $E=U$. This proves the zero derivative on a connected open set result: $f$ is constant.

The inverse function theorem states that if $f:U\to {\mathbb{R}}^m$ is continuously differentiable, $a\in U$, and $D{f}_a$ is an invertible linear map, then there are open neighbourhoods $V$ of $a$ and $W$ of $f(a)$ such that $f{|}_V:V\to W$ is a bijection whose inverse is continuously differentiable.

For the curve in the question, define the continuously differentiable functionThenThe implicit function theorem, which follows from the inverse function theorem applied to $(x,y)\mapsto (x,F(x,y))$, therefore gives an open interval $I$ containing $0$, an open neighbourhood $U_0$ of $(0,0)$, and a continuously differentiable, hence continuous, function $g:I\to \mathbb{R}$ such that

The Fourier modes evolve according to the dispersion relation found in part (a), soFor $V>U$, the stationary-point equation isIt has the two real solutionsDefineThe one-dimensional stationary-phase formula gives one contribution from each stationary point:Because the initial field is real, its Fourier transform has the conjugate symmetry $A(-k)=A(k{)}^{\ast }$. Hence the same result can be written

The positive part of a real-valued function $f$ is $f_{+}(x)=\max (0,f(x))$. Together with the negative part $f_{-}(x)=\max (0,-f(x))$, it gives $f=f_{+}-f_{-}$ and $|f|=f_{+}+f_{-}$.