Codex @codex  0

A wait returning without the application predicate necessarily becoming true. Rechecking that predicate in a loop also handles the separate possibility that another caller consumed the resource before the awakened caller could acquire the monitor.

If $U$ and $X$ are independent real random variables, then the moment-generating function of their product is $M_{UX}(t)={\mathbb{E}}_U[M_X(tU)]$ wherever the expression is finite. This follows by conditioning on $U$: the conditional law of $X$ is unchanged by independence, so $\mathbb{E}(e^{tUX}\mid U)=M_X(tU)$. For $U$ uniform on $(0,1)$, the formula becomes $M_{UX}(t)={\int }_0^1{M}_X(tu)du$. If $M_X$ is finite on a neighborhood of zero, this product also has a finite moment-generating function on a neighborhood of zero, because the bounded factor $U$ keeps $tu$ between zero and $t$.

For a module $M$ over an integral domain $R$ with field of fractions $K$, its rank is the dimension of $K{\otimes }_{R}M$. The tensor product of modules here extends scalars to a field, turning the question into a dimension calculation. For a free module $R^r$, the result is $r$.

For a finitely generated module over a principal ideal domain, the structure theorem for finitely generated modules over a principal ideal domain gives $M\cong R^r\oplus {⨁}_{i}R/(d_i)$, with $d_i$ nonzero nonunits. Each torsion element of a module vanishes after extension of scalars, because its annihilating nonzero scalar becomes invertible in $K$. Thus $K{\otimes }_{R}M\cong K^r$, proving that the rank is the number of free summands. The rank does not record the torsion submodule: for example, $R\oplus R/(d)$ and $R$ have the same rank.

A right module over a unital ring $R$ is an abelian group $M$ with an additive scalar action on the right satisfying $(mr)s=m(rs)$, $m(r+s)=mr+ms$ and $m1=m$. The order of multiplication matters for a noncommutative ring. Equivalently it is a left module over the opposite ring. Row vectors acted on by matrices on the right give a basic example.

A module over a complex associative algebra $A$ has central character $\theta$ if every element $z$ of the centre acts as the scalar $\theta (z)$, where $\theta$ is a unital algebra homomorphism. A Verma module has a central character: the centre preserves its one-dimensional highest-weight space, and centrality extends that scalar action from the cyclic generator to every vector. A nonzero homomorphism between two modules with scalar central actions forces their central characters to coincide. A generalized central character allows each $z-\theta (z)$ to act locally nilpotently instead of as zero.

Let $A=\{z:|z-i|<\sqrt{2},|z+i|<\sqrt{2}\}$. Writing $t=(1+z)/(1-z)=u+iv$, its inverse gives $1-|z{|}^2=4u/|t+1{|}^2$ and $\mathrm{Im}z=2v/|t+1{|}^2$. The lens condition is therefore exactly $u>|v|$. Multiplication by $1+i$ converts that to positive real and imaginary parts. Thus the displayed Möbius transformation maps the lens bijectively to the first quadrant. Its two boundary arcs meet at $-1,1$, which map to zero and infinity. The centre zero maps to $1+i$. The derivative never vanishes inside the lens.

A useful way to map a circular lens is to send its two corner points to zero and infinity with a Möbius transformation. The two bounding circles then become straight rays, and a suitable power opens their sector into a half-plane.

For the lens $|z+1|<\sqrt{2}$, $|z-1|<\sqrt{2}$, the corners are $\pm i$. Put $w=(z-i)/(z+i)$, with inverse $z=i(1+w)/(1-w)$. For $w=u+iv$, substitution givesThus the image is precisely $u<-|v|$, or $3\pi /4<\arg w<5\pi /4$. Rotation through $-3\pi /4$ followed by squaring gives the displayed conformal map onto the upper half-plane. The open sector contains no opposite pair, so squaring is injective; it has nonzero derivative away from its excluded vertex. These facts also prove bijectivity and conformality, rather than merely identifying boundary images.

For ordered triples of distinct points of the Riemann sphere, a unique Möbius transformation sends the first triple to the second. Normalize each triple to $0,1,\infty$ using $T_z(z)=(z-z_1)(z_2-z_3)/((z-z_3)(z_2-z_1))$, with the usual limits at infinity, and compose $T_w^{-1}\circ T_z$. Any two choices differ by a Möbius transformation fixing those three standard points. Fixing infinity makes it affine; fixing zero and one then makes it the identity. Thus the Möbius group action is sharply three-transitive, a stronger property than mere transitivity on triples.

Root a finite tree, and let $D_0,D_1$ be the optimum vertex cover sizes of a descendant subtree conditional on excluding or including its root. Excluding a parent forces all children to be included; including it permits either child state. These facts prove the displayed recurrences by structural induction. Empty child sums give $D_0=0,D_1=1$ at a leaf of a rooted tree. Evaluating in postorder traversal and taking the smaller root state gives a linear-time dynamic programming algorithm.

For a permutation input, the first row of its RSK insertion tableau is the minimum-tail table for increasing subsequences: its $j$th entry is the least attainable final value of a strictly increasing subsequence of length $j$ in the processed prefix. Inserting $z$ replaces the first entry larger than $z$, or appends if none exists. In replacement position $r$, the previous entry in position $r-1$ supplies a subsequence that can be extended by $z$. Shorter minimum tails were already smaller, and a longer subsequence ending at $z$ would require an old tail in position at least $r$ smaller than $z$, contrary to the replacement rule. This proves the invariant inductively. Consequently the first-row length is the longest increasing subsequence length. The row entries need not be a subsequence together: input $2,4,3,1$ gives first row $1,3$, although one occurs after three. They are minima for different lengths, obtained from potentially different subsequences.

Sort the edge weights of a minimum spanning tree $T$ and of any spanning tree $S$ in nondecreasing order. Then $w_i(T)\le w_i(S)$ for every position. To prove it, fix a threshold $t$ and retain the graph's edges of weight at most $t$. If this graph has $c$ connected components, $T$ contains a spanning forest of each component using those edges: otherwise a light edge joining two of its pieces could replace an edge heavier than $t$ on its tree path, decreasing total weight. Hence exactly $|V|-c$ edges of $T$ have weight at most $t$. No other spanning tree can have more, since its retained edges form a forest inside those components. These threshold counts imply the coordinatewise inequality for sorted weights.

Start with isolated vertices. In each round, determine the current connected components of a graph, choose a least-weight outgoing edge for each component, add their union, and recompute the components. With distinct weights, each chosen edge is the unique lightest edge across that component's graph cut. The minimum spanning tree cut property puts every such edge in every minimum spanning tree, so the selected edges remain acyclic. Every nonfinal component has an outgoing edge in a connected input, and merging makes progress until a spanning tree remains. Duplicate choices of the same edge are one set insertion.

Each new component contains at least two old components, so there are $O(\log |V|)$ rounds. Scanning all edges per round gives $O(|E|\log |V|)$ time. Equal edge weights require a consistent secondary order to avoid choosing a cycle of tied edges.

Otakar Borůvka formulated the distinct-cost minimum-connection problem in 1926.^[ref]

Let an edge set $F$ be contained in some minimum spanning tree, and let a cut of a graph have no crossing edge in $F$. Any least-weight edge crossing that cut of a graph can be added to $F$ while preserving its containment in some minimum spanning tree. Insert the chosen edge into an optimum containing $F$, then remove another crossing edge from the resulting graph cycle; it is no lighter and cannot belong to $F$. Ties imply existence of an optimum containing the chosen edge, rather than membership in every optimum.

A minimizing sequence can converge uniformly while its derivatives keep oscillating between distinct energy wells. For the functional $I(u)={\int }_0^1[u^4+(u^{\prime 4}-16{)}^4]$, with zero endpoint values and Lipschitz admissible functions, the triangular waves displayed above have slopes $\pm 2$ almost everywhere and height $1/N$. Direct integration gives $I(u_N)=1/(5N^4)$. Nonnegativity therefore makes the infimum zero. Attainment would require both $u=0$ and $|u^{\prime }|=2$ almost everywhere, an impossibility. The uniform limit is zero but its energy is $16^4$; thus the energy fails to be lower semicontinuous for this convergence. The example explains why control of function values alone cannot replace suitable convexity in the derivative variable in the direct method in the calculus of variations.

Let $A$ be a companion matrix of a monic irreducible polynomial $f\in F[x]$ of degree $n$. Form the $N$-by-$N$ block matrix $B$ with $A$ on its diagonal, $I_n$ immediately above the diagonal, and zero elsewhere. If the field characteristic is $p>0$, write $f(x)=h(x^q)$ with $q=p^r$ maximal, so that $h^{\prime }\ne 0$; in characteristic zero take $q=1$ and $h=f$. ThenThus a separable polynomial gives $m_B=f^N$, but an irreducible polynomial with zero formal derivative can give a smaller exponent. For example, over the rational function field ${\mathbb{F}}_2(t)$, the irreducible polynomial $f(x)=x^2-t$ has $q=2$, so a two-block chain still has minimal polynomial $f$.

To prove the formula, write $B=D+K$, where $D$ has diagonal blocks $A$ and $K$ is the block shift. These are commuting operators, and $K^j$ vanishes exactly when $j\ge N$. The binomial theorem in positive field characteristic gives $B^q=D^q+K^q$. Expanding $h(D^q+K^q)$ gives $f(B)=K^{q}H$, with $H$ commuting with $K$. The diagonal blocks of $H$ are $h^{\prime }(A^q)$, which are invertible by Bézout's identity for polynomials, since $h$ is irreducible with nonzero formal derivative and $h(A^q)=0$. Therefore $f(B{)}^s=K^{qs}{H}^s$ vanishes exactly when $qs\ge N$. Finally, the block upper triangular matrix determinant gives the displayed characteristic polynomial, while the Cayley-Hamilton theorem and irreducibility force the minimal polynomial to be a power of $f$.

For a linear operator $T$ on an $n$-dimensional vector space over a field, the polynomials annihilating a fixed vector $v$ form an ideal of $K[X]$. It is nonzero because $v,Tv,\dots ,T^{n}v$ are linearly dependent. Since $K[X]$ is a principal ideal domain, its unique monic generator $m_v$ exists and has degree at most $n$. It divides $f$ exactly when $f(T)v=0$. For $v=0$ it equals one. Its degree is the dimension of the cyclic subspace generated by $v$: the vectors up to $T^{d-1}v$ are independent by minimality and span an invariant space by the annihilating recurrence.

For a linear operator on a finite-dimensional vector space, an eigenvector gives $m_T(T)v=m_T(\lambda )v=0$, proving the forward implication from eigenvalue to root. Conversely write $m_T(X)=(X-\lambda )q(X)$. If $T-\lambda I$ were invertible, the equation $(T-\lambda I)q(T)=0$ would imply $q(T)=0$, contradicting minimal degree. Thus $T-\lambda I$ has a nonzero kernel of a linear map. The equivalence concerns roots in the scalar field; roots in an extension describe eigenvalues after extending scalars.

For a linear operator on a finite-dimensional vector space over a field $K$, all polynomial kernels stabilize at their first power exactly when its minimal polynomial $m$ has no repeated irreducible polynomial factor in $K[X]$. This formulation does not require those factors to be linear.

To prove it, the Bézout's identity for polynomials gives $\ker q(T)=\ker \gcd (q,m)(T)$: a greatest common divisor is a combination of $q$ and $m$, while $q$ is its multiple. If $m$ is square-free, $\gcd (p^n,m)=\gcd (p,m)$, proving the displayed equality. Conversely, if an irreducible factor $f$ occurs to exponent $e\ge 2$, its primary decomposition theorem summand has minimal polynomial $f^e$. On this summand $f(T)$ is nonzero, while $f(T{)}^e=0$. Thus the kernels of those two powers differ. An eigenbasis follows from this criterion precisely when the distinct factors of $m$ are also linear over $K$; a real rotation through a right angle has square-free $m=X^2+1$ but no real eigenvalues.

A finite conjunction from the signed atomic diagram of $A$ becomes, after existentially closing its new names, a sentence in its existential theory. Joint satisfiability with $T$ therefore makes the full diagram finitely satisfiable with $T$. Compactness gives the embedding, with inequalities ensuring injectivity and signed atomic formulas ensuring both preservation and reflection of relations as required for a structure embedding. The reverse implication is preservation of existential truth under embeddings.

A communication object with an output port used to send values and an input port used to receive them. Its contract specifies ordering, capacity, sharing and closure. In synchronous message passing, a send completes through a matching receive; a buffered message-passing channel can retain accepted values until a receiver is ready.