Leech lattice

In mathematics, the Leech lattice is an even unimodular lattice Λ24 in 24-dimensional Euclidean space, which is one of the best models for the kissing number problem. It was discovered by . It may also have been discovered (but not published) by Ernst Witt in 1940.
Characterization.
The Leech lattice Λ24 is the unique lattice in with the following list of properties:
The last condition is equivalent to the condition that unit balls centered at the points of Λ24 do not overlap. Each is tangent to 196,560 neighbors, and this is known to be the largest number of non-overlapping 24-dimensional unit balls that can simultaneously touch a single unit ball. This arrangement of 196,560 unit balls centred about another unit ball is so efficient that there is no room to move any of the balls; this configuration, together with its mirror-image, is the "only" 24-dimensional arrangement where 196,560 unit balls simultaneously touch another. This property is also true in 1, 2 and 8 dimensions, with 2, 6 and 240 unit balls, respectively, based on the integer lattice, hexagonal tiling and E8 lattice, respectively.
It has no root system and in fact is the first unimodular lattice with no "roots" (vectors of norm less than 4), and therefore has a centre density of 1. By multiplying this value by the volume of a unit ball in 24 dimensions, formula_1, one can derive its absolute density.
 showed that the Leech lattice is isometric to the set of simple roots (or the Dynkin diagram) of the reflection group of the 26-dimensional even Lorentzian unimodular lattice II25,1. By comparison, the Dynkin diagrams of II9,1 and II17,1 are finite.
Applications.
The binary Golay code, independently developed in 1949, is an application in coding theory. More specifically, it is an error-correcting code capable of correcting up to three errors in each 24-bit word, and detecting a fourth. It was used to communicate with the Voyager probes, as it is much more compact than the previously-used Hadamard code.
Quantizers, or analog-to-digital converters, can use lattices to minimise the average root-mean-square error. Most quantizers are based on the one-dimensional integer lattice, but using multi-dimensional lattices reduces the RMS error. The Leech lattice is a good solution to this problem, as the Voronoi cells have a low second moment.
The vertex algebra of the two-dimensional conformal field theory describing bosonic string theory, compactified on the 24-dimensional quotient torus R24/Λ24 and orbifolded by a two-element reflection group, provides an explicit construction of the Griess algebra that has the monster group as its automorphism group. This monster vertex algebra was also used to prove the monstrous moonshine conjectures.
Constructions.
The Leech lattice can be constructed in a variety of ways. As with all lattices, it can be constructed by taking the integral span of the columns of its generator matrix, a 24×24 matrix with determinant 1.
Using the binary Golay code.
The Leech lattice can be explicitly constructed as the set of vectors of the form 2−3/2("a"1, "a"2, ..., "a"24) where the "a""i" are integers such that
and for each fixed residue class modulo 4, the 24 bit word, whose 1s correspond to the coordinates "i" such that "a""i" belongs to this residue class, is a word in the binary Golay code. The Golay code, together with the related Witt design, features in a construction for the 196560 minimal vectors in the Leech lattice.
Using the Lorentzian lattice II25,1.
The Leech lattice can also be constructed as formula_3 where "w" is the Weyl vector:
in the 26-dimensional even Lorentzian unimodular lattice II25,1. The existence of such an integral vector of Lorentzian norm zero relies on the fact that 12 + 22 + ... + 242 is a perfect square (in fact 702); the number 24 is the only integer bigger than 1 with this property. This was conjectured by Édouard Lucas, but the proof came much later, based on elliptic functions.
The vector
formula_5
in this construction is really the Weyl vector of the even sublattice "D"24 of the odd unimodular lattice "I"25. More generally, if "L" is any positive definite unimodular lattice of dimension 25 with at least 4 vectors of norm 1, then the Weyl vector of its norm 2 roots has integral length, and there is a similar construction of the Leech lattice using "L" and this Weyl vector.
Based on other lattices.
 described another 23 constructions for the Leech lattice, each based on a Niemeier lattice. It can also be constructed by using three copies of the E8 lattice, in the same way that the binary Golay code can be constructed using three copies of the extended Hamming code, H8. This construction is known as the Turyn construction of the Leech lattice.
As a laminated lattice.
Starting with a single point, Λ0, one can stack copies of the lattice Λn to form an ("n" + 1)-dimensional lattice, Λ"n"+1, without reducing the minimal distance between points. Λ1 corresponds to the integer lattice, Λ2 is to the hexagonal lattice, and Λ3 is the face-centered cubic packing. showed that the Leech lattice is the unique laminated lattice in 24 dimensions.
As a complex lattice.
The Leech lattice is also a 12-dimensional lattice over the Eisenstein integers. This is known as the complex Leech lattice, and is isomorphic to the 24-dimensional real Leech lattice. In the complex construction of the Leech lattice, the binary Golay code is replaced with the ternary Golay code, and the Mathieu group "M"24 is replaced with the Mathieu group "M"12. The "E"6 lattice, "E"8 lattice and Coxeter–Todd lattice also have constructions as complex lattices, over either the Eisenstein or Gaussian integers.
Using the icosian ring.
The Leech lattice can also be constructed using the ring of icosians. The icosian ring is abstractly isomorphic to the E8 lattice, three copies of which can be used to construct the Leech lattice using the Turyn construction.
Witt's construction.
In 1972 Witt gave the following construction, which he said he found in 1940, on January 28. Suppose that "H" is an "n" by "n" Hadamard matrix, where "n"=4"ab". Then the matrix formula_6 defines a bilinear form in 2"n" dimensions, whose kernel has "n" dimensions. The quotient by this kernel is a nonsinguar bilinear form taking values in (1/2)Z. It has 3 sublattices of index 2 that are integral bilinear forms. Witt obtained the Leech lattice as one of these three sublattices by taking "a"=2, "b"=3, and taking "H" to be the 24 by 24 matrix (indexed by Z/23Z ∪ ∞) with entries Χ("m"+"n") where Χ(∞)=1, Χ(0)=−1, Χ("n")=is the quadratic residue symbol mod 23 for nonzero "n". This matrix "H" is a Paley matrix with some insignificant sign changes.
Using a Paley matrix.
 described a construction using a
skew Hadamard matrix of Paley type.
The Niemeier lattice with root system formula_7 can be made into a module
for the ring of integers of the field formula_8. Multiplying this
Niemeier lattice by a non-principal ideal of the ring of integers gives the Leech lattice.
Using octonions.
If "L" is the set of octonions with coordinates on the formula_9 lattice, then the Leech lattice is the set of triplets formula_10 such that
where formula_14. This construction is due to .
Symmetries.
The Leech lattice is highly symmetrical. Its automorphism group is the Conway group Co0, which is of order 8 315 553 613 086 720 000. The center of Co0 has two elements, and the quotient of Co0 by this center is the Conway group Co1, a finite simple group. Many other sporadic groups, such as the remaining Conway groups and Mathieu groups, can be constructed as the stabilizers of various configurations of vectors in the Leech lattice.
Despite having such a high "rotational" symmetry group, the Leech lattice does not possess any hyperplanes of reflection symmetry. In other words, the Leech lattice is chiral. It also has far fewer symmetries than the 24-dimensional hypercube and simplex.
The automorphism group was first described by John Conway. The 398034000 vectors of norm 8 fall into 8292375 'crosses' of 48 vectors. Each cross contains 24 mutually orthogonal vectors and their negatives, and thus describe the vertices of a 24-dimensional orthoplex. Each of these crosses can be taken to be the coordinate system of the lattice, and has the same symmetry of the Golay code, namely 212 × |M24|. Hence the full automorphism group of the Leech lattice has order 8292375 × 4096 × 244823040, or 8 315 553 613 086 720 000.
Geometry.
 showed that the covering radius of the Leech lattice is formula_15; in other words, if we put a closed ball of this radius around each lattice point, then these just cover Euclidean space. The points at distance at least formula_15 from all lattice points are called the deep holes of the Leech lattice. There are 23 orbits of them under the automorphism group of the Leech lattice, and these orbits correspond to the 23 Niemeier lattices other than the Leech lattice: the set of vertices of deep hole is isometric to the affine Dynkin diagram of the corresponding Niemeier lattice.
The Leech lattice has a density of formula_17. showed that it gives the densest lattice packing of balls in 24-dimensional space. improved this by showing that it is the densest sphere packing, even among non-lattice packings.
The 196560 minimal vectors are of three different varieties, known as "shapes":
The ternary Golay code, binary Golay code and Leech lattice give very efficient 24-dimensional spherical codes of 729, 4096 and 196560 points, respectively. Spherical codes are higher-dimensional analogues of Tammes problem, which arose as an attempt to explain the distribution of pores on pollen grains. These are distributed as to maximise the minimal angle between them. In two dimensions, the problem is trivial, but in three dimensions and higher it is not. An example of a spherical code in three dimensions is the set of the 12 vertices of the regular icosahedron.
Theta series.
One can associate to any (positive-definite) lattice Λ a theta function given by
The theta function of a lattice is then a holomorphic function on the upper half-plane. Furthermore, the theta function of an even unimodular lattice of rank "n" is actually a modular form of weight "n"/2 for the full modular group "PSL"(2,Z). The theta function of an integral lattice is often written as a power series in formula_22 so that the coefficient of "q""n" gives the number of lattice vectors of squared norm 2"n". In the Leech lattice, there are 196560 vectors of squared norm 4, 16773120 vectors of squared norm 6, 398034000 vectors of squared norm 8 and so on. The theta series of the Leech lattice is
where formula_24 is the normalized Eisenstein series of weight 12, formula_25 is the modular discriminant, formula_26 is the divisor function for exponent 11, and formula_27 is the Ramanujan tau function. It follows that for "m"≥1 the number of vectors of squared norm 2"m" is
History.
Many of the cross-sections of the Leech lattice, including the Coxeter–Todd lattice and Barnes–Wall lattice, in 12 and 16 dimensions, were found much earlier than the Leech lattice. discovered a related odd unimodular lattice in 24 dimensions, now called the odd Leech lattice, one of whose two even neighbors is the Leech lattice. The Leech lattice was discovered in 1965 by , by improving some earlier sphere packings he found .
 calculated the order of the automorphism group of the Leech lattice, and, working with John G. Thompson, discovered three new sporadic groups as a by-product: the Conway groups, Co1, Co2, Co3. They also showed that four other (then) recently announced sporadic groups, namely, Higman-Sims, Suzuki, McLaughlin, and the Janko group J2 could be found inside the Conway groups using the geometry of the Leech lattice. (Ronan, p. 155)
, has a single rather cryptic sentence mentioning that he found more than 10 even unimodular lattices in 24 dimensions without giving further details. stated that he found 9 of these lattices earlier in 1938, and found two more, the Niemeier lattice with A root system and the Leech lattice (and also the odd Leech lattice), in 1940.


Nil ideal

In mathematics, more specifically ring theory, a left, right or two-sided ideal of a ring is said to be a nil ideal if each of its elements is nilpotent.
The nilradical of a commutative ring is an example of a nil ideal; in fact, it is the ideal of the ring maximal with respect to the property of being nil. Unfortunately the set of nil elements does not always form an ideal for noncommutative rings. Nil ideals are still associated with interesting open questions, especially the unsolved Köthe conjecture.
Commutative rings.
In commutative rings, the nil ideals are better understood than in noncommutative rings, primarily because in commutative rings, products involving nilpotent elements and sums of nilpotent elements are both nilpotent. This is because if "a" and "b" are nilpotent elements of "R" with "a"n=0 and "b"m=0, and r is any element of R, then ("a·r")n = "a"n·r"n = 0, and by the binomial theorem, ("a"+"b")m+n=0. Therefore, the set of all nilpotent elements forms an ideal known as the nilradical of a ring. Because the nilradical contains every nilpotent element, an ideal of a commutative ring is nil if and only if it is a subset of the nilradical, and so the nilradical is maximal among nil ideals. Furthermore, for any nilpotent element "a" of a commutative ring "R", the ideal "aR" is nil. For a noncommutative ring however, it is not in general true that the set of nilpotent elements forms an ideal, or that "a·"R" is a nil (one-sided) ideal, even if "a" is nilpotent.
Noncommutative rings.
The theory of nil ideals is of major importance in noncommutative ring theory. In particular, through the understanding of nil rings—rings whose every element is nilpotent—one may obtain a much better understanding of more general rings.
In the case of commutative rings, there is always a maximal nil ideal: the nilradical of the ring. The existence of such a maximal nil ideal in the case of noncommutative rings is guaranteed by the fact that the sum of nil ideals is again nil. However, the truth of the assertion that the sum of two left nil ideals is again a left nil ideal remains elusive; it is an open problem known as the Köthe conjecture. The Köthe conjecture was first posed in 1930 and yet remains unresolved as of 2010.
Relation to nilpotent ideals.
The notion of a nil ideal has a deep connection with that of a nilpotent ideal, and in some classes of rings, the two notions coincide. If an ideal is nilpotent, it is of course nil. There are two main barriers for nil ideals to be nilpotent:
Clearly both of these barriers must be avoided for a nil ideal to qualify as nilpotent.
In a right artinian ring, any nil ideal is nilpotent. This is proven by observing that any nil ideal is contained in the Jacobson radical of the ring, and since the Jacobson radical is a nilpotent ideal (due to the artinian hypothesis), the result follows. In fact, this has been generalized to right noetherian rings; the result is known as Levitzky's theorem. A particularly simple proof due to Utumi can be found in .


John Stillwell

John Colin Stillwell (born 1942) is an Australian mathematician on the faculties of the University of San Francisco and Monash University.
Biography.
He was born in Melbourne, Australia and lived there until he went to the Massachusetts Institute of Technology for his doctorate. He received his PhD from MIT in 1970, working under Hartley Rogers, Jr who had himself worked under Alonzo Church. From 1970 until 2001 he taught at Monash University back in Australia and in 2002 began teaching in San Francisco.
Honors.
In 2005, Stillwell was the recipient of the Mathematical Association of America's prestigious Chauvenet Prize for his article “The Story of the 120-Cell,” Notices of the AMS, January 2001, pp. 17–24. In 2012 he became a fellow of the American Mathematical Society.
Works.
Books.
Stillwell is the author of many textbooks and other books on mathematics including:


Graph energy

In mathematics, the energy of a graph is the sum of the absolute values of the eigenvalues of the adjacency matrix of the graph. This quantity is studied in the context of spectral graph theory.
More precisely, let "G" be a graph with "n" vertices. It is assumed that "G" is simple, that is, it does not contain loops or parallel edges. Let "A" be the adjacency matrix of "G" and let formula_1, formula_2, be the eigenvalues of "A". Then the energy of the graph is defined as:


Numerical certification

Numerical certification is the process of verifying the correctness of a candidate solution to a system of equations. In (numerical) computational mathematics, such as numerical algebraic geometry, candidate solutions are computed algorithmically, but there is the possibility that errors have corrupted the candidates. For instance, in addition to the inexactness of input data and candidate solutions, numerical errors or errors in the discretization of the problem may result in corrupted candidate solutions. The goal of numerical certification is to provide a certificate which proves which of these candidates are, indeed, approximate solutions.
Methods for certification can be divided into two flavors: "a priori" certification and "a posteriori" certification. "A posteriori" certification confirms the correctness of the final answers (regardless of how they are generated), while "a priori" certification confirms the correctness of each step of a specific computation. A typical example of "a posteriori" certification is Smale's alpha theory, while a typical example of "a priori" certification is interval arithmetic.
Certificates.
A certificate for a root is a computational proof of the correctness of a candidate solution. For instance, a certificate may consist of an approximate solution formula_1, a region formula_2 containing formula_1, and a proof that formula_2 contains exactly one solution to the system of equations.
In this context, an "a priori" numerical certificate is a certificate in the sense of correctness in computer science. On the other hand, an "a posteriori" numerical certificate operates only on solutions, regardless of how they are computed. Hence, "a posteriori" certification is different from algorithmic correctness – for an extreme example, an algorithm could randomly generate candidates and attempt to certify them as approximate roots using "a posteriori" certification.
"A posteriori" certification methods.
There are a variety of methods for "a posteriori" certification, including
Alpha theory.
The cornerstone of Smale's alpha theory is bounding the error for Newton's method. Smale's 1986 work introduced the quantity formula_5, which quantifies the convergence of Newton's method. More precisely, let formula_6 be a system of analytic functions in the variables formula_1, formula_8 the derivative operator, and formula_9 the Newton operator. The quantities
formula_10
formula_11
and
formula_12
are used to certify a candidate solution. In particular, if
formula_13
then formula_1 is an approximate solution for formula_15, i.e., the candidate is in the domain of quadratic convergence for Newton's method. In other words, if this inequality holds, then there is a root formula_16 of formula_6 so that iterates of the Newton operator converge as
formula_18
The software package alphaCertified provides an implementation of the alpha test for polynomials by estimating formula_19 and formula_20.
Interval Newton and Krawczyck methods.
Suppose formula_21 is a function whose fixed points correspond to the roots of formula_6. For example, the Newton operator has this property. Suppose that formula_23 is a region, then,
There are versions of the following methods over the complex numbers, but both the interval arithmetic and conditions must be adjusted to reflect this case.
Interval Newton method.
In the univariate case, Newton's method can be directly generalized to certify a root over an interval. For an interval formula_34, let formula_35 be the midpoint of formula_34. Then, the interval Newton operator applied to formula_34 is
In practice, any interval containing formula_39 can be used in this computation. If formula_1 is a root of formula_6, then by the mean value theorem, there is some formula_42 such that formula_43. In other words, formula_44. Since formula_39 contains the inverse of formula_6 at all points of formula_34, it follows that formula_48. Therefore, formula_49.
Furthermore, if formula_50, then either formula_35 is a root of formula_6 and formula_53 or formula_54. Therefore, formula_55 is at most half the width of formula_34. Therefore, if there is some root of formula_6 in formula_34, the iterative procedure of replacing formula_34 by formula_60 will converge to this root. If, on the other hand, there is no root of formula_6 in formula_34, this iterative procedure will eventually produce an empty interval, a witness to the nonexistence of roots.
See interval Newton method for higher dimensional analogues of this approach.
Krawczyck method.
Let formula_63 be any formula_64 invertible matrix in formula_65. Typically, one takes formula_63 to be an approximation to formula_67. Then, define the function formula_68 We observe that formula_1 is a fixed of formula_24 if and only if formula_1 is a root of formula_6. Therefore the approach above can be used to identify roots of formula_6. This approach is similar to a multivariate version of Newton's method, replacing the derivative with the fixed matrix formula_63.
We observe that if formula_34 is a compact and convex region and formula_76, then, for any formula_77, there exist formula_78 such that
Let formula_80 be the Jacobian matrix of formula_24 evaluated on formula_34. In other words, the entry formula_83 consists of the image of formula_84 over formula_34. It then follows that formula_86
where the matrix-vector product is computed using interval arithmetic. Then, allowing formula_1 to vary in formula_34, it follows that the image of formula_24 on formula_34 satisfies the following containment: formula_91
where the calculations are, once again, computed using interval arithmetic. Combining this with the formula for formula_24, the result is the Krawczyck operator
where formula_23 is the identity matrix.
If formula_95, then formula_24 has a fixed point in formula_34, i.e., formula_6 has a root in formula_34. On the other hand, if the maximum matrix norm using the supremum norm for vectors of all matrices in formula_100 is less than formula_101, then formula_24 is contractive within formula_34, so formula_24 has a unique fixed point.
A simpler test, when formula_34 is an axis-aligned parallelepiped, uses formula_106, i.e., the midpoint of formula_34. In this case, there is a unique root of formula_6 if
where formula_110 is the length of the longest side of formula_34.
"A priori" certification methods.
Interval arithmetic.
Interval arithmetic can be used to provide an "a priori" numerical certificate by computing intervals containing unique solutions. By using intervals instead of plain numeric types during path tracking, resulting candidates are represented by intervals. The candidate solution-interval is itself the certificate, in the sense that the solution is guaranteed to be inside the interval.
Condition numbers.
Numerical algebraic geometry solves polynomial systems using homotopy continuation and path tracking methods. By monitoring the condition number for a tracked homotopy at every step, and ensuring that no two solution paths ever intersect, one can compute a numerical certificate along with a solution. This scheme is called "a priori" path tracking.
Non-certified numerical path tracking relies on heuristic methods for controlling time step size and precision. In contrast, "a priori" certified path tracking goes beyond heuristics to provide step size control that "guarantees" that for every step along the path, the current point is within the domain of quadratic convergence for the current path.


Orthostochastic matrix

In mathematics, an orthostochastic matrix is a doubly stochastic matrix whose entries are the squares of
the absolute values of the entries of some orthogonal matrix.
The detailed definition is as follows. A square matrix "B" of size "n" is doubly stochastic (or "bistochastic") if all its rows and columns sum to 1 and all its entries are nonnegative real numbers. It is orthostochastic if there exists an orthogonal matrix "O" such that
All 2-by-2 doubly stochastic matrices are orthostochastic (and also unistochastic)
since for any
we find the corresponding orthogonal matrix
with
formula_4 such that
formula_5
For larger "n" the sets of bistochastic matrices includes the set of unistochastic matrices,
which includes the set of orthostochastic matrices and these inclusion relations are proper.


F-crystal

In algebraic geometry, F-crystals are objects introduced by that capture some of the structure of crystalline cohomology groups. The letter "F" stands for Frobenius, indicating that "F"-crystals have an action of Frobenius on them. F-isocrystals are crystals "up to isogeny".
F-crystals and F-isocrystals over perfect fields.
Suppose that "k" is a perfect field, with ring of Witt vectors "W" and let "K" be the quotient field of "W", with Frobenius automorphism σ.
Over the field "k", an "F"-crystal is a free module "M" of finite rank over the ring "W" of Witt vectors of "k", together with a σ-linear injective endomorphism of "M". An "F"-isocrystal is defined in the same way, except that "M" is a module for the quotient field "K" of "W" rather than "W".
Dieudonné–Manin classification theorem.
The Dieudonné–Manin classification theorem was proved by and . It describes the structure of "F"-isocrystals over an algebraically closed field "k". The category of such "F"-isocrystals is abelian and semisimple, so every "F"-isocrystal is a direct sum of simple "F"-isocrystals. The simple "F"-isocrystals are the modules "E""s"/"r" where "r" and "s" are coprime integers with "r">0. The "F"-isocrystal "E""s"/"r" has a basis over "K" of the form "v", "Fv", "F"2"v"...,"F""r"−1"v" for some element "v", and "F""r""v" = "p""s""v". The rational number "s"/"r" is called the slope of the "F"-isocrystal.
Over a non-algebraically closed field "k" the simple "F"-isocrystals are harder to describe explicitly, but an "F"-isocrystal can still be written as a direct sum of subcrystals that are isoclinic, where an "F"-crystal is called isoclinic if over the algebraic closure of "k" it is a sum of "F"-isocrystals of the same slope.
The Newton polygon of an "F"-isocrystal.
The Newton polygon of an "F"-isocrystal encodes the dimensions of the pieces of given slope. If the "F"-isocrystal is a sum of isoclinic pieces with slopes "s"1 < "s"2 < ... and dimensions (as Witt ring modules) "d"1, "d"2... then the Newton polygon has vertices (0,0), ("x"1, "y"1), ("x"2, "y"2)... where the "n"th line segment joining the vertices has slope "s""n" = ("y""n"−"y""n"−1)/("x""n"−"x""n"−1) and projection onto the "x"-axis of length "d""n" = "x""n" − "x""n"−1.
The Hodge polygon of an "F"-crystal.
The Hodge polygon of an "F"-crystal "M" encodes the structure of "M"/"FM" considered as a module over the Witt ring. More precisely since the Witt ring is a principal ideal domain, the module "M"/"FM" can be written as a direct sum of indecomposable modules of lengths "n"1 ≤ "n"2 ≤ ... and the Hodge polygon then has vertices (0,0), (1,"n"1), (2,"n"1+ "n"2), ...
While the Newton polygon of an "F"-crystal depends only on the corresponding isocrystal, it is possible for two "F"-crystals corresponding to the same "F"-isocrystal to have different Hodge polygons. The Hodge polygon has edges with integer slopes, while the Newton polygon has edges with rational slopes.
Isocrystals over more general schemes.
Suppose that "A" is a complete discrete valuation ring of characteristic 0 with quotient field "k" of characteristic "p">0 and perfect. An affine enlargement of a scheme "X"0 over "k" consists of a torsion-free "A"-algebra "B" and an ideal "I" of "B" such that "B" is complete in the "I" topology and the image of "I" is nilpotent in "B"/"pB", together with a morphism from Spec("B"/"I") to "X"0.
A convergent isocrystal over a "k"-scheme "X"0 consists of a module over "B"⊗Q for every affine enlargement "B" that is compatible with maps between affine enlargements .
An F-isocrystal (short for Frobenius isocrystal) is an isocrystal together with an isomorphism to its pullback under a Frobenius morphism.


Variable shadowing

In computer programming, variable shadowing occurs when a variable declared within a certain scope (decision block, method, or inner class) has the same name as a variable declared in an outer scope. At the level of identifiers (names, rather than variables), this is known as name masking. This outer variable is said to be shadowed by the inner variable, while the inner identifier is said to "mask" the outer identifier. This can lead to confusion, as it may be unclear which variable subsequent uses of the shadowed variable name refer to, which depends on the name resolution rules of the language.
One of the first languages to introduce variable shadowing was ALGOL, which first introduced blocks to establish scopes. It was also permitted by many of the derivative programming languages including C, C++ and Java.
The C# language breaks this tradition, allowing variable shadowing between an inner and an outer class, and between a method and its containing class, but not between an if-block and its containing method, or between case statements in a switch block.
Some languages allow variable shadowing in more cases than others. For example Kotlin allow an inner variable in a function to shadow a passed argument and a variable in inner block to shadow another in outer block, while Java does not allow these. Both languages allow a passed argument to a function/Method to shadow a Class Field.
Some languages disallow variable shadowing completely such as CoffeeScript.
Example.
Lua.
The following Lua code provides an example of variable shadowing, in multiple blocks.
v = 1 -- a global variable
do
 local v = v + 1 -- a new local that shadows global v
 print(v) -- prints 2
 do
 local v = v * 2 -- another local that shadows outer local v
 print(v) -- prints 4
 end
 print(v) -- prints 2
end
print(v) -- prints 1
Python.
The following Python code provides another example of variable shadowing:
x = 0
def outer():
 x = 1
 def inner():
 x = 2
 print("inner:", x)
 inner()
 print("outer:", x)
outer()
print("global:", x)
As there is no variable declaration but only variable assignment in Python, the keyword codice_1 introduced in Python 3 is used to avoid variable shadowing and assign to non-local variables:
x = 0
def outer():
 x = 1
 def inner():
 nonlocal x
 x = 2
 print("inner:", x)
 inner()
 print("outer:", x)
outer()
print("global:", x)
The keyword codice_2 is used to avoid variable shadowing and assign to global variables:
x = 0
def outer():
 x = 1
 def inner():
 global x
 x = 2
 print("inner:", x)
 inner()
 print("outer:", x)
outer()
print("global:", x)
Rust.
fn main() {
 let x = 0;
 {
 let x = 1;
 println!("Inner x: {}", x); // prints 1

 println!("Outer x: {}", x); // prints 0
 // Shadow
 let x = "Rust";
 println!("Outer x: {}", x); // prints 'Rust'
//# Inner x: 1
//# Outer x: 0
//# Outer x: Rust
C++.
int main()
 int x = 42;
 int sum = 0;
 for (int i = 0; i < 10; i++) {
 int x = i;
 std::cout « "x: " « x « '\n'; // prints values of i from 0 to 9
 sum += x;
 std::cout « "sum: " « sum « '\n';
 std::cout « "x: " « x « '\n'; // prints out 42
 return 0;
Java.
public class Shadow {
 private int myIntVar = 0;
 public void shadowTheVar() {
 // Since it has the same name as above object instance field, it shadows above
 // field inside this method.
 int myIntVar = 5;
 // If we simply refer to 'myIntVar' the one of this method is found
 // (shadowing a second one with the same name)
 System.out.println(myIntVar); // prints 5
 // If we want to refer to the shadowed myIntVar from this class we need to
 // refer to it like this:
 System.out.println(this.myIntVar); // prints 0
 public static void main(String[] args){
 new Shadow("red").shadowTheVar();
JavaScript.
ECMAScript 6 introduction of `let` and `const` with block scoping allow variable shadowing.
function myFunc() {
 let my_var = 'test';
 if (true) {
 let my_var = 'new test';
 console.log(my_var); // new test
 console.log(my_var); // test
myFunc();


Weighted projective space

In algebraic geometry, a weighted projective space P("a"0...,"a""n") is the projective variety Proj("k"["x"0...,"x""n"]) associated to the graded ring "k"["x"0...,"x""n"] where the variable "x""k" has degree "a""k".


Necklace ring

In mathematics, the necklace ring is a ring introduced by to elucidate the multiplicative properties of necklace polynomials.
Definition.
If "A" is a commutative ring then the necklace ring over "A" consists of all infinite sequences formula_1 of elements of "A". Addition in the necklace ring is given by pointwise addition of sequences. Multiplication is given by a sort of arithmetic convolution: the product of formula_1 and formula_3 has components
where formula_5 is the least common multiple of formula_6 and formula_7, and formula_8 is their greatest common divisor.
This ring structure is isomorphic to the multiplication of formal power series written in "necklace coordinates": that is, identifying an integer sequence formula_1 with the power series formula_10.


Smooth functor

In differential topology, a branch of mathematics, a smooth functor is a type of functor defined on finite-dimensional real vector spaces. Intuitively, a smooth functor is smooth in the sense that it sends smoothly parameterized families of vector spaces to smoothly parameterized families of vector spaces. Smooth functors may therefore be uniquely extended to functors defined on vector bundles.
Let Vect be the category of finite-dimensional real vector spaces whose morphisms consist of all linear mappings, and let "F" be a covariant functor that maps Vect to itself. For vector spaces "T", "U" ∈ Vect, the functor "F" induces a mapping
where Hom is notation for Hom functor. If this map is smooth as a map of infinitely differentiable manifolds then "F" is said to be a smooth functor.
Common smooth functors include, for some vector space "W":
Smooth functors are significant because any smooth functor can be applied fiberwise to a differentiable vector bundle on a manifold. Smoothness of the functor is the condition required to ensure that the patching data for the bundle are smooth as mappings of manifolds. For instance, because the "n"th exterior power of a vector space defines a smooth functor, the "n"th exterior power of a smooth vector bundle is also a smooth vector bundle.
Although there are established methods for proving smoothness of standard constructions on finite-dimensional vector bundles, smooth functors can be generalized to categories of topological vector spaces and vector bundles on infinite-dimensional Fréchet manifolds.


Closure with a twist

Closure with a twist is a property of subsets of an algebraic structure. A subset formula_1 of an algebraic structure formula_2 is said to exhibit closure with a twist if for every two elements
there exists an automorphism formula_4 of formula_2 and an element formula_6 such that
where "formula_8" is notation for an operation on formula_2 preserved by formula_4.
Two examples of algebraic structures which exhibit closure with a twist are the cwatset and the generalized cwatset, or GC-set.
Cwatset.
In mathematics, a cwatset is a set of bitstrings, all of the same length, which is closed with a twist.
If each string in a cwatset, "C", say, is of length "n", then "C" will be a subset of formula_11. Thus, two strings in "C" are added by adding the bits in the strings modulo 2 (that is, addition without carry, or exclusive disjunction). The symmetric group on "n" letters, formula_12, acts on formula_11 by bit permutation:
where formula_15 is an element of formula_11 and "p" is an element of formula_12. Closure "with a twist" now means that for each element "c" in "C", there exists some permutation formula_18 such that, when you add "c" to an arbitrary element "e" in the cwatset and then apply the permutation, the result will also be an element of "C". That is, denoting addition without carry by formula_19, "C" will be a cwatset if and only if
This condition can also be written as
Examples.
To demonstrate that "F" is a cwatset, observe that
To see that "F" is a cwatset using this notation, note that
where formula_28 and formula_29 denote permutations of the rows and columns of the matrix, respectively, expressed in cycle notation.
Note that for formula_35, formula_36.
Properties.
Let formula_38 be a cwatset.
analogous to Lagrange's Theorem in group theory. To wit,
"Theorem". If "C" is a cwatset of degree "n" and order "m", then "m" divides formula_39.
The divisibility condition is necessary but not sufficient. For example there does not exist a cwatset of degree 5 and order 15.
Generalized cwatset.
In mathematics, a generalized cwatset (GC-set) is an algebraic structure generalizing the notion of closure with a twist, the defining characteristic of the cwatset.
Definitions.
A subset "H" of a group "G" is a "GC-set" if for each formula_40, there exists a formula_41 such that formula_42.
Furthermore, a GC-set "H" ⊆ "G" is a "cyclic GC-set" if there exists an formula_40 and a formula_44 such that formula_45 where formula_46 and formula_47 for all formula_48.


QR algorithm

In numerical linear algebra, the QR algorithm or QR iteration is an eigenvalue algorithm: that is, a procedure to calculate the eigenvalues and eigenvectors of a matrix. The QR algorithm was developed in the late 1950s by John G. F. Francis and by Vera N. Kublanovskaya, working independently. The basic idea is to perform a QR decomposition, writing the matrix as a product of an orthogonal matrix and an upper triangular matrix, multiply the factors in the reverse order, and iterate.
The practical QR algorithm.
Formally, let "A" be a real matrix of which we want to compute the eigenvalues, and let "A"0:="A". At the "k"-th step (starting with "k" = 0), we compute the QR decomposition "A""k"="Q""k""R""k" where "Q""k" is an orthogonal matrix (i.e., "Q""T" = "Q"−1) and "R""k" is an upper triangular matrix. We then form "A""k"+1 = "R""k""Q""k". Note that
so all the "A""k" are similar and hence they have the same eigenvalues. The algorithm is numerically stable because it proceeds by "orthogonal" similarity transforms.
Under certain conditions, the matrices "A""k" converge to a triangular matrix, the Schur form of "A". The eigenvalues of a triangular matrix are listed on the diagonal, and the eigenvalue problem is solved. In testing for convergence it is impractical to require exact zeros, but the Gershgorin circle theorem provides a bound on the error.
In this crude form the iterations are relatively expensive. This can be mitigated by first bringing the matrix "A" to upper Hessenberg form (which costs formula_2 arithmetic operations using a technique based on Householder reduction), with a finite sequence of orthogonal similarity transforms, somewhat like a two-sided QR decomposition. (For QR decomposition, the Householder reflectors are multiplied only on the left, but for the Hessenberg case they are multiplied on both left and right.) Determining the QR decomposition of an upper Hessenberg matrix costs formula_3 arithmetic operations. Moreover, because the Hessenberg form is already nearly upper-triangular (it has just one nonzero entry below each diagonal), using it as a starting point reduces the number of steps required for convergence of the QR algorithm.
If the original matrix is symmetric, then the upper Hessenberg matrix is also symmetric and thus tridiagonal, and so are all the "A""k". This procedure costs formula_4 arithmetic operations using a technique based on Householder reduction. Determining the QR decomposition of a symmetric tridiagonal matrix costs formula_5 operations.
The rate of convergence depends on the separation between eigenvalues, so a practical algorithm will use shifts, either explicit or implicit, to increase separation and accelerate convergence. A typical symmetric QR algorithm isolates each eigenvalue (then reduces the size of the matrix) with only one or two iterations, making it efficient as well as robust.
The implicit QR algorithm.
In modern computational practice, the QR algorithm is performed in an implicit version which makes the use of multiple shifts easier to introduce. The matrix is first brought to upper Hessenberg form formula_6 as in the explicit version; then, at each step, the first column of formula_7 is transformed via a small-size Householder similarity transformation to the first column of formula_8 (or formula_9), where formula_8, of degree formula_11, is the polynomial that defines the shifting strategy (often formula_12, where formula_13 and formula_14 are the two eigenvalues of the trailing formula_15 principal submatrix of formula_7, the so-called "implicit double-shift"). Then successive Householder transformations of size formula_17 are performed in order to return the working matrix formula_7 to upper Hessenberg form. This operation is known as "bulge chasing", due to the peculiar shape of the non-zero entries of the matrix along the steps of the algorithm. As in the first version, deflation is performed as soon as one of the sub-diagonal entries of formula_7 is sufficiently small.
Renaming proposal.
Since in the modern implicit version of the procedure no QR decompositions are explicitly performed, some authors, for instance Watkins, suggested changing its name to "Francis algorithm". Golub and Van Loan use the term "Francis QR step".
Interpretation and convergence.
The QR algorithm can be seen as a more sophisticated variation of the basic "power" eigenvalue algorithm. Recall that the power algorithm repeatedly multiplies "A" times a single vector, normalizing after each iteration. The vector converges to an eigenvector of the largest eigenvalue. Instead, the QR algorithm works with a complete basis of vectors, using QR decomposition to renormalize (and orthogonalize). For a symmetric matrix "A", upon convergence, "AQ" = "QΛ", where "Λ" is the diagonal matrix of eigenvalues to which "A" converged, and where "Q" is a composite of all the orthogonal similarity transforms required to get there. Thus the columns of "Q" are the eigenvectors.
History.
The QR algorithm was preceded by the "LR algorithm", which uses the LU decomposition instead of the QR decomposition. The QR algorithm is more stable, so the LR algorithm is rarely used nowadays. However, it represents an important step in the development of the QR algorithm.
The LR algorithm was developed in the early 1950s by Heinz Rutishauser, who worked at that time as a research assistant of Eduard Stiefel at ETH Zurich. Stiefel suggested that Rutishauser use the sequence of moments "y"0T "A""k" "x"0, "k" = 0, 1, … (where "x"0 and "y"0 are arbitrary vectors) to find the eigenvalues of "A". Rutishauser took an algorithm of Alexander Aitken for this task and developed it into the "quotient–difference algorithm" or "qd algorithm". After arranging the computation in a suitable shape, he discovered that the qd algorithm is in fact the iteration "A""k" = "L""k""U""k" (LU decomposition), "A""k"+1 = "U""k""L""k", applied on a tridiagonal matrix, from which the LR algorithm follows.
Other variants.
One variant of the "QR algorithm", "the Golub-Kahan-Reinsch" algorithm starts with reducing a general matrix into a bidiagonal one. This variant of the "QR algorithm" for the computation of singular values was first described by . The LAPACK subroutine DBDSQR implements this iterative method, with some modifications to cover the case where the singular values are very small . Together with a first step using Householder reflections and, if appropriate, QR decomposition, this forms the DGESVD routine for the computation of the singular value decomposition. The QR algorithm can also be implemented in infinite dimensions with corresponding convergence results.


Direct product

In mathematics, one can often define a direct product of objects already known, giving a new one. This generalizes the Cartesian product of the underlying sets, together with a suitably defined structure on the product set. More abstractly, one talks about the product in category theory, which formalizes these notions.
Examples are the product of sets, groups (described below), rings, and other algebraic structures. The product of topological spaces is another instance.
There is also the direct sum – in some areas this is used interchangeably, while in others it is a different concept.
Examples.
In a similar manner, we can talk about the direct product of finitely many algebraic structures, e.g. formula_17. This relies on the fact that the direct product is associative up to isomorphism. That is, formula_18 for any algebraic structures formula_19, formula_20, and formula_21 of the same kind. The direct product is also commutative up to isomorphism, i.e. formula_22 for any algebraic structures formula_19 and formula_20 of the same kind. We can even talk about the direct product of infinitely many algebraic structures; for example we can take the direct product of countably many copies of formula_25, which we write as formula_26.
Group direct product.
In group theory one can define the direct product of two groups ("G", ∘) and ("H", ∙), denoted by "G" × "H". For abelian groups which are written additively, it may also be called the direct sum of two groups, denoted by formula_27.
It is defined as follows:
This construction gives a new group. It has a normal subgroup isomorphic to "G" (given by the elements of the form ("g", 1)), and one isomorphic to "H" (comprising the elements (1, "h")).
The reverse also holds, there is the following recognition theorem: If a group "K" contains two normal subgroups "G" and "H", such that "K"= "GH" and the intersection of "G" and "H" contains only the identity, then "K" is isomorphic to "G" × "H". A relaxation of these conditions, requiring only one subgroup to be normal, gives the semidirect product.
As an example, take as "G" and "H" two copies of the unique (up to isomorphisms) group of order 2, "C"2: say {1, "a"} and {1, "b"}. Then "C"2×"C"2 = {(1,1), (1,"b"), ("a",1), ("a","b")}, with the operation element by element. For instance, (1,"b")*("a",1) = (1*"a", "b"*1) = ("a","b"), and (1,"b")*(1,"b") = (1,"b"2) = (1,1).
With a direct product, we get some natural group homomorphisms for free: the projection maps define by
called the coordinate functions.
Also, every homomorphism "f" to the direct product is totally determined by its component functions
formula_29.
For any group ("G", ∘) and any integer "n" ≥ 0, repeated application of the direct product gives the group of all "n"-tuples "G""n" (for "n" = 0 we get the trivial group), for example Z"n" and R"n".
Direct product of modules.
The direct product for modules (not to be confused with the tensor product) is very similar to the one defined for groups above, using the Cartesian product with the operation of addition being componentwise, and the scalar multiplication just distributing over all the components. Starting from R we get Euclidean space R"n", the prototypical example of a real "n"-dimensional vector space. The direct product of R"m" and R"n" is R"m"+"n".
Note that a direct product for a finite index formula_30 is identical to the direct sum formula_31. The direct sum and direct product differ only for infinite indices, where the elements of a direct sum are zero for all but for a finite number of entries. They are dual in the sense of category theory: the direct sum is the coproduct, while the direct product is the product.
For example, consider formula_32 and formula_33, the infinite direct product and direct sum of the real numbers. Only sequences with a finite number of non-zero elements are in "Y". For example, (1,0,0,0...) is in "Y" but (1,1,1,1...) is not. Both of these sequences are in the direct product "X"; in fact, "Y" is a proper subset of "X" (that is, "Y" ⊂ "X").
Topological space direct product.
The direct product for a collection of topological spaces "Xi" for "i" in "I", some index set, once again makes use of the Cartesian product
Defining the topology is a little tricky. For finitely many factors, this is the obvious and natural thing to do: simply take as a basis of open sets to be the collection of all Cartesian products of open subsets from each factor:
This topology is called the product topology. For example, directly defining the product topology on R2 by the open sets of R (disjoint unions of open intervals), the basis for this topology would consist of all disjoint unions of open rectangles in the plane (as it turns out, it coincides with the usual metric topology).
The product topology for infinite products has a twist, and this has to do with being able to make all the projection maps continuous and to make all functions into the product continuous if and only if all its component functions are continuous (i.e. to satisfy the categorical definition of product: the morphisms here are continuous functions): we take as a basis of open sets to be the collection of all Cartesian products of open subsets from each factor, as before, with the proviso that all but finitely many of the open subsets are the entire factor:
The more natural-sounding topology would be, in this case, to take products of infinitely many open subsets as before, and this does yield a somewhat interesting topology, the box topology. However it is not too difficult to find an example of bunch of continuous component functions whose product function is not continuous (see the separate entry box topology for an example and more). The problem which makes the twist necessary is ultimately rooted in the fact that the intersection of open sets is only guaranteed to be open for finitely many sets in the definition of topology.
Products (with the product topology) are nice with respect to preserving properties of their factors; for example, the product of Hausdorff spaces is Hausdorff; the product of connected spaces is connected, and the product of compact spaces is compact. That last one, called Tychonoff's theorem, is yet another equivalence to the axiom of choice.
For more properties and equivalent formulations, see the separate entry product topology.
Direct product of binary relations.
On the Cartesian product of two sets with binary relations R and S, define ("a", "b")T("c", "d") as "a"R"c" and "b"S"d". If R and S are both reflexive, irreflexive, transitive, symmetric, or antisymmetric, then T will be also. Similarly, seriality of "T" is inherited from "R" and "S". Combining properties it follows that this also applies for being a preorder and being an equivalence relation. However if R and S are connected relations, T need not be connected; for example, the direct product of ≤ on ℕ with itself does not relate (1,2) and (2,1).
Direct product in universal algebra.
If Σ is a fixed signature, "I" is an arbitrary (possibly infinite) index set, and (A"i")"i"∈"I" is an indexed family of Σ algebras, the direct product A = ∏"i"∈"I" A"i" is a Σ algebra defined as follows:
For each , the "i"th projection is defined by . It is a surjective homomorphism between the Σ algebras A and A"i".
As a special case, if the index set the direct product of two Σ algebras A1 and A2 is obtained, written as . If Σ just contains one binary operation "f", the above definition of the direct product of groups is obtained, using the notation , , , , and . Similarly, the definition of the direct product of modules is subsumed here.
Categorical product.
The direct product can be abstracted to an arbitrary category. In a general category, given a collection of objects "Ai" "and" a collection of morphisms "pi" from "A" to "Ai" with "i" ranging in some index set "I", an object "A" is said to be a categorical product in the category if, for any object "B" and any collection of morphisms "fi" from "B" to "Ai", there exists a unique morphism "f" from "B" to "A" such that "fi = pi f" and this object "A" is unique. This not only works for two factors, but arbitrarily (even infinitely) many.
For groups we similarly define the direct product of a more general, arbitrary collection of groups "Gi" for "i" in "I", "I" an index set. Denoting the Cartesian product of the groups by "G" we define multiplication on "G" with the operation of componentwise multiplication; and corresponding to the "pi" in the definition above are the projection maps
the functions that take formula_38 to its "i"th component "gi".
Internal and external direct product.
Some authors draw a distinction between an internal direct product and an external direct product. If formula_39 and formula_40, then we say that "X" is an "internal" direct product of "A" and "B", while if "A" and "B" are not subobjects then we say that this is an "external" direct product.


Polynomial interpolation

In numerical analysis, polynomial interpolation is the interpolation of a given data set by the polynomial of lowest possible degree that passes through the points of the dataset.
Applications.
Polynomials can be used to approximate complicated curves, for example, the shapes of letters in typography, given a few points. A relevant application is the evaluation of the natural logarithm and trigonometric functions: pick a few known data points, create a lookup table, and interpolate between those data points. This results in significantly faster computations. Polynomial interpolation also forms the basis for algorithms in numerical quadrature and numerical ordinary differential equations and Secure Multi Party Computation, Secret Sharing schemes.
Polynomial interpolation is also essential to perform sub-quadratic multiplication and squaring such as Karatsuba multiplication and Toom–Cook multiplication, where an interpolation through points on a polynomial which defines the product yields the product itself. For example, given "a" = "f"("x") = "a"0"x"0 + "a"1"x"1 + ... and "b" = "g"("x") = "b"0"x"0 + "b"1"x"1 + ..., the product "ab" is equivalent to "W"("x") = "f"("x")"g"("x"). Finding points along "W"("x") by substituting "x" for small values in "f"("x") and "g"("x") yields points on the curve. Interpolation based on those points will yield the terms of "W"("x") and subsequently the product "ab". In the case of Karatsuba multiplication this technique is substantially faster than quadratic multiplication, even for modest-sized inputs. This is especially true when implemented in parallel hardware.
Definition.
Given a set of data points where no two are the same, a polynomial formula_1 is said to "interpolate" the data if formula_2 for each formula_3.
Interpolation theorem.
Given formula_4 distinct points formula_5 and corresponding values formula_6, there exists a unique polynomial of degree at most formula_7 that interpolates the data formula_8.
Proof.
Consider the Lagrange basis functions given by
Notice that formula_10 is a polynomial of degree formula_7. Furthermore, for each formula_12 we have formula_13, where formula_14 is the Kronecker delta. It follows that the linear combination
is an interpolating polynomial of degree formula_7.
To prove uniqueness, assume that there exists another interpolating polynomial formula_17 of degree at most formula_7. Since formula_19 for all formula_20, it follows that the polynomial formula_21 has formula_4 distinct zeros. However, formula_21 is of degree at most formula_7 and, by the fundamental theorem of algebra, can have at most formula_7 zeros; therefore, formula_26.
Corollary.
An interesting corollary to the interpolation theorem is that if formula_27 is a polynomial of degree at most formula_7, then the interpolating polynomial of formula_27 at formula_4 distinct points is formula_27 itself.
Unisolvence theorem.
Given a set of data points where no two are the same, one is looking for a polynomial of degree at most with the property
The unisolvence theorem states that such a polynomial "p" exists and is unique, and can be proved by the Vandermonde matrix, as described below.
The theorem states that for interpolation nodes , polynomial interpolation defines a linear bijection
where Π"n" is the vector space of polynomials (defined on any interval containing the nodes) of degree at most .
Constructing the interpolation polynomial.
Suppose that the interpolation polynomial is in the form
The statement that "p" interpolates the data points means that
If we substitute equation (1) in here, we get a system of linear equations in the coefficients . The system in matrix-vector form reads the following multiplication:
We have to solve this system for to construct the interpolant "p"("x"). The matrix on the left is commonly referred to as a Vandermonde matrix.
The condition number of the Vandermonde matrix may be large, causing large errors when computing the coefficients if the system of equations is solved using Gaussian elimination.
Several authors have therefore proposed algorithms which exploit the structure of the Vandermonde matrix to compute numerically stable solutions in O("n"2) operations instead of the O("n"3) required by Gaussian elimination. These methods rely on constructing first a Newton interpolation of the polynomial and then converting it to the monomial form above.
Alternatively, we may write down the polynomial immediately in terms of Lagrange polynomials:
For matrix arguments, this formula is called Sylvester's formula and the matrix-valued Lagrange polynomials are the Frobenius covariants.
Uniqueness of the interpolating polynomial.
Proof 1.
Suppose we interpolate through data points with an at-most degree polynomial "p"("x") (we need at least datapoints or else the polynomial cannot be fully solved for). Suppose also another polynomial exists also of degree at most that also interpolates the points; call it "q"("x").
Consider formula_38. We know,
But "r"("x") is a polynomial of degree . It has one root too many. Formally, if "r"("x") is any non-zero polynomial, it must be writable as formula_40, for some constant "A". By distributivity, the "x"'s multiply together to give leading term formula_41, i.e. one degree higher than the maximum we set. So the only way "r"("x") can exist is if , or equivalently, .
So "q"("x") (which could be any polynomial, so long as it interpolates the points) is identical with "p"("x"), and "q"("x") is unique.
Proof 2.
Given the Vandermonde matrix used above to construct the interpolant, we can set up the system
To prove that V is nonsingular we use the Vandermonde determinant formula:
since the points are distinct, the determinant can't be zero as formula_45 is never zero, therefore "V" is nonsingular and the system has a unique solution.
Either way this means that no matter what method we use to do our interpolation: direct, Lagrange etc., (assuming we can do all our calculations perfectly) we will always get the same polynomial.
Non-Vandermonde solutions.
We are trying to construct our unique interpolation polynomial in the vector space Π"n" of polynomials of degree . When using a monomial basis for Π"n" we have to solve the Vandermonde matrix to construct the coefficients for the interpolation polynomial. This can be a very costly operation (as counted in clock cycles of a computer trying to do the job). By choosing another basis for Π"n" we can simplify the calculation of the coefficients but then we have to do additional calculations when we want to express the interpolation polynomial in terms of a monomial basis.
One method is to write the interpolation polynomial in the Newton form and use the method of divided differences to construct the coefficients, e.g. Neville's algorithm. The cost is O("n"2) operations, while Gaussian elimination costs O("n"3) operations. Furthermore, you only need to do O("n") extra work if an extra point is added to the data set, while for the other methods, you have to redo the whole computation.
Another method is to use the Lagrange form of the interpolation polynomial. The resulting formula immediately shows that the interpolation polynomial exists under the conditions stated in the above theorem. Lagrange formula is to be preferred to Vandermonde formula when we are not interested in computing the coefficients of the polynomial, but in computing the value of "p"("x") in a given "x" not in the original data set. In this case, we can reduce complexity to O("n"2).
The Bernstein form was used in a constructive proof of the Weierstrass approximation theorem by Bernstein and has gained great importance in computer graphics in the form of Bézier curves.
Linear combination of the given values.
The Lagrange form of the interpolating polynomial is a linear combination of the given values. In many scenarios, an efficient and convenient polynomial interpolation is a linear combination of the given values, using previously known coefficients. Given a set of formula_46 data points formula_47 where each data point is a (position, value) pair and where no two positions formula_48 are the same, the interpolation polynomial in the Lagrange form is a linear combination
of the given values formula_50 with each coefficient formula_51 given by evaluating the corresponding Lagrange basis polynomial using the given formula_46 positions formula_48.
Each coefficient formula_51 in the linear combination depends on the given positions formula_48 and the desired position formula_57, but not on the given values formula_50. For each coefficient, inserting the values of the given positions formula_48 and simplifying yields an expression formula_51, which depends only on formula_57. Thus the same coefficient expressions formula_62 can be used in a polynomial interpolation of a given second set of formula_46 data points formula_64 at the same given positions formula_48, where the second given values formula_66 differ from the first given values formula_50. Using the same coefficient expressions formula_62 as for the first set of data points, the interpolation polynomial of the second set of data points is the linear combination
For each coefficient formula_51 in the linear combination, the expression resulting from the Lagrange basis polynomial formula_71 only depends on the relative spaces between the given positions, not on the individual value of any position. Thus the same coefficient expressions formula_62 can be used in a polynomial interpolation of a given third set of formula_46 data points
where each position formula_75 is related to the corresponding position formula_48 in the first set by formula_77 and the desired positions are related by formula_78, for a constant scaling factor "a" and a constant shift "b" for all positions. Using the same coefficient expressions formula_79 as for the first set of data points, the interpolation polynomial of the third set of data points is the linear combination
In many applications of polynomial interpolation, the given set of formula_46 data points is at equally spaced positions. In this case, it can be convenient to define the "x"-axis of the positions such that formula_82. For example, a given set of 3 equally-spaced data points formula_83 is then formula_84.
The interpolation polynomial in the Lagrange form is the linear combination
This quadratic interpolation is valid for any position "x", near or far from the given positions. So, given 3 equally-spaced data points at formula_86 defining a quadratic polynomial, at an example desired position formula_87, the interpolated value after simplification is given by formula_88
This is a quadratic interpolation typically used in the Multigrid method. Again given 3 equally-spaced data points at formula_86 defining a quadratic polynomial, at the next equally spaced position formula_90, the interpolated value after simplification is given by
In the above polynomial interpolations using a linear combination of the given values, the coefficients were determined using the Lagrange method. In some scenarios, the coefficients can be more easily determined using other methods. Examples follow.
According to the method of finite differences, for any polynomial of degree "d" or less, any sequence of formula_92 values at equally spaced positions has a formula_93th difference exactly equal to 0. The element "s""d+1" of the Binomial transform is such a formula_93th difference. This area is surveyed here. The binomial transform, "T", of a sequence of values {"v""n"}, is the sequence {"s""n"} defined by
Ignoring the sign term formula_96, the formula_4 coefficients of the element "s""n" are the respective formula_4 elements of the row "n" of Pascal's Triangle. The triangle of binomial transform coefficients is like Pascal's triangle. The entry in the "n"th row and "k"th column of the BTC triangle is formula_99 for any non-negative integer "n" and any integer "k" between 0 and "n". This results in the following example rows "n" = 0 through "n" = 7, top to bottom, for the BTC triangle:
For convenience, each row "n" of the above example BTC triangle also has a label formula_100. Thus for any polynomial of degree "d" or less, any sequence of formula_92 values at equally spaced positions has a linear combination result of 0, when using the formula_92 elements of row "d" as the corresponding linear coefficients.
For example, 4 equally spaced data points of a quadratic polynomial obey the linear equation given by row formula_103 of the BTC triangle. formula_104 This is the same linear equation as obtained above using the Lagrange method.
The BTC triangle can also be used to derive other polynomial interpolations. For example, the above quadratic interpolation
can be derived in 3 simple steps as follows. The equally spaced points of a quadratic polynomial obey the rows of the BTC triangle with formula_103 or higher. First, the row formula_107 spans the given and desired data points formula_108 with the linear equation
Second, the unwanted data point formula_110 is replaced by an expression in terms of wanted data points. The row formula_103 provides a linear equation with a term formula_112, which results in a term formula_113 by multiplying both sides of the linear equation by 4. formula_114 Third, the above two linear equations are added to yield a linear equation equivalent to the above quadratic interpolation for formula_115. formula_116
Similar to other uses of linear equations, the above derivation scales and adds vectors of coefficients. In polynomial interpolation as a linear combination of values, the elements of a vector correspond to a contiguous sequence of regularly spaced positions. The "p" non-zero elements of a vector are the "p" coefficients in a linear equation obeyed by any sequence of "p" data points from any degree "d" polynomial on any regularly spaced grid, where "d" is noted by the subscript of the vector. For any vector of coefficients, the subscript obeys formula_117. When adding vectors with various subscript values, the lowest subscript applies for the resulting vector. So, starting with the vector of row formula_107 and the vector of row formula_103 of the BTC triangle, the above quadratic interpolation for formula_115 is derived by the vector calculation
Similarly, the cubic interpolation typical in the Multigrid method,
can be derived by a vector calculation starting with the vector of row formula_123 and the vector of row formula_107 of the BTC triangle.
Interpolation error.
When interpolating a given function "f" by a polynomial of degree at the nodes "x"0...,"x""n" we get the error
where
is the notation for divided differences.
If "f" is times continuously differentiable on a closed interval "I" and formula_128 is a polynomial of degree at most that interpolates "f" at distinct points {"x""i"} ("i"=0,1...,n) in that interval, then for each x in the interval there exists in that interval such that
The above error bound suggests choosing the interpolation points such that the product formula_130 is as small as possible. The Chebyshev nodes achieve this.
Proof.
Set the error term as
and set up an auxiliary function:
where
Since are roots of formula_134 and formula_135, we have , which means has at least roots. From Rolle's theorem, formula_136 has at least roots, then formula_137 has at least one root , where is in the interval .
So we can get
Since formula_128 is a polynomial of degree at most , then
Thus
Since is the root of formula_137, so
Therefore,
Thus the remainder term in the Lagrange form of the Taylor theorem is a special case of interpolation error when all interpolation nodes are identical. Note that the error will be zero when formula_145 for any "i". Thus, the maximum error will occur at some point in the interval between two successive nodes.
For equally spaced intervals.
In the case of equally spaced interpolation nodes where formula_146, for formula_147 and where formula_148 the product term in the interpolation error formula can be bound as
Thus the error bound can be given as
However, this assumes that formula_151 is dominated by formula_152, i.e. formula_153. In several cases, this is not true and the error actually increases as (see Runge's phenomenon). That question is treated in the section "Convergence properties".
Lebesgue constants.
We fix the interpolation nodes "x"0, ..., "x""n" and an interval ["a", "b"] containing all the interpolation nodes. The process of interpolation maps the function "f" to a polynomial "p". This defines a mapping "X" from the space "C"(["a", "b"]) of all continuous functions on ["a", "b"] to itself. The map "X" is linear and it is a projection on the subspace Π"n" of polynomials of degree "n" or less.
The Lebesgue constant "L" is defined as the operator norm of "X". One has (a special case of Lebesgue's lemma):
In other words, the interpolation polynomial is at most a factor ("L" + 1) worse than the best possible approximation. This suggests that we look for a set of interpolation nodes that makes "L" small. In particular, we have for Chebyshev nodes:
We conclude again that Chebyshev nodes are a very good choice for polynomial interpolation, as the growth in "n" is exponential for equidistant nodes. However, those nodes are not optimal.
Convergence properties.
It is natural to ask, for which classes of functions and for which interpolation nodes the sequence of interpolating polynomials converges to the interpolated function as ? Convergence may be understood in different ways, e.g. pointwise, uniform or in some integral norm.
The situation is rather bad for equidistant nodes, in that uniform convergence is not even guaranteed for infinitely differentiable functions. One classical example, due to Carl Runge, is the function "f"("x") = 1 / (1 + "x"2) on the interval . The interpolation error grows without bound as . Another example is the function "f"("x") = |"x"| on the interval , for which the interpolating polynomials do not even converge pointwise except at the three points "x" = ±1, 0.
One might think that better convergence properties may be obtained by choosing different interpolation nodes. The following result seems to give a rather encouraging answer:
Proof. It's clear that the sequence of polynomials of best approximation formula_157 converges to "f"("x") uniformly (due to Weierstrass approximation theorem). Now we have only to show that each formula_157 may be obtained by means of interpolation on certain nodes. But this is true due to a special property of polynomials of best approximation known from the equioscillation theorem. Specifically, we know that such polynomials should intersect "f"("x") at least times. Choosing the points of intersection as interpolation nodes we obtain the interpolating polynomial coinciding with the best approximation polynomial.
The defect of this method, however, is that interpolation nodes should be calculated anew for each new function "f"("x"), but the algorithm is hard to be implemented numerically. Does there exist a single table of nodes for which the sequence of interpolating polynomials converge to any continuous function "f"("x")? The answer is unfortunately negative:
The proof essentially uses the lower bound estimation of the Lebesgue constant, which we defined above to be the operator norm of "X""n" (where "X""n" is the projection operator on Π"n"). Now we seek a table of nodes for which
Due to the Banach–Steinhaus theorem, this is only possible when norms of "X""n" are uniformly bounded, which cannot be true since we know that
For example, if equidistant points are chosen as interpolation nodes, the function from Runge's phenomenon demonstrates divergence of such interpolation. Note that this function is not only continuous but even infinitely differentiable on . For better Chebyshev nodes, however, such an example is much harder to find due to the following result:
Related concepts.
Runge's phenomenon shows that for high values of , the interpolation polynomial may oscillate wildly between the data points. This problem is commonly resolved by the use of spline interpolation. Here, the interpolant is not a polynomial but a spline: a chain of several polynomials of a lower degree.
Interpolation of periodic functions by harmonic functions is accomplished by Fourier transform. This can be seen as a form of polynomial interpolation with harmonic base functions, see trigonometric interpolation and trigonometric polynomial.
Hermite interpolation problems are those where not only the values of the polynomial "p" at the nodes are given, but also all derivatives up to a given order. This turns out to be equivalent to a system of simultaneous polynomial congruences, and may be solved by means of the Chinese remainder theorem for polynomials. Birkhoff interpolation is a further generalization where only derivatives of some orders are prescribed, not necessarily all orders from 0 to a "k".
Collocation methods for the solution of differential and integral equations are based on polynomial interpolation.
The technique of rational function modeling is a generalization that considers ratios of polynomial functions.
At last, multivariate interpolation for higher dimensions.


Doubly stochastic matrix

In mathematics, especially in probability and combinatorics, a doubly stochastic matrix
(also called bistochastic matrix), is a square matrix formula_1 of nonnegative real numbers, each of whose rows and columns sums to 1, i.e.,
Thus, a doubly stochastic matrix is both left stochastic and right stochastic.
Indeed, any matrix that is both left and right stochastic must be square: if every row sums to one then the sum of all entries in the matrix must be equal to the number of rows, and since the same holds for columns, the number of rows and columns must be equal.
Birkhoff polytope.
The class of formula_3 doubly stochastic matrices is a convex polytope known as the Birkhoff polytope formula_4. Using the matrix entries as Cartesian coordinates, it lies in an formula_5-dimensional affine subspace of formula_6-dimensional Euclidean space defined by formula_7 independent linear constraints specifying that the row and column sums all equal one. (There are formula_7 constraints rather than formula_9 because one of these constraints is dependent, as the sum of the row sums must equal the sum of the column sums.) Moreover, the entries are all constrained to be non-negative and less than or equal to one.
Birkhoff–von Neumann theorem.
The Birkhoff–von Neumann theorem states that the polytope formula_4 is the convex hull of the set of formula_3 permutation matrices, and furthermore that the vertices of formula_4 are precisely the permutation matrices. In other words, if formula_13 is a doubly stochastic matrix, then there exist formula_14 and permutation matrices formula_15 such that
This representation is known as the Birkhoff–von Neumann decomposition, and it may not be unique in general. By Carathéodory's theorem, however, there exists a decomposition with no more than formula_17 terms, i.e. with
In other words, while there exists a decomposition with formula_19 permutation matrices, there is at least one constructible decomposition with no more than formula_20 matrices. Such a decomposition can be found in polynomial time using the Birkhoff algorithm. This is often described as a real-valued generalization of Kőnig's theorem, where the correspondence is established through adjacency matrices of graphs.


Adjacency algebra

In algebraic graph theory, the adjacency algebra of a graph "G" is the algebra of polynomials in the adjacency matrix "A"("G") of the graph. It is an example of a matrix algebra and is the set of the linear combinations of powers of "A".
Some other similar mathematical objects are also called "adjacency algebra".
Properties.
Properties of the adjacency algebra of "G" are associated with various spectral, adjacency and connectivity properties of "G".
"Statement". The number of walks of length "d" between vertices "i" and "j" is equal to the ("i", "j")-th element of "Ad".
"Statement". The dimension of the adjacency algebra of a connected graph of diameter "d" is at least "d" + 1.
"Corollary". A connected graph of diameter "d" has at least "d" + 1 distinct eigenvalues.


Bateman polynomials

In mathematics, the Bateman polynomials are a family "F""n" of orthogonal polynomials introduced by . The Bateman–Pasternack polynomials are a generalization introduced by .
Bateman polynomials can be defined by the relation
where "P""n" is a Legendre polynomial. In terms of generalized hypergeometric functions, they are given by
 generalized the Bateman polynomials to polynomials "F" with
These generalized polynomials also have a representation in terms of generalized hypergeometric functions, namely
 showed that the polynomials "Q""n" studied by , see Touchard polynomials, are the same as Bateman polynomials up to a change of variable: more precisely
Bateman and Pasternack's polynomials are special cases of the symmetric continuous Hahn polynomials.
Examples.
The polynomials of small "n" read
Properties.
Orthogonality.
The Bateman polynomials satisfy the orthogonality relation
The factor formula_13 occurs on the right-hand side of this equation because the Bateman polynomials as defined here must be scaled by a factor formula_14 to make them remain real-valued for imaginary argument. The orthogonality relation is simpler when expressed in terms of a modified set of polynomials defined by formula_15, for which it becomes
Recurrence relation.
The sequence of Bateman polynomials satisfies the recurrence relation
Generating function.
The Bateman polynomials also have the generating function
which is sometimes used to define them.


Quaternionic discrete series representation

In mathematics, a quaternionic discrete series representation is a discrete series representation of a semisimple Lie group "G" associated with a quaternionic structure on the symmetric space of "G". They were introduced by .
Quaternionic discrete series representations exist when the maximal compact subgroup of the group "G" has a normal subgroup isomorphic to SU(2). Every complex simple Lie group has a real form with quaternionic discrete series representations. In particular the classical groups SU(2,"n"), SO(4,"n"), and Sp(1,"n") have quaternionic discrete series representations.
Quaternionic representations are analogous to holomorphic discrete series representations, which exist when the symmetric space of the group has a complex structure. The groups SU(2,"n") have both holomorphic and quaternionic discrete series representations.


Category with zero morphisms


Binomial ring

In mathematics, a binomial ring is a commutative ring whose additive group is torsion-free and contains all binomial coefficients
for "x" in the ring and "n" a positive integer. Binomial rings were introduced by .
 showed that binomial rings are essentially the same as λ-rings for which all Adams operations are the identity.


Exponential object

In mathematics, specifically in category theory, an exponential object or map object is the categorical generalization of a function space in set theory. Categories with all finite products and exponential objects are called cartesian closed categories. Categories (such as subcategories of Top) without adjoined products may still have an exponential law.
Definition.
Let formula_1 be a category, let formula_2 and formula_3 be objects of formula_1, and let formula_1 have all binary products with formula_3. An object formula_7 together with a morphism formula_8 is an "exponential object" if for any object formula_9 and morphism formula_10 there is a unique morphism formula_11 (called the "transpose" of formula_12) such that the following diagram commutes:
This assignment of a unique formula_13 to each formula_12 establishes an isomorphism of hom-sets, formula_15
If formula_7exists for all objects formula_17 in formula_1, then the functor formula_19 defined on objects by formula_20 and on arrows by formula_21, is a right adjoint to the product functor formula_22. For this reason, the morphisms formula_13 and formula_12 are sometimes called "exponential adjoints" of one another.
Equational definition.
Alternatively, the exponential object may be defined through equations:
Universal property.
The exponential formula_30 is given by a universal morphism from the product functor formula_22 to the object formula_2. This universal morphism consists of an object formula_30 and a morphism formula_8.
Examples.
In the category of sets, an exponential object formula_30 is the set of all functions formula_36. The map formula_37 is just the evaluation map, which sends the pair formula_38 to formula_39. For any map formula_40 the map formula_41 is the curried form of formula_12:
A Heyting algebra formula_44 is just a bounded lattice that has all exponential objects. Heyting implication, formula_45, is an alternative notation for formula_30. The above adjunction results translate to implication (formula_47) being right adjoint to meet (formula_48). This adjunction can be written as formula_49, or more fully as:
formula_50
In the category of topological spaces, the exponential object formula_30 exists provided that formula_3 is a locally compact Hausdorff space. In that case, the space formula_30 is the set of all continuous functions from formula_3 to formula_2 together with the compact-open topology. The evaluation map is the same as in the category of sets; it is continuous with the above topology. If formula_3 is not locally compact Hausdorff, the exponential object may not exist (the space formula_30 still exists, but it may fail to be an exponential object since the evaluation function need not be continuous). For this reason the category of topological spaces fails to be cartesian closed.
However, the category of locally compact topological spaces is not cartesian closed either, since formula_30 need not be locally compact for locally compact spaces formula_2 and formula_3. A cartesian closed category of spaces is, for example, given by the full subcategory spanned by the compactly generated Hausdorff spaces.
In functional programming languages, the morphism formula_61 is often called formula_62, and the syntax formula_13 is often written formula_64. The morphism formula_61 here must not to be confused with the eval function in some programming languages, which evaluates quoted expressions.


Derivation (differential algebra)

In mathematics, a derivation is a function on an algebra which generalizes certain features of the derivative operator. Specifically, given an algebra "A" over a ring or a field "K", a "K"-derivation is a "K"-linear map that satisfies Leibniz's law:
More generally, if "M" is an "A"-bimodule, a "K"-linear map that satisfies the Leibniz law is also called a derivation. The collection of all "K"-derivations of "A" to itself is denoted by Der"K"("A"). The collection of "K"-derivations of "A" into an "A"-module "M" is denoted by .
Derivations occur in many different contexts in diverse areas of mathematics. The partial derivative with respect to a variable is an R-derivation on the algebra of real-valued differentiable functions on R"n". The Lie derivative with respect to a vector field is an R-derivation on the algebra of differentiable functions on a differentiable manifold; more generally it is a derivation on the tensor algebra of a manifold. It follows that the adjoint representation of a Lie algebra is a derivation on that algebra. The Pincherle derivative is an example of a derivation in abstract algebra. If the algebra "A" is noncommutative, then the commutator with respect to an element of the algebra "A" defines a linear endomorphism of "A" to itself, which is a derivation over "K". An algebra "A" equipped with a distinguished derivation "d" forms a differential algebra, and is itself a significant object of study in areas such as differential Galois theory.
Properties.
If "A" is a "K"-algebra, for "K" a ring, and is a "K"-derivation, then
Graded derivations.
Given a graded algebra "A" and a homogeneous linear map "D" of grade on "A", "D" is a homogeneous derivation if
for every homogeneous element "a" and every element "b" of "A" for a commutator factor . A graded derivation is sum of homogeneous derivations with the same "ε".
If , this definition reduces to the usual case. If , however, then
for odd , and "D" is called an anti-derivation.
Examples of anti-derivations include the exterior derivative and the interior product acting on differential forms.
Graded derivations of superalgebras (i.e. Z2-graded algebras) are often called superderivations.
Related notions.
Hasse–Schmidt derivations are "K"-algebra homomorphisms
Composing further with the map which sends a formal power series formula_15 to the coefficient formula_16 gives a derivation.


Regular local ring

In commutative algebra, a regular local ring is a Noetherian local ring having the property that the minimal number of generators of its maximal ideal is equal to its Krull dimension. In symbols, let "A" be a Noetherian local ring with maximal ideal m, and suppose "a"1, ..., "a""n" is a minimal set of generators of m. Then by Krull's principal ideal theorem "n" ≥ dim "A", and "A" is defined to be regular if "n" = dim "A".
The appellation "regular" is justified by the geometric meaning. A point "x" on an algebraic variety "X" is nonsingular if and only if the local ring formula_1 of germs at "x" is regular. (See also: regular scheme.) Regular local rings are "not" related to von Neumann regular rings.
For Noetherian local rings, there is the following chain of inclusions:
Characterizations.
There are a number of useful definitions of a regular local ring, one of which is mentioned above. In particular, if formula_2 is a Noetherian local ring with maximal ideal formula_3, then the following are equivalent definitions
Multiplicity one criterion states: if the completion of a Noetherian local ring "A" is unimixed (in the sense that there is no embedded prime divisor of the zero ideal and for each minimal prime "p", formula_19) and if the multiplicity of "A" is one, then "A" is regular. (The converse is always true: the multiplicity of a regular local ring is one.) This criterion corresponds to a geometric intuition in algebraic geometry that a local ring of an intersection is regular if and only if the intersection is a transversal intersection.
In the positive characteristic case, there is the following important result due to Kunz: A Noetherian local ring formula_20 of positive characteristic "p" is regular if and only if the Frobenius morphism formula_21 is flat and formula_20 is reduced. No similar result is known in the characteristic zero (just because how to replace Frobenius is unclear).
Non-Examples.
The ring formula_23 is not a regular local ring since it is finite dimensional but does not have finite global dimension. For example, there is an infinite resolution
Basic properties.
The Auslander–Buchsbaum theorem states that every regular local ring is a unique factorization domain.
Every localization of a regular local ring is regular.
The completion of a regular local ring is regular.
If formula_34 is a complete regular local ring that contains a field, then
where formula_9 is the residue field, and formula_37, the Krull dimension.
See also: Serre's inequality on height and Serre's multiplicity conjectures.
Origin of basic notions.
Regular local rings were originally defined by Wolfgang Krull in 1937, but they first became prominent in the work of Oscar Zariski a few years later, who showed that geometrically, a regular local ring corresponds to a smooth point on an algebraic variety. Let "Y" be an algebraic variety contained in affine "n"-space over a perfect field, and suppose that "Y" is the vanishing locus of the polynomials "f1"...,"fm". "Y" is nonsingular at "P" if "Y" satisfies a Jacobian condition: If "M" = (∂"fi"/∂"xj") is the matrix of partial derivatives of the defining equations of the variety, then the rank of the matrix found by evaluating "M" at "P" is "n" − dim "Y". Zariski proved that "Y" is nonsingular at "P" if and only if the local ring of "Y" at "P" is regular. (Zariski observed that this can fail over non-perfect fields.) This implies that smoothness is an intrinsic property of the variety, in other words it does not depend on where or how the variety is embedded in affine space. It also suggests that regular local rings should have good properties, but before the introduction of techniques from homological algebra very little was known in this direction. Once such techniques were introduced in the 1950s, Auslander and Buchsbaum proved that every regular local ring is a unique factorization domain.
Another property suggested by geometric intuition is that the localization of a regular local ring should again be regular. Again, this lay unsolved until the introduction of homological techniques. It was Jean-Pierre Serre who found a homological characterization of regular local rings: A local ring "A" is regular if and only if "A" has finite global dimension, i.e. if every "A"-module has a projective resolution of finite length. It is easy to show that the property of having finite global dimension is preserved under localization, and consequently that localizations of regular local rings at prime ideals are again regular.
This allows us to define regularity for all commutative rings, not just local ones: A commutative ring "A" is said to be a regular ring if its localizations at all of its prime ideals are regular local rings.
If "A" is finite dimensional, it is equivalent to say that "A" has finite global dimension.
Regular ring.
In commutative algebra, a regular ring is a commutative Noetherian ring, such that the localization at every prime ideal is a regular local ring: that is, every such localization has the property that the minimal number of generators of its maximal ideal is equal to its Krull dimension.
The origin of the term "regular ring" lies in the fact that an affine variety is nonsingular (that is every point is regular) if and only if its ring of regular functions is regular.
For regular rings, Krull dimension agrees with global homological dimension.
Jean-Pierre Serre defined a regular ring as a commutative noetherian ring of "finite" global homological dimension. His definition is stronger than the definition above, which allows regular rings of infinite Krull dimension.
Examples of regular rings include fields (of dimension zero) and Dedekind domains. If "A" is regular then so is "A"["X"], with dimension one greater than that of "A".
In particular if is a field, the ring of integers, or a principal ideal domain, then the polynomial ring formula_38 is regular. In the case of a field, this is Hilbert's syzygy theorem.
Any localization of a regular ring is regular as well.
A regular ring is reduced but need not be an integral domain. For example, the product of two regular integral domains is regular, but not an integral domain.


Rogers polynomials

In mathematics, the Rogers polynomials, also called Rogers–Askey–Ismail polynomials and continuous q-ultraspherical polynomials, are a family of orthogonal polynomials introduced by in the course of his work on the Rogers–Ramanujan identities. They are "q"-analogs of ultraspherical polynomials, and are the Macdonald polynomials for the special case of the "A"1 affine root system .
 and discuss the properties of Rogers polynomials in detail.
Definition.
The Rogers polynomials can be defined in terms of the "q"-Pochhammer symbol and the basic hypergeometric series by
where "x" = cos("θ").


Medial magma

In abstract algebra, a medial magma or medial groupoid is a magma or groupoid (that is, a set with a binary operation) which satisfies the identity
for all "x", "y", "u" and "v", using the convention that juxtaposition denotes the same operation but has higher precedence. This identity has been variously called "medial", "abelian", "alternation", "transposition", "interchange", "bi-commutative", "bisymmetric", "surcommutative", "entropic" etc.
Any commutative semigroup is a medial magma, and a medial magma has an identity element if and only if it is a commutative monoid. Another class of semigroups forming medial magmas are normal bands. Medial magmas need not be associative: for any nontrivial abelian group with operation and integers , the new binary operation defined by formula_3 yields a medial magma which in general is neither associative nor commutative.
Using the categorical definition of product, for a magma , one may define the Cartesian square magma  with the operation
The binary operation of , considered as a mapping from to , maps to , to , and to .
Hence, a magma  is medial if and only if its binary operation is a magma homomorphism from  to . This can easily be expressed in terms of a commutative diagram, and thus leads to the notion of a medial magma object in a category with a Cartesian product. (See the discussion in auto magma object.)
If and are endomorphisms of a medial magma, then the mapping   defined by pointwise multiplication
is itself an endomorphism. It follows that the set End() of all endomorphisms of a medial magma is itself a medial magma.
Bruck–Murdoch–Toyoda theorem.
The Bruck–Murdoch-Toyoda theorem provides the following characterization of medial quasigroups. Given an abelian group and two commuting automorphisms φ and ψ of , define an operation on by
where some fixed element of . It is not hard to prove that forms a medial quasigroup under this operation. The Bruck–Toyoda theorem states that every medial quasigroup is of this form, i.e. is isomorphic to a quasigroup defined from an abelian group in this way. In particular, every medial quasigroup is isotopic to an abelian group.
The result was obtained independently in 1941 by D.C. Murdoch and K. Toyoda. It was then rediscovered by Bruck in 1944.
Generalizations.
The term "medial" or (more commonly) "entropic" is also used for a generalization to multiple operations. An algebraic structure is an entropic algebra if every two operations satisfy a generalization of the medial identity. Let "f" and "g" be operations of arity "m" and "n", respectively. Then "f" and "g" are required to satisfy


Euclidean field

In mathematics, a Euclidean field is an ordered field for which every non-negative element is a square: that is, in implies that for some in .
The constructible numbers form a Euclidean field. It is the smallest Euclidean field, as every Euclidean field contains it as an ordered subfield. In other words, the constructible numbers form the Euclidean closure of the rational numbers.
Examples.
Every real closed field is a Euclidean field. The following examples are also real closed fields.
Euclidean closure.
The Euclidean closure of an ordered field is an extension of in the quadratic closure of which is maximal with respect to being an ordered field with an order extending that of . It is also the smallest subfield of the algebraic closure of that is a Euclidean field and is an ordered extension of .


Erhard Schmidt

Erhard Schmidt (13 January 1876 – 6 December 1959) was a Baltic German mathematician whose work significantly influenced the direction of mathematics in the twentieth century. Schmidt was born in Tartu (), in the Governorate of Livonia (now Estonia).
Mathematics.
His advisor was David Hilbert and he was awarded his doctorate from University of Göttingen in 1905. His doctoral dissertation was entitled "Entwickelung willkürlicher Funktionen nach Systemen vorgeschriebener" and was a work on integral equations. Together with David Hilbert he made important contributions to functional analysis. Ernst Zermelo credited conversations with Schmidt for the idea and method for his classic 1904 proof of the Well-ordering theorem from an "Axiom of choice", which has become an integral part of modern set theory.
After the war, in 1948, Schmidt founded and became the first editor-in-chief of the journal "Mathematische Nachrichten".
National Socialism.
During World War II Schmidt held positions of authority at the University of Berlin and had to carry out various Nazi resolutions against the Jews—a job that he apparently did not do well, since he was criticized at one point for not understanding the "Jewish question." At the celebration of Schmidt's 75th birthday in 1951 a prominent Jewish mathematician, Hans Freudenthal, who had survived the Nazi years, spoke of the difficulties that Schmidt faced during that period without criticism. He was, however, a conservative and a nationalist, and defended Hitler after Kristallnacht, telling Issai Schur that "Suppose we had to fight a war to rearm Germany, unite with Austria, liberate the Saar and the German part of Czechoslovakia. Such a war would have cost us half a million young men. But everybody would have admired our victorious leader. Now, Hitler has sacrificed half a million Jews and has achieved great things for Germany. I hope some day you will be recompensed but I am still grateful to Hitler".