Valuation (algebra)

In algebra (in particular in algebraic geometry or algebraic number theory), a valuation is a function on a field that provides a measure of size or multiplicity of elements of the field. It generalizes to commutative algebra the notion of size inherent in consideration of the degree of a pole or multiplicity of a zero in complex analysis, the degree of divisibility of a number by a prime number in number theory, and the geometrical concept of contact between two algebraic or analytic varieties in algebraic geometry. A field with a valuation on it is called a valued field.
Definition.
One starts with the following objects:
The ordering and group law on are extended to the set } by the rules
Then a valuation of is any map
which satisfies the following properties for all "a", "b" in "K":
A valuation "v" is trivial if "v"("a") = 0 for all "a" in "K"×, otherwise it is non-trivial.
The second property asserts that any valuation is a group homomorphism. The third property is a version of the triangle inequality on metric spaces adapted to an arbitrary Γ (see "Multiplicative notation" below). For valuations used in geometric applications, the first property implies that any non-empty germ of an analytic variety near a point contains that point.
The valuation can be interpreted as the order of the leading-order term. The third property then corresponds to the order of a sum being the order of the larger term, unless the two terms have the same order, in which case they may cancel, in which case the sum may have larger order.
For many applications, is an additive subgroup of the real numbers formula_1 in which case ∞ can be interpreted as +∞ in the extended real numbers; note that formula_2 for any real number "a", and thus +∞ is the unit under the binary operation of minimum. The real numbers (extended by +∞) with the operations of minimum and addition form a semiring, called the min tropical semiring, and a valuation "v" is almost a semiring homomorphism from "K" to the tropical semiring, except that the homomorphism property can fail when two elements with the same valuation are added together.
Multiplicative notation and absolute values.
We could define the same concept writing the group in multiplicative notation as : instead of ∞, we adjoin a formal symbol "O" to Γ, with the ordering and group law extended by the rules
Then a valuation of "K" is any map
satisfying the following properties for all "a", "b" ∈ "K":
If Γ is a subgroup of the positive real numbers under multiplication, the last condition is the ultrametric inequality, a stronger form of the triangle inequality , and "| - |v" is an absolute value. In this case, we may pass to the additive notation with value group formula_3 by taking "v"+("a") = −log "|a|v".
Each valuation on "K" defines a corresponding linear preorder: "a" ≼ "b" ⇔ "|a|v" ≤ "|b|v". Conversely, given a '≼' satisfying the required properties, we can define valuation "|a|v" = {"b": "b" ≼ "a" ∧ "a" ≼ "b"}, with multiplication and ordering based on "K" and ≼.
Terminology.
In this article, we use the terms defined above, in the additive notation. However, some authors use alternative terms:
Associated objects.
There are several objects defined from a given valuation ;
Basic properties.
Equivalence of valuations.
Two valuations "v"1 and "v"2 of with valuation group Γ1 and Γ2, respectively, are said to be equivalent if there is an order-preserving group isomorphism such that "v"2("a") = φ("v"1("a")) for all "a" in "K"×. This is an equivalence relation.
Two valuations of "K" are equivalent if and only if they have the same valuation ring.
An equivalence class of valuations of a field is called a place. "Ostrowski's theorem" gives a complete classification of places of the field of rational numbers formula_4 these are precisely the equivalence classes of valuations for the "p"-adic completions of formula_5
Extension of valuations.
Let "v" be a valuation of and let "L" be a field extension of . An extension of "v" (to "L") is a valuation "w" of "L" such that the restriction of "w" to is "v". The set of all such extensions is studied in the ramification theory of valuations.
Let "L"/"K" be a finite extension and let "w" be an extension of "v" to "L". The index of Γ"v" in Γ"w", e("w"/"v") = [Γ"w" : Γ"v"], is called the reduced ramification index of "w" over "v". It satisfies e("w"/"v") ≤ ["L" : "K"] (the degree of the extension "L"/"K"). The relative degree of "w" over "v" is defined to be "f"("w"/"v") = ["Rw"/"mw" : "Rv"/"mv"] (the degree of the extension of residue fields). It is also less than or equal to the degree of "L"/"K". When "L"/"K" is separable, the ramification index of "w" over "v" is defined to be e("w"/"v")"pi", where "pi" is the inseparable degree of the extension "Rw"/"mw" over "Rv"/"mv".
Complete valued fields.
When the ordered abelian group is the additive group of the integers, the associated valuation is equivalent to an absolute value, and hence induces a metric on the field . If is complete with respect to this metric, then it is called a complete valued field. If "K" is not complete, one can use the valuation to construct its completion, as in the examples below, and different valuations can define different completion fields.
In general, a valuation induces a uniform structure on , and is called a complete valued field if it is complete as a uniform space. There is a related property known as spherical completeness: it is equivalent to completeness if formula_6 but stronger in general.
Examples.
p-adic valuation.
The most basic example is the -adic valuation "v""p" associated to a prime integer "p", on the rational numbers formula_7 with valuation ring formula_8 where formula_9 is the localization of formula_10 at the prime ideal formula_11. The valuation group is the additive integers formula_12 For an integer formula_13 the valuation "v""p"("a") measures the divisibility of "a" by powers of "p":
and for a fraction, "v""p"("a"/"b") = "v""p"("a") − "v""p"("b").
Writing this multiplicatively yields the -adic absolute value, which conventionally has as base formula_15, so formula_16.
The completion of formula_17 with respect to "v""p" is the field formula_18 of p-adic numbers.
Order of vanishing.
Let K = F(x), the rational functions on the affine line X = F1, and take a point "a" ∈ X. For a polynomial formula_19 with formula_20, define "v""a"("f") = k, the order of vanishing at "x" = "a"; and "v""a"("f" /"g") = "v""a"("f") − "v""a"("g"). Then the valuation ring "R" consists of rational functions with no pole at "x" = "a", and the completion is the formal Laurent series ring F(("x"−"a")). This can be generalized to the field of Puiseux series "K" (fractional powers), the Levi-Civita field (its Cauchy completion), and the field of Hahn series, with valuation in all cases returning the smallest exponent of "t" appearing in the series.
-adic valuation.
Generalizing the previous examples, let be a principal ideal domain, be its field of fractions, and be an irreducible element of . Since every principal ideal domain is a unique factorization domain, every non-zero element "a" of can be written (essentially) uniquely as
where the "e"'s are non-negative integers and the "pi" are irreducible elements of that are not associates of . In particular, the integer "ea" is uniquely determined by "a".
The π-adic valuation of "K" is then given by
If π' is another irreducible element of such that (π') = (π) (that is, they generate the same ideal in "R"), then the π-adic valuation and the π'-adic valuation are equal. Thus, the π-adic valuation can be called the "P"-adic valuation, where "P" = (π).
"P"-adic valuation on a Dedekind domain.
The previous example can be generalized to Dedekind domains. Let be a Dedekind domain, its field of fractions, and let "P" be a non-zero prime ideal of . Then, the localization of at "P", denoted "RP", is a principal ideal domain whose field of fractions is . The construction of the previous section applied to the prime ideal "PRP" of "RP" yields the -adic valuation of .
Geometric notion of contact.
Valuations can be defined for a field of functions on a space of dimension greater than one. Recall that the order-of-vanishing valuation "v""a"("f") on formula_24 measures the multiplicity of the point "x" = "a" in the zero set of "f"; one may consider this as the order of contact (or local intersection number) of the graph "y" = "f"("x") with the "x"-axis "y" = 0 near the point ("a",0). If, instead of the "x"-axis, one fixes another irreducible plane curve "h"("x","y") = 0 and a point ("a","b"), one may similarly define a valuation "v""h" on formula_25 so that "v""h"("f") is the order of contact (the intersection number) between the fixed curve and "f"("x","y") = 0 near ("a","b"). This valuation naturally extends to rational functions formula_26
In fact, this construction is a special case of the π-adic valuation on a PID defined above. Namely, consider the local ring formula_27, the ring of rational functions which are defined on some open subset of the curve "h" = 0. This is a PID; in fact a discrete valuation ring whose only ideals are the powers formula_28. Then the above valuation "v""h" is the π-adic valuation corresponding to the irreducible element π = "h" ∈ "R".
Example: Consider the curve formula_29 defined by formula_30, namely the graph formula_31 near the origin formula_32. This curve can be parametrized by formula_33 as:
with the special point (0,0) corresponding to "t" = 0. Now define formula_35 as the order of the formal power series in obtained by restriction of any non-zero polynomial formula_36 to the curve :
This extends to the field of rational functions formula_38 by formula_39, along with formula_40.
Some intersection numbers:
Vector spaces over valuation fields.
Suppose that ∪ {0} is the set of non-negative real numbers under multiplication. Then we say that the valuation is non-discrete if its range (the valuation group) is infinite (and hence has an accumulation point at 0).
Suppose that "X" is a vector space over "K" and that "A" and "B" are subsets of "X". Then we say that A" absorbs "B if there exists a "α" ∈ "K" such that "λ" ∈ "K" and "|λ| ≥ |α|" implies that "B ⊆ λ A". "A" is called radial or absorbing if "A" absorbs every finite subset of "X". Radial subsets of "X" are invariant under finite intersection. Also, "A" is called circled if "λ" in "K" and "|λ| ≥ |α|" implies "λ A ⊆ A". The set of circled subsets of "L" is invariant under arbitrary intersections. The circled hull of "A" is the intersection of all circled subsets of "X" containing "A".
Suppose that "X" and "Y" are vector spaces over a non-discrete valuation field "K", let "A ⊆ X", "B ⊆ Y", and let "f : X → Y" be a linear map. If "B" is circled or radial then so is formula_42. If "A" is circled then so is "f(A)" but if "A" is radial then "f(A)" will be radial under the additional condition that "f" is surjective.


Touchard polynomials

The Touchard polynomials, studied by , also called the exponential polynomials or Bell polynomials, comprise a polynomial sequence of binomial type defined by
where formula_2is a Stirling number of the second kind, i.e., the number of partitions of a set of size "n" into "k" disjoint non-empty subsets.
Properties.
Basic properties.
The value at 1 of the "n"th Touchard polynomial is the "n"th Bell number, i.e., the number of partitions of a set of size "n":
If "X" is a random variable with a Poisson distribution with expected value λ, then its "n"th moment is E("X""n") = "T""n"(λ), leading to the definition:
Using this fact one can quickly prove that this polynomial sequence is of binomial type, i.e., it satisfies the sequence of identities:
The Touchard polynomials constitute the only polynomial sequence of binomial type with the coefficient of "x" equal 1 in every polynomial.
The Touchard polynomials satisfy the Rodrigues-like formula:
The Touchard polynomials satisfy the recurrence relation
and
In the case "x" = 1, this reduces to the recurrence formula for the Bell numbers.
Using the umbral notation "T""n"("x")="T""n"("x"), these formulas become:
The generating function of the Touchard polynomials is
which corresponds to the generating function of Stirling numbers of the second kind.
Touchard polynomials have contour integral representation:
Zeroes.
All zeroes of the Touchard polynomials are real and negative. This fact was observed by L. H. Harper in 1967.
The smallest zero is bounded from below (in absolute value) by
although it is conjectured that the smallest zero grows linearly with the index "n".
The Mahler measure formula_14of the Touchard polynomials can be estimated as follows:
\frac{\lbrace\textstyle{n\atop \Omega_n}\rbrace}{\binom{n}{\Omega_n}}\le M(T_n)\le\sqrt{n+1}\left\


Category of CW-complexes


Orthogonal basis

In mathematics, particularly linear algebra, an orthogonal basis for an inner product space is a basis for whose vectors are mutually orthogonal. If the vectors of an orthogonal basis are normalized, the resulting basis is an orthonormal basis.
As coordinates.
Any orthogonal basis can be used to define a system of orthogonal coordinates . Orthogonal (not necessarily orthonormal) bases are important due to their appearance from curvilinear orthogonal coordinates in Euclidean spaces, as well as in Riemannian and pseudo-Riemannian manifolds.
In functional analysis.
In functional analysis, an orthogonal basis is any basis obtained from an orthonormal basis (or Hilbert basis) using multiplication by nonzero scalars.
Extensions.
The concept of an orthogonal (but not of an orthonormal) basis is applicable to a vector space (over any field) equipped with a symmetric bilinear form , where "orthogonality" of two vectors and means . For an orthogonal basis :
where is a quadratic form associated with : (in an inner product space ).
Hence for an orthogonal basis ,
where and are components of and in the basis.


Moduli stack of vector bundles

In algebraic geometry, the moduli stack of rank-"n" vector bundles Vect"n" is the stack parametrizing vector bundles (or locally free sheaves) of rank "n" over some reasonable spaces.
It is a smooth algebraic stack of the negative dimension formula_1. Moreover, viewing a rank-"n" vector bundle as a principal formula_2-bundle, Vect"n" is isomorphic to the classifying stack formula_3
Definition.
For the base category, let "C" be the category of schemes of finite type over a fixed field "k". Then formula_4 is the category where
Let formula_9 be the forgetful functor. Via "p", formula_4 is a prestack over "C". That it is a stack over "C" is precisely the statement "vector bundles have the descent property". Note that each fiber formula_11 over "U" is the category of rank-"n" vector bundles over "U" where every morphism is an isomorphism (i.e., each fiber of "p" is a groupoid).


Lax natural transformation

In the mathematical field of category theory, specifically the theory of 2-categories, a lax natural transformation is a kind of morphism between 2-functors.
Definition.
Let "C" and "D" be 2-categories, and let formula_1 be 2-functors. A lax natural transformation formula_2 between them consists of
satisfying some equations (see or )


Philipp Habegger

Philipp Habegger (born 23 July 1978) is a Swiss mathematician and a professor of mathematics at the University of Basel who works in Diophantine geometry.
Early life and education.
Habegger was born on 23 July 1978. He received his Ph.D. under the supervision of David Masser at the University of Basel in 2007.
Career.
From 2008 to 2010, Habegger was a ETH Fellow at ETH Zurich. He moved to the University of Zurich for a lectureship position in 2010. In 2013, he was a von Neumann Fellow at the Institute for Advanced Study. As of 2021, Habegger is a professor of mathematics at the University of Basel.
Research.
Habegger's research focuses on height functions and their applications to unlikely intersections.


Q-Bessel polynomials

In mathematics, the "q"-Bessel polynomials are a family of basic hypergeometric orthogonal polynomials in the basic Askey scheme. give a detailed list of their properties.
Definition.
The polynomials are given in terms of basic hypergeometric functions by ：
<br>Also known as alternative q-Charlier polynomials formula_2
Orthogonality.
where formula_4 are q-Pochhammer symbols.


Analytic space

An analytic space is a generalization of an analytic manifold that allows singularities. An analytic space is a space that is locally the same as an analytic variety. They are prominent in the study of several complex variables, but they also appear in other contexts.
Definition.
Fix a field "k" with a valuation. Assume that the field is complete and not discrete with respect to this valuation. For example, this includes R and C with respect to their usual absolute values, as well as fields of Puiseux series with respect to their natural valuations.
Let "U" be an open subset of "k""n", and let "f"1, ..., "f""k" be a collection of analytic functions on "U". Denote by "Z" the common vanishing locus of "f"1, ..., "f""k", that is, let "Z" = { "x" | "f"1("x") = ... = "f""k"("x") = 0 }. "Z" is an analytic variety.
Suppose that the structure sheaf of "U" is formula_1. Then "Z" has a structure sheaf formula_2, where formula_3 is the ideal generated by "f"1, ..., "f""k". In other words, the structure sheaf of "Z" consists of all functions on "U" modulo the possible ways they can differ outside of "Z".
An analytic space is a locally ringed space formula_4 such that around every point "x" of "X", there exists an open neighborhood "U" such that formula_5 is isomorphic (as locally ringed spaces) to an analytic variety with its structure sheaf. Such an isomorphism is called a local model for "X" at "x".
An analytic mapping or morphism of analytic spaces is a morphism of locally ringed spaces.
This definition is similar to the definition of a scheme. The only difference is that for a scheme, the local models are spectra of rings, whereas for an analytic space, the local models are analytic varieties. Because of this, the basic theories of analytic spaces and of schemes are very similar. Furthermore, analytic varieties have much simpler behavior than arbitrary commutative rings (for example, analytic varieties are defined over fields and are always finite-dimensional), so analytic spaces behave very similarly to finite-type schemes over a field.
Basic results.
Every point in an analytic space has a local dimension. The dimension at "x" is found by choosing a local model at "x" and determining the local dimension of the analytic variety at the point corresponding to "x".
Every point in an analytic space has a tangent space. If "x" is a point of "X" and "mx" is ideal sheaf of all functions vanishing at "x", then the cotangent space at "x" is . The tangent space is , the dual vector space to the cotangent space. Analytic mappings induce pushforward maps on tangent spaces and pullback maps on cotangent spaces.
The dimension of the tangent space at "x" is called the embedding dimension at "x". By looking at a local model it is easy to see that the dimension is always less than or equal to the embedding dimension.
Smoothness.
An analytic space is called smooth at "x" if it has a local model at "x" which is an open subset of "k""n" for some "n". The analytic space is called smooth if it is smooth at every point, and in this case it is an analytic manifold. The subset of points at which an analytic space is not smooth is a closed analytic subset.
An analytic space is reduced if every local model for the space is defined by a radical sheaf of ideals. An analytic space "X" which isn't reduced has a reduction "X"red, a reduced analytic space with the same underlying topological space. There is a canonical morphism . Every morphism from "X" to a reduced analytic space factors through "r".
An analytic space is normal if every stalk of the structure sheaf is a normal ring (meaning an integrally closed integral domain). In a normal analytic space, the singular locus has codimension at least two. When "X" is a local complete intersection at "x", then "X" is normal at "x".
Non-normal analytic spaces can be smoothed out into normal spaces in a canonical way. This construction is called the normalization. The normalization "N"("X") of an analytic space "X" comes with a canonical map . Every dominant morphism from a normal analytic space to "X" factors through ν.
Coherent sheaves.
An analytic space is coherent if its structure sheaf formula_6 is a coherent sheaf. A coherent sheaf of formula_6-modules is called a coherent analytic sheaf. For example, on a coherent space, locally free sheaves and sheaves of ideals are coherent analytic sheaves.
Analytic spaces over algebraically closed fields are coherent. In the complex case, this is known as the Oka coherence theorem. This is not true over non-algebraically closed fields; there are examples of real analytic spaces that are not coherent.
Generalizations.
In some situations, the concept of an analytic space is too restrictive. This is often because the ground field has additional structure that is not captured by analytic sets. In these situations, there are generalizations of analytic spaces which allow more flexibility in the local model spaces.
For example, over the real numbers, consider the circle . The circle is an analytic subset of the analytic space R2. But its projection onto the "x"-axis is the closed interval , which is not an analytic set. Therefore the image of an analytic set under an analytic map is not necessarily an analytic set. This can be avoided by working with subanalytic sets, which are much less rigid than analytic sets but which are not defined over arbitrary fields. The corresponding generalization of an analytic space is a subanalytic space. (However, under mild point-set topology hypotheses, it turns out that subanalytic spaces are essentially equivalent to subanalytic sets.)


Noncommutative algebraic geometry

Noncommutative algebraic geometry is a branch of mathematics, and more specifically a direction in noncommutative geometry, that studies the geometric properties of formal duals of non-commutative algebraic objects such as rings as well as geometric objects derived from them (e.g. by gluing along localizations or taking noncommutative stack quotients).
For example, noncommutative algebraic geometry is supposed to extend a notion of an algebraic scheme by suitable gluing of spectra of noncommutative rings; depending on how literally and how generally this aim (and a notion of spectrum) is understood in noncommutative setting, this has been achieved in various level of success. The noncommutative ring generalizes here a commutative ring of regular functions on a commutative scheme. Functions on usual spaces in the traditional (commutative) algebraic geometry have a product defined by pointwise multiplication; as the values of these functions commute, the functions also commute: "a" times "b" equals "b" times "a". It is remarkable that viewing noncommutative associative algebras as algebras of functions on "noncommutative" would-be space is a far-reaching geometric intuition, though it formally looks like a fallacy.
Much of the motivation for noncommutative geometry, and in particular for the noncommutative algebraic geometry, is from physics; especially from quantum physics, where the algebras of observables are indeed viewed as noncommutative analogues of functions, hence having the ability to observe their geometric aspects is desirable.
One of the values of the field is that it also provides new techniques to study objects in commutative algebraic geometry such as Brauer groups.
The methods of noncommutative algebraic geometry are analogs of the methods of commutative algebraic geometry, but frequently the foundations are different. Local behavior in commutative algebraic geometry is captured by commutative algebra and especially the study of local rings. These do not have a ring-theoretic analogue in the noncommutative setting; though in a categorical setup one can talk about stacks of local categories of quasicoherent sheaves over noncommutative spectra. Global properties such as those arising from homological algebra and K-theory more frequently carry over to the noncommutative setting.
History.
Classical approach: the issue of non-commutative localization.
Commutative algebraic geometry begins by constructing the spectrum of a ring. The points of the algebraic variety (or more generally, scheme) are the prime ideals of the ring, and the functions on the algebraic variety are the elements of the ring. A noncommutative ring, however, may not have any proper non-zero two-sided prime ideals. For instance, this is true of the Weyl algebra of polynomial differential operators on affine space: The Weyl algebra is a simple ring. Therefore, one can for instance attempt to replace a prime spectrum by a primitive spectrum: there are also the theory of non-commutative localization as well as descent theory. This works to some extent: for instance, Dixmier's "enveloping algebras" may be thought of as working out non-commutative algebraic geometry for the primitive spectrum of an enveloping algebra of a Lie algebra. Another work in a similar spirit is Michael Artin’s notes titled “noncommutative rings”, which in part is an attempt to study representation theory from a non-commutative-geometry point of view. The key insight to both approaches is that irreducible representations, or at least primitive ideals, can be thought of as “non-commutative points”.
Modern viewpoint using categories of sheaves.
As it turned out, starting from, say, primitive spectra, it was not easy to develop a workable sheaf theory. One might imagine this difficulty is because of a sort of quantum phenomenon: points in a space can influence points far away (and in fact, it is not appropriate to treat points individually and view a space as a mere collection of the points).
Due to the above, one accepts a paradigm implicit in Pierre Gabriel's thesis and partly justified by the Gabriel–Rosenberg reconstruction theorem (after Pierre Gabriel and Alexander L. Rosenberg) that a commutative scheme can be reconstructed, up to isomorphism of schemes, solely from the abelian category of quasicoherent sheaves on the scheme. Alexander Grothendieck taught that to do geometry one does not need a space, it is enough to have a category of sheaves on that would be space; this idea has been transmitted to noncommutative algebra by Yuri Manin. There are, a bit weaker, reconstruction theorems from the derived categories of (quasi)coherent sheaves motivating the derived noncommutative algebraic geometry (see just below).
Derived algebraic geometry.
Perhaps the most recent approach is through the deformation theory, placing non-commutative algebraic geometry in the realm of derived algebraic geometry.
As a motivating example, consider the one-dimensional Weyl algebra over the complex numbers C. This is the quotient of the free ring C<"x", "y"> by the relation
This ring represents the polynomial differential operators in a single variable "x"; "y" stands in for the differential operator ∂"x". This ring fits into a one-parameter family given by the relations . When α is not zero, then this relation determines a ring isomorphic to the Weyl algebra. When α is zero, however, the relation is the commutativity relation for "x" and "y", and the resulting quotient ring is the polynomial ring in two variables, C["x", "y"]. Geometrically, the polynomial ring in two variables represents the two-dimensional affine space A2, so the existence of this one-parameter family says that "affine space admits non-commutative deformations to the space determined by the Weyl algebra." This deformation is related to the symbol of a differential operator and that A2 is the cotangent bundle of the affine line. (Studying the Weyl algebra can lead to information about affine space: The Dixmier conjecture about the Weyl algebra is equivalent to the Jacobian conjecture about affine space.)
In this line of the approach, the notion of "operad", a set or space of operations, becomes prominent: in the introduction to , Francis writes:
Proj of a noncommutative ring.
One of the basic constructions in commutative algebraic geometry is the Proj construction of a graded commutative ring. This construction builds a projective algebraic variety together with a very ample line bundle whose homogeneous coordinate ring is the original ring. Building the underlying topological space of the variety requires localizing the ring, but building sheaves on that space does not. By a theorem of Jean-Pierre Serre, quasi-coherent sheaves on Proj of a graded ring are the same as graded modules over the ring up to finite dimensional factors. The philosophy of topos theory promoted by Alexander Grothendieck says that the category of sheaves on a space can serve as the space itself. Consequently, in non-commutative algebraic geometry one often defines Proj in the following fashion: Let "R" be a graded C-algebra, and let Mod-"R" denote the category of graded right "R"-modules. Let "F" denote the subcategory of Mod-"R" consisting of all modules of finite length. Proj "R" is defined to be the quotient of the abelian category Mod-"R" by "F". Equivalently, it is a localization of Mod-"R" in which two modules become isomorphic if, after taking their direct sums with appropriately chosen objects of "F", they are isomorphic in Mod-"R".
This approach leads to a theory of non-commutative projective geometry. A non-commutative smooth projective curve turns out to be a smooth commutative curve, but for singular curves or smooth higher-dimensional spaces, the non-commutative setting allows new objects.


Matrix Chernoff bound

For certain applications in linear algebra, it is useful to know properties of the probability distribution of the largest eigenvalue of a finite sum of random matrices. Suppose formula_1 is a finite sequence of random matrices. Analogous to the well-known Chernoff bound for sums of scalars, a bound on the following is sought for a given parameter "t":
The following theorems answer this general question under various assumptions; these assumptions are named below by analogy to their classical, scalar counterparts. All of these theorems can be found in , as the specific application of a general result which is derived below. A summary of related works is given.
Matrix Gaussian and Rademacher series.
Self-adjoint matrices case.
Consider a finite sequence formula_3 of fixed,
self-adjoint matrices with dimension formula_4, and let formula_5 be a finite sequence of independent standard normal or independent Rademacher random variables.
Then, for all formula_6,
where
Rectangular case.
Consider a finite sequence formula_9 of fixed, self-adjoint matrices with dimension formula_10, and let formula_5 be a finite sequence of independent standard normal or independent Rademacher random variables.
Define the variance parameter
Then, for all formula_6,
Matrix Chernoff inequalities.
The classical Chernoff bounds concern the sum of independent, nonnegative, and uniformly bounded random variables.
In the matrix setting, the analogous theorem concerns a sum of positive-semidefinite random matrices subjected to a uniform eigenvalue bound.
Matrix Chernoff I.
Consider a finite sequence formula_1 of independent, random, self-adjoint matrices with dimension formula_4.
Assume that each random matrix satisfies
almost surely.
Define
Then
Matrix Chernoff II.
Consider a sequence formula_21 of independent, random, self-adjoint matrices that satisfy
almost surely.
Compute the minimum and maximum eigenvalues of the average expectation,
Then
The binary information divergence is defined as
for formula_27.
Matrix Bennett and Bernstein inequalities.
In the scalar setting, Bennett and Bernstein inequalities describe the upper tail of a sum of independent, zero-mean random variables that are either bounded or subexponential. In the matrix
case, the analogous results concern a sum of zero-mean random matrices.
Bounded case.
Consider a finite sequence formula_1 of independent, random, self-adjoint matrices with dimension formula_4.
Assume that each random matrix satisfies
almost surely.
Compute the norm of the total variance,
Then, the following chain of inequalities holds for all formula_32:
The function formula_34 is defined as formula_35 for formula_36.
Subexponential case.
Consider a finite sequence formula_1 of independent, random, self-adjoint matrices with dimension formula_4.
Assume that
for formula_40.
Compute the variance parameter,
Then, the following chain of inequalities holds for all formula_32:
Rectangular case.
Consider a finite sequence formula_44 of independent, random, matrices with dimension formula_10.
Assume that each random matrix satisfies
almost surely.
Define the variance parameter
Then, for all formula_32
holds.
Matrix Azuma, Hoeffding, and McDiarmid inequalities.
Matrix Azuma.
The scalar version of Azuma's inequality states that a scalar martingale exhibits normal concentration about its mean value, and the scale for deviations is controlled by the total maximum squared range of the difference sequence.
The following is the extension in matrix setting.
Consider a finite adapted sequence formula_1 of self-adjoint matrices with dimension formula_4, and a fixed sequence formula_3 of self-adjoint matrices that satisfy
almost surely.
Compute the variance parameter
Then, for all formula_32
The constant 1/8 can be improved to 1/2 when there is additional information available. One case occurs when each summand formula_57 is conditionally symmetric.
Another example requires the assumption that formula_57 commutes almost surely with formula_59.
Matrix Hoeffding.
Placing addition assumption that the summands in Matrix Azuma are independent gives a matrix extension of Hoeffding's inequalities.
Consider a finite sequence formula_1 of independent, random, self-adjoint matrices with dimension formula_4, and let formula_3 be a sequence of fixed self-adjoint matrices.
Assume that each random matrix satisfies
almost surely.
Then, for all formula_32
where
An improvement of this result was established in :
for all formula_32
where
Matrix bounded difference (McDiarmid).
In scalar setting, McDiarmid's inequality provides one common way of bounding the differences by applying Azuma's inequality to a Doob martingale. A version of the bounded differences inequality holds in the matrix setting.
Let formula_70 be an independent, family of random variables, and let formula_71 be a function that maps formula_72 variables to a self-adjoint matrix of dimension formula_4.
Consider a sequence formula_3 of fixed self-adjoint matrices that satisfy
where formula_76 and formula_77 range over all possible values of formula_78 for each index formula_79.
Compute the variance parameter
Then, for all formula_32
where formula_83.
An improvement of this result was established in (see also ):
for all formula_32
where formula_83 and
formula_8
Survey of related theorems.
The first bounds of this type were derived by . Recall the theorem above for self-adjoint matrix Gaussian and Rademacher bounds:
For a finite sequence formula_3 of fixed,
self-adjoint matrices with dimension formula_4 and for formula_5 a finite sequence of independent standard normal or independent Rademacher random variables, then
where
Ahlswede and Winter would give the same result, except with
By comparison, the formula_94 in the theorem above commutes formula_95 and formula_96; that is, it is the largest eigenvalue of the sum rather than the sum of the largest eigenvalues. It is never larger than the Ahlswede–Winter value (by the norm triangle inequality), but can be much smaller. Therefore, the theorem above gives a tighter bound than the Ahlswede–Winter result.
The chief contribution of was the extension of the Laplace-transform method used to prove the scalar Chernoff bound (see Chernoff bound#Theorem for additive form (absolute error)) to the case of self-adjoint matrices. The procedure given in the derivation below. All of the recent works on this topic follow this same procedure, and the chief differences follow from subsequent steps. Ahlswede & Winter use the Golden–Thompson inequality to proceed, whereas Tropp uses Lieb's Theorem.
Suppose one wished to vary the length of the series ("n") and the dimensions of the
matrices ("d") while keeping the right-hand side approximately constant. Then
n must vary approximately as the log of "d". Several papers have attempted to establish a bound without a dependence on dimensions. Rudelson and Vershynin give a result for matrices which are the outer product of two vectors. provide a result without the dimensional dependence for low rank matrices. The original result was derived independently from the Ahlswede–Winter approach, but proves a similar result using the Ahlswede–Winter approach.
Finally, Oliveira proves a result for matrix martingales independently from the Ahlswede–Winter framework. Tropp slightly improves on the result using the Ahlswede–Winter framework. Neither result is presented in this article.
Derivation and proof.
Ahlswede and Winter.
The Laplace transform argument found in is a significant result in its own right:
Let formula_97 be a random self-adjoint matrix. Then
To prove this, fix formula_99. Then
The second-to-last inequality is Markov's inequality. The last inequality holds since formula_101. Since the left-most quantity is independent of formula_102, the infimum over formula_103 remains an upper bound for it.
Thus, our task is to understand formula_104 Nevertheless, since trace and expectation are both linear, we can commute them, so it is sufficient to consider formula_105, which we call the matrix generating function. This is where the methods of and diverge. The immediately following presentation follows .
The Golden–Thompson inequality implies that
Suppose formula_107. We can find an upper bound for formula_108 by iterating this result. Noting that formula_109, then
Iterating this, we get
So far we have found a bound with an infimum over formula_102. In turn, this can be bounded. At any rate, one can see how the Ahlswede–Winter bound arises as the sum of largest eigenvalues.
Tropp.
The major contribution of is the application of Lieb's theorem where had applied the Golden–Thompson inequality. Tropp's corollary is the following: If formula_113 is a fixed self-adjoint matrix and formula_114 is a random self-adjoint matrix, then
Proof: Let formula_116. Then Lieb's theorem tells us that
is concave.
The final step is to use Jensen's inequality to move the expectation inside the function:
This gives us the major result of the paper: the subadditivity of the log of the matrix generating function.
Subadditivity of log mgf.
Let formula_119 be a finite sequence of independent, random self-adjoint matrices. Then for all formula_120,
Proof: It is sufficient to let formula_122. Expanding the definitions, we need to show that
To complete the proof, we use the law of total expectation. Let formula_124 be the expectation conditioned on formula_125. Since we assume all the formula_126 are independent,
Define formula_128.
Finally, we have
where at every step m we use Tropp's corollary with
Master tail bound.
The following is immediate from the previous result:
All of the theorems given above are derived from this bound; the theorems consist in various ways to bound the infimum. These steps are significantly simpler than the proofs given.


Generalized least squares

In statistics, generalized least squares (GLS) is a technique for estimating the unknown parameters in a linear regression model when there is a certain degree of correlation between the residuals in a regression model. In these cases, ordinary least squares and weighted least squares can be statistically inefficient, or even give misleading inferences. GLS was first described by Alexander Aitken in 1936.
Method outline.
In standard linear regression models we observe data formula_1 on "n" statistical units. The response values are placed in a vector formula_2, and the predictor values are placed in the design matrix formula_3, where formula_4 is a vector of the "k" predictor variables (including a constant) for the "i"th unit. The model forces the conditional mean of formula_5 given formula_6 to be a linear function of formula_6, and assumes the conditional variance of the error term given formula_6 is a "known" nonsingular "covariance matrix" formula_9. This is usually written as
Here formula_11 is a vector of unknown constants (known as “regression coefficients”) that must be estimated from the data.
Suppose formula_12 is a candidate estimate for formula_13. Then the residual vector for formula_12 will be formula_15. The generalized least squares method estimates formula_13 by minimizing the squared Mahalanobis length of this residual vector:
Since the objective is a quadratic form in formula_12, the estimator has an explicit formula:
Properties.
The GLS estimator is unbiased, consistent, efficient, and asymptotically normal with formula_20 and formula_21. GLS is equivalent to applying ordinary least squares to a linearly transformed version of the data. To see this, factor formula_22, for instance using the Cholesky decomposition. Then if we pre-multiply both sides of the equation formula_23 by formula_24, we get an equivalent linear model formula_25 where formula_26, formula_27, and formula_28. In this model formula_29, where formula_30 is the identity matrix. Thus we can efficiently estimate formula_13 by applying Ordinary least squares (OLS) to the transformed data, which requires minimizing
This has the effect of standardizing the scale of the errors and “de-correlating” them. Since OLS is applied to data with homoscedastic errors, the Gauss–Markov theorem applies, and therefore the GLS estimate is the best linear unbiased estimator for "β".
Weighted least squares.
A special case of GLS called weighted least squares (WLS) occurs when all the off-diagonal entries of "Ω" are 0. This situation arises when the variances of the observed values are unequal (i.e. heteroscedasticity is present), but where no correlations exist among the observed variances. The weight for unit "i" is proportional to the reciprocal of the variance of the response for unit "i".
Feasible generalized least squares.
If the covariance of the errors formula_33 is unknown, one can get a consistent estimate of formula_33, say formula_35, using an implementable version of GLS known as the feasible generalized least squares (FGLS) estimator. In FGLS, modeling proceeds in two stages: (1) the model is estimated by OLS or another consistent (but inefficient) estimator, and the residuals are used to build a consistent estimator of the errors covariance matrix (to do so, one often needs to examine the model adding additional constraints, for example if the errors follow a time series process, a statistician generally needs some theoretical assumptions on this process to ensure that a consistent estimator is available); and (2) using the consistent estimator of the covariance matrix of the errors, one can implement GLS ideas.
Whereas GLS is more efficient than OLS under heteroscedasticity or autocorrelation, this is not true for FGLS. The feasible estimator is, provided the errors covariance matrix is consistently estimated, "asymptotically" more efficient, but for a small or medium size sample, it can be actually less efficient than OLS. This is why, some authors prefer to use OLS, and reformulate their inferences by simply considering an alternative estimator for the variance of the estimator robust to heteroscedasticity or serial autocorrelation.
But for large samples FGLS is preferred over OLS under heteroskedasticity or serial correlation. A cautionary note is that the FGLS estimator is not always consistent. One case in which FGLS might be inconsistent is if there are individual specific fixed effects.
In general this estimator has different properties than GLS. For large samples (i.e., asymptotically) all properties are (under appropriate conditions) common with respect to GLS, but for finite samples the properties of FGLS estimators are unknown: they vary dramatically with each particular model, and as a general rule their exact distributions cannot be derived analytically. For finite samples, FGLS may be even less efficient than OLS in some cases. Thus, while GLS can be made feasible, it is not always wise to apply this method when the sample is small.
A method sometimes used to improve the accuracy of the estimators in finite samples is to iterate, i.e. taking the residuals from FGLS to update the errors covariance estimator, and then updating the FGLS estimation, applying the same idea iteratively until the estimators vary less than some tolerance. But this method does not necessarily improve the efficiency of the estimator very much if the original sample was small.
A reasonable option when samples are not too large is to apply OLS, but throwing away the classical variance estimator
(which is inconsistent in this framework) and using a HAC (Heteroskedasticity and Autocorrelation Consistent) estimator. For example, in autocorrelation context we can use the Bartlett estimator (often known as Newey-West estimator since these authors popularized the use of this estimator among econometricians in their 1987 "Econometrica" article), and in heteroskedastic context we can use the Eicker–White estimator. This approach is much safer, and it is the appropriate path to take unless the sample is large, and "large" is sometimes a slippery issue (e.g. if the errors distribution is asymmetric the required sample would be much larger).
The ordinary least squares (OLS) estimator is calculated as usual by
and estimates of the residuals formula_38 are constructed.
For simplicity consider the model for heteroskedastic errors. Assume that the variance-covariance matrix formula_39 of the error vector is diagonal, or equivalently that errors from distinct observations are uncorrelated. Then each diagonal entry may be estimated by the fitted residuals formula_40 so formula_41 may be constructed by
It is important to notice that the squared residuals cannot be used in the previous expression; we need an estimator of the errors variances. To do so, we can use a parametric heteroskedasticity model, or a nonparametric estimator. Once this step is fulfilled, we can proceed:
Estimate formula_43 using formula_44 using weighted least squares
The procedure can be iterated. The first iteration is given by
This estimation of formula_49 can be iterated to convergence.
Under regularity conditions any of the FGLS estimator (or that of any of its iterations, if we iterate a finite number of times) is asymptotically distributed as
where n is the sample size and
here p-lim means limit in probability


Linear function

In mathematics, the term linear function refers to two distinct but related notions:
As a polynomial function.
In calculus, analytic geometry and related areas, a linear function is a polynomial of degree one or less, including the zero polynomial (the latter not being considered to have degree zero).
When the function is of only one variable, it is of the form
where and are constants, often real numbers. The graph of such a function of one variable is a nonvertical line. is frequently referred to as the slope of the line, and as the intercept.
For a function formula_2 of any finite number of variables, the general formula is
and the graph is a hyperplane of dimension .
A constant function is also considered linear in this context, as it is a polynomial of degree zero or is the zero polynomial. Its graph, when there is only one variable, is a horizontal line.
In this context, a function that is also a linear map (the other meaning) may be referred to as a homogeneous linear function or a linear form. In the context of linear algebra, the polynomial functions of degree 0 or 1 are the scalar-valued affine maps.
As a linear map.
In linear algebra, a linear function is a map "f" between two vector spaces that preserves vector addition and scalar multiplication:
Here denotes a constant belonging to some field of scalars (for example, the real numbers) and and are elements of a vector space, which might be itself.
Some authors use "linear function" only for linear maps that take values in the scalar field; these are more commonly called linear forms.
The "linear functions" of calculus qualify as "linear maps" when (and only when) , or, equivalently, when the above constant equals zero. Geometrically, the graph of the function must pass through the origin.


Neumann polynomial

In mathematics, the Neumann polynomials, introduced by Carl Neumann for the special case formula_1, are a sequence of polynomials in formula_2 used to expand functions in term of Bessel functions.
The first few polynomials are
A general form for the polynomial is
and they have the "generating function"
where "J" are Bessel functions.
To expand a function "f" in the form
for formula_11, compute
where formula_13 and "c" is the distance of the nearest singularity of formula_14 from formula_15.
Examples.
An example is the extension
or the more general Sonine formula
where formula_18 is Gegenbauer's polynomial. Then,
the confluent hypergeometric function
and in particular
the index shift formula
the Taylor expansion (addition formula)
(cf.) and the expansion of the integral of the Bessel function,
are of the same type.


Peter Ludwig Mejdell Sylow

Peter Ludwig Mejdell Sylow () (12 December 1832 – 7 September 1918) was a Norwegian mathematician who proved foundational results in group theory.
Biography.
He was born and died in Christiania (now Oslo). Sylow was a son of government minister Thomas Edvard von Westen Sylow, and a brother of military officer and sports official Carl Sylow. He attended Christiania Cathedral School (1850) and the University of Christiania (cand.real. 1856) .
Sylow was a high school teacher at Hartvig Nissen School, later before becoming a headmaster in Halden from 1858 to 1898. He was a substitute lecturer at University of Christiania in 1862, covering Galois theory. It was then that he posed the question that led to his theorems regarding Sylow subgroups. Sylow published the Sylow theorems in 1872, and subsequently devoted eight years of his life, with Sophus Lie, to the project of editing the mathematical works of his countryman, Niels Henrik Abel. In 1898, he was appointed professor at the University of Christiania.
In 1853, he was awarded the Crown Prince's gold medal ("Kronprinsens gullmedalje") by the University of Oslo. In 1868 he was elected into the Norwegian Academy of Science and Letters. In 1894 he was awarded an honorary doctorate from the University of Copenhagen and became an editor for Acta Mathematica.


Dmitry Gudkov (mathematician)

Dmitrii Andreevich Gudkov (1918–1992; alternative spelling Dmitry) was a Russian mathematician famous for his work on Hilbert's sixteenth problem and the related Gudkov's conjecture in algebraic geometry. He was a student of Aleksandr Andronov.


Transformation semigroup

In algebra, a transformation semigroup (or composition semigroup) is a collection of transformations (functions from a set to itself) that is closed under function composition. If it includes the identity function, it is a monoid, called a transformation (or composition) monoid. This is the semigroup analogue of a permutation group.
A transformation semigroup of a set has a tautological semigroup action on that set. Such actions are characterized by being faithful, i.e., if two elements of the semigroup have the same action, then they are equal.
An analogue of Cayley's theorem shows that any semigroup can be realized as a transformation semigroup of some set.
In automata theory, some authors use the term "transformation semigroup" to refer to a semigroup acting faithfully on a set of "states" different from the semigroup's base set. There is a correspondence between the two notions.
Transformation semigroups and monoids.
A transformation semigroup is a pair ("X","S"), where "X" is a set and "S" is a semigroup of transformations of "X". Here a transformation of "X" is just a function from subset of "X" to "X", not necessarily invertible, and therefore "S" is simply a set of transformations of "X" which is closed under composition of functions. The set of all partial functions on a given base set, "X", forms a regular semigroup called the semigroup of all partial transformations (or the partial transformation semigroup on "X"), typically denoted by formula_1.
If "S" includes the identity transformation of "X", then it is called a transformation monoid. Obviously any transformation semigroup "S" determines a transformation monoid "M" by taking the union of "S" with the identity transformation. A transformation monoid whose elements are invertible is a permutation group.
The set of all transformations of "X" is a transformation monoid called the full transformation monoid (or semigroup) of "X". It is also called the symmetric semigroup of "X" and is denoted by "T""X". Thus a transformation semigroup (or monoid) is just a subsemigroup (or submonoid) of the full transformation monoid of "X".
If ("X","S") is a transformation semigroup then "X" can be made into a semigroup action of "S" by evaluation:
This is a monoid action if "S" is a transformation monoid.
The characteristic feature of transformation semigroups, as actions, is that they are "faithful", i.e., if
then "s" = "t". Conversely if a semigroup "S" acts on a set "X" by "T"("s","x") = "s" • "x" then we can define, for "s" ∈ "S", a transformation "T""s" of "X" by
The map sending "s" to "T""s" is injective if and only if ("X", "T") is faithful, in which case the image of this map is a transformation semigroup isomorphic to "S".
Cayley representation.
In group theory, Cayley's theorem asserts that any group "G" is isomorphic to a subgroup of the symmetric group of "G" (regarded as a set), so that "G" is a permutation group. This theorem generalizes straightforwardly to monoids: any monoid "M" is a transformation monoid of its underlying set, via the action given by left (or right) multiplication. This action is faithful because if "ax" = "bx" for all "x" in "M", then by taking "x" equal to the identity element, we have "a" = "b".
For a semigroup "S" without a (left or right) identity element, we take "X" to be the underlying set of the monoid corresponding to "S" to realise "S" as a transformation semigroup of "X". In particular any finite semigroup can be represented as a subsemigroup of transformations of a set "X" with |"X"| ≤ |"S"| + 1, and if "S" is a monoid, we have the sharper bound |"X"| ≤ |"S"|, as in the case of finite groups.
In computer science.
In computer science, Cayley representations can be applied to improve the asymptotic efficiency of semigroups by reassociating multiple composed multiplications. The action given by left multiplication results in right-associated multiplication, and vice versa for the action given by right multiplication. Despite having the same results for any semigroup, the asymptotic efficiency will differ. Two examples of useful transformation monoids given by an action of left multiplication are the functional variation of the difference list data structure, and the monadic Codensity transformation (a Cayley representation of a monad, which is a monoid in a particular monoidal functor category).
Transformation monoid of an automaton.
Let "M" be a deterministic automaton with state space "S" and alphabet "A". The words in the free monoid "A"∗ induce transformations of "S" giving rise to a monoid morphism from "A"∗ to the full transformation monoid "T""S". The image of this morphism is the transformation semigroup of "M".
For a regular language, the syntactic monoid is isomorphic to the transformation monoid of the minimal automaton of the language.


Injective hull

In mathematics, particularly in algebra, the injective hull (or injective envelope) of a module is both the smallest injective module containing it and the largest essential extension of it. Injective hulls were first described in .
Definition.
A module "E" is called the injective hull of a module "M", if "E" is an essential extension of "M", and "E" is injective. Here, the base ring is a ring with unity, though possibly non-commutative.
Properties.
Ring structure.
In some cases, for "R" a subring of a self-injective ring "S", the injective hull of "R" will also have a ring structure. For instance, taking "S" to be a full matrix ring over a field, and taking "R" to be any ring containing every matrix which is zero in all but the last column, the injective hull of the right "R"-module "R" is "S". For instance, one can take "R" to be the ring of all upper triangular matrices. However, it is not always the case that the injective hull of a ring has a ring structure, as an example in shows.
A large class of rings which do have ring structures on their injective hulls are the nonsingular rings. In particular, for an integral domain, the injective hull of the ring (considered as a module over itself) is the field of fractions. The injective hulls of nonsingular rings provide an analogue of the ring of quotients for non-commutative rings, where the absence of the Ore condition may impede the formation of the classical ring of quotients. This type of "ring of quotients" (as these more general "fields of fractions" are called) was pioneered in , and the connection to injective hulls was recognized in .
Uniform dimension and injective modules.
An "R" module "M" has finite uniform dimension (="finite rank") "n" if and only if the injective hull of "M" is a finite direct sum of "n" indecomposable submodules.
Generalization.
More generally, let C be an abelian category. An object "E" is an injective hull of an object "M" if "M" → "E" is an essential extension and "E" is an injective object.
If C is locally small, satisfies Grothendieck's axiom AB5 and has enough injectives, then every object in C has an injective hull (these three conditions are satisfied by the category of modules over a ring). Every object in a Grothendieck category has an injective hull.


$CLS (environment variable)


Reverse Cuthill-McKee algorithm


Sastry automorphism

In mathematics, a Sastry automorphism, is an automorphism of a field of characteristic 2 satisfying some rather complicated conditions related to the problem of embedding Ree groups of type ²F₄ into Chevalley groups of type F₄. They were introduced by , and named and classified by who showed that there are 22 families of Sastry automorphisms, together with 22 exceptional ones over some finite fields of orders up to 210.


Cofree coalgebra

In algebra, the cofree coalgebra of a vector space or module is a coalgebra analog of the free algebra of a vector space. The cofree coalgebra of any vector space over a field exists, though it is more complicated than one might expect by analogy with the free algebra.
Definition.
If "V" is a vector space over a field F, then the cofree coalgebra "C" ("V"), of "V", is a coalgebra together with a linear map "C" ("V") → "V", such that any linear map from a coalgebra "X" to "V" factors through a coalgebra homomorphism from "X" to "C" ("V"). In other words, the functor "C" is right adjoint to the forgetful functor from coalgebras to vector spaces.
The cofree coalgebra of a vector space always exists, and is unique up to canonical isomorphism.
Cofree cocommutative coalgebras are defined in a similar way, and can be constructed as the largest cocommutative coalgebra in the cofree coalgebra.
Construction.
"C" ("V") may be constructed as a "completion" of the tensor coalgebra "T"("V") of "V". For "k" ∈ N = {0, 1, 2, ...}, let "T""k""V" denote the "k"-fold tensor power of "V":
with "T"0"V" = F, and "T"1"V" = "V". Then "T"("V") is the direct sum of all "T""k""V":
In addition to the graded algebra structure given by the tensor product isomorphisms "T""j""V" ⊗ "T""k""V" → "T""j"+"k""V" for "j", "k" ∈ N, "T"("V") has a graded coalgebra structure Δ : "T"("V") → "T"("V") ⊠ "T"("V") defined by extending
by linearity to all of "T"("V").
Here, the tensor product symbol ⊠ is used to indicate the tensor product used to define a coalgebra; it must not be confused with the tensor product ⊗, which is used to define the bilinear multiplication operator of the tensor algebra. The two act in different spaces, on different objects. Additional discussion of this point can be found in the tensor algebra article.
The sum above makes use of a short-hand trick, defining formula_4 to be the unit in the field formula_5. For example, this short-hand trick gives, for the case of formula_6 in the above sum, the result that
for formula_8. Similarly, for formula_9 and formula_10, one gets
Note that there is no need to ever write formula_12 as this is just plain-old scalar multiplication in the algebra; that is, one trivially has that formula_13
With the usual product this coproduct does not make "T"("V") into a bialgebra, but is instead dual to the algebra structure on "T"("V"∗), where "V"∗ denotes the dual vector space of linear maps "V" → F. It can be turned into a bialgebra with the product formula_14 where "(i,j)" denotes the binomial coefficient formula_15. This bialgebra is known as the divided power Hopf algebra. The product is dual to the coalgebra structure on "T"("V"∗) which makes the tensor algebra a bialgebra.
Here an element of "T"("V") defines a linear form on "T"("V"∗) using the nondegenerate pairings
induced by evaluation, and the duality between the coproduct on "T"("V") and the product on "T"("V"∗) means that
This duality extends to a nondegenerate pairing
where
is the direct product of the tensor powers of "V". (The direct sum "T"("V") is the subspace of the direct product for which only finitely many components are nonzero.) However, the coproduct Δ on "T"("V") only extends to a linear map
with values in the "completed tensor product", which in this case is
and contains the tensor product as a proper subspace:
The completed tensor coalgebra "C" ("V") is the largest subspace "C"  satisfying
which exists because if "C"1 and "C"2 satisfiy these conditions, then so does their sum "C"1 + "C"2.
It turns out that "C" ("V") is the subspace of all "representative elements":
Furthermore, by the finiteness principle for coalgebras, any "f" ∈ "C" ("V") must belong to a finite-dimensional subcoalgebra of "C" ("V"). Using the duality pairing with "T"("V"∗), it follows that "f" ∈ "C" ("V") if and only if the kernel of "f" on "T"("V"∗) contains a two-sided ideal of finite codimension. Equivalently,
is the union of annihilators "I" 0 of finite codimension ideals "I"  in "T"("V"∗), which are isomorphic to the duals of the finite-dimensional algebra quotients "T"("V"∗)/"I".
Example.
When "V" = F, "T"("V"∗) is the polynomial algebra F["t"] in one variable "t", and the direct product
may be identified with the vector space F of formal power series
in an indeterminate "τ". The coproduct Δ on the subspace F["τ"] is determined by
and "C" ("V") is the largest subspace of F on which this extends to a coalgebra structure.
The duality F × F["t"] → F is determined by "τ""j"("t""k") = "δ""jk" so that
Putting "t"="τ"−1, this is the constant term in the product of two formal Laurent series. Thus, given a polynomial "p"("t") with leading term "t""N", the formal Laurent series
is a formal power series for any "j" ∈ N, and annihilates the ideal "I"("p") generated by "p" for "j" < "N". Since F["t"]/"I"("p") has dimension "N", these formal power series span the annihilator of "I"("p"). Furthermore, they all belong to the localization of F["τ"] at the ideal generated by "τ", i.e., they have the form "f"("τ")/"g"("τ") where "f" and "g" are polynomials, and "g" has nonzero constant term. This is the space of rational functions in "τ" which are regular at zero. Conversely, any proper rational function annihilates an ideal of the form "I"("p").
Any nonzero ideal of F["t"] is principal, with finite-dimensional quotient. Thus "C" ("V") is the sum of the annihilators of the principal ideals "I"("p"), i.e., the space of rational functions regular at zero.


Matrix completion

Matrix completion is the task of filling in the missing entries of a partially observed matrix. A wide range of datasets are naturally organized in matrix form. One example is the movie-ratings matrix, as appears in the Netflix problem: Given a ratings matrix in which each entry formula_1 represents the rating of movie formula_2 by customer formula_3, if customer formula_3 has watched movie formula_2 and is otherwise missing, we would like to predict the remaining entries in order to make good recommendations to customers on what to watch next. Another example is the term-document matrix: The frequencies of words used in a collection of documents can be represented as a matrix, where each entry corresponds to the number of times the associated term appears in the indicated document.
Without any restrictions on the number of degrees of freedom in the completed matrix this problem is underdetermined since the hidden entries could be assigned arbitrary values. Thus matrix completion often seeks to find the lowest rank matrix or, if the rank of the completed matrix is known, a matrix of rank formula_6 that matches the known entries. The illustration shows that a partially revealed rank-1 matrix (on the left) can be completed with zero-error (on the right) since all the rows with missing entries should be the same as the third row. In the case of the Netflix problem the ratings matrix is expected to be low-rank since user preferences can often be described by a few factors, such as the movie genre and time of release. Other applications include computer vision, where missing pixels in images need to be reconstructed, detecting the global positioning of sensors in a network from partial distance information, and multiclass learning. The matrix completion problem is in general NP-hard, but under additional assumptions there are efficient algorithms that achieve exact reconstruction with high probability.
In statistical learning point of view, the matrix completion problem is an application of matrix regularization which is a generalization of vector regularization. For example, in the low-rank matrix completion problem one may apply the regularization penalty taking the form of a nuclear norm formula_7
Low rank matrix completion.
One of the variants of the matrix completion problem is to find the lowest rank matrix formula_8 which matches the matrix formula_9, which we wish to recover, for all entries in the set formula_10 of observed entries. The mathematical formulation of this problem is as follows:
Candès and Recht proved that with assumptions on the sampling of the observed entries and sufficiently many sampled entries this problem has a unique solution with high probability.
An equivalent formulation, given that the matrix formula_9 to be recovered is known to be of rank formula_6, is to solve for formula_8 where formula_15
Assumptions.
A number of assumptions on the sampling of the observed entries and the number of sampled entries are frequently made to simplify the analysis and to ensure the problem is not underdetermined.
Uniform sampling of observed entries.
To make the analysis tractable, it is often assumed that the set formula_10 of observed entries and fixed cardinality is sampled uniformly at random from the collection of all subsets of entries of cardinality formula_17. To further simplify the analysis, it is instead assumed that formula_10 is constructed by Bernoulli sampling, i.e. that each entry is observed with probability formula_19. If formula_20 is set to formula_21 where formula_22 is the desired expected cardinality of formula_10, and formula_24 are the dimensions of the matrix (let formula_25 without loss of generality), formula_17 is within formula_27 of formula_22 with high probability, thus Bernoulli sampling is a good approximation for uniform sampling. Another simplification is to assume that entries are sampled independently and with replacement.
Lower bound on number of observed entries.
Suppose the formula_29 by formula_30 matrix formula_9 (with formula_25) we are trying to recover has rank formula_6. There is an information theoretic lower bound on how many entries must be observed before formula_9 can be uniquely reconstructed. The set of formula_29 by formula_30 matrices with rank less than or equal to formula_6 is an algebraic variety in formula_38with dimension formula_39.
Using this result,
one can show that at least
formula_40
entries must be observed for matrix completion in
formula_41
to have a unique solution
when
formula_42
Secondly, there must be at least one observed entry per row and column of formula_9. The Singular Value Decomposition of formula_9 is given by formula_45. If row formula_3 is unobserved, it is easy to see the formula_47 right singular vector of formula_9, formula_49, can be changed to some arbitrary value and still yield a matrix matching formula_9 over the set of observed entries. Similarly, if column formula_2 is unobserved, the formula_52 left singular vector of formula_9, formula_54 can be arbitrary. If we assume Bernoulli sampling of the set of observed entries, the Coupon collector effect implies that entries on the order of formula_55 must be observed to ensure that there is an observation from each row and column with high probability.
Combining the necessary conditions and assuming that formula_56 (a valid assumption for many practical applications), the lower bound on the number of observed entries required to prevent the problem of matrix completion from being underdetermined is on the order of formula_57.
Incoherence.
The concept of incoherence arose in compressed sensing. It is introduced in the context of matrix completion to ensure the singular vectors of formula_9 are not too "sparse" in the sense that all coordinates of each singular vector are of comparable magnitude instead of just a few coordinates having significantly larger magnitudes. The standard basis vectors are then undesirable as singular vectors, and the vector formula_59 in formula_60 is desirable. As an example of what could go wrong if the singular vectors are sufficiently "sparse", consider the formula_29 by formula_30 matrix formula_63 with singular value decomposition formula_64. Almost all the entries of formula_9 must be sampled before it can be reconstructed.
Candès and Recht define the coherence of a matrix formula_66 with column space an formula_67dimensional subspace of formula_60 as formula_69, where formula_70 is the orthogonal projection onto formula_71. Incoherence then asserts that given the singular value decomposition formula_45 of the formula_29 by formula_30 matrix formula_9,
for some formula_79.
Low rank matrix completion with noise.
In real world application, one often observe only a few entries corrupted at least by a small amount of noise. For example, in the Netflix problem, the ratings are uncertain. Candès and Plan showed that it is possible to fill in the many missing entries of large low-rank matrices from just a few noisy samples by nuclear norm minimization. The noisy model assumes that we observe
formula_80
where formula_81 is a noise term. Note that the noise can be either stochastic or deterministic. Alternatively the model can be expressed as
formula_82
where formula_83 is an formula_84 matrix with entries formula_85 for formula_86 assuming that formula_87 for some formula_88 .To recover the incomplete matrix, we try to solve the following optimization problem:
formula_89
Among all matrices consistent with the data, find the one with minimum nuclear norm. Candès and Plan have shown that this reconstruction is accurate. They have proved that when perfect noiseless recovery occurs, then matrix completion is stable vis a vis perturbations. The error is proportional to the noise level formula_90. Therefore, when the noise level is small, the error is small. Here the matrix completion problem does not obey the restricted isometry property (RIP). For matrices, the RIP would assume that the sampling operator obeys
formula_91
for all matrices formula_8 with sufficiently small rank and formula_93 sufficiently small.
The methods are also applicable to sparse signal recovery problems in which the RIP does not hold.
High rank matrix completion.
The high rank matrix completion in general is NP-Hard. However, with certain assumptions, some incomplete high rank matrix or even full rank matrix can be completed.
Eriksson, Balzano and Nowak have considered the problem of completing a matrix with the assumption that the columns of the matrix belong to a union of multiple low-rank subspaces. Since the columns belong to a union of subspaces, the problem may be viewed as a missing-data version of the subspace clustering problem. Let formula_8 be an formula_95 matrix whose (complete) columns lie in a union of at most formula_96 subspaces, each of formula_97, and assume formula_98. Eriksson, Balzano and Nowak showed that under mild assumptions each column of formula_8 can be perfectly recovered with high probability from an incomplete version so long as at least formula_100 entries of formula_8 are observed uniformly at random, with formula_102 a constant depending on the usual incoherence conditions, the geometrical arrangement of subspaces, and the distribution of columns over the subspaces.
The algorithm involves several steps: (1) local neighborhoods; (2) local subspaces; (3) subspace refinement; (4) full matrix completion. This method can be applied to Internet distance matrix completion and topology identification.
Algorithms.
Various matrix completion algorithms have been proposed. These includes convex relaxation-based algorithm, gradient-based algorithm, and alternating minimization-based algorithm.
Convex relaxation.
The rank minimization problem is NP-hard. One approach, proposed by Candès and Recht, is to form a convex relaxation of the problem and minimize the nuclear norm formula_103 (which gives the sum of the singular values of formula_9) instead of formula_105 (which counts the number of non zero singular values of formula_9). This is analogous to minimizing the L1-norm rather than the L0-norm for vectors. The convex relaxation can be solved using semidefinite programming (SDP) by noticing that the optimization problem is equivalent to
formula_107
The complexity of using SDP to solve the convex relaxation is formula_108. State of the art solvers like SDP3 can only handle matrices of size up to 100 by 100 An alternative first order method that approximately solves the convex relaxation is the Singular Value Thresholding Algorithm introduced by Cai, Candès and Shen.
Candès and Recht show, using the study of random variables on Banach spaces, that if the number of observed entries is on the order of formula_109 (assume without loss of generality formula_25), the rank minimization problem has a unique solution which also happens to be the solution of its convex relaxation with probability formula_111 for some constant formula_112. If the rank of formula_9 is small (formula_114), the size of the set of observations reduces to the order of formula_115. These results are near optimal, since the minimum number of entries that must be observed for the matrix completion problem to not be underdetermined is on the order of formula_116.
This result has been improved by Candès and Tao. They achieve bounds that differ from the optimal bounds only by polylogarithmic factors by strengthening the assumptions. Instead of the incoherence property, they assume the strong incoherence property with parameter formula_117. This property states that:
Intuitively, strong incoherence of a matrix formula_66 asserts that the orthogonal projections of standard basis vectors to formula_66 has magnitudes that have high likelihood if the singular vectors were distributed randomly.
Candès and Tao find that when formula_6 is formula_127 and the number of observed entries is on the order of formula_128, the rank minimization problem has a unique solution which also happens to be the solution of its convex relaxation with probability formula_111 for some constant formula_112. For arbitrary formula_6, the number of observed entries sufficient for this assertion hold true is on the order of formula_132
Gradient descent.
Keshavan, Montanari and Oh consider a variant of matrix completion where the rank of the formula_29 by formula_30 matrix formula_9, which is to be recovered, is known to be formula_6. They assume Bernoulli sampling of entries, constant aspect ratio formula_137, bounded magnitude of entries of formula_9 (let the upper bound be formula_139), and constant condition number formula_140 (where formula_141 and formula_142 are the largest and smallest singular values of formula_9 respectively). Further, they assume the two incoherence conditions are satisfied with formula_144 and formula_145 where formula_144 and formula_147 are constants. Let formula_148 be a matrix that matches formula_9 on the set formula_10 of observed entries and is 0 elsewhere. They then propose the following algorithm:
Steps 1 and 2 of the algorithm yield a matrix formula_156 very close to the true matrix formula_9 (as measured by the root mean square error (RMSE) with high probability. In particular, with probability formula_169, formula_170 for some constant formula_171. formula_172 denotes the Frobenius norm. Note that the full suite of assumptions is not needed for this result to hold. The incoherence condition, for example, only comes into play in exact reconstruction. Finally, although trimming may seem counter intuitive as it involves throwing out information, it ensures projecting formula_148 onto its first formula_6 principal components gives more information about the underlying matrix formula_9 than about the observed entries.
In Step 3, the space of candidate matrices formula_159 can be reduced by noticing that the inner minimization problem has the same solution for formula_177 as for formula_178 where formula_179 and formula_180 are orthonormal formula_6 by formula_6 matrices. Then gradient descent can be performed over the cross product of two Grassman manifolds. If formula_183 and the observed entry set is in the order of formula_184, the matrix returned by Step 3 is exactly formula_9. Then the algorithm is order optimal, since we know that for the matrix completion problem to not be underdetermined the number of entries must be in the order of formula_184.
Alternating least squares minimization.
Alternating minimization represents a widely applicable and empirically successful approach for finding low-rank matrices that best fit the given data. For example, for the problem of low-rank matrix completion, this method is believed to be one of the most accurate and efficient, and formed a major component of the winning entry in the Netflix problem. In the alternating minimization approach, the low-rank target matrix is written in a bilinear form:
formula_187;
the algorithm then alternates between finding the best formula_66 and the best formula_189. While the overall problem is non-convex, each sub-problem is typically convex and can be solved efficiently. Jain, Netrapalli and Sanghavi have given one of the first guarantees for performance of alternating minimization for both matrix completion and matrix sensing.
The alternating minimization algorithm can be viewed as an approximate way to solve the following non-convex problem:
formula_190
The AltMinComplete Algorithm proposed by Jain, Netrapalli and Sanghavi is listed here:
They showed that by observing formula_208 random entries of an incoherent matrix formula_9, AltMinComplete algorithm can recover formula_9 in formula_211 steps. In terms of sample complexity (formula_212), theoretically, Alternating Minimization may require a bigger formula_191 than Convex Relaxation. However empirically it seems not the case which implies that the sample complexity bounds can be further tightened. In terms of time complexity, they showed that AltMinComplete needs time
formula_214.
It is worth noting that, although convex relaxation based methods have rigorous analysis, alternating minimization based algorithms are more successful in practice.
Applications.
Several applications of matrix completion are summarized by Candès and Plan as follows:
Collaborative filtering.
Collaborative filtering is the task of making automatic predictions about the interests of a user by collecting taste information from many users. Companies like Apple, Amazon, Barnes and Noble, and Netflix are trying to predict their user preferences from partial knowledge. In these kind of matrix completion problem, the unknown full matrix is often considered low rank because only a few factors typically contribute to an individual's tastes or preference.
System identification.
In control, one would like to fit a discrete-time linear time-invariant state-space model
formula_215
to a sequence of inputs formula_216 and outputs formula_217. The vector formula_218 is the state of the system at time formula_219 and formula_30 is the order of the system model. From the input/output pair, one would like to recover the matrices formula_221 and the initial state formula_222. This problem can also be viewed as a low-rank matrix completion problem.
Internet of things (IoT) localization.
The localization (or global positioning) problem emerges naturally in IoT sensor networks. The problem is to recover the sensor map in Euclidean space from a local or partial set of pairwise distances. Thus it is a matrix completion problem with rank two if the sensors are located in a 2-D plane and three if they are in a 3-D space.


Gerhard Hochschild

Gerhard Paul Hochschild (April 29, 1915 in Berlin – July 8, 2010 in El Cerrito, California) was a German-born American mathematician who worked on Lie groups, algebraic groups, homological algebra and algebraic number theory.
Early life.
On April 29, 1915, Hochschild was born in Berlin, Germany. Hochschild's father was a patent attorney who had an engineering degree. Hochschild had an older brother.
Education.
In 1936, Hochschild earned a BS degree in mathematics from University of Cape Town in Union of South Africa. In 1937, Hochschild earned a MS degree in mathematics from University of Cape Town.
In 1941, Hochschild earned his PhD in mathematics from Princeton University. Hochschild completed his thesis in 1941 at Princeton University with Claude Chevalley on "Semisimple Algebras and Generalized Derivations".
Career.
In 1956–7 Hochschild was at the Institute for Advanced Study. Hochschild was a professor at University of Illinois at Urbana-Champaign. In the late 1950s Hochschild was a professor at University of California, Berkeley.
 introduced Hochschild cohomology, a cohomology theory for algebras, which classifies deformations of algebras. introduced cohomology into class field theory. Along with Bertram Kostant and Alex F. T. W. Rosenberg, the Hochschild–Kostant–Rosenberg theorem is named after him.
Among his students were Andrzej Białynicki-Birula and James Ax.
In 1955, Hochschild was a Guggenheim Fellow. In 1979 Hochschild was elected to the National Academy of Sciences, and in 1980 he was awarded the Leroy P. Steele Prize of the AMS.
In 1982, Hochschild retired but continued teaching part-time until 1985.
Personal life.
Hochschild's wife was Ruth. Hochschild's children are Ann Hochschild and Peter Hochschild.
On July 8, 2010, Hochschild died at his home. Hochschild was 95.


Vector (mathematics and physics)

In mathematics and physics, a vector is an element of a vector space.
For many specific vector spaces, the vectors have received specific names, which are listed below.
Historically, vectors were introduced in geometry and physics (typically in mechanics) before the formalization of the concept of vector space. Therefore, one often talks about vectors without specifying the vector space to which they belong. Specifically, in a Euclidean space, one considers "spatial vectors", also called "Euclidean vectors" which are used to represent quantities that have both magnitude and direction, and may be added, subtracted and scaled (i.e. multiplied by a real number) for forming a vector space.
Vectors in Euclidean geometry.
In classical Euclidean geometry (i.e., synthetic geometry), vectors were introduced (during the 19th century) as equivalence classes under equipollence, of ordered pairs of points; two pairs and being equipollent if the points , in this order, form a parallelogram. Such an equivalence class is called a "vector", more precisely, a Euclidean vector. The equivalence class of is often denoted formula_1
A Euclidean vector is thus an equivalence class of directed segments with the same magnitude (e.g., the length of the line segment ) and same direction (e.g., the direction from to ). In physics, Euclidean vectors are used to represent physical quantities that have both magnitude and direction, but are not located at a specific place, in contrast to scalars, which have no direction. For example, velocity, forces and acceleration are represented by vectors.
In modern geometry, Euclidean spaces are often defined from linear algebra. More precisely, a Euclidean space is defined as a set to which is associated an inner product space of finite dimension over the reals formula_2 and a group action of the additive group of formula_2 which is free and transitive (See Affine space for details of this construction). The elements of formula_4 are called translations.
It has been proven that the two definitions of Euclidean spaces are equivalent, and that the equivalence classes under equipollence may be identified with translations.
Sometimes, Euclidean vectors are considered without reference to a Euclidean space. In this case, a Euclidean vector is an element of a normed vector space of finite dimension over the reals, or, typically, an element of formula_5 equipped with the dot product. This makes sense, as the addition in such a vector space acts freely and transitively on the vector space itself. That is, formula_5 is a Euclidean space, with itself as an associated vector space, and the dot product as an inner product.
The Euclidean space formula_5 is often presented as "the" Euclidean space of dimension . This is motivated by the fact that every Euclidean space of dimension is isomorphic to the Euclidean space formula_8 More precisely, given such a Euclidean space, one may choose any point as an origin. By Gram–Schmidt process, one may also find an orthonormal basis of the associated vector space (a basis such that the inner product of two basis vectors is 0 if they are different and 1 if they are equal). This defines Cartesian coordinates of any point of the space, as the coordinates on this basis of the vector formula_9 These choices define an isomorphism of the given Euclidean space onto formula_10 by mapping any point to the -tuple of its Cartesian coordinates, and every vector to its coordinate vector.
Tuples that are not really vectors.
The set formula_5 of tuples of real numbers has a natural structure of vector space defined by component-wise addition and scalar multiplication. When such tuples are used for representing some data, it is common to call them "vectors", even if the vector addition does not mean anything for these data, which may make the terminology confusing. Similarly, some physical phenomena involve a direction and a magnitude. They are often represented by vectors, even if operations of vector spaces do not apply to them.
Vectors in algebras.
Every algebra over a field is a vector space, but elements of an algebra are generally not called vectors. However, in some cases, they are called "vectors", mainly due to historical reasons.
See also.
Vector fields.
A vector field is a vector-valued function that, generally, has a domain of the same dimension (as a manifold) as its codomain,


List of permutation topics

This is a list of topics on mathematical permutations.


Product (category theory)

In category theory, the product of two (or more) objects in a category is a notion designed to capture the essence behind constructions in other areas of mathematics such as the Cartesian product of sets, the direct product of groups or rings, and the product of topological spaces. Essentially, the product of a family of objects is the "most general" object which admits a morphism to each of the given objects.
Definition.
Product of two objects.
Fix a category . Let and be objects of . A product of and is an object , typically denoted , equipped with a pair of morphisms , satisfying the following universal property:
Whether a product exists may depend on or on and . If it does exist, it is unique up to canonical isomorphism, because of the universal property, so one may speak of "the" product.
The morphisms and are called the canonical projections or projection morphisms. Given and , , the unique morphism is called the product of morphisms and and is denoted .
Product of an arbitrary family.
Instead of two objects, we can start with an arbitrary family of objects indexed by a set .
Given a family of objects, a product of the family is an object equipped with morphisms satisfying the following universal property:
The product is denoted . If , then it is denoted and the product of morphisms is denoted .
Equational definition.
Alternatively, the product may be defined through equations. So, for example, for the binary product:
As a limit.
The product is a special case of a limit. This may be seen by using a discrete category (a family of objects without any morphisms, other than their identity morphisms) as the diagram required for the definition of the limit. The discrete objects will serve as the index of the components and projections. If we regard this diagram as a functor, it is a functor from the index set considered as a discrete category. The definition of the product then coincides with the definition of the limit, being a cone and projections being the limit (limiting cone).
Universal property.
Just as the limit is a special case of the universal construction, so is the product. Starting with the definition given for the universal property of limits, take as the discrete category with two objects, so that is simply the product category . The diagonal functor assigns to each object the ordered pair and to each morphism the pair . The product in is given by a universal morphism from the functor to the object in . This universal morphism consists of an object of and a morphism which contains projections.
Examples.
In the category of sets, the product (in the category theoretic sense) is the Cartesian product. Given a family of sets the product is defined as
with the canonical projections
Given any set "Y" with a family of functions ,
the universal arrow is defined by := .
Other examples:
Discussion.
An example in which the product does not exist: In the category of fields, the product does not exist, since there is no field with homomorphisms to both and .
Another example: An empty product (i.e. is the empty set) is the same as a terminal object, and some categories, such as the category of infinite groups, do not have a terminal object: given any infinite group there are infinitely many morphisms so cannot be terminal.
If is a set such that all products for families indexed with exist, then one can treat each product as a functor . How this functor maps objects is obvious. Mapping of morphisms is subtle, because the product of morphisms defined above does not fit. First, consider the binary product functor, which is a bifunctor. For we should find a morphism . We choose . This operation on morphisms is called Cartesian product of morphisms. Second, consider the general product functor. For families we should find a morphism . We choose the product of morphisms .
A category where every finite set of objects has a product is sometimes called a Cartesian category
(although some authors use this phrase to mean "a category with all finite limits").
The product is associative. Suppose is a Cartesian category, product functors have been chosen as above, and denotes a terminal object of . We then have natural isomorphisms
These properties are formally similar to those of a commutative monoid; a Cartesian category with its finite products is an example of a symmetric monoidal category.
Distributivity.
For any objects , , and of a category with finite products and coproducts, there is a canonical morphism , where the plus sign here denotes the coproduct. To see this, note that the universal property of the coproduct guarantees the existence of unique arrows filling out the following diagram (the induced arrows are dashed):
The universal property of the product then guarantees a unique morphism induced by the dashed arrows in the above diagram. A distributive category is one in which this morphism is actually an isomorphism. Thus in a distributive category, one has the canonical isomorphism


Rebecca Waldecker

Rebecca Anne Hedwig Waldecker (born 1979) is a German mathematician specializing in group theory. She is professor for algebra at Martin Luther University of Halle-Wittenberg.
Education and career.
Waldecker is originally from Aachen. She earned her doctorate (Dr. rer. nat.) at the University of Kiel in 2007, under the supervision of , and in 2014 completed her habilitation at Martin Luther University of Halle-Wittenberg.
After postdoctoral research as a Leverhulme Fellow at the University of Birmingham, Waldecker joined Martin Luther University of Halle-Wittenberg as a junior professor in 2009. She became professor for algebra in 2015.
Books.
Waldecker is the author of the book "Isolated Involutions in Finite Groups" (Memoirs of the American Mathematical Society, 2013), developed from her doctoral dissertation.
With Lasse Rempe-Gillen, she is the coauthor of "Primzahltests für Einsteiger: Zahlentheorie, Algorithmik, Kryptographie" (Vieweg+Teubner, 2009; 2nd ed., Springer, 2016), a book on primality tests that was translated into English as "Primality Testing for Beginners" (Student Mathematical Library 70, American Mathematical Society, 2014).
She became a coauthor to the 2012 textbook "Elementare Algebra und Zahlentheorie" of , in its second edition (Mathematik Kompakt, Springer, 2019).


Subring

In mathematics, a subring of "R" is a subset of a ring that is itself a ring when binary operations of addition and multiplication on "R" are restricted to the subset, and which shares the same multiplicative identity as "R". For those who define rings without requiring the existence of a multiplicative identity, a subring of "R" is just a subset of "R" that is a ring for the operations of "R" (this does imply it contains the additive identity of "R"). The latter gives a strictly weaker condition, even for rings that do have a multiplicative identity, so that for instance all ideals become subrings (and they may have a multiplicative identity that differs from the one of "R"). With definition requiring a multiplicative identity (which is used in this article), the only ideal of "R" that is a subring of "R" is "R" itself.
Definition.
A subring of a ring is a subset "S" of "R" that preserves the structure of the ring, i.e. a ring with . Equivalently, it is both a subgroup of and a submonoid of .
Examples.
The ring formula_1 and its quotients formula_2 have no subrings (with multiplicative identity) other than the full ring.
Every ring has a unique smallest subring, isomorphic to some ring formula_2 with "n" a nonnegative integer (see characteristic). The integers formula_1 correspond to in this statement, since formula_1 is isomorphic to formula_6.
Subring test.
The subring test is a theorem that states that for any ring "R", a subset "S" of "R" is a subring if and only if it is closed under multiplication and subtraction, and contains the multiplicative identity of "R".
As an example, the ring Z of integers is a subring of the field of real numbers and also a subring of the ring of polynomials Z["X"].
Ring extensions.
If "S" is a subring of a ring "R", then equivalently "R" is said to be a ring extension of "S", written as "R"/"S" in similar notation to that for field extensions.
Subring generated by a set.
Let "R" be a ring. Any intersection of subrings of "R" is again a subring of "R". Therefore, if "X" is any subset of "R", the intersection of all subrings of "R" containing "X" is a subring "S" of "R". "S" is the smallest subring of "R" containing "X". ("Smallest" means that if "T" is any other subring of "R" containing "X", then "S" is contained in "T".) "S" is said to be the subring of "R" generated by "X". If "S" = "R," we may say that the ring "R" is "generated" by "X".
Relation to ideals.
Proper ideals are subrings (without unity) that are closed under both left and right multiplication by elements of "R".
If one omits the requirement that rings have a unity element, then subrings need only be non-empty and otherwise conform to the ring structure, and ideals become subrings. Ideals may or may not have their own multiplicative identity (distinct from the identity of the ring):
If "I" is a prime ideal of a commutative ring "R", then the intersection of "I" with any subring "S" of "R" remains prime in "S". In this case one says that "I" lies over "I" ∩ "S". The situation is more complicated when "R" is not commutative.
Profile by commutative subrings.
A ring may be profiled by the variety of commutative subrings that it hosts:


Sieved ultraspherical polynomials

In mathematics, the two families "c"("x";"k") and "B"("x";"k") of sieved ultraspherical polynomials, introduced by Waleed Al-Salam, W.R. Allaway and Richard Askey in 1984, are the archetypal examples of sieved orthogonal polynomials. Their recurrence relations are a modified (or "sieved") version of the recurrence relations for ultraspherical polynomials.
Recurrence relations.
For the sieved ultraspherical polynomials of the first kind the recurrence relations are
For the sieved ultraspherical polynomials of the second kind the recurrence relations are


Parafactorial local ring

In algebraic geometry, a Noetherian local ring "R" is called parafactorial if it has depth at least 2 and the Picard group Pic(Spec("R") − "m") of its spectrum with the closed point "m" removed is trivial.
More generally, a scheme "X" is called parafactorial along a closed subset "Z" if the subset "Z" is "too small" for invertible sheaves to detect; more precisely if for every open set "V" the map from "P"("V") to "P"("V" ∩ "U") is an equivalence of categories, where "U" = "X" – "Z" and "P"("V") is the category of invertible sheaves on "V". A Noetherian local ring is parafactorial if and only if its spectrum is parafactorial along its closed point.
Parafactorial local rings were introduced by