Family of curves

A family of curves is a set of curves, each of which is given by a function or parametrization in which one or more of the parameters is variable. In general, the parameter(s) influence the shape of the curve in a way that is more complicated than a simple linear transformation. Sets of curves given by an implicit relation may also represent families of curves.
Families of curves appear frequently in solutions of differential equations; when an additive constant of integration is introduced, it will usually be manipulated algebraically until it no longer represents a simple linear transformation.
Families of curves may also arise in other areas. For example, all non-degenerate conic sections can be represented using a single polar equation with one parameter, the eccentricity of the curve:
as the value of e changes, the appearance of the curve varies in a relatively complicated way.
Applications.
Families of curves may arise in various topics in geometry, including the envelope of a set of curves and the caustic of a given curve.
Generalizations.
In algebraic geometry, an algebraic generalization is given by the notion of a linear system of divisors.


Index calculus algorithm

In computational number theory, the index calculus algorithm is a probabilistic algorithm for computing discrete logarithms.
Dedicated to the discrete logarithm in formula_1 where formula_2 is a prime, index calculus leads to a family of algorithms adapted to finite fields and to some families of elliptic curves. The algorithm collects relations among the discrete logarithms of small primes, computes them by a linear algebra procedure and finally expresses the desired discrete logarithm with respect to the discrete logarithms of small primes.
Description.
Roughly speaking, the discrete log problem asks us to find an "x" such that formula_3, where "g", "h", and the modulus "n" are given.
The algorithm (described in detail below) applies to the group formula_1 where "q" is prime. It requires a "factor base" as input. This "factor base" is usually chosen to be the number −1 and the first "r" primes starting with 2. From the point of view of efficiency, we want this factor base to be small, but in order to solve the discrete log for a large group we require the "factor base" to be (relatively) large. In practical implementations of the algorithm, those conflicting objectives are compromised one way or another.
The algorithm is performed in three stages. The first two stages depend only on the generator "g" and prime modulus "q", and find the discrete logarithms of a "factor base" of "r" small primes. The third stage finds the discrete log of the desired number "h" in terms of the discrete logs of the factor base.
The first stage consists of searching for a set of "r" linearly independent "relations" between the factor base and power of the generator "g". Each relation contributes one equation to a system of linear equations in "r" unknowns, namely the discrete logarithms of the "r" primes in the factor base. This stage is embarrassingly parallel and easy to divide among many computers.
The second stage solves the system of linear equations to compute the discrete logs of the factor base. A system of hundreds of thousands or millions of equations is a significant computation requiring large amounts of memory, and it is "not" embarrassingly parallel, so a supercomputer is typically used. This was considered a minor step compared to the others for smaller discrete log computations. However, larger discrete logarithm records were made possible only by shifting the work away from the linear algebra and onto the sieve (i.e., increasing the number of equations while reducing the number of variables).
The third stage searches for a power "s" of the generator "g" which, when multiplied by the argument "h", may be factored in terms of the factor base "gsh" = (−1)"f"0 2"f"1 3"f"2···"p""r""f""r".
Finally, in an operation too simple to really be called a fourth stage, the results of the second and third stages can be rearranged by simple algebraic manipulation to work out the desired discrete logarithm "x" = "f"0log"g"(−1) + "f"1log"g"2 + "f"2log"g"3 + ··· + "f""r"log"g""pr" − "s".
The first and third stages are both embarrassingly parallel, and in fact the third stage does not depend on the results of the first two stages, so it may be done in parallel with them.
The choice of the factor base size "r" is critical, and the details are too intricate to explain here. The larger the factor base, the easier it is to find relations in stage 1, and the easier it is to complete stage 3, but the more relations you need before you can proceed to stage 2, and the more difficult stage 2 is. The relative availability of computers suitable for the different types of computation required for stages 1 and 2 is also important.
Applications in other groups.
The lack of the notion of "prime elements" in the group of points on elliptic curves makes it impossible to find an efficient "factor base" to run index calculus method as presented here in these groups. Therefore this algorithm is incapable of solving discrete logarithms efficiently in elliptic curve groups. However: For special kinds of curves (so called supersingular elliptic curves) there are specialized algorithms for solving the problem faster than with generic methods. While the use of these special curves can easily be avoided, in 2009 it has been proven that for certain fields the discrete logarithm problem in the group of points on "general" elliptic curves over these fields can be solved faster than with generic methods. The algorithms are indeed adaptations of the index calculus method.
The algorithm.
Input: Discrete logarithm generator "g", modulus "q" and argument "h". Factor base {−1,2,3,5,7,11...,"pr"}, of length "r" + 1.
Output: "x" such that "gx" ≡ "h" (mod "q").
Complexity.
Assuming an optimal selection of the factor base, the expected running time (using L-notation) of the index-calculus algorithm can be stated as
formula_12.
History.
The basic idea of the algorithm is due to Western and Miller (1968), which ultimately relies on ideas from Kraitchik (1922). The first practical implementations followed the 1976 introduction of the Diffie-Hellman cryptosystem which relies on the discrete logarithm. Merkle's Stanford University dissertation (1979) was credited by Pohlig (1977) and Hellman and Reyneri (1983), who also made improvements to the implementation. Adleman optimized the algorithm and presented it in the present form.
The Index Calculus family.
Index Calculus inspired a large family of algorithms. In finite fields formula_13 with formula_14 for some prime formula_15, the state-of-art algorithms are
the Number Field Sieve for Discrete Logarithms, formula_16, when formula_17 is large compared to formula_2, the function field sieve, formula_19, and Joux, formula_20 for formula_21, when formula_15 is small compared to formula_23 and the Number Field Sieve in High Degree, formula_24 for formula_21 when formula_26 is middle-sided. Discrete logarithm in some families of elliptic curves can be solved in time formula_27 for formula_28, but the general case remains exponential.


Smooth scheme

In algebraic geometry, a smooth scheme over a field is a scheme which is well approximated by affine space near any point. Smoothness is one way of making precise the notion of a scheme with no singular points. A special case is the notion of a smooth variety over a field. Smooth schemes play the role in algebraic geometry of manifolds in topology.
Definition.
First, let "X" be an affine scheme of finite type over a field "k". Equivalently, "X" has a closed immersion into affine space "An" over "k" for some natural number "n". Then "X" is the closed subscheme defined by some equations "g"1 = 0, ..., "g""r" = 0, where each "gi" is in the polynomial ring "k"["x"1..., "x""n"]. The affine scheme "X" is smooth of dimension "m" over "k" if "X" has dimension at least "m" in a neighborhood of each point, and the matrix of derivatives (∂"g""i"/∂"x""j") has rank at least "n"−"m" everywhere on "X". (It follows that "X" has dimension equal to "m" in a neighborhood of each point.) Smoothness is independent of the choice of immersion of "X" into affine space.
The condition on the matrix of derivatives is understood to mean that the closed subset of "X" where all ("n"−"m") × ("n" − "m") minors of the matrix of derivatives are zero is the empty set. Equivalently, the ideal in the polynomial ring generated by all "g""i" and all those minors is the whole polynomial ring.
In geometric terms, the matrix of derivatives (∂"g""i"/∂"x""j") at a point "p" in "X" gives a linear map "F""n" → "F""r", where "F" is the residue field of "p". The kernel of this map is called the Zariski tangent space of "X" at "p". Smoothness of "X" means that the dimension of the Zariski tangent space is equal to the dimension of "X" near each point; at a singular point, the Zariski tangent space would be bigger.
More generally, a scheme "X" over a field "k" is smooth over "k" if each point of "X" has an open neighborhood which is a smooth affine scheme of some dimension over "k". In particular, a smooth scheme over "k" is locally of finite type.
There is a more general notion of a smooth morphism of schemes, which is roughly a morphism with smooth fibers. In particular, a scheme "X" is smooth over a field "k" if and only if the morphism "X" → Spec "k" is smooth.
Properties.
A smooth scheme over a field is regular and hence normal. In particular, a smooth scheme over a field is reduced.
Define a variety over a field "k" to be an integral separated scheme of finite type over "k". Then any smooth separated scheme of finite type over "k" is a finite disjoint union of smooth varieties over "k".
For a smooth variety "X" over the complex numbers, the space "X"(C) of complex points of "X" is a complex manifold, using the classical (Euclidean) topology. Likewise, for a smooth variety "X" over the real numbers, the space "X"(R) of real points is a real manifold, possibly empty.
For any scheme "X" that is locally of finite type over a field "k", there is a coherent sheaf Ω1 of differentials on "X". The scheme "X" is smooth over "k" if and only if Ω1 is a vector bundle of rank equal to the dimension of "X" near each point. In that case, Ω1 is called the cotangent bundle of "X". The tangent bundle of a smooth scheme over "k" can be defined as the dual bundle, "TX" = (Ω1)*.
Smoothness is a geometric property, meaning that for any field extension "E" of "k", a scheme "X" is smooth over "k" if and only if the scheme "XE" := "X" ×Spec "k" Spec "E" is smooth over "E". For a perfect field "k", a scheme "X" is smooth over "k" if and only if "X" is locally of finite type over "k" and "X" is regular.
Generic smoothness.
A scheme "X" is said to be generically smooth of dimension "n" over "k" if "X" contains an open dense subset that is smooth of dimension "n" over "k". Every variety over a perfect field (in particular an algebraically closed field) is generically smooth.


Chow variety

In mathematics, particularly in the field of algebraic geometry, a Chow variety is an algebraic variety whose points correspond to effective algebraic cycles of fixed dimension and degree on a given projective space. More precisely, the Chow variety formula_1 is the fine moduli variety parametrizing all effective algebraic cycles of dimension formula_2 and degree formula_3 in formula_4.
The Chow variety formula_1 may be constructed via a Chow embedding into a sufficiently large projective space. This is a direct generalization of the construction of a Grassmannian variety via the Plücker embedding, as Grassmannians are the formula_6 case of Chow varieties.
Chow varieties are distinct from Chow groups, which are the abelian group of all algebraic cycles on a variety (not necessarily projective space) up to rational equivalence. Both are named for Wei-Liang Chow(周煒良), a pioneer in the study of algebraic cycles.
Background on algebraic cycles.
If X is a closed subvariety of formula_4 of dimension formula_8, the degree of X is the number of intersection points between X and a generic formula_9-dimensional projective subspace of formula_4.
Degree is constant in families of subvarieties, except in certain degenerate limits. To see this, consider the following family parametrized by t.
Whenever formula_12, formula_13 is a conic (an irreducible subvariety of degree 2), but formula_14 degenerates to the line formula_15 (which has degree 1). There are several approaches to reconciling this issue, but the simplest is to declare formula_14 to be a "line of multiplicity 2" (and more generally to attach multiplicities to subvarieties) using the language of "algebraic cycles".
A formula_2-dimensional algebraic cycle is a finite formal linear combination
in which formula_19s are formula_2-dimensional irreducible closed subvarieties in formula_4, and formula_22s are integers. An algebraic cycle is effective if each formula_23. The degree of an algebraic cycle is defined to be
A homogeneous polynomial or homogeneous ideal in n-many variables defines an effective algebraic cycle in formula_4, in which the multiplicity of each irreducible component is the order of vanishing at that component. In the family of algebraic cycles defined by formula_26, the formula_27 cycle is 2 times the line formula_15, which has degree 2. More generally, the degree of an algebraic cycle is constant in families, and so it makes sense to consider the moduli problem of effective algebraic cycles of fixed dimension and degree.
Examples of Chow varieties.
There are three special classes of Chow varieties with particularly simple constructions.
Degree 1: Subspaces.
An effective algebraic cycle in formula_4 of dimension k-1 and degree 1 is the projectivization of a k-dimensional subspace of n-dimensional affine space. This gives an isomorphism to a Grassmannian variety:
The latter space has a distinguished system of homogeneous coordinates, given by the Plücker coordinates.
Dimension 0: Points.
An effective algebraic cycle in formula_4 of dimension 0 and degree d is an (unordered) d-tuple of points in formula_4, possibly with repetition. This gives an isomorphism to a symmetric power of formula_4:
Codimension 1: Divisors.
An effective algebraic cycle in formula_4 of codimension 1 and degree d can be defined by the vanishing of a single degree d polynomial in n-many variables, and this polynomial is unique up to rescaling. Letting formula_36 denote the vector space of degree d polynomials in n-many variables, this gives an isomorphism to a projective space:
Note that the latter space has a distinguished system of homogeneous coordinates, which send a polynomial to the coefficient of a fixed monomial.
A non-trivial example.
The Chow variety formula_38 parametrizes dimension 1, degree 2 cycles in formula_39. This Chow variety has two irreducible components.
These two 8-dimensional components intersect in the moduli of coplanar pairs of lines, which is the singular locus in formula_38. This shows that, in contrast with the special cases above, Chow varieties need not be smooth or irreducible.
The Chow embedding.
Let X be an irreducible subvariety in formula_4 of dimension k-1 and degree d. By the definition of the degree, most formula_9-dimensional projective subspaces of formula_4 intersect X in d-many points. By contrast, most formula_44-dimensional projective subspaces of formula_4 do not intersect at X at all. This can be sharpened as follows.
Lemma. The set formula_46 parametrizing the subspaces of formula_4 which intersect X non-trivially is an irreducible hypersurface of degree d.
As a consequence, there exists a degree d form formula_48 on formula_49 which vanishes precisely on formula_50, and this form is unique up to scaling. This construction can be extended to an algebraic cycle formula_18 by declaring that formula_52. To each degree d algebraic cycle, this associates a degree d form formula_48 on formula_49, called the Chow form of X, which is well-defined up to scaling.
Let formula_55 denote the vector space of degree d forms on formula_49.
The Chow-van-der-Waerden Theorem. The map formula_57 which sends formula_58 is a closed embedding of varieties.
In particular, an effective algebraic cycle X is determined by its Chow form formula_48.
If a basis for formula_55 has been chosen, sending formula_61 to the coefficients of formula_48 in this basis gives a system of homogeneous coordinates on the Chow variety formula_1, called the Chow coordinates of formula_61. However, as there is no consensus as to the ‘best’ basis for formula_55, this term can be ambiguous.
From a foundational perspective, the above theorem is usually used as the definition of formula_1. That is, the Chow variety is usually defined as a subvariety of formula_67, and only then shown to be a fine moduli space for the moduli problem in question.
Relation to the Hilbert scheme.
A more sophisticated solution to the problem of 'correctly' counting the degree of a degenerate subvariety is to work with subschemes of formula_4 rather than subvarieties. Schemes can keep track of infinitesimal information that varieties and algebraic cycles cannot.
For example, if two points in a variety approach each other in an algebraic family, the limiting subvariety is a single point, the limiting algebraic cycle is a point with multiplicity 2, and the limiting subscheme is a 'fat point' which contains the tangent direction along which the two points collided.
The Hilbert scheme formula_69 is the fine moduli scheme of closed subschemes of dimension k-1 and degree d inside formula_4. Each closed subscheme determines an effective algebraic cycle, and the induced map
is called the cycle map or the Hilbert-Chow morphism. This map is generically an isomorphism over the points in formula_1 corresponding to irreducible subvarieties of degree d, but the fibers over non-simple algebraic cycles can be more interesting.
Chow quotient.
A Chow quotient parametrizes closures of generic orbits. It is constructed as a closed subvariety of a Chow variety.
Kapranov's theorem says that the moduli space formula_73 of stable genus-zero curves with "n" marked points is the Chow quotient of Grassmannian formula_74 by the standard maximal torus.


Small set (category theory)

In category theory, a small set is one in a fixed universe of sets (as the word "universe" is used in mathematics in general). Thus, the category of small sets is the category of all sets one cares to consider. This is used when one does not wish to bother with set-theoretic concerns of what is and what is not considered a set, which concerns would arise if one tried to speak of the category of "all sets".
A category C is called small if both the collection of objects and arrows are sets. Otherwise the category is called large.
A small set is not to be confused with a small category, which is a category whose collection of arrows (and therefore of objects) forms a small set. For more on small categories, see Category theory.
In other choices of foundations, such as Grothendieck universes, there exist both sets that belong to the universe, called “small sets” and sets that do not, such as the universe itself, “large sets”. We gain an intermediate notion of moderate set: a subset of the universe, which may be small or large. Again, Every small set is moderate, but not conversely.
Since in many cases the choice of foundations is irrelevant, it makes sense to always say “small set” for emphasis even if one has in mind a foundation where all sets are small.
Similarly, a small family is a family indexed by a small set; the axiom of replacement (if it applies in the foundation in question) then says that the image of the family is also small.


Adjoint representation

In mathematics, the adjoint representation (or adjoint action) of a Lie group "G" is a way of representing the elements of the group as linear transformations of the group's Lie algebra, considered as a vector space. For example, if "G" is formula_1, the Lie group of real "n"-by-"n" invertible matrices, then the adjoint representation is the group homomorphism that sends an invertible "n"-by-"n" matrix formula_2 to an endomorphism of the vector space of all linear transformations of formula_3 defined by: formula_4.
For any Lie group, this natural representation is obtained by linearizing (i.e. taking the differential of) the action of "G" on itself by conjugation. The adjoint representation can be defined for linear algebraic groups over arbitrary fields.
Definition.
Let "G" be a Lie group, and let
be the mapping ,
with Aut("G") the automorphism group of "G" and given by the inner automorphism (conjugation)
This Ψ is a Lie group homomorphism.
For each "g" in "G", define to be the derivative of at the origin:
where is the differential and formula_8 is the tangent space at the origin ( being the identity element of the group ). Since formula_9 is a Lie group automorphism, Ad"g" is a Lie algebra automorphism; i.e., an invertible linear transformation of formula_10 to itself that preserves the Lie bracket. Moreover, since formula_11 is a group homomorphism, formula_12 too is a group homomorphism. Hence, the map
is a group representation called the adjoint representation of "G".
If "G" is an immersed Lie subgroup of the general linear group formula_14 (called immersely linear Lie group), then the Lie algebra formula_15 consists of matrices and the exponential map is the matrix exponential formula_16 for matrices "X" with small operator norms. Thus, for "g" in "G" and small "X" in formula_15, taking the derivative of formula_18 at "t" = 0, one gets:
where on the right we have the products of matrices. If formula_20 is a closed subgroup (that is, "G" is a matrix Lie group), then this formula is valid for all "g" in "G" and all "X" in formula_10.
Succinctly, an adjoint representation is an isotropy representation associated to the conjugation action of "G" around the identity element of "G".
Derivative of Ad.
One may always pass from a representation of a Lie group "G" to a representation of its Lie algebra by taking the derivative at the identity.
Taking the derivative of the adjoint map
at the identity element gives the adjoint representation of the Lie algebra formula_23 of "G":
where formula_25 is the Lie algebra of formula_26 which may be identified with the derivation algebra of formula_10. One can show that
for all formula_29, where the right hand side is given (induced) by the Lie bracket of vector fields. Indeed, recall that, viewing formula_15 as the Lie algebra of left-invariant vector fields on "G", the bracket on formula_10 is given as: for left-invariant vector fields "X", "Y",
where formula_33 denotes the flow generated by "X". As it turns out, formula_34, roughly because both sides satisfy the same ODE defining the flow. That is, formula_35 where formula_36 denotes the right multiplication by formula_37. On the other hand, since formula_38, by chain rule,
as "Y" is left-invariant. Hence,
which is what was needed to show.
Thus, formula_41 coincides with the same one defined in below. Ad and ad are related through the exponential map: Specifically, Adexp("x") = exp(ad"x") for all "x" in the Lie algebra. It is a consequence of the general result relating Lie group and Lie algebra homomorphisms via the exponential map.
If "G" is an immersely linear Lie group, then the above computation simplifies: indeed, as noted early, formula_42 and thus with formula_43,
Taking the derivative of this at formula_45, we have:
The general case can also be deduced from the linear case: indeed, let formula_47 be an immersely linear Lie group having the same Lie algebra as that of "G". Then the derivative of Ad at the identity element for "G" and that for "G" coincide; hence, without loss of generality, "G" can be assumed to be "G".
The upper-case/lower-case notation is used extensively in the literature. Thus, for example, a vector in the algebra formula_15 generates a vector field in the group . Similarly, the adjoint map of vectors in formula_15 is homomorphic to the Lie derivative of vector fields on the group considered as a manifold.
Further see the derivative of the exponential map.
Adjoint representation of a Lie algebra.
Let formula_15 be a Lie algebra over some field. Given an element of a Lie algebra formula_15, one defines the adjoint action of on formula_15 as the map
for all in formula_15. It is called the adjoint endomorphism or adjoint action. (formula_55 is also often denoted as formula_56.) Since a bracket is bilinear, this determines the linear mapping
given by . Within Endformula_58, the bracket is, by definition, given by the commutator of the two operators:
where formula_60 denotes composition of linear maps. Using the above definition of the bracket, the Jacobi identity
takes the form
where , , and are arbitrary elements of formula_15.
This last identity says that ad is a Lie algebra homomorphism; i.e., a linear mapping that takes brackets to brackets. Hence, ad is a representation of a Lie algebra and is called the adjoint representation of the algebra formula_15.
If formula_15 is finite-dimensional, then Endformula_58 is isomorphic to formula_67, the Lie algebra of the general linear group of the vector space formula_15 and if a basis for it is chosen, the composition corresponds to matrix multiplication.
In a more module-theoretic language, the construction says that formula_15 is a module over itself.
The kernel of ad is the center of formula_15 (that's just rephrasing the definition). On the other hand, for each element in formula_15, the linear mapping formula_72 obeys the Leibniz' law:
for all and in the algebra (the restatement of the Jacobi identity). That is to say, ad"z" is a derivation and the image of formula_15 under ad is
a subalgebra of Derformula_58, the space of all derivations of formula_15.
When formula_77 is the Lie algebra of a Lie group "G", ad is the differential of Ad at the identity element of "G" (see #Derivative of Ad above).
There is the following formula similar to the Leibniz formula: for scalars formula_78 and Lie algebra elements formula_79,
Structure constants.
The explicit matrix elements of the adjoint representation are given by the structure constants of the algebra. That is, let {ei} be a set of basis vectors for the algebra, with
Then the matrix elements for
adei
are given by
Thus, for example, the adjoint representation of su(2) is the defining rep of so(3).
Properties.
The following table summarizes the properties of the various maps mentioned in the definition
The image of "G" under the adjoint representation is denoted by Ad("G"). If "G" is connected, the kernel of the adjoint representation coincides with the kernel of Ψ which is just the center of "G". Therefore, the adjoint representation of a connected Lie group "G" is faithful if and only if "G" is centerless. More generally, if "G" is not connected, then the kernel of the adjoint map is the centralizer of the identity component "G"0 of "G". By the first isomorphism theorem we have
Given a finite-dimensional real Lie algebra formula_15, by Lie's third theorem, there is a connected Lie group formula_86 whose Lie algebra is the image of the adjoint representation of formula_15 (i.e., formula_88.) It is called the adjoint group of formula_15.
Now, if formula_15 is the Lie algebra of a connected Lie group "G", then formula_86 is the image of the adjoint representation of "G": formula_92.
Roots of a semisimple Lie group.
If "G" is semisimple, the non-zero weights of the adjoint representation form a root system. (In general, one needs to pass to the complexification of the Lie algebra before proceeding.) To see how this works, consider the case "G" = SL("n", R). We can take the group of diagonal matrices diag("t"1, ..., "t""n") as our maximal torus "T". Conjugation by an element of "T" sends
Thus, "T" acts trivially on the diagonal part of the Lie algebra of "G" and with eigenvectors "t""i""t""j"−1 on the various off-diagonal entries. The roots of "G" are the weights diag("t"1, ..., "t""n") → "t""i""t""j"−1. This accounts for the standard description of the root system of "G" = SL"n"(R) as the set of vectors of the form "ei"−"ej".
Example SL(2, R).
When computing the root system for one of the simplest cases of Lie Groups, the group SL(2, R) of two dimensional matrices with determinant 1 consists of the set of matrices of the form:
with "a", "b", "c", "d" real and "ad" − "bc" = 1.
A maximal compact connected abelian Lie subgroup, or maximal torus "T", is given by the subset of all matrices of the form
with formula_96. The Lie algebra of the maximal torus is the Cartan subalgebra consisting of the matrices
If we conjugate an element of SL(2, "R") by an element of the maximal torus we obtain
The matrices
are then 'eigenvectors' of the conjugation operation with eigenvalues formula_100. The function Λ which gives formula_101 is a multiplicative character, or homomorphism from the group's torus to the underlying field R. The function λ giving θ is a weight of the Lie Algebra with weight space given by the span of the matrices.
It is satisfying to show the multiplicativity of the character and the linearity of the weight. It can further be proved that the differential of Λ can be used to create a weight. It is also educational to consider the case of SL(3, R).
Variants and analogues.
The adjoint representation can also be defined for algebraic groups over any field.
The co-adjoint representation is the contragredient representation of the adjoint representation. Alexandre Kirillov observed that the orbit of any vector in a co-adjoint representation is a symplectic manifold. According to the philosophy in representation theory known as the orbit method (see also the Kirillov character formula), the irreducible representations of a Lie group "G" should be indexed in some way by its co-adjoint orbits. This relationship is closest in the case of nilpotent Lie groups.


Probability vector

In mathematics and statistics, a probability vector or stochastic vector is a vector with non-negative entries that add up to one.
The positions (indices) of a probability vector represent the possible outcomes of a discrete random variable, and the vector gives us the probability mass function of that random variable, which is the standard way of characterizing a discrete probability distribution.
Examples.
Here are some examples of probability vectors. The vectors can be either columns or rows.
Geometric interpretation.
Writing out the vector components of a vector formula_5 as
the vector components must sum to one:
Each individual component must have a probability between zero and one:
for all formula_9. Therefore, the set of stochastic vectors coincides with the standard formula_10-simplex. It is a point if formula_11, a segment if formula_12, a (filled) triangle if formula_13, a (filled) tetrahedron formula_14, etc.


Giusto Bellavitis

Giusto Bellavitis (22 November 1803 – 6 November 1880) was an Italian mathematician, senator, and municipal councilor.
According to Charles Laisant,
Born in Bassano del Grappa in 1803 to Ernesto Bellavitis and Giovanna Navarini, Giusto studied largely alone. In 1840 he entered Institut Venitian and in 1842 began instructing at Lycee de Vicence. In 1845 he became professor of descriptive geometry at University of Padua. With the unification of Italy he took the opportunity to revise the curriculum to include complementary algebra and analytic geometry. Bellavitis married in 1842 and had one son who also taught geometry at the University of Padua.
Bellavitis anticipated the idea of a Euclidean vector with his notion of equipollence. Two line segments "AB" and "CD" are equipollent if they are parallel and have the same length and direction. The relation is denoted formula_1 In modern terminology, this relation between line segments is an example of an equivalence relation. The concept of vector addition was written by Bellavitis as
According to Laissant, Bellavitis published works in "arithmetic, algebra, geometry, infinitesimal calculus, probability, mechanics, physics, astronomy, chemistry, mineralogy, geodesy, geography, telegraphy, social science, philosophy, and literature."


Algebraic element

In mathematics, if is a field extension of , then an element of is called an algebraic element over , or just algebraic over , if there exists some non-zero polynomial with coefficients in such that . Elements of which are not algebraic over are called transcendental over .
These notions generalize the algebraic numbers and the transcendental numbers (where the field extension is , being the field of complex numbers and being the field of rational numbers).
Properties.
The following conditions are equivalent for an element of :
This characterization can be used to show that the sum, difference, product and quotient of algebraic elements over are again algebraic over . The set of all elements of which are algebraic over is a field that sits in between and .
If is algebraic over , then there are many nonzero polynomials with coefficients in such that . However, there is a single one with smallest degree and with leading coefficient 1. This is the minimal polynomial of "a" and it encodes many important properties of .
Fields that do not allow any algebraic elements over them (except their own elements) are called algebraically closed. The field of complex numbers is an example.


Natural transformation

In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i.e., the composition of morphisms) of the categories involved. Hence, a natural transformation can be considered to be a "morphism of functors". Indeed, this intuition can be formalized to define so-called functor categories. Natural transformations are, after categories and functors, one of the most fundamental notions of category theory and consequently appear in the majority of its applications.
Definition.
If formula_1 and formula_2 are functors between the categories formula_3 and formula_4, then a natural transformation formula_5 from formula_1 to formula_2 is a family of morphisms that satisfies two requirements.
The last equation can conveniently be expressed by the commutative diagram
If both formula_1 and formula_2 are contravariant, the vertical arrows in this diagram are reversed. If formula_5 is a natural transformation from formula_1 to formula_22, we also write formula_23 or formula_24. This is also expressed by saying the family of morphisms formula_25 is natural in formula_14.
If, for every object formula_8 in formula_28, the morphism formula_12 is an isomorphism in formula_4, then formula_5 is said to be a (or sometimes natural equivalence or isomorphism of functors). Two functors formula_32 and formula_2 are called "naturally isomorphic" or simply "isomorphic" if there exists a natural isomorphism from formula_1 to formula_2.
An infranatural transformation formula_5 from formula_1 to formula_2 is simply a family of morphisms formula_39, for all formula_8 in formula_3. Thus a natural transformation is an infranatural transformation for which formula_42 for every morphism formula_43. The naturalizer of formula_44, natformula_45, is the largest subcategory of formula_3 containing all the objects of formula_3 on which formula_5 restricts to a natural transformation.
Examples.
Opposite group.
Statements such as
abound in modern mathematics. We will now give the precise meaning of this statement as well as its proof. Consider the category
formula_49 of all groups with group homomorphisms as morphisms. If formula_50 is a group, we define
its opposite group formula_51 as follows: formula_52 is the same set as formula_53, and the operation formula_54 is defined
by formula_55. All multiplications in formula_56 are thus "turned around". Forming the opposite group becomes
a (covariant) functor from formula_49 to formula_49 if we define formula_59 for any group homomorphism formula_60. Note that
formula_61 is indeed a group homomorphism from formula_52 to formula_63:
The content of the above statement is:
To prove this, we need to provide isomorphisms formula_67 for every group formula_53, such that the above diagram commutes.
Set formula_69.
The formulas formula_70 and formula_71
show that formula_72 is a group homomorphism with inverse formula_73. To prove the naturality, we start with a group homomorphism
formula_74 and show formula_75, i.e.
formula_76 for all formula_77 in formula_53. This is true since
formula_59 and every group homomorphism has the property formula_80.
Abelianization.
Given a group formula_53, we can define its abelianization formula_82 formula_83. Let
formula_84 denote the projection map onto the cosets of formula_83. This homomorphism is "natural in
formula_53", i.e., it defines a natural transformation, which we now check. Let formula_87 be a group. For any homomorphism formula_74, we have that
formula_83 is contained in the kernel of formula_90, because any homomorphism into an abelian group kills the commutator subgroup. Then
formula_90 factors through formula_92 as formula_93 for the unique homomorphism
formula_94. This makes formula_95 a functor and
formula_96 a natural transformation, but not a natural isomorphism, from the identity functor to formula_97.
Hurewicz homomorphism.
Functors and natural transformations abound in algebraic topology, with the Hurewicz homomorphisms serving as examples. For any pointed topological space formula_98 and positive integer formula_99 there exists a group homomorphism
from the formula_99-th homotopy group of formula_98 to the formula_99-th homology group of formula_104. Both formula_105 and formula_106 are functors from the category Top* of pointed topological spaces to the category Grp of groups, and formula_107 is a natural transformation from formula_105 to formula_106.
Determinant.
Given commutative rings formula_110 and formula_111 with a ring homomorphism formula_112, the respective groups of invertible formula_113 matrices formula_114 and formula_115 inherit a homomorphism which we denote by formula_116, obtained by applying formula_117
to each matrix entry. Similarly, formula_117 restricts to a group homomorphism formula_119, where formula_120 denotes the group of units of formula_110. In fact, formula_122 and formula_123 are functors from the category of commutative rings formula_124 to formula_49.
The determinant on the group formula_114, denoted by formula_127, is a group homomorphism
which is natural in formula_110: because the determinant is defined by the same formula for every ring, formula_130 holds. This makes the determinant a natural transformation from formula_122 to formula_123.
Double dual of a vector space.
If formula_133 is a field, then for every vector space formula_134 over formula_133 we have a "natural" injective linear map formula_136 from the vector space into its double dual. These maps are "natural" in the following sense: the double dual operation is a functor, and the maps are the components of a natural transformation from the identity functor to the double dual functor.
Finite calculus.
For every abelian group formula_53, the set formula_138 of functions from the integers to the underlying set of formula_53
forms an abelian group formula_140 under pointwise addition. (Here formula_141 is the standard forgetful functor formula_142.)
Given an formula_143 morphism formula_144, the map formula_145 given by left composing formula_146 with the elements of the former is itself a homomorphism of abelian groups; in this way we
obtain a functor formula_147. The finite difference operator formula_148 taking each function
formula_149 to formula_150 is a map from formula_140 to itself, and the collection formula_152 of such maps gives a natural transformation formula_153.
Tensor-hom adjunction.
Consider the category formula_143 of abelian groups and group homomorphisms. For all abelian groups formula_104, formula_156 and formula_157 we have a group isomorphism
These isomorphisms are "natural" in the sense that they define a natural transformation between the two involved functors formula_159.
This is formally the tensor-hom adjunction, and is an archetypal example of a pair of adjoint functors. Natural transformations arise frequently in conjunction with adjoint functors, and indeed, adjoint functors are defined by a certain natural isomorphism. Additionally, every pair of adjoint functors comes equipped with two natural transformations (generally not isomorphisms) called the "unit" and "counit".
Unnatural isomorphism.
The notion of a natural transformation is categorical, and states (informally) that a particular map between functors can be done consistently over an entire category. Informally, a particular map (esp. an isomorphism) between individual objects (not entire categories) is referred to as a "natural isomorphism", meaning implicitly that it is actually defined on the entire category, and defines a natural transformation of functors; formalizing this intuition was a motivating factor in the development of category theory. Conversely, a particular map between particular objects may be called an unnatural isomorphism (or "this isomorphism is not natural") if the map cannot be extended to a natural transformation on the entire category. Given an object formula_162 a functor formula_53 (taking for simplicity the first functor to be the identity) and an isomorphism formula_164 proof of unnaturality is most easily shown by giving an automorphism formula_165 that does not commute with this isomorphism (so formula_166). More strongly, if one wishes to prove that formula_104 and formula_168 are not naturally isomorphic, without reference to a particular isomorphism, this requires showing that for "any" isomorphism formula_169, there is some formula_170 with which it does not commute; in some cases a single automorphism formula_170 works for all candidate isomorphisms formula_169 while in other cases one must show how to construct a different formula_173 for each isomorphism. The maps of the category play a crucial role – any infranatural transform is natural if the only maps are the identity map, for instance.
This is similar (but more categorical) to concepts in group theory or module theory, where a given decomposition of an object into a direct sum is "not natural", or rather "not unique", as automorphisms exist that do not preserve the direct sum decomposition – see for example.
Some authors distinguish notationally, using formula_174 for a natural isomorphism and formula_175 for an unnatural isomorphism, reserving formula_176 for equality (usually equality of maps).
Example: fundamental group of torus.
As an example of the distinction between the functorial statement and individual objects, consider homotopy groups of a product space, specifically the fundamental group of the torus.
The homotopy groups of a product space are naturally the product of the homotopy groups of the components, formula_177 with the isomorphism given by projection onto the two factors, fundamentally because maps into a product space are exactly products of maps into the components – this is a functorial statement.
However, the torus (which is abstractly a product of two circles) has fundamental group isomorphic to formula_178, but the splitting formula_179 is not natural. Note the use of formula_175, formula_174, and formula_182:
This abstract isomorphism with a product is not natural, as some isomorphisms of formula_184 do not preserve the product: the self-homeomorphism of formula_184 (thought of as the quotient space formula_186) given by formula_187 (geometrically a Dehn twist about one of the generating curves) acts as this matrix on formula_188 (it's in the general linear group formula_189 of invertible integer matrices), which does not preserve the decomposition as a product because it is not diagonal. However, if one is given the torus as a product formula_190 – equivalently, given a decomposition of the space – then the splitting of the group follows from the general statement earlier. In categorical terms, the relevant category (preserving the structure of a product space) is "maps of product spaces, namely a pair of maps between the respective components".
Naturality is a categorical notion, and requires being very precise about exactly what data is given – the torus as a space that happens to be a product (in the category of spaces and continuous maps) is different from the torus presented as a product (in the category of products of two spaces and continuous maps between the respective components).
Example: dual of a finite-dimensional vector space.
Every finite-dimensional vector space is isomorphic to its dual space, but there may be many different isomorphisms between the two spaces. There is in general no natural isomorphism between a finite-dimensional vector space and its dual space. However, related categories (with additional structure and restrictions on the maps) do have a natural isomorphism, as described below.
The dual space of a finite-dimensional vector space is again a finite-dimensional vector space of the same dimension, and these are thus isomorphic, since dimension is the only invariant of finite-dimensional vector spaces over a given field. However, in the absence of additional constraints (such as a requirement that maps preserve the chosen basis), the map from a space to its dual is not unique, and thus such an isomorphism requires a choice, and is "not natural". On the category of finite-dimensional vector spaces and linear maps, one can define an infranatural isomorphism from vector spaces to their dual by choosing an isomorphism for each space (say, by choosing a basis for every vector space and taking the corresponding isomorphism), but this will not define a natural transformation. Intuitively this is because it required a choice, rigorously because "any" such choice of isomorphisms will not commute with, say, the zero map; see for detailed discussion.
Starting from finite-dimensional vector spaces (as objects) and the identity and dual functors, one can define a natural isomorphism, but this requires first adding additional structure, then restricting the maps from "all linear maps" to "linear maps that respect this structure". Explicitly, for each vector space, require that it comes with the data of an isomorphism to its dual, formula_191. In other words, take as objects vector spaces with a nondegenerate bilinear form formula_192. This defines an infranatural isomorphism (isomorphism for each object). One then restricts the maps to only those maps formula_193 that commute with the isomorphisms: formula_194 or in other words, preserve the bilinear form: formula_195. (These maps define the "naturalizer" of the isomorphisms.) The resulting category, with objects finite-dimensional vector spaces with a nondegenerate bilinear form, and maps linear transforms that respect the bilinear form, by construction has a natural isomorphism from the identity to the dual (each space has an isomorphism to its dual, and the maps in the category are required to commute). Viewed in this light, this construction (add transforms for each object, restrict maps to commute with these) is completely general, and does not depend on any particular properties of vector spaces.
In this category (finite-dimensional vector spaces with a nondegenerate bilinear form, maps linear transforms that respect the bilinear form), the dual of a map between vector spaces can be identified as a transpose. Often for reasons of geometric interest this is specialized to a subcategory, by requiring that the nondegenerate bilinear forms have additional properties, such as being symmetric (orthogonal matrices), symmetric and positive definite (inner product space), symmetric sesquilinear (Hermitian spaces), skew-symmetric and totally isotropic (symplectic vector space), etc. – in all these categories a vector space is naturally identified with its dual, by the nondegenerate bilinear form.
Operations with natural transformations.
If formula_196 and formula_197
are natural transformations between functors formula_198, then we can compose them to get a natural transformation formula_199.
This is done componentwise: formula_200. This "vertical composition" of natural transformation is associative and has an identity, and
allows one to consider the collection of all functors formula_201 itself as a category (see below under Functor categories).
Natural transformations also have a "horizontal composition". If formula_202
is a natural transformation between functors formula_203 and formula_204
is a natural transformation between functors formula_205, then the composition of functors allows a composition of natural transformations formula_206.
This operation is also associative with identity, and the identity coincides with that for vertical composition. The two operations are related by an identity which exchanges vertical composition with horizontal composition.
If formula_202 is a natural transformation between functors formula_203, and formula_209 is another functor, then we can form the natural transformation formula_210 by defining
If on the other hand formula_212 is a functor, the natural transformation formula_213 is defined by
Functor categories.
If formula_215 is any category and formula_216 is a small category, we can form the functor category formula_217 having as objects all functors from formula_216 to formula_215 and as morphisms the natural transformations between those functors. This forms a category since for any functor formula_220 there is an identity natural transformation formula_221 (which assigns to every object formula_104 the identity morphism on formula_223) and the composition of two natural transformations (the "vertical composition" above) is again a natural transformation.
The isomorphisms in formula_217 are precisely the natural isomorphisms. That is, a natural transformation formula_202 is a natural isomorphism if and only if there exists a natural transformation formula_226 such that formula_227 and formula_228.
The functor category formula_217 is especially useful if formula_216 arises from a directed graph. For instance, if formula_216 is the category of the directed graph , then formula_217 has as objects the morphisms of formula_215, and a morphism between formula_234 and formula_235 in formula_217 is a pair of morphisms formula_237 and formula_238 in formula_215 such that the "square commutes", i.e. formula_240.
More generally, one can build the 2-category formula_241 whose
The horizontal and vertical compositions are the compositions between natural transformations described previously. A functor category formula_217 is then simply a hom-category in this category (smallness issues aside).
More examples.
Every limit and colimit provides an example for a simple natural transformation, as a cone amounts to a natural transformation with the diagonal functor as domain. Indeed, if limits and colimits are defined directly in terms of their universal property, they are universal morphisms in a functor category.
Yoneda lemma.
If formula_104 is an object of a locally small category formula_215, then the assignment formula_253 defines a covariant functor formula_254. This functor is called "representable" (more generally, a representable functor is any functor naturally isomorphic to this functor for an appropriate choice of formula_104). The natural transformations from a representable functor to an arbitrary functor formula_256 are completely known and easy to describe; this is the content of the Yoneda lemma.
Historical notes.
Saunders Mac Lane, one of the founders of category theory, is said to have remarked, "I didn't invent categories to study functors; I invented them to study natural transformations." Just as the study of groups is not complete without a study of homomorphisms, so the study of categories is not complete without the study of functors. The reason for Mac Lane's comment is that the study of functors is itself not complete without the study of natural transformations.
The context of Mac Lane's remark was the axiomatic theory of homology. Different ways of constructing homology could be shown to coincide: for example in the case of a simplicial complex the groups defined directly would be isomorphic to those of the singular theory. What cannot easily be expressed without the language of natural transformations is how homology groups are compatible with morphisms between objects, and how two equivalent homology theories not only have the same homology groups, but also the same morphisms between those groups.


Local Euler characteristic formula

In the mathematical field of Galois cohomology, the local Euler characteristic formula is a result due to John Tate that computes the Euler characteristic of the group cohomology of the absolute Galois group "GK" of a non-archimedean local field "K".
Statement.
Let "K" be a non-archimedean local field, let "Ks" denote a separable closure of "K", let "GK" = Gal("Ks"/"K") be the absolute Galois group of "K", and let "Hi"("K", "M") denote the group cohomology of "GK" with coefficients in "M". Since the cohomological dimension of "GK" is two, "Hi"("K", "M") = 0 for "i" ≥ 3. Therefore, the Euler characteristic only involves the groups with "i" = 0, 1, 2.
Case of finite modules.
Let "M" be a "GK"-module of finite order "m". The Euler characteristic of "M" is defined to be
(the "i"th cohomology groups for "i" ≥ 3 appear tacitly as their sizes are all one).
Let "R" denote the ring of integers of "K". Tate's result then states that if "m" is relatively prime to the characteristic of "K", then
i.e. the inverse of the order of the quotient ring "R"/"mR".
Two special cases worth singling out are the following. If the order of "M" is relatively prime to the characteristic of the residue field of "K", then the Euler characteristic is one. If "K" is a finite extension of the "p"-adic numbers Q"p", and if "vp" denotes the "p"-adic valuation, then
where ["K":Q"p"] is the degree of "K" over Q"p".
The Euler characteristic can be rewritten, using local Tate duality, as
where "M"′ is the local Tate dual of "M".


Metanilpotent group

In mathematics, in the field of group theory, a metanilpotent group is a group that is nilpotent by nilpotent. In other words, it has a normal nilpotent subgroup such that the quotient group is also nilpotent.
In symbols, formula_1 is metanilpotent if there is a normal subgroup formula_2 such that both formula_2 and formula_4 are nilpotent.
The following are clear:


Michael Stillman

Michael Eugene Stillman (born March 24, 1957) is an American mathematician working in computational algebraic geometry and commutative algebra. He is a Professor of Mathematics at Cornell University. He is known for being one of the creators (with Daniel Grayson) of the Macaulay2 computer algebra system.
Education and career.
Michael Stillman completed his PhD at Harvard University in 1983 under the direction of David Mumford. He had postdoctoral positions at the University of Chicago, Brandeis University, and the Massachusetts Institute of Technology before moving to a permanent position at Cornell University in 1987.
Stillman is best known for his work on computer algebra systems. In 1983, he began work with Dave Bayer on the Macaulay computer algebra system, which they continued to improve until 1993. To get beyond several limitations in the design of Macaulay, Stillman and Daniel Grayson began work on the Macaulay2 system in 1993. Macaulay2 remains in active development as of 2019, and has been cited in over 2000 articles.
Stillman has over 30 mathematical publications, and has advised 11 PhD students.


Cycle graph

In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with "n" vertices is called "Cn". The number of vertices in "Cn" equals the number of edges, and every vertex has degree 2; that is, every vertex has exactly two edges incident with it.
Terminology.
There are many synonyms for "cycle graph". These include simple cycle graph and cyclic graph, although the latter term is less often used, because it can also refer to graphs which are merely not acyclic. Among graph theorists, cycle, polygon, or n"-gon are also often used. The term n"-cycle is sometimes used in other settings.
A cycle with an even number of vertices is called an even cycle; a cycle with an odd number of vertices is called an odd cycle.
Properties.
A cycle graph is:
In addition:
Similarly to the Platonic graphs, the cycle graphs form the skeletons of the dihedra. Their duals are the dipole graphs, which form the skeletons of the hosohedra.
Directed cycle graph.
A directed cycle graph is a directed version of a cycle graph, with all the edges being oriented in the same direction.
In a directed graph, a set of edges which contains at least one edge (or "arc") from each directed cycle is called a feedback arc set. Similarly, a set of vertices containing at least one vertex from each directed cycle is called a feedback vertex set.
A directed cycle graph has uniform in-degree 1 and uniform out-degree 1.
Directed cycle graphs are Cayley graphs for cyclic groups (see e.g. Trevisan).


Dual basis

In linear algebra, given a vector space "V" with a basis "B" of vectors indexed by an index set "I" (the cardinality of "I" is the dimensionality of "V"), the dual set of "B" is a set "B"∗ of vectors in the dual space "V"∗ with the same index set "I" such that "B" and "B"∗ form a biorthogonal system. The dual set is always linearly independent but does not necessarily span "V"∗. If it does span "V"∗, then "B"∗ is called the dual basis or reciprocal basis for the basis "B".
Denoting the indexed vector sets as formula_1 and formula_2, being biorthogonal means that the elements pair to have an inner product equal to 1 if the indexes are equal, and equal to 0 otherwise. Symbolically, evaluating a dual vector in "V"∗ on a vector in the original space "V":
where formula_4 is the Kronecker delta symbol.
Introduction.
To perform operations with a vector, we must have a straightforward method of calculating its components. In a Cartesian frame the necessary operation is the dot product of the vector and the base vector. E.g.,
where formula_6 is the bases in a Cartesian frame. The components of formula_7 can be found by
In a non-Cartesian frame, we do not necessarily have e"i" · for all . However, it is always possible to find a vector e"i" such that
The equality holds when e"i" is the dual base of e"i".
In a Cartesian frame, we have formula_10
Existence and uniqueness.
The dual set always exists and gives an injection from "V" into "V"∗, namely the mapping that sends "vi" to "vi". This says, in particular, that the dual space has dimension greater or equal to that of "V".
However, the dual set of an infinite-dimensional "V" does not span its dual space "V"∗. For example, consider the map "w" in "V"∗ from "V" into the underlying scalars "F" given by for all "i". This map is clearly nonzero on all "vi". If "w" were a finite linear combination of the dual basis vectors "vi", say formula_11 for a finite subset "K" of "I", then for any "j" not in "K", formula_12, contradicting the definition of "w". So, this "w" does not lie in the span of the dual set.
The dual of an infinite-dimensional space has greater dimensionality (this being a greater infinite cardinality) than the original space has, and thus these cannot have a basis with the same indexing set. However, a dual set of vectors exists, which defines a subspace of the dual isomorphic to the original space. Further, for topological vector spaces, a continuous dual space can be defined, in which case a dual basis may exist.
Finite-dimensional vector spaces.
In the case of finite-dimensional vector spaces, the dual set is always a dual basis and it is unique. These bases are denoted by and . If one denotes the evaluation of a covector on a vector as a pairing, the biorthogonality condition becomes:
The association of a dual basis with a basis gives a map from the space of bases of "V" to the space of bases of "V"∗, and this is also an isomorphism. For topological fields such as the real numbers, the space of duals is a topological space, and this gives a homeomorphism between the Stiefel manifolds of bases of these spaces.
A categorical and algebraic construction of the dual space.
Another way to introduce the dual space of a vector space (module) is by introducing it in a categorical sense. To do this, let formula_14 be a module defined over the ring formula_15 (that is, formula_14 is an object in the category formula_17). Then we define the dual space of formula_14, denoted formula_19, to be formula_20, the module formed of all formula_15-linear module homomorphisms from formula_14 into formula_15. Note then that we may define a dual to the dual, referred to as the double dual of formula_14, written as formula_25, and defined as formula_26.
To formally construct a basis for the dual space, we shall now restrict our view to the case where formula_27 is a finite-dimensional free (left) formula_15-module, where formula_15 is a ring of unity. Then, we assume that the set formula_30 is a basis for formula_27. From here, we define the Kronecker Delta function formula_32 over the basis formula_30 by formula_34 if formula_35 and formula_36 if formula_37. Then the set formula_38 describes a linearly independent set with each formula_39. Since formula_27 is finite-dimensional, the basis formula_30 is of finite cardinality. Then, the set formula_42 is a basis to formula_43 and formula_43 is a free (right) formula_15-module.
Examples.
For example, the standard basis vectors of R2 (the Cartesian plane) are
and the standard basis vectors of its dual space R2* are
In 3-dimensional Euclidean space, for a given basis {e1, e2, e3}, you can find the biorthogonal (dual) basis {e1, e2, e3} by formulas below:
where denotes the transpose and
is the volume of the parallelepiped formed by the basis vectors formula_50 and formula_51
In general the dual basis of a basis in a finite dimensional vector space can be readily computed as follows: given the basis formula_52 and corresponding dual basis formula_53 we can build matrices
Then the defining property of the dual basis states that
Hence the matrix for the dual basis formula_56 can be computed as


Block Wiedemann algorithm

The block Wiedemann algorithm for computing kernel vectors of a matrix over a finite field is a generalisation by Don Coppersmith of an algorithm due to Doug Wiedemann.
Wiedemann's algorithm.
Let formula_1 be an formula_2 square matrix over some finite field F, let formula_3 be a random vector of length formula_4, and let formula_5. Consider the sequence of vectors formula_6 obtained by repeatedly multiplying the vector by the matrix formula_1; let formula_8 be any other vector of length formula_4, and consider the sequence of finite-field elements formula_10
We know that the matrix formula_1 has a minimal polynomial; by the Cayley–Hamilton theorem we know that this polynomial is of degree (which we will call formula_12) no more than formula_4. Say formula_14. Then formula_15; so the minimal polynomial of the matrix annihilates the sequence formula_16 and hence formula_17.
But the Berlekamp–Massey algorithm allows us to calculate relatively efficiently some sequence formula_18 with formula_19. Our hope is that this sequence, which by construction annihilates formula_20, actually annihilates formula_16; so we have formula_22. We then take advantage of the initial definition of formula_23 to say formula_24 and so formula_25 is a hopefully non-zero kernel vector of formula_1.
The block Wiedemann (or Coppersmith-Wiedemann) algorithm.
The natural implementation of sparse matrix arithmetic on a computer makes it easy to compute the sequence "S" in parallel for a number of vectors equal to the width of a machine word – indeed, it will normally take no longer to compute for that many vectors than for one. If you have several processors, you can compute the sequence S for a different set of random vectors in parallel on all the computers.
It turns out, by a generalization of the Berlekamp–Massey algorithm to provide a sequence of small matrices, that you can take the sequence produced for a large number of vectors and generate a kernel vector of the original large matrix. You need to compute formula_27 for some formula_28 where formula_29 need to satisfy formula_30 and formula_31 are a series of vectors of length n; but in practice you can take formula_31 as a sequence of unit vectors and simply write out the first formula_33 entries in your vectors at each time "t".
References.
Wiedemann, D., "Solving sparse linear equations over finite fields," IEEE Trans. Inf. Theory IT-32, pp. 54-62, 1986.
D. Coppersmith, Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm, Math. Comp. 62 (1994), 333-350.
Villard's 1997 research report 'A study of Coppersmith's block Wiedemann algorithm using matrix polynomials' (the cover material is in French but the content in English) is a reasonable description.
Thomé's paper 'Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm' uses a more sophisticated FFT-based algorithm for computing the vector generating polynomials, and describes a practical implementation with "i"max = "j"max = 4 used to compute a kernel vector of a 484603×484603 matrix of entries modulo 2607−1, and hence to compute discrete logarithms in the field "GF"(2607).


Transitively normal subgroup

In mathematics, in the field of group theory, a subgroup of a group is said to be transitively normal in the group if every normal subgroup of the subgroup is also normal in the whole group. In symbols, formula_1 is a transitively normal subgroup of formula_2 if for every formula_3 normal in formula_1, we have that formula_3 is normal in formula_2.
An alternate way to characterize these subgroups is: every "normal subgroup preserving automorphism" of the whole group must restrict to a "normal subgroup preserving automorphism" of the subgroup.
Here are some facts about transitively normal subgroups:


Wreath product

In group theory, the wreath product is a special combination of two groups based on the semidirect product. It is formed by the action of one group on many copies of another group, somewhat analogous to exponentiation. Wreath products are used in the classification of permutation groups and also provide a way of constructing interesting examples of groups.
Given two groups "A" and "H" (sometimes known as the "bottom" and "top"), there exist two variations of the wreath product: the unrestricted wreath product "A" Wr "H" and the restricted wreath product "A" wr "H". The general form, denoted by "A" WrΩ "H" or "A" wrΩ "H" respectively, uses a set "Ω" with an "H"-action; when unspecified, usually "Ω" = "H" (a regular wreath product), though a different "Ω" is sometimes implied. The two variations coincide when "A", "H", and "Ω" are all finite. Either variation is also denoted as formula_1 (with \wr for the latex symbol) or "A" ≀ "H" (Unicode U+2240).
The notion generalizes to semigroups and is a central construction in the Krohn–Rhodes structure theory of finite semigroups.
Definition.
Let "A" and "H" be groups and Ω a set with "H" acting on it (from the left). Let "K" be the direct product
of copies of "A"ω := "A" indexed by the set Ω. The elements of "K" can be seen as arbitrary sequences ("a"ω) of elements of "A" indexed by Ω with component-wise multiplication. Then the action of "H" on Ω extends in a natural way to an action of "H" on the group "K" by
Then the unrestricted wreath product "A" WrΩ "H" of "A" by "H" is the semidirect product "K" ⋊ "H". The subgroup "K" of "A" WrΩ "H" is called the base of the wreath product.
The restricted wreath product "A" wrΩ "H" is constructed in the same way as the unrestricted wreath product except that one uses the direct sum
as the base of the wreath product. In this case the elements of "K" are sequences ("a"ω) of elements in "A" indexed by Ω of which all but finitely many "a"ω are the identity element of "A".
In the most common case, one takes Ω := "H", where "H" acts in a natural way on itself by left multiplication. In this case, the unrestricted and restricted wreath product may be denoted by "A" Wr "H" and "A" wr "H" respectively. This is called the regular wreath product.
Notation and conventions.
The structure of the wreath product of "A" by "H" depends on the "H"-set Ω and in case Ω is infinite it also depends on whether one uses the restricted or unrestricted wreath product. However, in literature the notation used may be deficient and one needs to pay attention to the circumstances.
Properties.
Agreement of unrestricted and restricted wreath product on finite Ω.
Since the finite direct product is the same as the finite direct sum of groups, it follows that the unrestricted "A" WrΩ "H" and the restricted wreath product "A" wrΩ "H" agree if the "H"-set Ω is finite. In particular this is true when Ω = "H" is finite.
Subgroup.
"A" wrΩ "H" is always a subgroup of "A" WrΩ "H".
Cardinality.
If "A", "H" and Ω are finite, then
Universal embedding theorem.
Universal embedding theorem: If "G" is an extension of "A" by "H", then there exists a subgroup of the unrestricted wreath product "A"≀"H" which is isomorphic to "G". This is also known as the "Krasner–Kaloujnine embedding theorem". The Krohn–Rhodes theorem involves what is basically the semigroup equivalent of this.
Canonical actions of wreath products.
If the group "A" acts on a set Λ then there are two canonical ways to construct sets from Ω and Λ on which "A" WrΩ "H" (and therefore also "A" wrΩ "H") can act.


Orbital integral

In mathematics, an orbital integral is an integral transform that generalizes the spherical mean operator to homogeneous spaces. Instead of integrating over spheres, one integrates over generalized spheres: for a homogeneous space "X" = "G"/"H", a generalized sphere centered at a point "x"0 is an orbit of the isotropy group of "x"0.
Definition.
The model case for orbital integrals is a Riemannian symmetric space "G"/"K", where "G" is a Lie group and "K" is a symmetric compact subgroup. Generalized spheres are then actual geodesic spheres and the spherical averaging operator is defined as
where
Orbital integrals of suitable functions can also be defined on homogeneous spaces "G"/"K" where the subgroup "K" is no longer assumed to be compact, but instead is assumed to be only unimodular. Lorentzian symmetric spaces are of this kind. The orbital integrals in this case are also obtained by integrating over a "K"-orbit in "G"/"K" with respect to the Haar measure of "K". Thus
is the orbital integral centered at "x" over the orbit through "y". As above, "g" is a group element that represents the coset "x".
Integral geometry.
A central problem of integral geometry is to reconstruct a function from knowledge of its orbital integrals. The Funk transform and Radon transform are two special cases. When "G"/"K" is a Riemannian symmetric space, the problem is trivial, since "M""r"ƒ("x") is the average value of ƒ over the generalized sphere of radius "r", and
When "K" is compact (but not necessarily symmetric), a similar shortcut works. The problem is more interesting when "K" is non-compact. For example, the Radon transform is the orbital integral that results by taking "G" to be the Euclidean isometry group and "K" the isotropy group of a hyperplane.
Orbital integrals are an important technical tool in the theory of automorphic forms, where they enter into the formulation of various trace formulas.


Cycle notation


Variable lifetime


Division ring

In algebra, a division ring, also called a skew field, is a ring in which division is possible. Specifically, it is a nonzero ring in which every nonzero element has a multiplicative inverse, that is, an element generally denoted , such that . So, "division" may be defined as , but this notation is generally avoided, as one may have .
A division ring is generally a noncommutative ring. It is commutative if and only if it is a field, in which case the term "division ring" is rarely used, except for properties of division rings that are true even if they are commutative or in the proof that a specific division ring is commutative. For example, Wedderburn's little theorem asserts that all finite division rings are commutative and therefore finite fields.
Historically, division rings were sometimes referred to as fields, while fields were called "commutative fields". In some languages, such as French, the word equivalent to "field" ("corps") is used for both commutative and noncommutative cases, and the distinction between the two cases is made by adding qualificatives such as "corps commutatif" (commutative field) or "corps gauche" (skew field).
All division rings are simple. That is, they have no two-sided ideal besides the zero ideal and itself.
Relation to fields and linear algebra.
All fields are division rings; more interesting examples are the non-commutative division rings. The best known example is the ring of quaternions H. If we allow only rational instead of real coefficients in the constructions of the quaternions, we obtain another division ring. In general, if "R" is a ring and "S" is a simple module over "R", then, by Schur's lemma, the endomorphism ring of "S" is a division ring; every division ring arises in this fashion from some simple module.
Much of linear algebra may be formulated, and remains correct, for modules over a division ring "D" instead of vector spaces over a field. Doing so it must be specified whether one is considering right or left modules, and some care is needed in properly distinguishing left and right in formulas. Working in coordinates, elements of a finite dimensional right module can be represented by column vectors, which can be multiplied on the right by scalars, and on the left by matrices (representing linear maps); for elements of a finite dimensional left module, row vectors must be used, which can be multiplied on the left by scalars, and on the right by matrices. The dual of a right module is a left module, and vice versa. The transpose of a matrix must be viewed as a matrix over the opposite division ring "D"op in order for the rule to remain valid.
Every module over a division ring is free; that is, it has a basis, and all bases of a module have the same number of elements. Linear maps between finite-dimensional modules over a division ring can be described by matrices; the fact that linear maps by definition commute with scalar multiplication is most conveniently represented in notation by writing them on the "opposite" side of vectors as scalars are. The Gaussian elimination algorithm remains applicable. The column rank of a matrix is the dimension of the right module generated by the columns, and the row rank is dimension of the left module generated by the rows; the same proof as for the vector space case can be used to show that these ranks are the same, and define the rank of a matrix.
In fact the converse is also true and this gives a "characterization of division rings" via their module category: A unital ring "R" is a division ring if and only if every R-module is free.
The center of a division ring is commutative and therefore a field. Every division ring is therefore a division algebra over its center. Division rings can be roughly classified according to whether or not they are finite-dimensional or infinite-dimensional over their centers. The former are called "centrally finite" and the latter "centrally infinite". Every field is, of course, one-dimensional over its center. The ring of Hamiltonian quaternions forms a 4-dimensional algebra over its center, which is isomorphic to the real numbers.
Main theorems.
Wedderburn's little theorem: All finite division rings are commutative and therefore finite fields. (Ernst Witt gave a simple proof.)
Frobenius theorem: The only finite-dimensional associative division algebras over the reals are the reals themselves, the complex numbers, and the quaternions.
Related notions.
Division rings "used to be" called "fields" in an older usage. In many languages, a word meaning "body" is used for division rings, in some languages designating either commutative or non-commutative division rings, while in others specifically designating commutative division rings (what we now call fields in English). A more complete comparison is found in the article on fields.
The name "Skew field" has an interesting semantic feature: a modifier (here "skew") "widens" the scope of the base term (here "field"). Thus a field is a particular type of skew field, and not all skew fields are fields.
While division rings and algebras as discussed here are assumed to have associative multiplication, nonassociative division algebras such as the octonions are also of interest.
A near-field is an algebraic structure similar to a division ring, except that it has only one of the two distributive laws.


Autocorrelation matrix


JLO cocycle

In noncommutative geometry, the JLO cocycle is a cocycle (and thus defines a cohomology class) in entire cyclic cohomology. It is a non-commutative version of the classic Chern character of the conventional differential geometry. In noncommutative geometry, the concept of a manifold is replaced by a noncommutative algebra formula_1 of "functions" on the putative noncommutative space. The cyclic cohomology of the algebra formula_1 contains the information about the topology of that noncommutative space, very much as the de Rham cohomology contains the information about the topology of a conventional manifold.
The JLO cocycle is associated with a metric structure of non-commutative differential geometry known as a formula_3-summable spectral triple (also known as a formula_3-summable Fredholm module).
formula_3-summable spectral triples.
A formula_3-summable spectral triple consists of the following data:
(a) A Hilbert space formula_7 such that formula_1 acts on it as an algebra of bounded operators.
(b) A formula_9-grading formula_10 on formula_7, formula_12. We assume that the algebra formula_1 is even under the formula_9-grading, i.e. formula_15, for all formula_16.
(c) A self-adjoint (unbounded) operator formula_17, called the "Dirac operator" such that
A classic example of a formula_3-summable spectral triple arises as follows. Let formula_28 be a compact spin manifold, formula_29, the algebra of smooth functions on formula_28, formula_7 the Hilbert space of square integrable forms on formula_28, and formula_17 the standard Dirac operator.
The cocycle.
The JLO cocycle formula_34 is a sequence
of functionals on the algebra formula_1, where
for formula_39. The cohomology class defined by formula_34 is independent of the value of formula_41.


Invertible


Folded cube graph

In graph theory, a folded cube graph is an undirected graph formed from a hypercube graph by adding to it a perfect matching that connects "opposite" pairs of hypercube vertices.
Construction.
The folded cube graph of dimension "k" (containing 2"k" − 1 vertices) may be formed by adding edges between opposite pairs of vertices in a hypercube graph of dimension "k" − 1. (In a hypercube with 2"n" vertices, a pair of vertices are "opposite" if the shortest path between them has length "n".) It can, equivalently, be formed from a hypercube graph (also) of dimension "k", which has twice as many vertices, by identifying together (or contracting) every opposite pair of vertices.
Properties.
A dimension-"k" folded cube graph is a "k"-regular with 2"k" − 1 vertices and 2"k" − 2"k" edges.
The chromatic number of the dimension-"k" folded cube graph is two when "k" is even (that is, in this case, the graph is bipartite) and four when "k" is odd. The odd girth of a folded cube of odd dimension is "k", so for odd "k" greater than three the folded cube graphs provide a class of triangle-free graphs with chromatic number four and arbitrarily large odd girth. As a distance-regular graph with odd girth "k" and diameter ("k" − 1)/2, the folded cubes of odd dimension are examples of generalized odd graphs.
When "k" is odd, the bipartite double cover of the dimension-"k" folded cube is the dimension-"k" cube from which it was formed.
However, when "k" is even, the dimension-"k" cube is a double cover but not the "bipartite" double cover. In this case, the folded cube is itself already bipartite. Folded cube graphs inherit from their hypercube subgraphs the property of having a Hamiltonian cycle, and from the hypercubes that double cover them the property of being a distance-transitive graph.
When "k" is odd, the dimension-"k" folded cube contains as a subgraph a complete binary tree with 2"k" − 1 nodes. However, when "k" is even, this is not possible, because in this case the folded cube is a bipartite graph with equal numbers of vertices on each side of the bipartition, very different from the nearly two-to-one ratio for the bipartition of a complete binary tree.
Applications.
In parallel computing, folded cube graphs have been studied as a potential network topology, as an alternative to the hypercube. Compared to a "hypercube", a "folded cube" with the same number of nodes has nearly the same vertex degree but only half the diameter. Efficient distributed algorithms (relative to those for a "hypercube") are known for broadcasting information in a folded cube.


Triple system

In algebra, a triple system (or ternar) is a vector space "V" over a field F together with a F-trilinear map
The most important examples are Lie triple systems and Jordan triple systems. They were introduced by Nathan Jacobson in 1949 to study subspaces of associative algebras closed under triple commutators anticommutator]]s {"u", {"v", "w"}}. In particular, any [[Lie algebra]] defines a Lie triple system and any [[Jordan algebra]] defines a Jordan triple system. They are important in the theories of [[symmetric space]]s, particularly [[Hermitian symmetric space]]s and their generalizations ([[symmetric R-space]]s and their noncompact duals).
Lie triple systems.
A triple system is said to be a "Lie triple system" if the trilinear map, denoted formula_2, satisfies the following identities:
The first two identities abstract the skew symmetry and Jacobi identity for the triple commutator, while the third identity means that the linear map L"u","v": "V" → "V", defined by L"u","v"("w") = ["u", "v", "w"], is a derivation of the triple product. The identity also shows that the space k = span {L"u","v" : "u", "v" ∈ "V"} is closed under commutator bracket, hence a Lie algebra.
Writing m in place of "V", it follows that
can be made into a formula_7-graded Lie algebra, the "standard embedding" of m, with bracket
The decomposition of g is clearly a symmetric decomposition for this Lie bracket, and hence if "G" is a connected Lie group with Lie algebra g and "K" is a subgroup with Lie algebra k, then "G"/"K" is a symmetric space.
Conversely, given a Lie algebra g with such a symmetric decomposition (i.e., it is the Lie algebra of a symmetric space), the triple bracket [["u", "v"], "w"] makes m into a Lie triple system.
Jordan triple systems.
A triple system is said to be a Jordan triple system if the trilinear map, denoted {...}, satisfies the following identities:
The first identity abstracts the symmetry of the triple anticommutator, while the second identity means that if L"u","v":"V"→"V" is defined by L"u","v"("y") = {"u", "v", "y"} then
so that the space of linear maps span {L"u","v":"u","v" ∈ "V"} is closed under commutator bracket, and hence is a Lie algebra g0.
Any Jordan triple system is a Lie triple system with respect to the product
A Jordan triple system is said to be positive definite (resp. nondegenerate) if the bilinear form on "V" defined by the trace of L"u","v" is positive definite (resp. nondegenerate). In either case, there is an identification of "V" with its dual space, and a corresponding involution on g0. They induce an involution of
which in the positive definite case is a Cartan involution. The corresponding [[symmetric space]] is a [[symmetric R-space]]. It has a noncompact dual given by replacing the Cartan involution by its composite with the involution equal to +1 on g0 and −1 on "V" and "V"*. A special case of this construction arises when g0 preserves a complex structure on "V". In this case we obtain dual [[Hermitian symmetric space]]s of compact and noncompact type (the latter being [[bounded symmetric domain]]s).
Jordan pair.
A Jordan pair is a generalization of a Jordan triple system involving two vector spaces "V"+ and "V"−. The trilinear map is then replaced by a pair of trilinear maps
which are often viewed as quadratic maps "V"+ → Hom("V"−, "V"+) and "V"− → Hom("V"+, "V"−). The other Jordan axiom (apart from symmetry) is likewise replaced by two axioms, one being
and the other being the analogue with + and − subscripts exchanged.
As in the case of Jordan triple systems, one can define, for "u" in "V"− and "v" in "V"+, a linear map
and similarly L−. The Jordan axioms (apart from symmetry) may then be written
which imply that the images of L+ and L− are closed under commutator brackets in End("V"+) and End("V"−). Together they determine a linear map
whose image is a Lie subalgebra formula_20, and the Jordan identities become Jacobi identities for a graded Lie bracket on
so that conversely, if
is a graded Lie algebra, then the pair formula_23 is a Jordan pair, with brackets
Jordan triple systems are Jordan pairs with "V"+ = "V"− and equal trilinear maps. Another important case occurs when "V"+ and "V"− are dual to one another, with dual trilinear maps determined by an element of
These arise in particular when formula_26 above is semisimple, when the Killing form provides a duality between formula_27 and formula_28.
References.
[[Category:Representation theory]]


Chevalley scheme

A Chevalley scheme in algebraic geometry was a precursor notion of scheme theory.
Let "X" be a separated integral noetherian scheme, "R" its function field. If we denote by formula_1 the set of subrings formula_2 of "R", where "x" runs through "X" (when formula_3, we denote formula_1 by formula_5), formula_1 verifies the following three properties
Originally, Chevalley also supposed that R was an extension of finite type of a field K and that the formula_15's were algebras of finite type over a field too (this simplifies the second condition above).


Degree of a polynomial

In mathematics, the degree of a polynomial is the highest of the degrees of the polynomial's monomials (individual terms) with non-zero coefficients. The degree of a term is the sum of the exponents of the variables that appear in it, and thus is a non-negative integer. For a univariate polynomial, the degree of the polynomial is simply the highest exponent occurring in the polynomial. The term order has been used as a synonym of "degree" but, nowadays, may refer to several other concepts (see order of a polynomial (disambiguation)).
For example, the polynomial formula_1 which can also be written as formula_2 has three terms. The first term has a degree of 5 (the sum of the powers 2 and 3), the second term has a degree of 1, and the last term has a degree of 0. Therefore, the polynomial has a degree of 5, which is the highest degree of any term.
To determine the degree of a polynomial that is not in standard form, such as formula_3, one can put it in standard form by expanding the products (by distributivity) and combining the like terms; for example, formula_4 is of degree 1, even though each summand has degree 2. However, this is not needed when the polynomial is written as a product of polynomials in standard form, because the degree of a product is the sum of the degrees of the factors.
Names of polynomials by degree.
The following names are assigned to polynomials according to their degree:
For higher degrees, names have sometimes been proposed, but they are rarely used:
Names for degree above three are based on Latin ordinal numbers, and end in "-ic". This should be distinguished from the names used for the number of variables, the arity, which are based on Latin distributive numbers, and end in "-ary". For example, a degree two polynomial in two variables, such as formula_5, is called a "binary quadratic": "binary" due to two variables, "quadratic" due to degree two. There are also names for the number of terms, which are also based on Latin distributive numbers, ending in "-nomial"; the common ones are "monomial", "binomial", and (less commonly) "trinomial"; thus formula_6 is a "binary quadratic binomial".
Examples.
The polynomial formula_7 is a cubic polynomial: after multiplying out and collecting terms of the same degree, it becomes formula_8, with highest exponent 3.
The polynomial formula_9 is a quintic polynomial: upon combining like terms, the two terms of degree 8 cancel, leaving formula_10, with highest exponent 5.
Behavior under polynomial operations.
The degree of the sum, the product or the composition of two polynomials is strongly related to the degree of the input polynomials.
Addition.
The degree of the sum (or difference) of two polynomials is less than or equal to the greater of their degrees; that is,
For example, the degree of formula_13 is 2, and 2 ≤ max{3, 3}.
The equality always holds when the degrees of the polynomials are different. For example, the degree of formula_14 is 3, and 3 = max{3, 2}.
Multiplication.
The degree of the product of a polynomial by a non-zero scalar is equal to the degree of the polynomial; that is,
For example, the degree of formula_16 is 2, which is equal to the degree of formula_17.
Thus, the set of polynomials (with coefficients from a given field "F") whose degrees are smaller than or equal to a given number "n" forms a vector space; for more, see Examples of vector spaces.
More generally, the degree of the product of two polynomials over a field or an integral domain is the sum of their degrees:
For example, the degree of formula_19 is 5 = 3 + 2.
For polynomials over an arbitrary ring, the above rules may not be valid, because of cancellation that can occur when multiplying two nonzero constants. For example, in the ring formula_20 of integers modulo 4, one has that formula_21, but formula_22, which is not equal to the sum of the degrees of the factors.
Composition.
The degree of the composition of two non-constant polynomials formula_23 and formula_24 over a field or integral domain is the product of their degrees:
For example:
Note that for polynomials over an arbitrary ring, this is not necessarily true. For example, in formula_20, formula_30, but formula_31.
Degree of the zero polynomial.
The degree of the zero polynomial is either left undefined, or is defined to be negative (usually −1 or formula_32).
Like any constant value, the value 0 can be considered as a (constant) polynomial, called the zero polynomial. It has no nonzero terms, and so, strictly speaking, it has no degree either. As such, its degree is usually undefined. The propositions for the degree of sums and products of polynomials in the above section do not apply, if any of the polynomials involved is the zero polynomial.
It is convenient, however, to define the degree of the zero polynomial to be "negative infinity", formula_33 and to introduce the arithmetic rules
and
These examples illustrate how this extension satisfies the behavior rules above:
Computed from the function values.
A number of formulae exist which will evaluate the degree of a polynomial function "f". One based on asymptotic analysis is
this is the exact counterpart of the method of estimating the slope in a log–log plot.
This formula generalizes the concept of degree to some functions that are not polynomials.
For example:
The formula also gives sensible results for many combinations of such functions, e.g., the degree of formula_50 is formula_51.
Another formula to compute the degree of "f" from its values is
this second formula follows from applying L'Hôpital's rule to the first formula. Intuitively though, it is more about exhibiting the degree "d" as the extra constant factor in the derivative formula_53 of formula_54.
A more fine grained (than a simple numeric degree) description of the asymptotics of a function can be had by using big O notation. In the analysis of algorithms, it is for example often relevant to distinguish between the growth rates of formula_55 and formula_56, which would both come out as having the "same" degree according to the above formulae.
Extension to polynomials with two or more variables.
For polynomials in two or more variables, the degree of a term is the "sum" of the exponents of the variables in the term; the degree (sometimes called the total degree) of the polynomial is again the maximum of the degrees of all terms in the polynomial. For example, the polynomial "x"2"y"2 + 3"x"3 + 4"y" has degree 4, the same degree as the term "x"2"y"2.
However, a polynomial in variables "x" and "y", is a polynomial in "x" with coefficients which are polynomials in "y", and also a polynomial in "y" with coefficients which are polynomials in "x". The polynomial
has degree 3 in "x" and degree 2 in "y".
Degree function in abstract algebra.
Given a ring "R", the polynomial ring "R"["x"] is the set of all polynomials in "x" that have coefficients in "R". In the special case that "R" is also a field, the polynomial ring "R"["x"] is a principal ideal domain and, more importantly to our discussion here, a Euclidean domain.
It can be shown that the degree of a polynomial over a field satisfies all of the requirements of the "norm" function in the euclidean domain. That is, given two polynomials "f"("x") and "g"("x"), the degree of the product "f"("x")"g"("x") must be larger than both the degrees of "f" and "g" individually. In fact, something stronger holds:
For an example of why the degree function may fail over a ring that is not a field, take the following example. Let "R" = formula_59, the ring of integers modulo 4. This ring is not a field (and is not even an integral domain) because 2 × 2 = 4 ≡ 0 (mod 4). Therefore, let "f"("x") = "g"("x") = 2"x" + 1. Then, "f"("x")"g"("x") = 4"x"2 + 4"x" + 1 = 1. Thus deg("f"⋅"g") = 0 which is not greater than the degrees of "f" and "g" (which each had degree 1).
Since the "norm" function is not defined for the zero element of the ring, we consider the degree of the polynomial "f"("x") = 0 to also be undefined so that it follows the rules of a norm in a Euclidean domain.