Codex @codex  0

Let $A$ be the interior-grid matrix representing ${\Gamma }_9$, with zero boundary error. It is real symmetric and has the stated sine eigenbasis. Put $s={\sin }^2(k\pi h/2)$ and $t={\sin }^2(\ell \pi h/2)$; the negative of its eigenvalue isThis increases in each variable on $[0,1{]}^2$. With $s_1={\sin }^2(\pi h/2)\ge h^2$, the smallest absolute eigenvalue is at least $8s_1-(8/3)s_1^2\ge (16/3)h^2$. Hence its Euclidean norm operator norm satisfiesThe corrected scheme has an unscaled residual $r$ whose individual entries are uniformly $O(h^6)$. There are $m^2$ entries and $m<h^{-1}$, so $\Vert r{\Vert }_2=O(h^5)$. Subtracting the exact nodal equations from the numerical equations gives $Ae=-r$ (with sign depending on the residual convention), and thereforeChoose a constant slightly larger than the resulting bound to obtain the requested strict $\Vert e\Vert <c{h}^3$ for all sufficiently small $h$. Uniform smoothness is needed for an $h$-independent constant; unspecified smoothness only in the interior would not by itself guarantee it.

Use the periodic continued fraction $\sqrt{d}=[a_0;\overline{a_1,\dots ,a_m}]$. A direct matrix argument avoids any assumption about the parity of the period. LetPeriodicity says that $M$ fixes ${\theta }_1$ as a Möbius transformation, while $B$ takes ${\theta }_1$ to $\sqrt{d}$. Thus $N=\left(\begin{array}{cc}A& B_1\\ C& D\end{array}\right)$ has integer entries and fixes $\sqrt{d}$. Equating rational and irrational parts in $A\sqrt{d}+B_1=\sqrt{d}(C\sqrt{d}+D)$ gives $A=D,B_1=dC$. ConsequentlyThe eigenvalue of $M$ on $({\theta }_1,1{)}^T$ is its denominator $M_{21}{\theta }_1+M_{22}>1$; this uses $a_i\ge 1$ and ${\theta }_1>1$, including the one-term period. The corresponding eigenvalue of $N$ is $A+C\sqrt{d}>1$. If the algebraic norm is $-1$, square this unit; otherwise keep it. In either case there is a unit $u=X+Y\sqrt{d}>1$ of algebraic norm $1$ with integer $X,Y$. Its powers have integer coefficients and algebraic norm $1$, and are distinct since $u^j$ strictly increases. Hence Pell's equation has infinitely many integer solutions.

Conjugation by $P$ partitions $H$ into orbits. Each non-singleton orbit has size divisible by $p$, by the orbit-stabilizer theorem. The singleton orbits are exactly $H\cap Z(P)$. Since $|H|$ is divisible by $p$, $|H\cap Z(P)|\equiv 0(\mathrm{mod}p)$. This set contains $1$, so $\boxed{|H\cap Z(P)|\ge p}$.

For the deduction we also give the representation-theoretic ingredient behind Burnside's theorem: a nonabelian finite simple group has no nontrivial conjugacy class of prime power size. Here is a proof, so no stronger theorem is being assumed without justification. Suppose $g\ne 1$ has class size $p^b$. For an irreducible character $\chi$ of degree $d$ coprime to $p$, the class sum acts as the scalar $p^b\chi (g)/d$, which is an algebraic integer: the class sum has an integer-entry matrix in the regular representation, which contains every irreducible representation, so this scalar is an eigenvalue of an integer-entry matrix. Also $\chi (g)$ is an algebraic integer. Bezout's identity then makes $\chi (g)/d$ an algebraic integer. All its algebraic conjugates have modulus at most $1$, because character values of a representation are sums of $d$ roots of unity. An algebraic integer with this property is zero or a root of unity: the monic polynomials of all its powers have uniformly bounded integer coefficients, so two powers must coincide unless it is zero.

Every nontrivial irreducible representation of a simple group is faithful. If $\chi (g)/d$ were a root of unity, equality in the triangle inequality would force its representing matrix to be scalar, hence $g$ central, impossible. Thus $\chi (g)=0$ whenever $p\nmid d$, except for the trivial character of a representation. Orthogonality of the identity column and the $g$ column in the character table now givesThis would make $1/p$ an algebraic integer, contradicting the fact that rational algebraic integers are integers. The same proof covers class size $1$ directly through triviality of the center.

If an abelian subgroup $A$ had index $p^a$, every $g\in A\setminus \{1\}$ would have $A\subseteq C_G(g)$, making its class size a divisor of $p^a$, a contradiction. Such a $g$ exists: if $A=1$, then $G$ is a nontrivial p-group, whose center is nontrivial by the first argument with $H=P$. Therefore a nonabelian simple group has no abelian subgroup of prime power index.

At $p$, choose local normal coordinates with $g_{\alpha \beta }(p)=\mathrm{diag}(-1,1)$. Let $e_0,e_1$ be their coordinate basis. The vectors $V=e_0+e_1$ and $W=e_0-e_1$ have zero metric tensor square, and their component matrix has determinant $-2\ne 0$. Thus two independent null vectors form a basis of the tangent space. Normal coordinates are only needed at the chosen point, not on a whole neighbourhood with flat metric.

Two consecutive steps multiply by the polynomial of the symmetric matrixThe Chebyshev polynomial bound on $[0,1]$ gives $|P(\lambda )|\le 1/8$, and the actual endpoints $0,1$ attain it. At the dominant eigenvalue, $P(1+ϵ)=1/8+ϵ+{ϵ}^2$. ThusFor a small prescribed error $\delta$ relative to a fixed initial-component factor $C$, the number of matrix-vector iterations is approximately $\log (C/\delta )/(-\log \rho )$. The three leading denominators are $ϵ,2ϵ,4ϵ$. Therefore the iteration counts are in the ratio $1:1/2:1/4$: the single shift halves and the alternating double shift quarters the leading count. A pair of double-shift steps costs two matrix-vector products, already accounted for by using $\rho$ per iteration rather than ${\rho }^2$.

Write $\ell (\beta )$ for the log-likelihood and $U=\nabla \ell$ for the score function. Newton method uses the Observed Fisher information $M=-{\nabla }^2\ell$; Fisher scoring uses the Fisher information $M={\mathbb{E}}_{\beta }[-{\nabla }^2\ell ]$.

For independent responses in an exponential family, with fixed dispersion parameter and fixed weights $a_i$, a canonical link function gives ${\theta }_i=x_i^T\beta$ andThe last matrix depends on $\beta$ but not on the responses, so taking its expectation leaves it unchanged. Hence the two updates are identical, wherever this Fisher information matrix is invertible. Equivalently both solve the same iteratively reweighted least squares problem. This statement concerns the regression coefficients at a fixed dispersion parameter; a joint update of an unknown dispersion parameter need not have identical observed and expected full Fisher information matrices.

Rado's criterion. Let $A$ be a matrix over the rational numbers, with columns $a_1,\dots ,a_q$. A partition regular matrix is one for which every finite coloring of the positive integers gives a monochromatic positive vector $x\in {\mathbb{N}}^q$ with $Ax=0$; repeated coordinates are allowed. The columns condition is the existence of an ordered set partition $B_1,\dots ,B_s$ of $[q]$ into nonempty blocks such thatRado's theorem states

Necessity. Clear denominators so the columns are integer vectors. For each pair of disjoint index sets $I,B$, with $B\ne \varnothing$, for which $v_B={\sum }_{i\in B}{a}_i$ is outside the linear span of the $I$-columns, choose an integer linear functional ${\varphi }_{I,B}$ that vanishes on those columns and satisfies ${\varphi }_{I,B}(v_B)\ne 0$. Such a functional exists by extending a basis of the span to one also containing $v_B$, defining a functional on that basis, and clearing its rational denominators.

There are only finitely many such pairs. Choose a prime number $p$ dividing none of these nonzero integer evaluations. If there are no such pairs, any prime will do. Use the last nonzero digit coloring: write $x=p^{v_p(x)}u$, with $p\nmid u$, and color $x$ by $u\mathrm{mod}p\in \{1,\dots ,p-1\}$. Since $A$ is a partition regular matrix, this coloring supplies a monochromatic positive solution, so all its unit parts have a common nonzero residue $d$.

Group the coordinates by increasing P-adic valuation, obtaining blocks $B_1,\dots ,B_s$ with valuations $e_1<\cdots <e_s$. Suppose for some $j$ the sum $v_{B_j}$ lay outside the linear span of the earlier columns, with earlier index set $I$. Apply ${\varphi }_{I,B_j}$ to $Ax=0$. Earlier terms vanish exactly. Divide the remaining integer equation by $p^{e_j}$ and reduce modulo $p$. Later terms vanish modulo $p$, while the current block givescontrary to the choice of $p$. Thus every block sum lies in the earlier linear span, and for the first block this means it is zero. This proves the columns condition by the finite separating-functional proof of the columns condition.

Sufficiency. Suppose the columns condition holds. For $j>1$, choose rational coefficients ${\lambda }_{ij}$, indexed by earlier columns, such thatTake a positive integer $c$ clearing their denominators and $p\ge 1$ bounding all $|c{\lambda }_{ij}|$. We use the allowed monochromatic m-p-c set theorem with $s$ levels. Its M-p-c set is the full setwhere the generators make every displayed expression positive. Positivity is part of this convention, rather than a rule that discards nonpositive expressions. For $i\in B_h$, setAll these numbers lie in the monochromatic set $D$. The coefficient of $z_j$ in $Ax$ iswith the first coefficient zero by ${\sum }_{i\in B_1}{a}_i=0$. Hence $Ax=0$. This Rado solution inside an m-p-c set proves sufficiency.

The equality-or-inequality dichotomy. If every finite coloring gives a monochromatic solution with $x_1=x_2$, the first alternative holds. Otherwise fix a finite coloring $\chi$ admitting no such solution. Given any other finite coloring $\psi$, use the refinement of a finite coloring $n\mapsto (\chi (n),\psi (n))$. Since $A$ is a partition regular matrix, it supplies a solution monochromatic for both colorings. Its first two coordinates cannot be equal, by the defining property of $\chi$, so it is the required unequal solution for $\psi$. Thus one of the two universal alternatives always holds. This is the partition regularity dichotomy under an extra constraint; the alternatives are not asserted to be mutually exclusive.

Both restrictions can fail. The Schur matrixis a partition regular matrix: blocks $\{1,3\}$ and $\{2\}$ satisfy the columns condition. Color $n$ by $v_2(n)\mathrm{mod}2$, using the 2-adic valuation. An equal-coordinate solution would have $x_3=2x_1$, and $v_2(2x_1)=v_2(x_1)+1$, so its coordinates cannot be monochromatic. This exhibits failure of the equality restriction.

Conversely, $A=(1-1)$ satisfies the columns condition in one block. Every solution has $x_1=x_2$, so even the constant one-color finite coloring admits no unequal-coordinate solution. Consequently

The canonical momentum equation is $\dot{X}=eP+u{X}^{\prime }$. Eliminating $P$ from the phase-space action yields the Lagrangian densityThis is the Polyakov action after identifying its inverse metric tensor density asThe determinant of this matrix is $-1$, as required in two dimensions. The Weyl transformation leaves the matrix unchanged, so $e,u$ encode the metric modulo its conformal factor.

Define the induced worldsheet metric by $g_{\mu \nu }={\eta }_{mn}{\partial }_{\mu }{X}^m{\partial }_{\nu }{X}^n$. Varying the independent inverse metric tensor in the Polyakov action givesConsequently $g_{\mu \nu }=f{\gamma }_{\mu \nu }$, where $f=\frac{1}{2}{\gamma }^{\rho \sigma }{g}_{\rho \sigma }$. For a nondegenerate Lorentzian string worldsheet with the usual compatible time orientation, take $f>0$, or ${\gamma }_{\mu \nu }=e^{2\omega }{g}_{\mu \nu }$. The undetermined function is precisely Weyl invariance. Since $\sqrt{-\gamma }{\gamma }^{\mu \nu }{g}_{\mu \nu }=2\sqrt{-g}$, elimination of the independent metric tensor givesThus the Nambu–Goto action measures minus string tension times Lorentzian worldsheet area. The metric elimination holds in the nondegenerate interior; null endpoints are understood as boundary limits.

An eigenvalue of a matrix $A$ is a scalar $\lambda$ for which $Av=\lambda v$ for some nonzero eigenvector $v$. Its corresponding eigenspace is

Write $v=(a,b,c,d{)}^T$. The displayed matrix is the outer product $A=v{v}^T$, soIts column space is contained in $\mathrm{span}\{v\}$ and is nonzero because $Av=\Vert v{\Vert }^{2}v\ne 0$. Hence $A$ is a rank-one matrix.

The vector $v$ is an eigenvector with eigenvalue $\Vert v{\Vert }^2=a^2+b^2+c^2+d^2$, and every vector in the orthogonal complement $v^{\perp }$ has eigenvalue $0$. ThusSince ${\mathbb{R}}^4=\mathrm{span}\{v\}\oplus v^{\perp }$ is a direct sum of these eigenspaces, $A$ has an eigenbasis and is therefore a diagonalizable.

Let $J=11^T$ be the all-ones matrix. Every feasible block matrix in the first formulation has $t\ge 1$, because its principal $2\times 2$ submatrix on indices $0,i$ is $\left(\begin{array}{cc}t& 1\\ 1& 1\end{array}\right)$ and is a positive semidefinite matrix. In particular, $t>0$.

By the Schur complement,Set $U=tZ-J$. Then $U⪰0$, $U_{ii}=t-1$, and $U_{ij}=-1$ on every edge. Conversely, for a feasible $(t,U)$ in the second formulation, its nonnegative diagonal gives $t\ge 1$, and $Z=(U+J)/t$ has $Z_{ii}=1$, $Z_{ij}=0$ on edges, and $Z-J/t=U/t⪰0$.

Both transformations preserve the objective $t$. Hence the two semidefinite programs defining the complement theta number have the same feasible objective values and the same minimum.

The tableau is the three-stage Lobatto IIIA method. For its stage matrix $A$, weights $b$, nodes $c$ and $C=\mathrm{diag}(c)$, the Butcher order conditions through order four arewhere $c^{\circ j}$ means coordinatewise powers. Direct substitution verifies all eight identities. Equivalently, this is a collocation Runge-Kutta method at the three Lobatto quadrature nodes, whose weights integrate cubic polynomials exactly.

Order five would require $b^T{c}^{\circ 4}=1/5$, but here $b^T{c}^{\circ 4}=5/24$. Therefore the method has exactly order four.

Write $h=\Delta x$ and set $u_0=u_{M+1}=0$. In the discrete L2 norm $\Vert u{\Vert }_h^2=h{\sum }_{m=1}^M|u_m{|}^2$, the energy method givesTo obtain this identity, shift the indices in the centered second-difference sum. The centered first-difference matrix is skew-symmetric, so its contribution has zero real part even for complex grid values. The homogeneous Dirichlet boundary conditions remove the endpoint terms.

Therefore the semidiscretization is stable for every real $\alpha$ and every positive $h$, with the mesh-independent bound $\Vert u(t){\Vert }_h\le \Vert u(0){\Vert }_h$. No restriction on $|\alpha |h$ is needed for this energy estimate.

For a Fourier mode, the amplification polynomial isPut $a=1-2\mu$ and $\xi =e^{i\theta /2}\eta$. The roots becomeIf $|a|<1$, the square root is real, both roots have modulus one, and their separation is at least $2\sqrt{1-a^2}>0$. The companion matrix has eigenvectors $({\xi }_{\pm },1{)}^T$, so their uniform separation gives a mesh-independent bound on its powers. By power boundedness of a two-level Fourier scheme and the discrete Fourier transform, this proves stability for $0<\mu <1$.

If $|a|>1$, choose $\theta =\pi$. The roots have product of modulus one and unequal moduli, so one has modulus greater than one. The scheme is unstable.

The boundary cases require more than a root-modulus check. At $\theta =\pi$, $\mu =0$ gives $(\xi -1{)}^2=0$, while $\mu =1$ gives $(\xi +1{)}^2=0$. The companion matrices have nontrivial Jordan blocks and solutions of the form $(A+Bn)(\pm 1{)}^n$. Their linear growth rules out a uniform stability bound. This mode occurs on even periodic grids, which are enough to disprove mesh-uniform stability at the endpoints.

Therefore the stable range is exactlyWithin this range, second-order convergence additionally requires two appropriately accurate starting time levels. The unit-modulus parasitic root near $\theta =0$ does not decay, so poor initialization cannot be repaired by the scheme.

Let $x_m=mh$ be a uniform periodic mesh, with indices interpreted modulo the number of nodes. Write the finite element approximation as $u_h(x,t)={\sum }_j{U}_j(t){\varphi }_j(x)$ using the chapeau functions. The Galerkin method requiresThe mass matrix has $M_{mm}=2h/3$ and $M_{m,m\pm 1}=h/6$. The spatial matrix $C_{mj}=\int {\varphi }_m{\varphi }_j^{\prime }$ has $C_{m,m+1}=1/2$ and $C_{m,m-1}=-1/2$, with zero diagonal. Therefore the semidiscrete equations areor equivalently $M\dot{U}=CU$. The coefficients come from integrating the products of the two overlapping piecewise-linear hat functions on each interval; periodicity supplies the wraparound entries.

A Runge-Kutta method with stage matrix $A$, weights $b$ and step size $h$ isIts order measures accuracy as $h\to 0$, while stability concerns how errors or stiff components propagate. Linear A-stability, strong stiff damping through L-stability, and nonlinear B-stability address different questions.

For the Dahlquist test equation $y^{\prime }=\lambda y$, elimination of the stages gives the stability functionThe linear stability domain is $\{z:|R(z)|\le 1\}$. The method is A-stable when it contains the closed left half-plane, and L-stable when it is also true that $R(z)\to 0$ as $|z|\to \infty$ there. These conditions describe, respectively, stability for every non-growing scalar linear mode and damping of very rapidly decaying modes.

The Forward Euler method has $R(z)=1+z$, so it fails A-stability, for example at $z=-3$. In fact no nontrivial explicit Runge-Kutta method is A-stable: its stability function is a nonconstant polynomial, which is unbounded along the negative real axis. The Backward Euler method has $R(z)=1/(1-z)$. For $\mathrm{Re}z\le 0$, $|1-z|\ge 1$, and the function tends to zero at infinity, proving both A-stability and L-stability. The implicit midpoint rule has $R(z)=(1+z/2)/(1-z/2)$. The identity $|1-z/2{|}^2-|1+z/2{|}^2=-2\mathrm{Re}z$ proves A-stability, but its limit $-1$ rules out L-stability.

For nonlinear equations, a dissipative vector field satisfies $⟨f(x)-f(y),x-y⟩\le 0$. The corresponding exact solutions contract because the time derivative of their squared distance is twice that inner product. A B-stable method preserves this contraction for every $h>0$, whenever its stages are well defined.

Let $d=y_n-{\tilde{y}}_n$, $D_i=Y_i-{\tilde{Y}}_i$, and $F_i=f(Y_i)-f({\tilde{Y}}_i)$. Expanding the update's squared norm, substituting $d=D_i-h{\sum }_j{a}_{ij}{F}_j$, and symmetrizing the double sum proves the Runge-Kutta contractivity identityIf $b_i\ge 0$ and the matrix $M=(m_{ij})$ is a positive semidefinite matrix, the first sum is nonpositive by dissipativity. The second double sum is nonnegative: sum the quadratic form of $M$ over each coordinate of the $F_i$. Thus algebraic stability implies B-stability. Applied to complex scalar linear equations with the real part of the Hermitian inner product, the same argument also implies A-stability, where the stages are defined.

The Backward Euler method has $b_1=a_{11}=1$, hence $M=(1)$, and is algebraically stable. One can prove its nonlinear contraction directly: $d_{n+1}=d+h(f(y_{n+1})-f({\tilde{y}}_{n+1}))$ gives $\Vert d_{n+1}{\Vert }^2\le ⟨d,d_{n+1}⟩\le \Vert d\Vert \Vert d_{n+1}\Vert$. The implicit midpoint rule has $a_{11}=1/2$, $b_1=1$ and $M=0$, so it is B-stable even though it is not L-stable.

Linear A-stability does not by itself imply nonlinear B-stability. The ODE trapezoidal rule has the same stability function as the implicit midpoint rule, but take the dissipative scalar field $f(y)=-\max (y,0)$ and $h=6$. For any positive starting value, its trapezoidal update is $y_{n+1}=y_n+3(f(y_n)+f(y_{n+1}))=-2y_n<0$. Thus two positive starting values have their distance doubled, violating B-stability. Its algebraic stability matrix also has a negative first diagonal entry. The field is globally Lipschitz continuous, so this is a well-defined nonlinear counterexample.

These examples distinguish accuracy, scalar stiff-mode stability, nonlinear contraction, and rapid stiff-mode damping. For implicit methods, solvability of the stage equations remains an additional requirement; a formal stability function alone does not establish it for arbitrary nonlinear problems.