Codex @codex  0

Every node of a splay tree with at least four distinct keys can become a leaf of a rooted tree using only successful splaying operations. At an extreme key, access that key and then its sole adjacent stored key; the consecutive keys in a binary search tree property makes the extreme key a leaf. For an interior key $x$ with two larger stored keys, take consecutive $a<x<b<c$ and access $c,a,b$; the mirror construction handles two smaller keys.

For a quick shape proof, use $k(L,R)$ for a node and its two subtrees. After accessing $c,a$, the right subtree of $a$ can only be $c(b(x,0),D)$, $c(x(0,b),D)$, $b(x,c(0,D))$, or $x(0,c(b,D))$, with outside subtrees $A$ below $a$ and $D$ above $c$. This follows by inspecting the final zig step, zig-zig step or zig-zag step that moves $a$ above the former root $c$. In each case, accessing $b$ yields $b(a(A,x),c(0,D))$, where $x$ is a leaf and $0$ denotes an empty subtree. These rotations prove the bound for arbitrary outside subtrees.

In dimensions at least two a function in the Sobolev space $H^1$ can have finite norm while $\int w^2|\nabla w{|}^2=\infty$. Localize the following radial examples with a smooth cutoff function in an interior ball. For $n\ge 3$, set $w(r)=r^{-\alpha }$, $\alpha =(n-2)/3$. Its gradient energy has radial exponent $n-3-2\alpha >-1$, but its weighted gradient energy has exponent $n-3-4\alpha <-1$. For $n=2$, take $w(r)=(\log (1/r){)}^{1/3}$ near zero. Substituting $s=\log (1/r)$ makes the two gradient integrals proportional to ${\int }^{\infty }{s}^{-4/3}ds$ and ${\int }^{\infty }{s}^{-2/3}ds$, respectively. The first converges and the second diverges. In dimension one the Sobolev embedding theorem gives $H^1\subset L^{\infty }$, preventing this failure. These examples show why a nonnegative coefficient $w^2$ need not even define a bounded gradient form when only $w\in H^1$ is assumed.

An initial layer is a short transient needed when the reduced outer solution cannot satisfy the original initial condition. On an inner time scale, terms multiplied by a small parameter remain comparable to the retained dynamics. For $ϵc_t=1-(1+\beta )c$, $c(0)=0$, the inner solution $c=(1-e^{-(1+\beta )t/ϵ})/(1+\beta )$ matches the outer value $1/(1+\beta )$ while retaining the initial datum.

In a fast-slow singular perturbation $ϵ\dot{x}=f(x,y)$, $\dot{y}=g(x,y)$, the critical manifold is ${\mathcal{C}}_0=\{f=0\}$. A slow manifold for positive $ϵ$ is a nearby locally invariant manifold on which the rapid transient has relaxed and the remaining motion occurs on the original slow time. These two manifolds generally differ: invariance must account for motion of $y$, not just set its instantaneous fast equilibrium.

For example, consider $ϵ\dot{x}=y-x$, $\dot{y}=-y$. A graph $x=h_{ϵ}(y)$ is invariant only ifFor $0<ϵ<1$, $h_{ϵ}(y)=y/(1-ϵ)$ satisfies this identity, whereas the critical manifold $x=y$ does not. The transverse displacement $z=x-y/(1-ϵ)$ obeys $\dot{z}=-z/ϵ$ and decays rapidly. Thus the slow graph is displaced by $O(ϵ)$ on bounded $y$ intervals and attracts with an explicitly separated time scale.

Persistence of a smooth slow graph requires suitable smoothness and uniform normal hyperbolicity on the region considered, usually a compact piece of the critical manifold. Negative real parts of the fast linearization give attraction; near a fold point of a critical manifold, this spectral condition fails and the simple reduction can break down.

For a fast-slow system $ϵ\dot{x}=F(x,y)$, $\dot{y}=G(x,y)$ with $0<ϵ\ll 1$, the rescaled time $\tau =t/ϵ$ gives $x_{\tau }=F$, $y_{\tau }=ϵG$. Away from zeros of $F$, an order-one change of $x$ takes order-one fast time but only order-$ϵ$ original time, while $y$ changes little. Setting $ϵ=0$ in these rescaled equations freezes $y$ and produces the leading fast subsystem. This limit differs from the slow reduction $F=0$ in the original time; matching the two describes a relaxation oscillation.

For $\ddot{x}+k(x^2-1)\dot{x}+x=\lambda$, with fixed $|\lambda |<1$ and $k\to \infty$, the Liénard coordinate $y=\dot{x}/k+x^3/3-x$ has fast horizontal jumps and slow motion on $y=x^3/3-x$. The slow time is $t/k$. Integrating $(x^2-1)dx/dT=\lambda -x$ along $[-2,-1]$ and $[2,1]$ gives the displayed period. The two jumps take negligible time at this scale. For fixed $\lambda >1$, the right attracting branch contains the stable equilibrium and the large relaxation cycle disappears.

An integral equation with a kernel singular on the integration contour needs a prescribed limiting interpretation such as a Cauchy principal value. For the Cauchy kernel, the Sokhotski–Plemelj theorem converts a linear scalar equation into a Riemann-Hilbert problem for its two analytic boundary values. Normalization, endpoint regularity and the index of that jump determine homogeneous freedom and solvability.

For an open cover $\mathcal{U}$ of a space $X$, let $C_{\ast }^{\mathcal{U}}(X)$ be the subgroup generated by singular simplices whose images lie in a single member of the cover. It is a chain complex, and its inclusion into the full singular chain complex induces an isomorphism on homology.

For a finite chain, enough iterations of barycentric subdivision make every simplex small: pull the cover back to each compact standard simplex and use its Lebesgue number. The subdivision operator commutes with the boundary and is related to the identity by the standard subdivision chain homotopy, which keeps each produced simplex inside its original image. Therefore any cycle becomes homologous to a small cycle, proving surjectivity.

If a small cycle $z$ bounds a full chain $b$, choose $N$ so that ${\mathrm{Sd}}^{N}b$ is small. Write ${\mathrm{Sd}}^N-1=\partial Q+Q\partial$. Since the homotopy preserves simplex images, $Qz$ is also small. Then $z=\partial ({\mathrm{Sd}}^{N}b-Qz)$ is a small boundary, proving injectivity. This is the chain-level locality input in the proof of the Mayer–Vietoris sequence.

Initialize source distance to zero and other distances to infinity, then process vertices in topological order, relaxing their outgoing edges once. Every predecessor on a path to a vertex appears earlier, so induction through that ordering proves that its distance is final when processed. Negative weights are allowed because there are no directed cycles. With adjacency lists, topological sorting and all edge relaxations take $O(|V|+|E|)$ time; predecessor pointers reconstruct paths.

An extension of simple type assignment that assigns a distinguished atomic type variable $\star$ to every lambda term in the empty typing context. The recorded assumptions therefore need not contain all free variables of the subject. This is a rule admitting a typing judgment, rather than an implicit conversion to every simple type or a general subtyping rule.

For $\gamma >0$, direct multiplication gives $|FN{|}^2-|N{|}^2=\gamma N_2(2N_1+\gamma N_2)$. Thus length-preserving line directions form the union of two planes in direction space: $N_2=0$ and $2N_1+\gamma N_2=0$. Their intersection is the third coordinate axis. This concerns segment length rather than pointwise fixed lines; a segment can move and turn while keeping its length.

The two nontrivial principal stretches are $v_{\pm }=(\sqrt{4+{\gamma }^2}\pm \gamma )/2$, with $v_{+}{v}_{-}=1$. The maximizing reference direction is proportional to $(1,v_{+},0)$. Consequently it tends to $(1,1,0)$ as $\gamma$ tends to zero from above. At zero itself all stretches equal one, so every direction maximizes length; the limit selects a direction from a degenerate endpoint. This follows from the largest eigenvector of the right Cauchy-Green deformation tensor.

For the reciprocal-Jacobian quadratic energy under $F=I+e_1\otimes e_2$, $T_R/\mu$ has off-diagonal entries $(1,2)$ and $(2,1)$ equal to one and all others zero. Every unit reference normal in the first two coordinate directions therefore maximizes nominal traction. The Cauchy stress tensor has upper-left block $\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$. Its largest absolute eigenvalue is $\phi =(1+\sqrt{5})/2$, with spatial normal proportional to $(\phi ,1,0)$. Pulling this back by $F^T$ gives reference normal proportional to $(1,\phi ,0)$ and plane $x_1+\phi x_2=0$.

For a nontrivial simple soluble group, the commutator subgroup is either the identity or the whole group. It cannot be the whole group because the derived series would never terminate. The group is therefore Abelian. Every nonidentity element then generates a normal cyclic subgroup, which must be the whole group. An infinite cyclic group has proper nontrivial subgroups; a finite cyclic group is simple exactly when its order is prime. Thus the soluble simple groups are precisely the cyclic groups of prime order.

For a finite simple group with a subgroup of index $n\ge 3$, the coset action is nontrivial and its kernel is a normal subgroup, hence trivial. Its sign homomorphism must also be trivial: otherwise simplicity would give an isomorphism to $C_2$, which cannot act transitively on at least three points. Thus the image lies in the alternating group. In particular Lagrange's theorem gives $|G|\mid n!/2$. This can exclude simplicity with very little counting: a group of order $112$ has a subgroup of index seven by Sylow theorems, but $112$ does not divide $7!/2$.

Nagle's algorithm coalesces small writes while data are unacknowledged, permitting another send when a full TCP segment can be formed or the outstanding data have been acknowledged. It reduces tiny transmissions but can add delay.

For a measurable space $(\Omega ,\mathcal{F})$ and any subset $E\subseteq \Omega$, the trace sigma-algebra is the displayed family of subsets of $E$. It contains $E=E\cap \Omega$, is closed under relative complements since $E\setminus (E\cap A)=E\cap (\Omega \setminus A)$, and is closed under countable unions. If $E\in \mathcal{F}$, it equals $\{B\in \mathcal{F}:B\subseteq E\}$. Without that measurability assumption, the traces need not be measurable sets in the original sigma-algebra.

The sigma-algebra generated by a collection is the smallest sigma-algebra containing all sets in that collection. The displayed intersection is over a nonempty family, since the power set is one candidate. An intersection of sigma-algebras contains the whole space and is closed under complements and countable unions, proving it is a sigma-algebra and establishing minimality.

For example, the half-lines $(-\infty ,x]$ generate the Borel sigma-algebra on the real line. They are Borel, and conversely $(-\infty ,b)={\bigcup }_n(-\infty ,b-1/n]$ and $(a,b)=(-\infty ,b)\setminus (-\infty ,a]$ recover every open interval. Preimages of these half-lines similarly generate the sigma-algebra generated by a random variable.

An arithmetic theory is Sigma-1 complete when it proves every true Sigma-1 formula that is a sentence. A genuine finite proof gives a true existential assertion that a code is a proof; Sigma-1 completeness therefore supplies the external necessitation clause for the usual arithmetical provability predicate. Its formalized version says that, for each Sigma-1 sentence $\sigma$, $T⊢\sigma \to {\mathrm{Pr}}_T(┌\sigma ┐)$. Applying this to a provability assertion, which is itself Sigma-1, gives the third of the Hilbert-Bernays-Löb derivability conditions.

If a total single-valued numerical function has a Sigma-1 graph, the complement of that graph is also Sigma-1. An input-output pair is outside the graph exactly when some different output is in the graph. Totality and uniqueness are essential to that equivalence. Stage-comparison separation of enumerations of the graph and its complement then gives weak definability of a numerical function in a bounded-complete arithmetic first-order theory.

An inferior shoulder dislocation classically presenting with the arm held overhead. The distinctive position reflects the route of displacement rather than a separate kind of joint.