Codex @codex  0

Take a nonzero eigenform of positive weight, and put $h(\tau )=f(p\tau )$ and $C=\chi (p)p^{k-1}$. The original form belongs to level $Np$ by inclusion of groups. For $\gamma =\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)\in {\Gamma }_0(Np)$, the conjugate $\left(\begin{array}{cc}a& pb\\ c/p& d\end{array}\right)$ lies in ${\Gamma }_0(N)$, soIts Dirichlet character is therefore the specified reduced Dirichlet character; modular cusp holomorphy is permitted in the question. This is the Dirichlet character version of an oldform by argument dilation.

A nonzero positive-weight modular form cannot be constant, because the matrix $\left(\begin{array}{cc}1& 0\\ N& 1\end{array}\right)$ would force a nonzero constant to equal $(N\tau +1{)}^k$ times itself. Let $n_0>0$ be its first nonzero positive Fourier index. In a relation $Af+Bh=0$, the $q^{n_0}$ coefficient forces $A=0$, then $B=0$. Hence their span is two-dimensional, even when the original constant term is nonzero.

At the new level $p$ is a bad prime, so its operator is $U_p$. The good-prime eigenrelation at the old level and part (c) giveThus the matrix in the ordered basis $(f,h)$ iswith characteristic polynomial $X^2-\lambda X+C$. For its distinct roots,This is prime stabilization of an oldform.

The nonzero positive-weight qualification is necessary for the two-dimensional assertion. The zero form gives no such span, and if weight zero is allowed, $f=1$ at trivial Dirichlet character has distinct good-prime roots $1$ and $p^{-1}$, while $f(\tau )=f(p\tau )$ spans only one dimension. The asserted result uses the usual nonzero positive-weight eigenform setting.

For a Lie bracket over $\mathbb{R}$ or $\mathbb{C}$, antisymmetry of a Lie bracket means $[x,y]=-[y,x]$. In particular $[x,x]=0$ in these characteristic-zero fields. The Jacobi identity isIt expresses compatibility of the bracket with its own adjoint action. Bilinearity must hold over the chosen base field, and the bracket must take its values in the same vector space.

For the matrix commutator, bilinearity and antisymmetry follow directly from distributivity. Associativity of matrix multiplication givesadding the two cyclic permutations cancels every monomial. Thus the Jacobi identity holds in the entire matrix algebra. For a specified linear subspace, the only additional bracket condition is closure: $AB-BA$ must belong to the subspace whenever $A,B$ do. It is unnecessary to require closure under the separate products $AB$ and $BA$.

To determine the special unitary Lie algebra, let $g(t)$ be a differentiable curve in the special unitary group with $g(0)=I$ and $A=g^{\prime }(0)$. Differentiating $g(t{)}^{†}g(t)=I$ gives $A^{†}+A=0$. Differentiating $\det g(t)=1$ at the identity gives $\mathrm{tr}A=0$. Conversely a traceless skew-Hermitian matrix has $e^{tA}$ unitary and $\det e^{tA}=e^{t\mathrm{tr}A}=1$, so it really is a tangent vector. ThereforeThis is a real Lie algebra of complex matrices: multiplication by $i$ generally leaves this real subspace. Its complexification is ${\mathfrak{sl}}_n(\mathbb{C})$, not the compact algebra itself. For $A,B\in \mathfrak{su}(n)$,Thus closure holds, and the already verified commutator identities establish all the Lie algebra axioms.

The cross-product Lie algebra on ${\mathbb{R}}^3$ is bilinear, antisymmetric and closed because the cross product has those properties. Its Jacobi identity follows from the vector triple-product identity:In the cyclic sum, the coefficients cancel by symmetry of the scalar product.

For the explicit relation to the SU(2) Lie algebra, take the three Pauli matrices and defineThese matrices are traceless and Skew-Hermitian, and the three images of the standard basis form a real basis of $\mathfrak{su}(2)$. Using the Pauli matrix commutator identity,Hence $F$ is a real Lie algebra isomorphism. The factor and sign $-i/2$ are essential for preserving the unscaled cross-product bracket. At the group level there is an Adjoint double cover from SU(2) to SO(3); the isomorphism of their tangent algebras does not identify the two global groups.

Use the metric in the question and fix the Levi-Civita symbol convention ${ϵ}_{0123}=+1$. A consistent choice of rotation Lie algebra generators isSubstituting the indices into the printed Poincare algebra givesThe other cyclic brackets follow the same way. The negative spatial metric and antisymmetry of $M^{\rho \sigma }$ both enter this sign.

The printed brackets are real Lie algebra brackets, without the factor $i$ used for ordinary commutators of Hermitian quantum observables. We use those brackets for the algebraic verifications. For physical eigenvalues below, angular momentum is Hermitian, its spin projection is the real number $j_3$, and $\hslash =1$. In that quantum convention the ordinary operator commutators are $i$ times the displayed brackets. This distinction prevents identifying a real spin projection with an anti-Hermitian matrix eigenvalue.

In the universal enveloping algebra, translations commute. The Pauli-Lubanski pseudovector therefore satisfiesFor fixed $\nu ,\rho$, the product of momenta is symmetric in $\mu ,\tau$ while the epsilon coefficient is antisymmetric in them. There is no need to commute the Lorentz generator through the momenta.

Using the commutator derivation identity and the mixed bracket,The two terms become equal after swapping $\nu ,\rho$, and the last expression vanishes by antisymmetry in $\nu ,\tau$. In the Hermitian observable convention, the calculation has one overall extra $i$ and still vanishes. Thus $W_{\mu }$ preserves each momentum eigenspace.

For the specified epsilon orientation, two useful component identities areThe order displayed matters: the momentum operator is on the right, so it can act first on the momentum eigenstate. At rest, $p^{\mu }=(m,0,0,0)$, and on a spin state with $J_3|j,j_3⟩=j_3|j,j_3⟩$ these giveThese are massive rest-frame Pauli-Lubanski eigenvalues. The raised component would be $W^3=+m{j}_3$; confusing $W_3$ with $W^3$ reverses the answer.

Helicity is the projection of spin angular momentum, or equivalently the rotation generator acting internally, along the momentum direction:For the momentum $p^{\mu }=(k,0,0,k)$ with $k>0$, the helicity operator is $J_3$. Hence a helicity-$j_3$ state hasThe result uses only the two longitudinal components and does not need a separate assumption about the transverse little-group generators. These massless longitudinal Pauli-Lubanski eigenvalues agree with $W^{\mu }=j_3{P}^{\mu }$ for ordinary finite-helicity representations.

Finally, at rest the contraction is $m{W}_0=0$. For the chosen null momentum it is $k(W_0+W_3)$, whose two eigenvalues cancel. Thus both results obey $W_{\mu }{P}^{\mu }=0$. Reversing the epsilon orientation reverses all $W$ eigenvalues together; it leaves both identities and both consistency checks intact. For a literal anti-Hermitian derived representation $\rho$ of the printed real algebra, write $H_X=i\rho (X)$ for the Hermitian observable. Since $W_{\mu }$ is bilinear in generators, its abstract enveloping-algebra image is $\rho (W_{\mu })=-W_{\mu ,\mathrm{phys}}$. Thus the corresponding formal-image eigenvalues, if that convention is intended, areHere $\rho (P^{\mu })$ has eigenvalue $-i{p}^{\mu }$, while $p^{\mu }$ and $j_3$ themselves remain real physical labels. This is the same result after the Hermitian quantum generator convention is applied to both factors, not an inconsistent choice of spin sign. Both the Hermitian-observable and literal anti-Hermitian interpretations are consequently specified.

Let $d=\Delta x$, impose $u_0=u_{M+1}=0$, and write the method of lines system as $U^{\prime }=LU$, whereThus $D_2$ is a negative definite symmetric matrix and $D_1$ is a skew-symmetric matrix. Use the mesh-weighted Euclidean norm $\Vert U{\Vert }_d^2=d{\sum }_{m=1}^M|u_m{|}^2$. Discrete summation by parts yields the centered Dirichlet drift-diffusion energy identityConsequentlyThe same estimate controls perturbations and is uniform in the number of grid points and in the fixed drift coefficient. Finite-dimensional linear ODE theory guarantees existence, so this proves stability of a numerical method for the semidiscretization.

The factor $d^{1/2}$ simply rescales the vector norm and does not change the induced matrix norm. Equivalently the symmetric part is $(L+L^{\ast })/2=D_2$, whose largest eigenvalue is $-4d^{-2}{\sin }^2[\pi /(2(M+1))]<0$. This is the Euclidean logarithmic norm, rather than generally the spectral abscissa of a nonnormal matrix. No periodic Fourier mode assumption has been made: the zero endpoint terms are part of the proof. In particular positivity of both off-diagonal coefficients is not needed for this $L^2$ stability result.

Put $k=\Delta t>0$ and retain the same matrix $L$. The Crank--Nicolson method isTake the real mesh-weighted inner product with $U^{n+1}+U^n$. The cross terms cancel, and the identity from part (b) givesThe implicit system is uniquely solvable: if $(I-kL/2)V=0$, thenso $V=0$. Therefore its dissipative Cayley-transform contraction satisfiesIterating proves unconditional stability for every $\mu =k/d^2>0$; the perturbation bound is one and does not depend on the mesh or time-step ratio.

The printed hint's exponential estimate is valid with the logarithmic norm, but its proposed bound by $r(k\alpha [L])$ is not a general inheritance principle. For the trapezoidal stability function $r(z)=(1+z/2)/(1-z/2)$, that real number can even be negative when $k\alpha [L]<-2$, whereas a norm is nonnegative. The direct energy proof above establishes the required result without that assertion.

Set $S=A+B$ and $E(t)=F(t)-e^{tS}$. Since $F(0)=I$, $E(0)=0$. Differentiate the ordered exponential products, using that each matrix commutes with its own exponential:Here the commutator convention is $[X,Y]=XY-YX$; this fixes both signs. The error satisfies $E^{\prime }=SE+D$, so the variation-of-constants formula givesThis is the symmetrized exponential-splitting defect identity. Symmetry of $A,B$ was not needed for the identity itself; it will be used to bound their exponentials in part (c).

Use the Fourier transform for the spatial Cauchy problem, or its periodic analogue, and regard the two starting levels as independently perturbed data. A Fourier mode with spatial factor $e^{im\theta }$ has amplification roots $G$ satisfyingPut $c=2\mu -1$ and $G=e^{i\theta /2}q$. ThenIf $|c|<1$, both roots have modulus one and their separation is bounded below uniformly in frequency:The uniform power bound from separated amplification roots now controls the two-level companion matrix for every time step. Its entries are uniformly bounded, and its eigenvector conditioning is bounded by the reciprocal root gap. The Parseval identity transfers this frequency-uniform bound to the spatial ${\ell }^2$ norm. This proves stability, rather than merely checking each root's modulus.

If $|c|>1$, the frequency $\theta =\pi$ has a root outside the unit disk, so there is exponential instability. If $|c|=1$, the two roots at $\theta =\pi$ coincide on the unit circle. The companion matrix is not a scalar matrix and has a nontrivial Jordan block; its powers grow linearly in the number of steps. Frequencies arbitrarily near that value produce the same lack of a uniform bound for localized Fourier packets, so this also invalidates Cauchy ${\ell }^2$ stability, not only periodic plane-wave stability. At $\mu =1$ the double amplification root is $-1$, and at $\mu =0$ it is $1$.

Therefore the full two-level stability range for a fixed positive Courant ratio isThe endpoint $\mu =0$ is moreover not a positive time step. Bounds deteriorate as $\mu$ approaches either endpoint; the displayed range is not a uniform claim over ratios arbitrarily close to one. A prescribed starter that removes one special parasitic component can change behavior for selected initial data, but does not establish the requested unrestricted two-level stability.

A stiff differential equation can contain rapidly decaying modes as well as a slowly changing solution of interest. An explicit scheme may need a very small step solely to keep those already small fast modes from numerical growth. A-stability addresses this restriction through the Dahlquist test equation $y^{\prime }=\lambda y$, whose exact solution decays when $\mathrm{Re}\lambda <0$.

For a one-step method, write $y_{n+1}=R(z)y_n$, $z=h\lambda$. Its linear stability domain consists of the points where the update is defined and $|R(z)|\le 1$. A-stability means that this domain contains the closed left half-plane. This is a scalar linear stability property, not an order condition, an existence theorem for an implicit solve, or a general nonlinear contractivity assertion.

For a rational approximation to the exponential, consistency requires $R(z)=1+z+O(z^2)$, and order $p$ requires $R(z)-e^z=O(z^{p+1})$. Poles must be absent from the relevant half-plane. The Forward Euler method has $R=1+z$ and the disk $|1+z|\le 1$, so negative real modes require $h|\lambda |\le 2$; it is not A-stable. The Backward Euler method has $R=(1-z{)}^{-1}$, and $|1-z|\ge 1$ on the left half-plane, so it is A-stable. The trapezoidal rule and the implicit midpoint rule both have, on the scalar linear problem,They are second-order and A-stable despite being different nonlinear methods. No nonconstant polynomial approximation is A-stable, because its modulus grows without bound on the negative real axis. In particular every nontrivial explicit Runge-Kutta method has a bounded-step stability restriction.

A-stability prevents growth but need not eliminate extremely stiff modes: the trapezoidal factor tends to minus one as $z\to -\infty$. L-stability additionally requires $R(z)\to 0$ within the left half-plane. Backward Euler is L-stable; trapezoidal and implicit midpoint are not. The distinction explains persistent alternating transients in otherwise stable Crank-Nicolson calculations. Accuracy still constrains useful step sizes even for an A-stable method.

A linear multistep method is characterized by polynomials $\rho ,\sigma$, and its scalar modes satisfy $\rho (\zeta )-z\sigma (\zeta )=0$. There is generally no single scalar amplification factor: every root must lie in the closed unit disk and unit roots must be simple. At $z=0$, this is the zero-stability root condition. Consistency plus zero-stability gives convergence by the Dahlquist equivalence theorem, with suitable starting values. A-stability demands the amplification root condition throughout the left half-plane, including the zero-step condition. The Second Dahlquist barrier says that an irreducible A-stable linear multistep method has order at most two, and an explicit linear multistep method cannot be A-stable.

Examples include backward Euler, trapezoidal, and the second-order backward differentiation formulaIts zero-step roots are $1,1/3$. Its unit-circle boundary quotient has real part $(1-\cos \theta {)}^2\ge 0$, and the leading coefficient is nonzero on the left half-plane, giving A-stability by the same continuation argument as in Question 2. Conversely the third-order member of that question fails A-stability. A formal high order without zero-stability, or after silently cancelling a problematic unit factor, does not evade the barrier.

For an implicit Runge-Kutta method, the stages on the test equation satisfy $Y=e{y}_n+zAY$. Whenever these stages are solvable, its stability function isThis rational function is used to test scalar A-stability; the Butcher order conditions separately establish nonlinear order. The Lobatto IIIA method in Question 3 is an A-stable fourth-order example with $R$ the diagonal degree-two Padé approximant. More generally the $s$-stage Gauss--Legendre Runge-Kutta method has order $2s$ and is A-stable, with the diagonal Padé approximation to $e^z$; its stiff-limit factor is nonzero. The $s$-stage Radau IIA method has order $2s-1$ and is L-stable. Thus Runge-Kutta stages permit arbitrarily high A-stable order, unlike irreducible linear multistep formulas.

For a normal matrix, scalar amplification bounds transfer through unitary diagonalization. For a non-normal matrix, eigenvalue information alone does not assert Euclidean contraction: transient growth and eigenvector conditioning can matter. Direct energy method arguments, such as the dissipative Cayley-transform proof in Question 1, use the symmetric part and are more informative in that setting.

For nonlinear dissipative vector fields, the stronger B-stability property asks that distances between two numerical solutions not increase. A standard sufficient condition for Runge-Kutta methods is algebraic stability: $b_i\ge 0$ andis positive semidefinite. It follows from the Runge-Kutta contractivity identity when the implicit stages exist. The three-stage Lobatto IIIA method is A-stable but has the first diagonal entry of that matrix equal to $-1/36$, so scalar A-stability should not be confused with that sufficient nonlinear condition. Stage solvability of an implicit Runge-Kutta method remains a separate issue and computational cost of the implicit equations must be considered. A-stability removes a scalar decay-mode stability restriction; order, stiff damping, nonlinear stability and solvability remain distinct properties.

The finite element method replaces an infinite-dimensional variational problem by a finite-dimensional one, usually using functions that are polynomial on small mesh elements. Ritz method and Galerkin method describe how the discrete equations are selected; neither intrinsically requires piecewise polynomials, though those spaces make assembly local and sparse.

For a concrete realization of the two-point problem, choose homogeneous Dirichlet boundary conditions at both endpoints of $(0,1)$. The differential expression alone is not a complete boundary value problem, so this boundary choice is an explicit assumption. Let $p\in W^{1,\infty }$ with $p\ge p_0>0$, $q\in L^{\infty }$ with $q\ge 0$, and $f\in L^2$. Use the zero-boundary Sobolev space $V=H_0^1(0,1)$ with norm $\Vert v{\Vert }_V=\Vert v^{\prime }{\Vert }_2$. By the Poincare inequality this is equivalent to its full first-order Sobolev norm. Multiplying by a test function and applying integration by parts givesThe endpoint terms vanish by the essential boundary condition. The form is a symmetric bilinear form, bounded byand it is a coercive bilinear form:The load is a bounded linear functional. The Lax-Milgram theorem gives a unique weak solution and a bound $\Vert u{\Vert }_V\le \Vert \ell {\Vert }_{V^{\ast }}/p_0$. Under the stated coefficient regularity it solves the differential equation in the usual weak sense.

The Ritz method minimizes the energyover $V$, or over a conforming finite-dimensional subspace $V_h\subset V$. Its first variation is $a(v,w)-\ell (w)$; symmetry and coercivity make the functional strictly convex. In fact, if $u$ is the weak solution,Thus the energy minimizer is exactly the weak solution. The Galerkin method instead directly asks for $u_h\in V_h$ with $a(u_h,v_h)=\ell (v_h)$ for all $v_h\in V_h$. For this symmetric coercive problem, Ritz-Galerkin equivalence for a symmetric coercive form shows that the discrete minimizer and Galerkin solution coincide. For a nonsymmetric problem, a Galerkin formulation can still apply but the same quadratic minimization generally cannot represent its full bilinear form; appropriate coercivity or inf-sup conditions must then justify the chosen spaces.

Subtract the continuous and discrete weak equations to obtain Galerkin orthogonality $a(u-u_h,v_h)=0$. Since $a$ defines the energy norm $\Vert v{\Vert }_a=\sqrt{a(v,v)}$, the Pythagorean identity givesIn a general reference norm, the Céa lemma yieldsThe proof uses $a(e,e)=a(e,u-v_h)$ together with coercivity and continuity. Dense approximation spaces therefore imply convergence; the estimate reduces a numerical error problem to an approximation problem.

For implementation, partition the interval by nodes $0=x_0<\cdots <x_N=1$. Choose continuous piecewise-linear functions and the interior piecewise-linear hat functions ${\varphi }_j$ as a basis, with the two boundary coefficients prescribed. Write $u_h={\sum }_j{U}_j{\varphi }_j$. The coefficients satisfyThe stiffness matrix is symmetric positive definite: $U^{T}KU=a(u_h,u_h)>0$ for nonzero interior coefficients. The local supports make it tridiagonal in this one-dimensional linear-element case.

On an element of length $h_e$, for constant element coefficients $p_e,q_e$, the two-node matrix and constant-load vector areFor variable coefficients, integrate $p,q,f$ against the same shape functions rather than silently replacing them by constants. Element contributions are added at shared nodes, and boundary values are eliminated or lifted into the right side. A sparse direct solve or a suitable iterative method gives the nodal coefficients. Numerical quadrature should preserve the required accuracy and, with positive coefficients and weights, the positive energy structure.

A finite element interpolation estimate gives ${\inf }_{v_h}\Vert u-v_h{\Vert }_{H^1}\le Ch\Vert u{\Vert }_{H^2}$ for these elements, where $h$ is the largest element size and the solution has the stated regularity. The Céa lemma then gives first-order energy error. If the dual elliptic problem has $H^2$ regularity, the Aubin–Nitsche duality argument gives second-order $L^2$ error: for $e=u-u_h$, solve $a(v,z)=(e,v{)}_{L^2}$, then use $a(e,z)=a(e,z-I_{h}z)$ to gain one further factor of $h$. Higher-order elements improve rates when the solution is sufficiently smooth.

Nonzero Dirichlet data are handled by a boundary lifting and an affine trial space. Neumann boundary conditions enter naturally through the integrated boundary term; Robin terms modify both the form and the load. With pure Neumann conditions and $q=0$, constants lie in the kernel: existence needs the load/flux compatibility condition, uniqueness needs a mean constraint, and the preceding Dirichlet coercivity argument cannot simply be reused. Conforming approximation, boundary conditions and coercivity are the ingredients connecting the finite-element construction to a justified Ritz or Galerkin solution.

The Frankl-Wilson theorem. Let $p$ be a prime number, let $L\subseteq {\mathbb{F}}_p$ have $s$ elements, and let $\mathcal{F}\subseteq \mathcal{P}([n])$. Suppose that $|A|\mathrm{mod}p\notin L$ for every $A\in \mathcal{F}$, whereas $|A\cap B|\mathrm{mod}p\in L$ for all distinct members. Thenwith terms beyond $n$ understood as zero.

Work over the finite field ${\mathbb{F}}_p$. For each member define its intersection polynomialReplace every positive power $x_i^d$ by $x_i$ to obtain a multilinear polynomial ${\tilde{f}}_A$ of polynomial degree at most $s$. This Boolean multilinearization preserves its values at every characteristic vector of a set. At the characteristic vector of a set $B$,It is zero if $A\ne B$ and nonzero if $A=B$. Evaluating a proposed linear relation at each $1_B$ therefore establishes linear independence of the ${\tilde{f}}_A$. The vector space of multilinear polynomials of polynomial degree at most $s$ has the basis of monomials ${\prod }_{i\in T}{x}_i$, $|T|\le s$, of size ${\sum }_{j=0}^s\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. This proves the Frankl-Wilson theorem by the polynomial method in combinatorics. The empty product for $s=0$ is $1$, and the argument still applies.

The constant-intersection family bound, directly. Write $\mathcal{F}=\{F_1,\dots ,F_q\}$ and assume $n\ge 1$. The cases $q\le 1$ are immediate. If $\lambda =0$, the nonempty members are pairwise disjoint and there can also be the empty set, givingFor $\lambda >0$, every member has size at least $\lambda$. If every member has size strictly greater than $\lambda$, form the real matrix $X$ whose rows are their characteristic vectors of sets. Its Gram matrix satisfiesFor any nonzero real vector $z$,Thus the rows are linearly independent and $q\le n$. If a member $F_1$ has size $\lambda$, it lies inside every other member. The sets $F_i\setminus F_1$, $i>1$, are nonempty and pairwise disjoint, so $q-1\le n-\lambda$. This also givesThese bounds are sharp: the singletons together with $\varnothing$ attain $n+1$ at $\lambda =0$, while all complements of singletons attain $n$ at $\lambda =n-2>0$ when $n\ge 3$.

The constant t-wise intersection dichotomy. In its substantive form the last argument requires $m\ge t$. The printed statement does not explicitly impose this. Without it the $t$-fold condition can be vacuous and the claimed dichotomy is false: take $t=3$, $m=2$, $n=1$, $A_1=\varnothing$, $A_2=\{1\}$ and $\lambda =1$. There is no $3$-tuple to test, no common $1$-set, and $k=0$, so $m=2>k+t-2=1$. We therefore prove the intended assertion for $m\ge t$ and record this necessary qualification.

If $\lambda =0$, the first alternative always holds with $S=\varnothing$. Suppose $\lambda >0$. Choose $t-2$ indices attaining the minimum intersection size $k$, and writeFor each of the $q=m-t+2\ge 2$ remaining indices put $B_j=K\cap A_j$. The hypothesis gives $|B_j\cap B_{\ell }|=\lambda$ for distinct remaining indices. This reduces the constant t-wise intersection dichotomy to a constant-intersection family bound on the $k$-element set $K$. The two possibilities are treated below.

Use the part-preserving bipartite four-cycle density conventionHere $G(x,y)$ is the indicator function of adjacency, and repeated labels are allowed. This is the homomorphism density convention appropriate to the four-cycle norm. We derive the needed counting and operator norm facts directly.

Let $M=(G(x,y))$ be the $n$-by-$n$ biadjacency matrix, let $1$ be the all-ones vector, let $J=11^{\mathsf{T}}$, and put $H=M-\delta J$. The degree hypothesis saysso the centered matrix $H$ annihilates $1$ on both sides. In particular, $HJ=J{H}^{\mathsf{T}}=0$, andThe two terms have zero products in either order. Expanding the matrix trace directly counts four adjacency factors:Since $J^2=nJ$ and $\mathrm{tr}J=n$, we obtainThe given upper bound therefore impliesThis computation proves the centered four-cycle identity for a biregular graph, rather than assuming a four-cycle norm identity.

The matrix $Q=H{H}^{\mathsf{T}}$ is a positive semidefinite matrix. By the spectral theorem for real symmetric matrices it has nonnegative eigenvalues ${\lambda }_j$, andMoreover, for the Euclidean norm,Indeed $\Vert H^{\mathsf{T}}v{\Vert }_2^2=v^{\mathsf{T}}Qv$, whose maximum on unit vectors is ${\lambda }_{\max }$; the Cauchy-Schwarz inequality characterization $\Vert H{\Vert }_{\mathrm{op}}={\sup }_{\Vert u{\Vert }_2=\Vert v{\Vert }_2=1}|u^{\mathsf{T}}Hv|$ also shows that $H$ and $H^{\mathsf{T}}$ have the same operator norm. Taking fourth roots thus giveswhere the error parameter $c$ is nonnegative, as in the claimed bound.

Finally use the indicator vectors $a=1_A$, $b=1_B$. Their Euclidean norms are $\sqrt{|A|}$ and $\sqrt{|B|}$, so the Cauchy-Schwarz inequality and the operator norm estimate yieldThis is the required discrepancy bound. It also holds when either subset is empty or $\delta =0$. In fact, because $H$ annihilates constants, replacing $a,b$ by $a-\alpha 1,b-\beta 1$ gives the stronger bound $c\delta n^2\sqrt{\alpha (1-\alpha )\beta (1-\beta )}$. This is the spectral discrepancy bound for a biregular graph.

The original PDF has $u_m^{n+1}$ on the left of the update; the converted TeX omits its $+1$. Use the Forward Euler method with $k=\Delta t\ge 0$ and $\mu =k/h_x^2$. The explicit time stepping for bounded reaction diffusion update matrix isWhen $0\le \mu \le 1/2$, the heat update $H_h$ has nonnegative stencil weights $\mu ,1-2\mu ,\mu$ and row sums at most one. Hence its induced maximum operator norm is at most one. It is also a symmetric matrix with eigenvaluesall in $[-1,1]$, so its discrete L2 norm operator bound is at most one too. Let $A_{\ast }=\max (|a_0|,|a_{+}|)$. In either of these norms,Iteration gives the mesh-uniform stability estimateThe same estimate applies to differences of solutions. Adding a per-step defect $k{r}^n$ gives $\Vert e^n\Vert \le e^{A_{\ast }T}(\Vert e^0\Vert +k{\sum }_{j<n}\Vert r^j\Vert )$.

This proof only requires $\mu \le 1/2$ and bounded reaction coefficients. It does not assume the full update $E_h$ is nonnegative: a negative $a_m$ can make its middle stencil weight negative when $\mu =1/2$. Nor does it claim contractivity or an all-time bound for every coefficient. The required stability is a bound uniform in the discretization on fixed finite intervals.

For an evolutionary partial differential equation, stability of a numerical method means that errors in the starting data and forcing stay controlled on each fixed interval $0\le t\le T$, with constants independent of the mesh. Fourier stability analysis is especially effective for a constant-coefficient finite difference method on a uniform infinite or periodic grid: translation invariance makes different Fourier modes evolve independently.

For a scalar one-step scheme on the integer lattice, insert $U_m^n={\hat{U}}^n(\theta )e^{im\theta }$, with $-\pi \le \theta \le \pi$. The Fourier symbol of each shift is $e^{ij\theta }$, and the update reduces toThe amplification factor $G$ must be defined for every relevant frequency; for an implicit scheme this includes checking that its denominator is nonzero. The Parseval identity turns a bound ${\sup }_{\theta }|G(\theta ){|}^n\le C_T$ into a discrete L2 norm bound. Thus $|G|\le 1$ gives contractivity, while the more general bound $|G|\le 1+Ck$ gives $\Vert U^n{\Vert }_h\le e^{CT}\Vert U^0{\Vert }_h$ for $nk\le T$. Conversely, frequencies with amplification uniformly greater than one produce unstable wave packets or periodic Fourier modes under refinement.

For a system, $G(\theta )$ is an amplification matrix; for a multilevel scheme, a companion matrix evolves the vector of time levels. The actual requirement is a uniform bound on matrix powers, not just their spectral radius. A nontrivial Jordan block at a unit-modulus eigenvalue creates polynomial growth in the time index. Even simple eigenvalues inside the unit disk can fail to give a uniform bound if the eigenvector matrices become ill-conditioned as the mesh changes. Uniformly controlled diagonalization of a matrix, or a suitable quadratic energy estimate, resolves this issue. The power boundedness of a two-level Fourier scheme illustrates why root multiplicities and conditioning matter.

For the heat equation, put $\mu =k/h_x^2$. Centered space with the Forward Euler method hasThe Von Neumann stability analysis condition $|G|\le 1$ holds exactly for $0\le \mu \le 1/2$ on the full frequency interval. The Backward Euler diffusion scheme instead has $G=(1+4\mu {\sin }^2(\theta /2){)}^{-1}$ and is stable for every $\mu \ge 0$. The Crank-Nicolson diffusion scheme hasIt too is unconditionally stable, but poorly resolved high-frequency modes have $G\approx -1$ for large $\mu$, giving oscillatory numerical transients. A-stability therefore does not guarantee strong damping; L-stability distinguishes the damping of the Backward Euler method.

For the advection equation $u_t+c{u}_x=0$, let $\nu =ck/h_x$. Forward time and centered space giveFor nonzero fixed $\nu$, repeated steps amplify some modes by a fixed factor greater than one, so the method is unstable under the usual refinement $k\propto h_x$. This calculation also shows the refinement qualification: if $k=O(h_x^2)$, its finite-time growth can be bounded by $\exp (C{c}^{2}Tk/h_x^2)$, though the restrictive scaling defeats the usual hyperbolic time-step choice. For $c>0$, the upwind finite difference scheme hasso it is stable for $0\le \nu \le 1$. The Lax-Wendroff advection scheme instead hasgiving $|\nu |\le 1$. These examples separate the effects of the spatial stencil, temporal approximation and Courant number; a higher order of a numerical method by itself does not establish stability.

A periodic boundary condition is ideal for this analysis. The discrete Fourier transform diagonalizes the circulant update, with only the discrete frequencies $2\pi j/J$ needed on a grid of $J$ points. A bound on all $\theta$ is a convenient guarantee over every such grid. On the whole line, the Fourier transform uses a continuous frequency interval and the Parseval identity proves the corresponding square-summable-data estimate.

Homogeneous Dirichlet boundary conditions do not admit arbitrary complex exponential Fourier modes. For the standard centered second difference on $M$ interior points, a discrete sine transform diagonalizes the actual boundary-value matrix:The same heat amplification formulas then apply at these sine frequencies. For example, the exact forward-Euler contractivity limit on that fixed grid is $\mu \le [2{\cos }^2(\pi /(2(M+1))){]}^{-1}$; the mesh-independent sufficient limit $1/2$ follows by including all frequencies. Homogeneous Neumann boundary conditions can similarly permit a discrete cosine transform, provided the endpoint discretization and its weighted inner product are chosen consistently. The constant mode is then present, reflecting conservation of the heat equation's spatial mean. For inhomogeneous boundary conditions, subtract a suitable lifting of the prescribed boundary data and estimate the induced source using the homogeneous evolution's bound and a Duhamel principle estimate. Bounds for the lifting and source must themselves be uniform in the mesh.

General boundary conditions require separate boundary stability of a finite-difference method. For an advection equation, incoming data are prescribed at the inflow boundary, while an outflow closure must respect the outgoing characteristics. An interior periodic Fourier symbol cannot detect a growing mode confined near a boundary. A normal-mode test $U_m^n=z^n{\kappa }^m$ on a half-line seeks modes with $|z|>1$ and $|\kappa |<1$ that satisfy both the interior recurrence and boundary closure. Their existence proves instability, and uniform control requires more than merely excluding isolated growing roots; the Uniform Kreiss--Lopatinskii condition addresses boundary resolvent bounds. Alternatively, a direct energy method using summation by parts can include the boundary terms and establish the required estimate.

Variable coefficients and nonuniform meshes usually destroy exact Fourier transform diagonalization. Frozen-coefficient Fourier stability analysis is then a useful diagnostic, but it is not automatically a proof for the full variable-coefficient boundary problem. The mesh-uniform energy method in question 5 is an example of a direct proof. Also, an L2 norm proof is not automatically a mesh-uniform maximum-norm proof: finite-dimensional norm-equivalence constants may grow with the number of grid points.

Finally, stability measures error propagation; consistency of a numerical method measures the defect of inserting the exact solution. For a well-posed linear initial-value problem in the chosen norm, the Lax equivalence theorem says that a consistent approximation is convergent exactly when it is stable. Boundary discretization and starting data must be included in that assertion. A Fourier calculation proves convergence only after consistency, well-posedness and the actual boundary treatment have also been checked.