The dual linear program is the minimization problemIndeed, for $y\ge 0$ the optimization Lagrangian $c^{T}x+y^T(b-Ax)$ bounds the primal objective above on its feasible points. Its supremum over $x\ge 0$ is finite precisely when $A^{T}y\ge c$, and then equals $b^{T}y$. The two labelled parts below establish the relevant weak duality and strong duality conclusions.

For the subsequent infeasibility argument, introduce nonnegative slack variables $s$ and the convex coneThis is generated by the columns of $A$ and the coordinate vectors. Here is why this finitely generated cone is closed. Any representation with a minimal number of positive coefficients uses linearly independent generators: otherwise subtract a suitable multiple of a dependence until one positive coefficient vanishes, preserving nonnegativity. For each fixed independent selection of generators, its nonnegative combinations form a closed set, because the inverse coordinate map on its span is continuous. There are finitely many selections, so their union $C$ is closed. This is the closedness of finitely generated cones used in Farkas' lemma.

When the primal linear program is infeasible, $b\notin C$. Let $p$ be the nearest point of $C$ to $b$, and set $h=p-b$. The minimizing property gives $h^T(z-p)\ge 0$ for every $z\in C$. Taking $z=0,2p$ gives $h^{T}p=0$. ConsequentlyIn particular $h\ge 0$ and $A^{T}h\ge 0$. Rescaling $h$ by the positive number $-h^{T}b$ produces the requested Farkas' lemma certificate:Now a feasible point of the relaxed inequalities would satisfySince ${\lambda }^{T}b=-1$, the sum of the nonnegative ${\lambda }_i$ is positive. Thus robust infeasibility under uniform constraint relaxation givesThe ellipsoid method makes progress by reducing the volume of a containing ellipsoid. A nonempty linear polyhedron may have empty interior, so small volume alone cannot certify that the original system is infeasible. Relaxing the inequalities remedies this difficulty, but must not make an infeasible system appear feasible. The displayed positive gap proves exactly that sufficiently small relaxations preserve infeasibility. For rational input, determinant bounds give a Farkas' lemma certificate of polynomial encoding length, so a sufficiently small rational relaxation can be chosen from the input encoding length. Together with a bounding box and bounds on the volume of a relaxed feasible system, this lets the ellipsoid method distinguish infeasibility from a feasible system of very small or zero original volume in polynomial time. The certificate argument alone does not assert a polynomial precision bound for arbitrary unencoded real coefficients.

An abelian category is an additive category with kernels in a category and cokernels in a category in which the canonical comparison from coimage to image of every morphism is an isomorphism. This is the standard image-coimage form of the definition, equivalently expressed by normality of every monomorphism and epimorphism. Additivity means abelian-group hom-sets with bilinear composition, a zero object and finite biproducts. A sequence is exact at an object when the image of the incoming morphism is the kernel in a category of the outgoing one.

For $f:X\to Y$, construct $q:X\to \mathrm{coim}f=\mathrm{coker}(\ker f)$ and $j:\mathrm{im}f=\ker (\mathrm{coker}f)\to Y$. The universal properties give $f=j\bar{f}q$: first $f$ kills its kernel in a category and factors through $q$; then the resulting map is killed by $\mathrm{coker}f$ because $q$ is epic, so it factors through $j$. The comparison $\bar{f}$ is invertible by the abelian axiom. Cokernels in a category are epic and kernels in a category monic, directly by uniqueness in their universal properties, so $e=\bar{f}q$ is epic and $j$ monic. Thus $\boxed{f=je\text{ is an epimorphism-monomorphism factorization}}$.

In a short exact sequence $0\to X\stackrel{i}{\to }Y\stackrel{p}{\to }Z\to 0$, we have $i=\ker p$ and $p=\mathrm{coker}i$, up to the canonical isomorphisms. If $r:Y\to X$ retracts $i$, the map $1_Y-ir$ kills $i$ and factors as $sp$ for some $s:Z\to Y$. Composing with $p$ gives $psp=p$, so epicity gives $ps=1_Z$. Conversely if $ps=1_Z$, then $1_Y-sp$ is killed by $p$ and factors as $ir$. Composing with $i$ gives $iri=i$, so monicity gives $ri=1_X$. ConsequentlyIn that case $Y\cong X\oplus Z$.

For the derived-functor requests, use additive right exact functors, as customary in abelian homological algebra. An abelian category with enough projectives permits an augmented projective resolution $\cdots \to P_2\to P_1\to P_0\to X\to 0$, obtained by repeatedly taking an epimorphism from a projective onto the previous kernel in a category. Apply $F$ and defineProjective lifts construct maps of resolutions; the comparison and chain-homotopy results make the construction independent of choices and functorial. For a short exact sequence, the horseshoe construction produces a degreewise split short exact sequence of resolutions, hence of their images under additive $F$. Its homology objects give the long exact sequenceThis supplies the requested sketch; detailed comparison and functoriality proofs are not needed here.

A projective object $X$ has a resolution concentrated in degree zero, so $L_{1}F(X)=0$ for every such $F$. Conversely choose $0\to K\stackrel{i}{\to }P\to X\to 0$ with $P$ projective, and take $F=\mathcal{A}(-,K)$ with target ${\mathbf{Ab}}^{\mathrm{op}}$. Precomposition makes this covariant to the opposite category. The usual left exactness of contravariant Hom, which follows directly from the cokernel in a category universal property, says exactly that this $F$ is right exact in that opposite target. If $L_{1}F(X)=0$, the long exact sequence and $L_{1}F(P)=0$ make $F(K)\to F(P)$ monic in ${\mathbf{Ab}}^{\mathrm{op}}$. Equivalently,is epic, hence surjective, in abelian groups. The identity of $K$ has a preimage, giving a retraction of $i$. The sequence splits, and $X$ is a direct summand of $P$, hence projective: a lifting problem for $X$ extends along the projection $P\to X$, is solved for $P$, and restricts along the summand inclusion. ThereforeThis is projectivity detected by all first left derived functors. The following parts prove the three requested equivalent formulations of a hereditary abelian category with enough projectives.

A balanced category is one in which every morphism that is both monic and epic is an isomorphism. If a faithful functor sends $f$ to an isomorphism, then $f$ is monic: equality $fg=fh$ becomes $FfFg=FfFh$, cancellation gives $Fg=Fh$, and faithfulness gives $g=h$. The same argument on the other side makes $f$ epic. Balance therefore makes $f$ an isomorphism. Thus a faithful functor out of a balanced category reflects isomorphisms.

Under the adjunction, the transpose of $Ff:FX\to FA$ is ${\eta }_{A}f:X\to GFA$. Hence if $F$ is faithful, ${\eta }_{A}f={\eta }_{A}g$ forces $Ff=Fg$ and then $f=g$, making every ${\eta }_A$ monic. Conversely, if the unit is pointwise monic and $Ff=Fg$, naturality gives ${\eta }_{B}f=GFf{\eta }_A=GFg{\eta }_A={\eta }_{B}g$, whence $f=g$. ThereforeWe also use the standard adjunction fact with its justification: $F$ is full and faithful exactly when $\eta$ is invertible. Indeed the composite hom-set map $\mathcal{C}(X,A)\to \mathcal{D}(FX,FA)\cong \mathcal{C}(X,GFA)$ is postcomposition by ${\eta }_A$. If $F$ is full and faithful these maps are bijective; taking $X=GFA$ produces a right inverse, and taking $X=A$ gives injectivity and therefore a left inverse. Conversely an invertible unit makes these hom-set maps bijective.

For the final example, view the two-element ordered set $0<1$ as a category $\mathcal{C}$, and let $\mathcal{D}$ have one object and only its identity. The unique $F:\mathcal{C}\to \mathcal{D}$ is left adjoint to the functor $G$ selecting $1$, since every $\mathcal{C}(x,1)$ is a singleton. Every arrow in an ordered-set category is monic, so the unit arrows $x\to 1$ and the identity counit are monic. But $F$ is not full: $\mathcal{C}(1,0)$ is empty whereas $\mathcal{D}(F1,F0)$ is a singleton. The example does not contradict the upcoming equivalence because $\mathcal{C}$ is not balanced; its arrow $0\to 1$ is both monic and epic but not invertible.

The comma category $(A\downarrow F)$ has objects $(C,u)$ with $C\in \mathcal{C}$ and $u:A\to FC$ a set map. A morphism $(C,u)\to (D,v)$ is an arrow $h:C\to D$ such that $Fh\circ u=v$. Composition and identities are those of $\mathcal{C}$. For $A=1$, this is the category of elements $E$ of $F$: objects are $(C,x)$ with $x\in FC$ and arrows satisfy $Fh(x)=y$.

Associate to $(C,x)$ the covariant representable functor $H_C=\mathcal{C}(C,-)$. An arrow $h:(C,x)\to (D,y)$ of $E$ gives, by precomposition, $H_D\to H_C$. Thus this is a diagram $H:E^{\mathrm{op}}\to [\mathcal{C},\mathbf{Set}]$. There is a compatible natural map $H_C\to F$ sending $f:C\to B$ to $Ff(x)$.

Colimits in this functor category are pointwise. At an object $B$, the induced map from the colimit sends a class represented by $(C,x,f:C\to B)$ to $Ff(x)$. It is surjective because $z\in FB$ is represented by $(B,z,1_B)$. It is injective because every representative with value $z$ is identified with that same canonical representative: the arrow $f:(C,x)\to (B,z)$ in $E$ becomes an arrow of the indexing diagram sending $1_B$ to $f$. These bijections are natural in $B$, provingSmallness of $\mathcal{C}$ and set-valuedness of $F$ ensure that $E$ is small, so the displayed colimit is defined. This proves the introductory density request before the three equivalent conditions.

The Higman embedding theorem says that a finitely generated group embeds in a finitely presented group if and only if it has a recursive presentation of a group, that is, a presentation on finitely many generators with a recursively enumerable set of relators. We use its embedding direction as an assumed theorem. The reverse direction follows by expressing subgroup generators as words in the larger group and enumerating finite products of conjugates of its relators and their inverses; comparison after free reduction enumerates all null words in the subgroup. This is the enumerable identities of finitely generated subgroups argument. The theorem does not assume that the recursively presented group's word problem for a group is decidable.

Use the Riemannian curvature two-form conventionand define its four-covariant Riemann curvature tensor by $R(X,Y,Z,W)=g(R(X,Y)W,Z)$. This makes $R(X,Y,X,Y)$ positive on an orthonormal two-plane of the unit sphere. The full algebraic symmetries areTogether with multilinearity, these are antisymmetry in each pair, interchange of pairs, and the first Bianchi identity.

Define the Ricci tensor by the basis-independent contractionfor any orthonormal basis $(e_a)$. The trace is invariant under change of basis, and contraction of the smooth curvature tensor gives a smooth covariant two-tensor. Pair interchange gives $R(e_a,Y,e_a,W)=R(e_a,W,e_a,Y)$, so $\mathrm{Ric}(Y,W)=\mathrm{Ric}(W,Y)$. Thus the Ricci tensor is a symmetric covariant 2-tensor.

The sectional curvature of the two-plane $\sigma =\mathrm{span}(u,v)$ isBoth numerator and denominator multiply by the square of the determinant under a change of basis of $\sigma$, so this is a plane invariant. The directional Ricci curvature of $u\ne 0$ is $\mathrm{Ric}(u,u)/g(u,u)$. For an orthonormal basis beginning with $u/|u|$, it equals the sum of the sectional curvatures of the planes containing that basis vector.

In dimension three, suppose this directional value is $c$ at the point under consideration. For any orthonormal triple $(e_1,e_2,e_3)$, put $K_{ij}=K(\mathrm{span}(e_i,e_j))$. Thenso all three are $c/2$. Every two-plane can be the span of the first two members of such a triple. ConsequentlyThis is a pointwise conclusion, as required; it uses sectional curvatures from Ricci curvature in dimension three and asserts no spatial constancy.

For the product, the canonical identification $T_{(p,q)}(M\times N)=T_{p}M\oplus T_{q}N$ defines the product Riemannian metricIt is smooth in product charts and positive definite, since a nonzero vector has a nonzero component in at least one factor. Those components are orthogonal. The coordinate connection computation in the subparts below givesTaking the trace in orthonormal bases of the two factors therefore gives ${\mathrm{Ric}}_{M\times N}={\mathrm{Ric}}_M\oplus {\mathrm{Ric}}_N$.

For the final example choose the two round unit spheres. Each has sectional curvature one and Ricci tensor equal to its metric. Hence the product has $\mathrm{Ric}=g$, so every directional Ricci curvature is one. A two-plane tangent to one factor has sectional curvature one, whereas a mixed two-plane has sectional curvature zero by (iii). This gives constant Ricci curvature without constant sectional curvature:Both kinds of plane occur at every point, so the sectional curvatures fail to be constant even at a single point.

For closed connected oriented $d$-manifolds, the degree of a map between oriented manifolds is the integer defined by $f_{\ast }[M]=(\mathrm{deg}f)[N]$ in $H_d(N;\mathbb{Z})$. If $y\in N$ has finite fiber $\{x_1,\dots ,x_r\}$, choose disjoint small neighbourhoods $U_i$ containing no other points of that fiber. The map of local relative homology groupssends the local orientation generator at $x_i$ to $d_i$ times the one at $y$. This integer is its local degree of a continuous map, independent of the small neighbourhood by excision. Excision also identifies $H_d(M,M\setminus f^{-1}(y))$ with the direct sum of the local groups, and the global fundamental class restricts to their orientation generators. Naturality of the maps to relative homology therefore proves the degree as a sum of local degrees:The empty fiber gives degree zero. For smooth maps at a regular value, a local degree is the sign of the derivative determinant, but general continuous maps can have larger local multiplicities.

For the unrestricted zero sequence, introduce the Weierstrass elementary factorsFor $|u|\le 1/2$, cancellation of the first $p$ terms of the logarithm power series gives a holomorphic logarithm of the factor:Define the canonical productFix any compact disc $|z|\le R$. Since $|z_n|\to \infty$, eventually $|z/z_n|\le 1/2$ uniformly on this disc. The tail logarithms are then bounded by $2(1/2{)}^{n+1}$, a summable bound independent of $z$. Their sum is holomorphic by locally uniform convergence of holomorphic functions, and its exponential is nowhere zero. Multiplication by the finite initial product therefore gives an entire function. Each factor has a simple zero exactly at its specified $z_n$, the exponential factor has none, and a tail beginning beyond any given compact disc is nonvanishing there. Thus $f$ has precisely the prescribed zeros and no others, each simple, and $f(0)=1$. This proves the required existence without an assumption on ${\sum }_n|z_n{|}^{-1}$.

For the final, unheaded product request, suppose now that ${\sum }_n|z_n{|}^{-1}<\infty$. On $|z|\le R$, all sufficiently late factors have $|z/z_n|\le 1/2$, so part (a) bounds their principal complex logarithms by $2R/|z_n|$. The logarithms converge absolutely and uniformly; infinite product convergence from logarithmic tails proves thatis entire and again has exactly the prescribed simple zeros. For its finite partial products,Passing to the limit provesIn particular $P$ is an entire function of exponential type. This argument uses a valid modulus estimate and does not require the false logarithm assertion in part (c).

Choose $0<R<R_1$, $0<S<S_1$ and $0<T<T_1$. On this smaller closed polydisc, the holomorphic function $A$ and its $w$-derivative are bounded; write $|A|\le M$ and $|{\partial }_{w}A|\le L$. Choose $0<r<R$ with $rM<S/2$ and $rL<1$, replacing a zero bound by any positive upper bound if necessary, and choose $0<\epsilon <T$.

Consider functions $u(z,\alpha )$ continuous on $\overline{D(0,r)}\times \overline{D(0,\epsilon )}$, jointly holomorphic in the interior, with $u(0,\alpha )=0$ and $\Vert u{\Vert }_{\infty }\le S/2$. This is a closed subset of a Banach space in the supremum norm. The integral operatoris well defined on the straight segment and is jointly holomorphic. Indeed, it equals $z{\int }_0^{1}A(tz,u(tz,\alpha ),\alpha )dt$, an integral of jointly holomorphic functions locally uniformly bounded in both variables. Convexity of the $w$-disc and the derivative bound giveThus the Banach fixed-point theorem gives a fixed point $f(z,\alpha )$. More explicitly, the successive integral iterates starting from zero converge uniformly, and locally uniform convergence of holomorphic functions makes their limit jointly holomorphic. Differentiating the integral equation gives the required complex ordinary differential equation and initial value. This proves local existence, uniqueness and joint holomorphic dependence on $(z,\alpha )$. Uniqueness among arbitrary local solutions follows first on a small disc where their values stay within $|w|<S$, by the same contraction mapping estimate, and then throughout their common connected domain by the identity theorem.

For holomorphic dependence of ordinary differential equations on parameters in the initial value, fix an admissible initial value $w_{\ast }$ and put $u=f-w_0$. The equation becomesIts right-hand side is jointly holomorphic in $(z,u,w_0)$ near $(0,0,w_{\ast })$. The preceding construction supplies a common disc and a jointly holomorphic solution for $w_0$ near $w_{\ast }$. Consequently $f=u+w_0$ is jointly holomorphic in $z$ and its initial value $w_0$.

Take a nonzero complex unital Banach algebra, with identity $1$. The spectrum of an element isThe standard Banach algebra spectrum theorem states that it is a nonempty compact subset of $\mathbb{C}$, contained in the disk $|\lambda |\le \Vert a\Vert$. Conversely, every nonempty compact set $K\subseteq \mathbb{C}$ occurs: in the Banach algebra $C(K)$, the coordinate function $a(z)=z$ has Banach algebra spectrum exactly $K$, since $\lambda -a$ has a continuous reciprocal precisely when $\lambda \notin K$. Thus the possible Banach algebra spectra are exactly the nonempty compact subsets of the complex plane.

For a nonconstant polynomial $p$, factor $p(z)-\lambda =c{\prod }_{j=1}^n(z-z_j)$ over $\mathbb{C}$. Substitution givesThese factors commute. A finite commuting product is invertible exactly when every factor is invertible: if $P={\prod }_j{x}_j$ is invertible, its inverse commutes with each $x_j$, and $x_j^{-1}=({\prod }_{k\ne j}{x}_k)P^{-1}$ is a two-sided inverse. Hence $\lambda$ belongs to the Banach algebra spectrum of $p(a)$ exactly when some root $z_j$ belongs to ${\sigma }_A(a)$, which is equivalent to $\lambda \in p({\sigma }_A(a))$. Constant polynomials give the same result directly, since ${\sigma }_A(c1)=\{c\}$. This proves the polynomial spectral mapping theorem:For a closed unital Banach subalgebra $B\subseteq A$, use the common identity $1_A\in B$. An inverse in $B$ is an inverse in $A$, so $\boxed{{\sigma }_A(b)\subseteq {\sigma }_B(b)}$. Let $\lambda \in \partial {\sigma }_B(b)$. Choose ${\lambda }_n\notin {\sigma }_B(b)$ tending to $\lambda$. Then ${\lambda }_n\notin {\sigma }_A(b)$, and $({\lambda }_{n}1-b{)}^{-1}\in B$. If $\lambda$ were outside ${\sigma }_A(b)$, continuity of inversion in $A$ would givewhere membership follows from closedness. This would make $\lambda \notin {\sigma }_B(b)$, contrary to the closed Banach algebra spectrum having its boundary inside it. Therefore $\lambda \in {\sigma }_A(b)$ and is approached by points outside that Banach algebra spectrum, provingContinuity of inversion here follows, for example, by writing a nearby element as an invertible element times $1+$ a norm-small perturbation and using the Neumann series. This is spectrum in a closed unital subalgebra.

To retain the original Banach algebra spectrum in a commutative subalgebra, take the resolvent-generated commutative algebraEvery generator commutes with $a$ and with every other generator: commuting invertible elements have commuting inverses, and their inverses commute with all elements commuting with them. commutativity persists on the algebra they generate and on its norm closure. For every $\lambda \notin {\sigma }_A(a)$, the required inverse is in $C$ by construction, so ${\sigma }_C(a)\subseteq {\sigma }_A(a)$. The inclusion for unital subalgebras gives the reverse containment. Hence $\boxed{{\sigma }_C(a)={\sigma }_A(a)}$.

Finally, the Banach subalgebra generated by one element is $D=\overline{\{p(a):p\text{ a polynomial}\}}$, and it is commutative. Put $K={\sigma }_D(a)$ and suppose its complement has a bounded connected component $U$. The boundary of $U$ lies in $K$. For $\lambda \in U$, the maximum modulus principle on a bounded domain applied to any polynomial givesHere $r_D$ is the spectral radius, and the equality uses the already proved polynomial spectral mapping theorem. Define $\chi (p(a))=p(\lambda )$. The displayed bound makes this well defined, even when two polynomials represent the same algebra element, and bounded on the dense polynomial algebra. Its continuous extension to $D$ remains linear and multiplicative, with $\chi (1)=1$ and $\chi (a)=\lambda$, so it is a character of an algebra. If $\lambda 1-a$ were invertible in $D$, applying $\chi$ to its inverse equation would give $0=1$. Thus $\lambda \in K$, contradicting $\lambda \in U$.

There are therefore no bounded complementary components. A compact subset of the plane has exactly one unbounded complementary component: everything outside a sufficiently large disk is connected, and every unbounded component meets it. Consequently $\boxed{\mathbb{C}\setminus {\sigma }_D(a)\text{ is connected}.}$

Let $d={\inf }_{v\in V}\Vert f-v\Vert$ and choose $v_n\in V$ with $\Vert f-v_n\Vert \to d$. The parallelogram identity givesCompleteness and closedness give $v_n\to v\in V$, attaining the distance. Put $w=f-v$. For $u\in V$ and real $t$, minimality gives $\Vert w-tu{\Vert }^2\ge \Vert w{\Vert }^2$, so $\mathrm{Re}⟨w,u⟩=0$. In a complex Hilbert space, also replace $u$ with $iu$ to get the imaginary part zero. ThereforeThe decomposition is unique since $V\cap V^{\perp }=\{0\}$. This proves the required orthogonal projection result rather than assuming it before the averaging argument.

If $g^{\prime }$ never vanishes on $[a,b]$, integration by parts gives $I(\lambda )=[f(t)e^{i\lambda g(t)}/(i\lambda g^{\prime }(t)){]}_a^b-(i\lambda {)}^{-1}{\int }_a^b(f/g^{\prime }{)}^{\prime }{e}^{i\lambda g(t)}dt$, hence $\boxed{I(\lambda )=O({\lambda }^{-1})}$ for smooth $f,g$. Endpoint terms usually attain this order; special cancellation can give faster decay.

For the final integral, take the imaginary part of ${\int }_0^1{e}^{i\lambda (t^3-t)}dt$. Its sole stationary point is $t_0=1/\sqrt{3}$, with $g(t_0)=-2/(3\sqrt{3})$ and $g^{\prime \prime }(t_0)=2\sqrt{3}$. The stationary phase formula in part (a) therefore gives

An irreducible continuous-time Markov chain is positive recurrent when the mean return time to a state is finite, and null recurrent when return occurs almost surely but the mean return time is infinite. For the nonexplosive chain here, whose rates are bounded, positive recurrence is equivalent to existence of a normalized stationary distribution. All rates are understood to be positive.

For a positively oriented simple closed curve on which the vector field is nonzero, its Poincaré index is the total rotation of the vector field along that curve divided by $2\pi$, equivalently the winding number of its normalized direction. The Poincaré index of an isolated fixed point is that of a sufficiently small enclosing curve containing no other fixed point. The index of a planar periodic orbit is $+1$.

Let $1$ be the constant function and define $h=L1\in C([0,1])$. Positivity gives $h\ge 0$. Fix any $x$ and any continuous $f$. The function $g=f-f(x)1$ vanishes at $x$, so the zero-preserving assumption gives $Lg(x)=0$. By linearity this is $Lf(x)-f(x)L1(x)=0$. Since $x$ was arbitrary,This proves the zero-preserving linear operator on continuous functions representation. Zero preservation and linearity determine the multiplication operator; positivity is needed only for the multiplier's sign. The three numbered conditions in the source are hypotheses of this one request, rather than three separate subquestions.