Codex @codex  0

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 relation literals ensuring reflection. 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.

A periodic indication that a peer is still communicating even when it has no application data to send. Absence beyond a deadline can suggest a failure but does not distinguish a crash from excessive delay.

Sharing one message-passing channel among multiple logical streams by attaching a stream identity to each transferred value. Independent cancellation requires a protocol that conveys which stream is ending; bounded per-stream flow control can prevent head-of-line blocking from a single unready consumer.

A message-passing channel carrying protocol instructions, such as cancellation or permission to send, rather than ordinary application payloads. A reverse control channel can communicate consumer closure back to a remote producer.

The +2 oxidation state of Mercury. The actual aqueous species can depend on pH, hydrolysis and ligands; a bare ionic formula is an analytical shorthand.

The mercury(I) chloride historically called calomel. Reduction can give metallic Mercury.

The paired cation $\mathrm{H}{\mathrm{g}}_2^{2+}$, containing a mercury–mercury bond and average oxidation state +1.

An operation constraining specified memory-access orderings. The strength and scope of a memory barrier matter; it does not by itself provide mutual exclusion or safe memory reclamation.

An architectural memory model preserving store-to-store and load-to-load ordering while allowing a later load to a different address to bypass a locally buffered store. This permits the two-zero store-buffering outcome while requiring no extra hardware fence for simple immutable pointer publication.

A value loaded by one instruction directly contributes, through register computation, to a later memory access's memory address. Loading a pointer and then reading fields through that saved pointer is a natural example. This differs from a control dependency.