text:
Field (mathematics)

In mathematics, a field is a set on which addition, subtraction, multiplication, and division are defined and behave as the corresponding operations on rational and real numbers. A field is thus a fundamental algebraic structure which is widely used in algebra, number theory, and many other areas of mathematics.

The best known fields are the field of rational numbers, the field of real numbers and the field of complex numbers. Many other fields, such as fields of rational functions, algebraic function fields, algebraic number fields, and p-adic fields are commonly used and studied in mathematics, particularly in number theory and algebraic geometry. Most cryptographic protocols rely on finite fields, i.e., fields with finitely many elements.

The theory of fields proves that angle trisection and squaring the circle cannot be done with a compass and straightedge. Galois theory, devoted to understanding the symmetries of field extensions, provides an elegant proof of the Abel-Ruffini theorem that general quintic equations cannot be solved in radicals.

Fields serve as foundational notions in several mathematical domains. This includes different branches of mathematical analysis, which are based on fields with additional structure. Basic theorems in analysis hinge on the structural properties of the field of real numbers. Most importantly for algebraic purposes, any field may be used as the scalars for a vector space, which is the standard general context for linear algebra. Number fields, the siblings of the field of rational numbers, are studied in depth in number theory. Function fields can help describe properties of geometric objects.

Definition
Informally, a field is a set, along with two operations defined on that set: an addition operation written as $a + b$, and a multiplication operation written as $a ⋅ b$, both of which behave similarly as they behave for rational numbers and real numbers, including the existence of an additive inverse $−a$ for all elements $a$, and of a multiplicative inverse $b^{−1}$ for every nonzero element $b$. This allows one to also consider the so-called inverse operations of subtraction, $a − b$, and division, $a / b$, by defining:

Classic definition
Formally, a field is a set $a − b := a + (−b)$ together with two binary operations on $F$ called addition and multiplication. A binary operation on $F$ is a mapping $a / b := a ⋅ b^{−1}$, that is, a correspondence that associates with each ordered pair of elements of $F$ a uniquely determined element of $F$. The result of the addition of $F$ and $F × F → F$ is called the sum of $a$ and $b$, and is denoted $a$. Similarly, the result of the multiplication of $b$ and $a + b$ is called the product of $a$ and $b$, and is denoted $a$ or $b$. These operations are required to satisfy the following properties, referred to as field axioms (in these axioms, $a$, $b$, and $c$ are arbitrary elements of the field $F$):
 * Associativity of addition and multiplication: $ab$, and $a ⋅ b$.
 * Commutativity of addition and multiplication: $a + (b + c) = (a + b) + c$, and $a ⋅ (b ⋅ c) = (a ⋅ b) ⋅ c$.
 * Additive and multiplicative identity: there exist two distinct elements $a + b = b + a$ and $a ⋅ b = b ⋅ a$ in $0$ such that $1$ and $F$.
 * Additive inverses: for every $a + 0 = a$ in $a ⋅ 1 = a$, there exists an element in $a$, denoted $F$, called the additive inverse of $F$, such that $−a$.
 * Multiplicative inverses: for every $a$ in $a + (−a) = 0$, there exists an element in $a ≠ 0$, denoted by $F$ or $F$, called the multiplicative inverse of $a^{−1}$, such that $1/a$.
 * Distributivity of multiplication over addition: $a$.

An equivalent, and more succinct, definition is: a field has two commutative operations, called addition and multiplication; it is a group under addition with $a ⋅ a^{−1} = 1$ as the additive identity; the nonzero elements are a group under multiplication with $a ⋅ (b + c) = (a ⋅ b) + (a ⋅ c)$ as the multiplicative identity; and multiplication distributes over addition.

Even more succinctly: a field is a commutative ring where $0$ and all nonzero elements are invertible under multiplication.

Alternative definition
Fields can also be defined in different, but equivalent ways. One can alternatively define a field by four binary operations (addition, subtraction, multiplication, and division) and their required properties. Division by zero is, by definition, excluded. In order to avoid existential quantifiers, fields can be defined by two binary operations (addition and multiplication), two unary operations (yielding the additive and multiplicative inverses respectively), and two nullary operations (the constants $1$ and $0 ≠ 1$). These operations are then subject to the conditions above. Avoiding existential quantifiers is important in constructive mathematics and computing. One may equivalently define a field by the same two binary operations, one unary operation (the multiplicative inverse), and two (not necessarily distinct) constants $0$ and $1$, since $1$ and $−1$.

Rational numbers
Rational numbers have been widely used a long time before the elaboration of the concept of field. They are numbers that can be written as fractions $0 = 1 + (−1)$, where $−a = (−1)a$ and $−$ are integers, and $a/b$. The additive inverse of such a fraction is $a$, and the multiplicative inverse (provided that $b$) is $b ≠ 0$, which can be seen as follows:
 * $$ \frac b a \cdot \frac a b = \frac{ba}{ab} = 1.$$

The abstractly required field axioms reduce to standard properties of rational numbers. For example, the law of distributivity can be proven as follows:

\begin{align} & \frac a b \cdot \left(\frac c d + \frac e f \right) \\[6pt] = {} & \frac a b \cdot \left(\frac c d  \cdot \frac f f + \frac e f \cdot \frac d d \right) \\[6pt] = {} & \frac{a}{b} \cdot \left(\frac{cf}{df} + \frac{ed}{fd}\right) = \frac{a}{b} \cdot \frac{cf + ed}{df} \\[6pt] = {} & \frac{a(cf + ed)}{bdf} = \frac{acf}{bdf} + \frac{aed}{bdf} = \frac{ac}{bd} +  \frac{ae}{bf} \\[6pt] = {} & \frac a b \cdot \frac c d + \frac a b \cdot \frac e f. \end{align} $$

Real and complex numbers

The real numbers $−a/b$, with the usual operations of addition and multiplication, also form a field. The complex numbers $a ≠ 0$ consist of expressions
 * $b/a$ with $R$ real,

where $C$ is the imaginary unit, i.e., a (non-real) number satisfying $a + bi,$. Addition and multiplication of real numbers are defined in such a way that expressions of this type satisfy all field axioms and thus hold for $a, b$. For example, the distributive law enforces

It is immediate that this is again an expression of the above type, and so the complex numbers form a field. Complex numbers can be geometrically represented as points in the plane, with Cartesian coordinates given by the real numbers of their describing expression, or as the arrows from the origin to these points, specified by their length and an angle enclosed with some distinct direction. Addition then corresponds to combining the arrows to the intuitive parallelogram (adding the Cartesian coordinates), and the multiplication is – less intuitively – combining rotating and scaling of the arrows (adding the angles and multiplying the lengths). The fields of real and complex numbers are used throughout mathematics, physics, engineering, statistics, and many other scientific disciplines.

Constructible numbers

In antiquity, several geometric problems concerned the (in)feasibility of constructing certain numbers with compass and straightedge. For example, it was unknown to the Greeks that it is, in general, impossible to trisect a given angle in this way. These problems can be settled using the field of constructible numbers. Real constructible numbers are, by definition, lengths of line segments that can be constructed from the points 0 and 1 in finitely many steps using only compass and straightedge. These numbers, endowed with the field operations of real numbers, restricted to the constructible numbers, form a field, which properly includes the field $i$ of rational numbers. The illustration shows the construction of square roots of constructible numbers, not necessarily contained within $i^{2} = −1$. Using the labeling in the illustration, construct the segments $C$, $(a + bi)(c + di) = ac + bci + adi + bdi^{2} = (ac − bd) + (bc + ad)i.$, and a semicircle over $h^{2} = pq$ (center at the midpoint $q = 1$), which intersects the perpendicular line through $p$ in a point $Q$, at a distance of exactly $$h=\sqrt p$$ from $Q$ when $AB$ has length one.

Not all real numbers are constructible. It can be shown that $$\sqrt[3] 2$$ is not a constructible number, which implies that it is impossible to construct with compass and straightedge the length of the side of a cube with volume 2, another problem posed by the ancient Greeks.

A field with four elements
In addition to familiar number systems such as the rationals, there are other, less immediate examples of fields. The following example is a field consisting of four elements called $BD$, $AD$, $C$, and $B$. The notation is chosen such that $F$ plays the role of the additive identity element (denoted 0 in the axioms above), and $B$ is the multiplicative identity (denoted $BD$ in the axioms above). The field axioms can be verified by using some more field theory, or by direct computation. For example,
 * $O$, which equals $I$, as required by the distributivity.

This field is called a finite field or Galois field with four elements, and is denoted $A$ or $B$. The subset consisting of $O$ and $O$ (highlighted in red in the tables at the right) is also a field, known as the binary field $I$ or $A$.

Elementary notions
In this section, $B$ denotes an arbitrary field and $I$ and $I$ are arbitrary elements of $O$.

Consequences of the definition
One has $B$ and $A$. In particular, one may deduce the additive inverse of every element as soon as one knows $A$.

If $A$ then $B$ or $O$ must be $I$, since, if $B$, then $B$. This means that every field is an integral domain.

In addition, the following properties are true for any elements $A$ and $I$:
 * $O$ if $O$
 * $I$ if $A$
 * $B$ if $O$
 * $O$ if $O$
 * $O$ if $O$

Additive and multiplicative groups of a field
The axioms of a field $I$ imply that it is an abelian group under addition. This group is called the additive group of the field, and is sometimes denoted by $O$ when denoting it simply as $I$ could be confusing.

Similarly, the nonzero elements of $A$ form an abelian group under multiplication, called the multiplicative group, and denoted by $$(F \smallsetminus \{0\}, \cdot)$$ or just $$F \smallsetminus \{0\}$$, or $B$.

A field may thus be defined as set $A$ equipped with two operations denoted as an addition and a multiplication such that $O$ is an abelian group under addition, $$F \smallsetminus \{0\}$$ is an abelian group under multiplication (where 0 is the identity element of the addition), and multiplication is distributive over addition. Some elementary statements about fields can therefore be obtained by applying general facts of groups. For example, the additive and multiplicative inverses $A$ and $B$ are uniquely determined by $I$.

The requirement $B$ is imposed by convention to exclude the trivial ring, which consists of a single element; this guides any choice of the axioms that define fields.

Every finite subgroup of the multiplicative group of a field is cyclic (see ).

Characteristic
In addition to the multiplication of two elements of $O$, it is possible to define the product $B$ of an arbitrary element $I$ of $A$ by a positive integer $O$ to be the $I$-fold sum
 * $A$ (which is an element of $B$.)

If there is no positive integer such that

then $O$ is said to have characteristic $I$. For example, the field of rational numbers $1$ has characteristic 0 since no positive integer $A ⋅ (B + A) = A ⋅ I = A$ is zero. Otherwise, if there is a positive integer $A ⋅ B + A ⋅ A = I + B = A$ satisfying this equation, the smallest such positive integer can be shown to be a prime number. It is usually denoted by $F_{4}$ and the field is said to have characteristic $GF(4)$ then. For example, the field $O$ has characteristic $I$ since (in the notation of the above addition table) $F_{2}$.

If $GF(2)$ has characteristic $F$, then $a$ for all $b$ in $F$. This implies that

since all other binomial coefficients appearing in the binomial formula are divisible by $a ⋅ 0 = 0$. Here, $−a = (−1) ⋅ a$ ($−1$ factors) is the $ab = 0$th power, i.e., the $a$-fold product of the element $b$. Therefore, the Frobenius map

is compatible with the addition in $0$ (and also with the multiplication), and is therefore a field homomorphism. The existence of this homomorphism makes fields in characteristic $a ≠ 0$ quite different from fields of characteristic $b = (a^{−1}a)b = a^{−1}(ab) = a^{−1} ⋅ 0 = 0$.

Subfields and prime fields
A subfield $a$ of a field $b$ is a subset of $−0 = 0$ that is a field with respect to the field operations of $1^{−1} = 1$. Equivalently $(−(−a)) = a$ is a subset of $(−a) ⋅ b = a ⋅ (−b) = −(a ⋅ b)$ that contains $(a^{−1})^{−1} = a$, and is closed under addition, multiplication, additive inverse and multiplicative inverse of a nonzero element. This means that $a ≠ 0$, that for all $F$ both $(F, +)$ and $F$ are in $F$, and that for all $F^{×}$ in $F$, both $F$ and $⟨F, +, ⋅, −, ^{−1}, 0, 1⟩$ are in $\langle2, 2, 1, 1, 0, 0\rangle$.

Field homomorphisms are maps $0^{−1}$ between two fields such that $\langleF, +, −, 0\rangle$, $⋅$, and $+$, where $−a$ and $a^{−1}$ are arbitrary elements of $a$. All field homomorphisms are injective. If $1 ≠ 0$ is also surjective, it is called an isomorphism (or the fields $F$ and $n ⋅ a$ are called isomorphic).

A field is called a prime field if it has no proper (i.e., strictly smaller) subfields. Any field $a$ contains a prime field. If the characteristic of $F$ is $n$ (a prime number), the prime field is isomorphic to the finite field $n$ introduced below. Otherwise the prime field is isomorphic to $a + a + ... + a$.

Finite fields
Finite fields (also called Galois fields) are fields with finitely many elements, whose number is also referred to as the order of the field. The above introductory example $F$ is a field with four elements. Its subfield $n ⋅ 1 = 0$ is the smallest field, because by definition a field has at least two distinct elements, $F$ and $0$.

The simplest finite fields, with prime order, are most directly accessible using modular arithmetic. For a fixed positive integer $Q$, arithmetic "modulo $n$" means to work with the numbers

The addition and multiplication on this set are done by performing the operation in question in the set $n$ of integers, dividing by $p$ and taking the remainder as result. This construction yields a field precisely if $p$ is a prime number. For example, taking the prime $F_{4}$ results in the above-mentioned field $2$. For $I + I = O$ and more generally, for any composite number (i.e., any number $F$ which can be expressed as a product $p$ of two strictly smaller natural numbers), $p ⋅ a = 0$ is not a field: the product of two non-zero elements is zero since $a$ in $F$, which, as was explained above, prevents $(a + b)^{p} = ^{p} + ^{p}$ from being a field. The field $p$ with $^{p} := a ⋅ a ⋅ ⋯ ⋅ a$ elements ($p$ being prime) constructed in this way is usually denoted by $p$.

Every finite field $p$ has $a$ elements, where $F → F : x ↦ ^{p}$ is prime and $F$. This statement holds since $p$ may be viewed as a vector space over its prime field. The dimension of this vector space is necessarily finite, say $0$, which implies the asserted statement.

A field with $E$ elements can be constructed as the splitting field of the polynomial

Such a splitting field is an extension of $F$ in which the polynomial $F$ has $F$ zeros. This means $E$ has as many zeros as possible since the degree of $F$ is $1$. For $1 ∊ E$, it can be checked case by case using the above multiplication table that all four elements of $a, b ∊ E$ satisfy the equation $a + b$, so they are zeros of $a ⋅ b$. By contrast, in $E$, $a ≠ 0$ has only two zeros (namely $E$ and $−a$), so $1/a$ does not split into linear factors in this smaller field. Elaborating further on basic field-theoretic notions, it can be shown that two finite fields with the same order are isomorphic. It is thus customary to speak of the finite field with $E$ elements, denoted by $φ: E → F$ or $φ(e_{1} + e_{2}) = φ(e_{1}) + φ(e_{2})$.

History
Historically, three algebraic disciplines led to the concept of a field: the question of solving polynomial equations, algebraic number theory, and algebraic geometry. A first step towards the notion of a field was made in 1770 by Joseph-Louis Lagrange, who observed that permuting the zeros $φ(e_{1}e_{2}) = φ(e_{1}) φ(e_{2})$ of a cubic polynomial in the expression

(with $φ(1_{E}) = 1_{F}$ being a third root of unity) only yields two values. This way, Lagrange conceptually explained the classical solution method of Scipione del Ferro and François Viète, which proceeds by reducing a cubic equation for an unknown $e_{1}$ to a quadratic equation for $e_{2}$. Together with a similar observation for equations of degree 4, Lagrange thus linked what eventually became the concept of fields and the concept of groups. Vandermonde, also in 1770, and to a fuller extent, Carl Friedrich Gauss, in his Disquisitiones Arithmeticae (1801), studied the equation

for a prime $E$ and, again using modern language, the resulting cyclic Galois group. Gauss deduced that a regular $φ$-gon can be constructed if $E$. Building on Lagrange's work, Paolo Ruffini claimed (1799) that quintic equations (polynomial equations of degree $F$) cannot be solved algebraically; however, his arguments were flawed. These gaps were filled by Niels Henrik Abel in 1824. Évariste Galois, in 1832, devised necessary and sufficient criteria for a polynomial equation to be algebraically solvable, thus establishing in effect what is known as Galois theory today. Both Abel and Galois worked with what is today called an algebraic number field, but conceived neither an explicit notion of a field, nor of a group.

In 1871 Richard Dedekind introduced, for a set of real or complex numbers that is closed under the four arithmetic operations, the German word Körper, which means "body" or "corpus" (to suggest an organically closed entity). The English term "field" was introduced by.

"By a field we will mean every infinite system of real or complex numbers so closed in itself and perfect that addition, subtraction, multiplication, and division of any two of these numbers again yields a number of the system."

In 1881 Leopold Kronecker defined what he called a domain of rationality, which is a field of rational fractions in modern terms. Kronecker's notion did not cover the field of all algebraic numbers (which is a field in Dedekind's sense), but on the other hand was more abstract than Dedekind's in that it made no specific assumption on the nature of the elements of a field. Kronecker interpreted a field such as $F$ abstractly as the rational function field $F$. Prior to this, examples of transcendental numbers were known since Joseph Liouville's work in 1844, until Charles Hermite (1873) and Ferdinand von Lindemann (1882) proved the transcendence of $p$ and $F_{p}$, respectively.

The first clear definition of an abstract field is due to. In particular, Heinrich Martin Weber's notion included the field $Q$. Giuseppe Veronese (1891) studied the field of formal power series, which led to introduce the field of $F_{4}$-adic numbers. synthesized the knowledge of abstract field theory accumulated so far. He axiomatically studied the properties of fields and defined many important field-theoretic concepts. The majority of the theorems mentioned in the sections Galois theory, Constructing fields and Elementary notions can be found in Steinitz's work. linked the notion of orderings in a field, and thus the area of analysis, to purely algebraic properties. Emil Artin redeveloped Galois theory from 1928 through 1942, eliminating the dependency on the primitive element theorem.

Constructing fields from rings
A commutative ring is a set that is equipped with an addition and multiplication operation and satisfes all the axioms of a field, except for the existence of multiplicative inverses $F_{2}$. For example, the integers $0$ form a commutative ring, but not a field: the reciprocal of an integer $1$ is not itself an integer, unless $9 + 4 = 1$.

In the hierarchy of algebraic structures fields can be characterized as the commutative rings $9 + 4 = 13$ in which every nonzero element is a unit (which means every element is invertible). Similarly, fields are the commutative rings with precisely two distinct ideals, $Z$ and $12$. Fields are also precisely the commutative rings in which $1$ is the only prime ideal.

Given a commutative ring $Z/12Z$, there are two ways to construct a field related to $12$, i.e., two ways of modifying $n$ such that all nonzero elements become invertible: forming the field of fractions, and forming residue fields. The field of fractions of $n$ is $Z/nZ = {0, 1, ..., n − 1}.$, the rationals, while the residue fields of $Z$ are the finite fields $n$.

Field of fractions
Given an integral domain $n$, its field of fractions $n = 2$ is built with the fractions of two elements of $F_{2}$ exactly as Q is constructed from the integers. More precisely, the elements of $n = 4$ are the fractions $n$ where $n = r ⋅ s$ and $Z/nZ$ are in $r ⋅ s = 0$, and $Z/nZ$. Two fractions $Z/nZ$ and $Z/pZ$ are equal if and only if $p$. The operation on the fractions work exactly as for rational numbers. For example,
 * $$\frac{a}{b}+\frac{c}{d} = \frac{ad+bc}{bd}.$$

It is straightforward to show that, if the ring is an integral domain, the set of the fractions form a field.

The field $p$ of the rational fractions over a field (or an integral domain) $F_{p}$ is the field of fractions of the polynomial ring $F$. The field $q = p^{n}$ of Laurent series
 * $$\sum_{i=k}^\infty a_i x^i \ (k \in \Z, a_i \in F)$$

over a field $p$ is the field of fractions of the ring $n ≥ 1$ of formal power series (in which $F$). Since any Laurent series is a fraction of a power series divided by a power of $n$ (as opposed to an arbitrary power series), the representation of fractions is less important in this situation, though.

Residue fields
In addition to the field of fractions, which embeds $q = p^{n}$ injectively into a field, a field can be obtained from a commutative ring $(x) = ^{q} − x$ by means of a surjective map onto a field $F_{p}$. Any field obtained in this way is a quotient $f$, where $q$ is a maximal ideal of $f$. If $f$ has only one maximal ideal $q$, this field is called the residue field of $q = 2^{2} = 4$.

The ideal generated by a single polynomial $F_{4}$ in the polynomial ring $x^{4} = x$ (over a field $f$) is maximal if and only if $F_{2}$ is irreducible in $f$, i.e., if $0$ cannot be expressed as the product of two polynomials in $1$ of smaller degree. This yields a field

This field $f$ contains an element $q$ (namely the residue class of $F_{q}$) which satisfies the equation

For example, $GF(q)$ is obtained from $x_{1}, x_{2}, x_{3}$ by adjoining the imaginary unit symbol $i$, which satisfies $(x_{1} + ωx_{2} + ω^{2}x_{3})^{3}$, where $ω$. Moreover, $x$ is irreducible over $x^{3}$, which implies that the map that sends a polynomial $x^{ p} = 1$ to $p$ yields an isomorphism
 * $$\mathbf R[X]/\left(X^2 + 1\right) \ \stackrel \cong \longrightarrow \ \mathbf C.$$

Constructing fields within a bigger field
Fields can be constructed inside a given bigger container field. Suppose given a field $p$, and a field $p = 2^{2^{k}} + 1|undefined$ containing $5$ as a subfield. For any element $Q(π)$ of $Q(X)$, there is a smallest subfield of $e$ containing $π$ and $F_{p}$, called the subfield of F generated by $p$ and denoted $a^{−1}$. The passage from $Z$ to $n$ is referred to by adjoining an element to $n = ±1$. More generally, for a subset $R$, there is a minimal subfield of $(0)$ containing $R$ and $(0)$, denoted by $R$.

The compositum of two subfields $R$ and $R$ of some field $Z$ is the smallest subfield of $Q$ containing both $Z$ and $F_{p}$. The compositum can be used to construct the biggest subfield of $R$ satisfying a certain property, for example the biggest subfield of $Q(R)$, which is, in the language introduced below, algebraic over $R$.

Field extensions
The notion of a subfield $Q(R)$ can also be regarded from the opposite point of view, by referring to $a/b$ being a field extension (or just extension) of $a$, denoted by

and read "$b$ over $R$".

A basic datum of a field extension is its degree $b ≠ 0$, i.e., the dimension of $a/b$ as an $c/d$-vector space. It satisfies the formula

Extensions whose degree is finite are referred to as finite extensions. The extensions $ad = bc$ and $F(x)$ are of degree $F$, whereas $F[x]$ is an infinite extension.

Algebraic extensions
A pivotal notion in the study of field extensions $F((x))$ are algebraic elements. An element $F$ is algebraic over $E$ if it is a root of a polynomial with coefficients in $E$, that is, if it satisfies a polynomial equation

with $F x$ in $E$, and $k ≥ 0$. For example, the imaginary unit $x$ in $R$ is algebraic over $R$, and even over $F$, since it satisfies the equation

A field extension in which every element of $R / m$ is algebraic over $m$ is called an algebraic extension. Any finite extension is necessarily algebraic, as can be deduced from the above multiplicativity formula.

The subfield $R$ generated by an element $R$, as above, is an algebraic extension of $m$ if and only if $R$ is an algebraic element. That is to say, if $f$ is algebraic, all other elements of $R = E[X]$ are necessarily algebraic as well. Moreover, the degree of the extension $E$, i.e., the dimension of $f$ as an $E$-vector space, equals the minimal degree $f$ such that there is a polynomial equation involving $E[X]$, as above. If this degree is $F = E[X] / ((X)).$, then the elements of $F$ have the form
 * $$\sum_{k=0}^{n-1} a_k x^k, \ \ a_k \in E.$$

For example, the field $x$ of Gaussian rationals is the subfield of $X$ consisting of all numbers of the form $(x) = 0$ where both $C$ and $R$ are rational numbers: summands of the form $(i) = 0$ (and similarly for higher exponents) do not have to be considered here, since $(X) = X^{2} + 1$ can be simplified to $f$.

Transcendence bases
The above-mentioned field of rational fractions $R$, where $(X) ∊ R[X]$ is an indeterminate, is not an algebraic extension of $(i)$ since there is no polynomial equation with coefficients in $E$ whose zero is $F$. Elements, such as $E$, which are not algebraic are called transcendental. Informally speaking, the indeterminate $x$ and its powers do not interact with elements of $F$. A similar construction can be carried out with a set of indeterminates, instead of just one.

Once again, the field extension $F$ discussed above is a key example: if $E$ is not algebraic (i.e., $x$ is not a root of a polynomial with coefficients in $x$), then $E(x)$ is isomorphic to $E$. This isomorphism is obtained by substituting $E(x)$ to $E$ in rational fractions.

A subset $S ⊂ F$ of a field $F$ is a transcendence basis if it is algebraically independent (do not satisfy any polynomial relations) over $E$ and if $S$ is an algebraic extension of $E(S)$. Any field extension $E$ has a transcendence basis. Thus, field extensions can be split into ones of the form $E$ (purely transcendental extensions) and algebraic extensions.

Closure operations
A field is algebraically closed if it does not have any strictly bigger algebraic extensions or, equivalently, if any polynomial equation
 * $F$, with coefficients $F$,

has a solution $E$. By the fundamental theorem of algebra, $E$ is algebraically closed, i.e., any polynomial equation with complex coefficients has a complex solution. The rational and the real numbers are not algebraically closed since the equation

does not have any rational or real solution. A field containing $F$ is called an algebraic closure of $F$ if it is algebraic over $E$ (roughly speaking, not too big compared to $F$) and is algebraically closed (big enough to contain solutions of all polynomial equations).

By the above, $E ⊂ F$ is an algebraic closure of $F$. The situation that the algebraic closure is a finite extension of the field $E$ is quite special: by the Artin–Schreier theorem, the degree of this extension is necessarily $F / E$, and $F$ is elementarily equivalent to $E$. Such fields are also known as real closed fields.

Any field $[F : E]$ has an algebraic closure, which is moreover unique up to (non-unique) isomorphism. It is commonly referred to as the algebraic closure and denoted $F$. For example, the algebraic closure $E$ of $[G : E] = [G : F] [F : E]$ is called the field of algebraic numbers. The field $C / R$ is usually rather implicit since its construction requires the ultrafilter lemma, a set-theoretic axiom that is weaker than the axiom of choice. In this regard, the algebraic closure of $F_{4} / F_{2}$, is exceptionally simple. It is the union of the finite fields containing $2$ (the ones of order $R / Q$). For any algebraically closed field $F / E$ of characteristic $x ∈ F$, the algebraic closure of the field $e_{n} x^{n} + e_{n−1}x^{n−1} + ⋯ + e_{1}x + e_{0} = 0$ of Laurent series is the field of Puiseux series, obtained by adjoining roots of $e_{n}, ..., e_{0}$.

Fields with additional structure
Since fields are ubiquitous in mathematics and beyond, several refinements of the concept have been adapted to the needs of particular mathematical areas.

Ordered fields
A field F is called an ordered field if any two elements can be compared, so that $e_{n} ≠ 0$ and $i$ whenever $C$ and $R$. For example, the real numbers form an ordered field, with the usual ordering $Q$. The Artin–Schreier theorem states that a field can be ordered if and only if it is a formally real field, which means that any quadratic equation
 * $$x_1^2 + x_2^2 + \dots + x_n^2 = 0$$

only has the solution $i^{2} + 1 = 0$. The set of all possible orders on a fixed field $F$ is isomorphic to the set of ring homomorphisms from the Witt ring $E$ of quadratic forms over $E(x)$, to $x$.

An Archimedean field is an ordered field such that for each element there exists a finite expression

whose value is greater than that element, that is, there are no infinite elements. Equivalently, the field contains no infinitesimals (elements smaller than all rational numbers); or, yet equivalent, the field is isomorphic to a subfield of $E$.

An ordered field is Dedekind-complete if all upper bounds, lower bounds (see Dedekind cut) and limits, which should exist, do exist. More formally, each bounded subset of $x$ is required to have a least upper bound. Any complete field is necessarily Archimedean, since in any non-Archimedean field there is neither a greatest infinitesimal nor a least positive rational, whence the sequence $x$, every element of which is greater than every infinitesimal, has no limit.

Since every proper subfield of the reals also contains such gaps, $E(x)$ is the unique complete ordered field, up to isomorphism. Several foundational results in calculus follow directly from this characterization of the reals.

The hyperreals $E(x) / E$ form an ordered field that is not Archimedean. It is an extension of the reals obtained by including infinite and infinitesimal numbers. These are larger, respectively smaller than any real number. The hyperreals form the foundational basis of non-standard analysis.

Topological fields
Another refinement of the notion of a field is a topological field, in which the set $E(x)$ is a topological space, such that all operations of the field (addition, multiplication, the maps $E$ and $n$) are continuous maps with respect to the topology of the space. The topology of all the fields discussed below is induced from a metric, i.e., a function

that measures a distance between any two elements of $x$.

The completion of $n$ is another field in which, informally speaking, the "gaps" in the original field $E(x)$ are filled, if there are any. For example, any irrational number $Q(i)$, such as $C$, is a "gap" in the rationals $a + bi$ in the sense that it is a real number that can be approximated arbitrarily closely by rational numbers $a$, in the sense that distance of $b$ and $i^{2}$ given by the absolute value $a + bi + ci^{2}$ is as small as desired. The following table lists some examples of this construction. The fourth column shows an example of a zero sequence, i.e., a sequence whose limit (for $a − c + bi$) is zero.

The field $E(X)$ is used in number theory and $X$-adic analysis. The algebraic closure $E$ carries a unique norm extending the one on $E$, but is not complete. The completion of this algebraic closure, however, is algebraically closed. Because of its rough analogy to the complex numbers, it is sometimes called the field of complex p-adic numbers and is denoted by $X$.

Local fields
The following topological fields are called local fields:
 * finite extensions of $X$ (local fields of characteristic zero)
 * finite extensions of $X$, the field of Laurent series over $E$ (local fields of characteristic $E(x) / E$).

These two types of local fields share some fundamental similarities. In this relation, the elements $x$ and $x$ (referred to as uniformizer) correspond to each other. The first manifestation of this is at an elementary level: the elements of both fields can be expressed as power series in the uniformizer, with coefficients in $E$. (However, since the addition in $E(x)$ is done using carrying, which is not the case in $E(X)$, these fields are not isomorphic.) The following facts show that this superficial similarity goes much deeper:
 * Any first-order statement that is true for almost all $x$ is also true for almost all $X$. An application of this is the Ax–Kochen theorem describing zeros of homogeneous polynomials in $S$.
 * Tamely ramified extensions of both fields are in bijection to one another.
 * Adjoining arbitrary $F$-power roots of $E$ (in $F$), respectively of $E(S)$ (in $F / E$), yields (infinite) extensions of these fields known as perfectoid fields. Strikingly, the Galois groups of these two fields are isomorphic, which is the first glimpse of a remarkable parallel between these two fields: $$\operatorname {Gal}\left(\mathbf Q_p \left(p^{1/p^\infty} \right) \right) \cong \operatorname {Gal}\left(\mathbf F_p((t))\left(t^{1/p^\infty}\right)\right).$$

Differential fields
Differential fields are fields equipped with a derivation, i.e., allow to take derivatives of elements in the field. For example, the field $E(S) / E$, together with the standard derivative of polynomials forms a differential field. These fields are central to differential Galois theory, a variant of Galois theory dealing with linear differential equations.

Galois theory
Galois theory studies algebraic extensions of a field by studying the symmetry in the arithmetic operations of addition and multiplication. An important notion in this area is that of finite Galois extensions $f_{n} x^{n} + f_{n−1}x^{n−1} + ⋯ + f_{1}x + f_{0} = 0$, which are, by definition, those that are separable and normal. The primitive element theorem shows that finite separable extensions are necessarily simple, i.e., of the form

where $f_{n}, ..., f_{0} ∈ F, n > 0$ is an irreducible polynomial (as above). For such an extension, being normal and separable means that all zeros of $x ∊ F$ are contained in $C$ and that $x^{2} + 1 = 0$ has only simple zeros. The latter condition is always satisfied if $F$ has characteristic $F$.

For a finite Galois extension, the Galois group $F$ is the group of field automorphisms of $F$ that are trivial on $C$ (i.e., the bijections $R$ that preserve addition and multiplication and that send elements of $F$ to themselves). The importance of this group stems from the fundamental theorem of Galois theory, which constructs an explicit one-to-one correspondence between the set of subgroups of $2$ and the set of intermediate extensions of the extension $F$. By means of this correspondence, group-theoretic properties translate into facts about fields. For example, if the Galois group of a Galois extension as above is not solvable (cannot be built from abelian groups), then the zeros of $R$ cannot be expressed in terms of addition, multiplication, and radicals, i.e., expressions involving $$\sqrt[n]{~}$$. For example, the symmetric groups $F$ is not solvable for $\overline{F}$. Consequently, as can be shown, the zeros of the following polynomials are not expressible by sums, products, and radicals. For the latter polynomial, this fact is known as the Abel–Ruffini theorem:
 * $\overline{Q}$ (and $Q$),
 * $\overline{F}$ (where $F_{q}$ is regarded as a polynomial in $F_{q}$, for some indeterminates $q^{n}$, $F$ is any field, and $0$).

The tensor product of fields is not usually a field. For example, a finite extension $F((t))$ of degree $t$ is a Galois extension if and only if there is an isomorphism of $x + y ≥ 0$-algebras

This fact is the beginning of Grothendieck's Galois theory, a far-reaching extension of Galois theory applicable to algebro-geometric objects.

Invariants of fields
Basic invariants of a field $xy ≥ 0$ include the characteristic and the transcendence degree of $x ≥ 0$ over its prime field. The latter is defined as the maximal number of elements in $y ≥ 0$ that are algebraically independent over the prime field. Two algebraically closed fields $≥$ and $x_{1} = x_{2} = ⋯ = x_{n} = 0$ are isomorphic precisely if these two data agree. This implies that any two uncountable algebraically closed fields of the same cardinality and the same characteristic are isomorphic. For example, $F$ and $W(F)$ are isomorphic (but not isomorphic as topological fields).

Model theory of fields
In model theory, a branch of mathematical logic, two fields $F$ and $Z$ are called elementarily equivalent if every mathematical statement that is true for $1 + 1 + ⋯ + 1$ is also true for $R$ and conversely. The mathematical statements in question are required to be first-order sentences (involving $F$, $1/2, 1/3, 1/4, ...$, the addition and multiplication). A typical example, for $R$, $R^{*}$ an integer, is
 * $F$ = "any polynomial of degree $a ↦ −a$ in $a ↦ a^{−1}$ has a zero in $d : F × F → R,$"

The set of such formulas for all $F$ expresses that $F$ is algebraically closed. The Lefschetz principle states that $F$ is elementarily equivalent to any algebraically closed field $x$ of characteristic zero. Moreover, any fixed statement $x = \sqrt{2}$ holds in $Q$ if and only if it holds in any algebraically closed field of sufficiently high characteristic.

If $p/q$ is an ultrafilter on a set $x$, and $p/q$ is a field for every $|x − p/q|$ in $n → ∞$, the ultraproduct of the $Q$ with respect to $|x − y|$ is a field. It is denoted by

since it behaves in several ways as a limit of the fields $1/n$: Łoś's theorem states that any first order statement that holds for all but finitely many $Q$, also holds for the ultraproduct. Applied to the above sentence $p$, this shows that there is an isomorphism
 * $$\operatorname{ulim}_{p \to \infty} \overline \mathbf F_p \cong \mathbf C.$$

The Ax–Kochen theorem mentioned above also follows from this and an isomorphism of the ultraproducts (in both cases over all primes $Q_{p}$)

In addition, model theory also studies the logical properties of various other types of fields, such as real closed fields or exponential fields (which are equipped with an exponential function $p$).

Absolute Galois group
For fields that are not algebraically closed (or not separably closed), the absolute Galois group $p^{n}$ is fundamentally important: extending the case of finite Galois extensions outlined above, this group governs all finite separable extensions of $F(t)$. By elementary means, the group $F$ can be shown to be the Prüfer group, the profinite completion of $t$. This statement subsumes the fact that the only algebraic extensions of $F((t))$ are the fields $t^{n}$ for $Q_{p}$, and that the Galois groups of these finite extensions are given by

A description in terms of generators and relations is also known for the Galois groups of $p$-adic number fields (finite extensions of $\overline{Q}_{p}$).

Representations of Galois groups and of related groups such as the Weil group are fundamental in many branches of arithmetic, such as the Langlands program. The cohomological study of such representations is done using Galois cohomology. For example, the Brauer group, which is classically defined as the group of central simple $Q_{p}$-algebras, can be reinterpreted as a Galois cohomology group, namely

K-theory
Milnor K-theory is defined as
 * $$K_n^M(F) = F^\times \otimes \cdots \otimes F^\times / \left\langle x \otimes (1-x) \mid x \in F \smallsetminus \{0, 1\} \right\rangle.$$

The norm residue isomorphism theorem, proved around 2000 by Vladimir Voevodsky, relates this to Galois cohomology by means of an isomorphism
 * $$K_n^M(F) / p = H^n(F, \mu_l^{\otimes n}).$$

Algebraic K-theory is related to the group of invertible matrices with coefficients the given field. For example, the process of taking the determinant of an invertible matrix leads to an isomorphism $C_{p}$. Matsumoto's theorem shows that $R$ agrees with $C$. In higher degrees, K-theory diverges from Milnor K-theory and remains hard to compute in general.

Linear algebra and commutative algebra
If $Q_{p}$, then the equation

has a unique solution $F_{p}((t))$ in a field $F_{p}$, namely $$x=a^{-1}b.$$ This immediate consequence of the definition of a field is fundamental in linear algebra. For example, it is an essential ingredient of Gaussian elimination and of the proof that any vector space has a basis.

The theory of modules (the analogue of vector spaces over rings instead of fields) is much more complicated, because the above equation may have several or no solutions. In particular systems of linear equations over a ring are much more difficult to solve than in the case of fields, even in the specially simple case of the ring $p$ of the integers.

Finite fields: cryptography and coding theory
A widely applied cryptographic routine uses the fact that discrete exponentiation, i.e., computing
 * $p ∈ Q_{p}$ ($t ∈ F_{p}((t))$ factors, for an integer $F_{p}$)

in a (large) finite field $Q_{p}$ can be performed much more efficiently than the discrete logarithm, which is the inverse operation, i.e., determining the solution $F_{p}((t))$ to an equation

In elliptic curve cryptography, the multiplication in a finite field is replaced by the operation of adding points on an elliptic curve, i.e., the solutions of an equation of the form

Finite fields are also used in coding theory and combinatorics.

Geometry: field of functions
Functions on a suitable topological space $Q_{p}$ into a field $F$ can be added and multiplied pointwise, e.g., the product of two functions is defined by the product of their values within the domain:

This makes these functions a $F_{p}((t))$-commutative algebra.

For having a field of functions, one must consider algebras of functions that are integral domains. In this case the ratios of two functions, i.e., expressions of the form
 * $$\frac{f(x)}{g(x)},$$

form a field, called field of functions.

This occurs in two main cases. When $Q_{p}$ is a complex manifold $p$. In this case, one considers the algebra of holomorphic functions, i.e., complex differentiable functions. Their ratios form the field of meromorphic functions on $p$.

The function field of an algebraic variety $Q_{p}$ (a geometric object defined as the common zeros of polynomial equations) consists of ratios of regular functions, i.e., ratios of polynomial functions on the variety. The function field of the $t$-dimensional space over a field $F_{p}((t))$ is $R(X)$, i.e., the field consisting of ratios of polynomials in $F / E$ indeterminates. The function field of $F = E[X] / (X)$ is the same as the one of any open dense subvariety. In other words, the function field is insensitive to replacing $f$ by a (slightly) smaller subvariety.

The function field is invariant under isomorphism and birational equivalence of varieties. It is therefore an important tool for the study of abstract algebraic varieties and for the classification of algebraic varieties. For example, the dimension, which equals the transcendence degree of $f$, is invariant under birational equivalence. For curves (i.e., the dimension is one), the function field $F$ is very close to $f$: if $E$ is smooth and proper (the analogue of being compact), $0$ can be reconstructed, up to isomorphism, from its field of functions. In higher dimension the function field remembers less, but still decisive information about $Gal(F/E)$. The study of function fields and their geometric meaning in higher dimensions is referred to as birational geometry. The minimal model program attempts to identify the simplest (in a certain precise sense) algebraic varieties with a prescribed function field.

Number theory: global fields
Global fields are in the limelight in algebraic number theory and arithmetic geometry. They are, by definition, number fields (finite extensions of $F$) or function fields over $E$ (finite extensions of $σ : F → F$). As for local fields, these two types of fields share several similar features, even though they are of characteristic $E$ and positive characteristic, respectively. This function field analogy can help to shape mathematical expectations, often first by understanding questions about function fields, and later treating the number field case. The latter is often more difficult. For example, the Riemann hypothesis concerning the zeros of the Riemann zeta function (open as of 2017) can be regarded as being parallel to the Weil conjectures (proven in 1974 by Pierre Deligne).

Cyclotomic fields are among the most intensely studied number fields. They are of the form $Gal(F/E)$, where $F/E$ is a primitive $f$th root of unity, i.e., a complex number $S_{n}$ that satisfies $n ≥ 5$ and $f(X) = X^{5} − 4X + 2$ for all $E = Q$. For $f(X) = ^{n} + a_{n−1}^{n−1} + ⋯ + a_{0}$ being a regular prime, Kummer used cyclotomic fields to prove Fermat's Last Theorem, which asserts the non-existence of rational nonzero solutions to the equation

Local fields are completions of global fields. Ostrowski's theorem asserts that the only completions of $f$, a global field, are the local fields $E(a_{0}, ..., a_{n−1})$ and $a_{i}$. Studying arithmetic questions in global fields may sometimes be done by looking at the corresponding questions locally. This technique is called the local–global principle. For example, the Hasse–Minkowski theorem reduces the problem of finding rational solutions of quadratic equations to solving these equations in $E$ and $n ≥ 5$, whose solutions can easily be described.

Unlike for local fields, the Galois groups of global fields are not known. Inverse Galois theory studies the (unsolved) problem whether any finite group is the Galois group $F / E$ for some number field $n$. Class field theory describes the abelian extensions, i.e., ones with abelian Galois group, or equivalently the abelianized Galois groups of global fields. A classical statement, the Kronecker–Weber theorem, describes the maximal abelian $F$ extension of $F ⊗_{E} F ≅ F^{n}$: it is the field

obtained by adjoining all primitive $F$th roots of unity. Kronecker's Jugendtraum asks for a similarly explicit description of $F$ of general number fields $F$. For imaginary quadratic fields, $$F=\mathbf Q(\sqrt{-d})$$, $E$, the theory of complex multiplication describes $F$ using elliptic curves. For general number fields, no such explicit description is known.

Related notions
In addition to the additional structure that fields may enjoy, fields admit various other related notions. Since in any field $\overline{Q}_{p}, C_{p}$, any field has at least two elements. Nonetheless, there is a concept of field with one element, which is suggested to be a limit of the finite fields $C$, as $E$ tends to $F$. In addition to division rings, there are various other weaker algebraic structures related to fields such as quasifields, near-fields and semifields.

There are also proper classes with field structure, which are sometimes called Fields, with a capital 'F'. The surreal numbers form a Field containing the reals, and would be a field except for the fact that they are a proper class, not a set. The nimbers, a concept from game theory, form such a Field as well.

Division rings
Dropping one or several axioms in the definition of a field leads to other algebraic structures. As was mentioned above, commutative rings satisfy all field axioms except for the existence of multiplicative inverses. Dropping instead commutativity of multiplication leads to the concept of a division ring or skew field; sometimes associativity is weakened as well. The only division rings that are finite-dimensional $E$-vector spaces are $F$ itself, $0$ (which is a field), and the quaternions $1$ (in which multiplication is non-commutative). This result is known as the Frobenius theorem. The octonions $n > 0$, for which multiplication is neither commutative nor associative, is a normed alternative division algebra, but is not a division ring. This fact was proved using methods of algebraic topology in 1958 by Michel Kervaire, Raoul Bott, and John Milnor.

title: Field (mathematics)


text:
Factorial

In mathematics, the factorial of a non-negative integer $n$, denoted by $n!$, is the product of all positive integers less than or equal to $n$. The factorial of $n$ also equals the product of $$n$$ with the next smaller factorial: $$ \begin{align} n! &= n \times  (n-1)  \times (n-2)  \times  (n-3) \times \cdots \times  3 \times  2 \times  1 \\ &= n\times(n-1)!\\ \end{align}$$ For example, $$5! = 5\times 4! = 5 \times  4  \times  3  \times  2  \times  1 = 120. $$ The value of 0! is 1, according to the convention for an empty product.

Factorials have been discovered in several ancient cultures, notably in Indian mathematics in the canonical works of Jain literature, and by Jewish mystics in the Talmudic book Sefer Yetzirah. The factorial operation is encountered in many areas of mathematics, notably in combinatorics, where its most basic use counts the possible distinct sequences – the permutations – of $$n$$ distinct objects: there are $n!$. In mathematical analysis, factorials are used in power series for the exponential function and other functions, and they also have applications in algebra, number theory, probability theory, and computer science.

Much of the mathematics of the factorial function was developed beginning in the late 18th and early 19th centuries. Stirling's approximation provides an accurate approximation to the factorial of large numbers, showing that it grows more quickly than exponential growth. Legendre's formula describes the exponents of the prime numbers in a prime factorization of the factorials, and can be used to count the trailing zeros of the factorials. Daniel Bernoulli and Leonhard Euler interpolated the factorial function to a continuous function of complex numbers, except at the negative integers, the (offset) gamma function.

Many other notable functions and number sequences are closely related to the factorials, including the binomial coefficients, double factorials, falling factorials, primorials, and subfactorials. Implementations of the factorial function are commonly used as an example of different computer programming styles, and are included in scientific calculators and scientific computing software libraries. Although directly computing large factorials using the product formula or recurrence is not efficient, faster algorithms are known, matching to within a constant factor the time for fast multiplication algorithms for numbers with the same number of digits.

History
The concept of factorials has arisen independently in many cultures:
 * In Indian mathematics, one of the earliest known descriptions of factorials comes from the Anuyogadvāra-sūtra, one of the canonical works of Jain literature, which has been assigned dates varying from 300 BCE to 400 CE. It separates out the sorted and reversed order of a set of items from the other ("mixed") orders, evaluating the number of mixed orders by subtracting two from the usual product formula for the factorial. The product rule for permutations was also described by 6th-century CE Jain monk Jinabhadra. Hindu scholars have been using factorial formulas since at least 1150, when Bhāskara II mentioned factorials in his work Līlāvatī, in connection with a problem of how many ways Vishnu could hold his four characteristic objects (a conch shell, discus, mace, and lotus flower) in his four hands, and a similar problem for a ten-handed god.
 * In the mathematics of the Middle East, the Hebrew mystic book of creation Sefer Yetzirah, from the Talmudic period (200 to 500 CE), lists factorials up to 7! as part of an investigation into the number of words that can be formed from the Hebrew alphabet. Factorials were also studied for similar reasons by 8th-century Arab grammarian Al-Khalil ibn Ahmad al-Farahidi. Arab mathematician Ibn al-Haytham (also known as Alhazen, c. 965 – c. 1040) was the first to formulate Wilson's theorem connecting the factorials with the prime numbers.
 * In Europe, although Greek mathematics included some combinatorics, and Plato famously used 5,040 (a factorial) as the population of an ideal community, in part because of its divisibility properties, there is no direct evidence of ancient Greek study of factorials. Instead, the first work on factorials in Europe was by Jewish scholars such as Shabbethai Donnolo, explicating the Sefer Yetzirah passage. In 1677, British author Fabian Stedman described the application of factorials to change ringing, a musical art involving the ringing of several tuned bells.

From the late 15th century onward, factorials became the subject of study by Western mathematicians. In a 1494 treatise, Italian mathematician Luca Pacioli calculated factorials up to 11!, in connection with a problem of dining table arrangements. Christopher Clavius discussed factorials in a 1603 commentary on the work of Johannes de Sacrobosco, and in the 1640s, French polymath Marin Mersenne published large (but not entirely correct) tables of factorials, up to 64!, based on the work of Clavius. The power series for the exponential function, with the reciprocals of factorials for its coefficients, was first formulated in 1676 by Isaac Newton in a letter to Gottfried Wilhelm Leibniz. Other important works of early European mathematics on factorials include extensive coverage in a 1685 treatise by John Wallis, a study of their approximate values for large values of $$n$$ by Abraham de Moivre in 1721, a 1729 letter from James Stirling to de Moivre stating what became known as Stirling's approximation, and work at the same time by Daniel Bernoulli and Leonhard Euler formulating the continuous extension of the factorial function to the gamma function. Adrien-Marie Legendre included Legendre's formula, describing the exponents in the factorization of factorials into prime powers, in an 1808 text on number theory.

The notation $$n!$$ for factorials was introduced by the French mathematician Christian Kramp in 1808. Many other notations have also been used. Another later notation $$\vert\!\underline{\,n}$$, in which the argument of the factorial was half-enclosed by the left and bottom sides of a box, was popular for some time in Britain and America but fell out of use, perhaps because it is difficult to typeset. The word "factorial" (originally French: factorielle) was first used in 1800 by Louis François Antoine Arbogast, in the first work on Faà di Bruno's formula, but referring to a more general concept of products of arithmetic progressions. The "factors" that this name refers to are the terms of the product formula for the factorial.

Definition
The factorial function of a positive integer $$n$$ is defined by the product of all positive integers not greater than $$n$$ $$n! = 1 \cdot 2 \cdot 3 \cdots (n-2) \cdot (n-1) \cdot n.$$ This may be written more concisely in product notation as $$n! = \prod_{i = 1}^n i.$$

If this product formula is changed to keep all but the last term, it would define a product of the same form, for a smaller factorial. This leads to a recurrence relation, according to which each value of the factorial function can be obtained by multiplying the previous value by $n$: $$ n! = n\cdot (n-1)!.$$ For example, $5! = 5\cdot 4!=5\cdot 24=120$.

Factorial of zero
The factorial of $0$ is $1$, or in symbols, $0!=1$. There are several motivations for this definition:
 * For $n=0$, the definition of $$n!$$ as a product involves the product of no numbers at all, and so is an example of the broader convention that the empty product, a product of no factors, is equal to the multiplicative identity.
 * There is exactly one permutation of zero objects: with nothing to permute, the only rearrangement is to do nothing.
 * This convention makes many identities in combinatorics valid for all valid choices of their parameters. For instance, the number of ways to choose all $$n$$ elements from a set of $$n$$ is $\tbinom{n}{n} = \tfrac{n!}{n!0!} = 1,$ a binomial coefficient identity that would only be valid with $0!=1$.
 * With $0!=1$, the recurrence relation for the factorial remains valid at $n=1$. Therefore, with this convention, a recursive computation of the factorial needs to have only the value for zero as a base case, simplifying the computation and avoiding the need for additional special cases.
 * Setting $$0!=1$$ allows for the compact expression of many formulae, such as the exponential function, as a power series: $ e^x = \sum_{n = 0}^\infty \frac{x^n}{n!}.$
 * This choice matches the gamma function $0! = \Gamma(0+1) = 1$, and the gamma function must have this value to be a continuous function.

Applications
The earliest uses of the factorial function involve counting permutations: there are $$n!$$ different ways of arranging $$n$$ distinct objects into a sequence. Factorials appear more broadly in many formulas in combinatorics, to account for different orderings of objects. For instance the binomial coefficients $$\tbinom{n}{k}$$ count the $k$-element combinations (subsets of $k$ elements) from a set with $n$ elements, and can be computed from factorials using the formula $$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$$ The Stirling numbers of the first kind sum to the factorials, and count the permutations of $n$ grouped into subsets with the same numbers of cycles. Another combinatorial application is in counting derangements, permutations that do not leave any element in its original position; the number of derangements of $$n$$ items is the nearest integer to $n!/e$.

In algebra, the factorials arise through the binomial theorem, which uses binomial coefficients to expand powers of sums. They also occur in the coefficients used to relate certain families of polynomials to each other, for instance in Newton's identities for symmetric polynomials. Their use in counting permutations can also be restated algebraically: the factorials are the orders of finite symmetric groups. In calculus, factorials occur in Faà di Bruno's formula for chaining higher derivatives. In mathematical analysis, factorials frequently appear in the denominators of power series, most notably in the series for the exponential function, $$e^x=1+\frac{x}{1}+\frac{x^2}{2}+\frac{x^3}{6}+\cdots=\sum_{i=0}^{\infty}\frac{x^i}{i!},$$ and in the coefficients of other Taylor series (in particular those of the trigonometric and hyperbolic functions), where they cancel factors of $$n!$$ coming from the $n$th derivative of $x^n$. This usage of factorials in power series connects back to analytic combinatorics through the exponential generating function, which for a combinatorial class with $$n_i$$ elements of size $i$ is defined as the power series $$\sum_{i=0}^{\infty} \frac{x^i n_i}{i!}.$$

In number theory, the most salient property of factorials is the divisibility of $$n!$$ by all positive integers up to $n$, described more precisely for prime factors by Legendre's formula. It follows that arbitrarily large prime numbers can be found as the prime factors of the numbers $$n!\pm 1$$, leading to a proof of Euclid's theorem that the number of primes is infinite. When $$n!\pm 1$$ is itself prime it is called a factorial prime; relatedly, Brocard's problem, also posed by Srinivasa Ramanujan, concerns the existence of square numbers of the form $n!+1$. In contrast, the numbers $$n!+2,n!+3,\dots n!+n$$ must all be composite, proving the existence of arbitrarily large prime gaps. An elementary proof of Bertrand's postulate on the existence of a prime in any interval of the form $[n,2n]$, one of the first results of Paul Erdős, was based on the divisibility properties of factorials. The factorial number system is a mixed radix notation for numbers in which the place values of each digit are factorials.

Factorials are used extensively in probability theory, for instance in the Poisson distribution and in the probabilities of random permutations. In computer science, beyond appearing in the analysis of brute-force searches over permutations, factorials arise in the lower bound of $$\log_2 n!=n\log_2n-O(n)$$ on the number of comparisons needed to comparison sort a set of $$n$$ items, and in the analysis of chained hash tables, where the distribution of keys per cell can be accurately approximated by a Poisson distribution. Moreover, factorials naturally appear in formulae from quantum and statistical physics, where one often considers all the possible permutations of a set of particles. In statistical mechanics, calculations of entropy such as Boltzmann's entropy formula or the Sackur–Tetrode equation must correct the count of microstates by dividing by the factorials of the numbers of each type of indistinguishable particle to avoid the Gibbs paradox. Quantum physics provides the underlying reason for why these corrections are necessary.

Growth and approximation

As a function of $n$, the factorial has faster than exponential growth, but grows more slowly than a double exponential function. Its growth rate is similar to $n^n$, but slower by an exponential factor. One way of approaching this result is by taking the natural logarithm of the factorial, which turns its product formula into a sum, and then estimating the sum by an integral: $$\ln n! = \sum_{x=1}^n \ln x \approx \int_1^n\ln x\, dx=n\ln n-n+1.$$ Exponentiating the result (and ignoring the negligible $$+1$$ term) approximates $$n!$$ as $(n/e)^n$. More carefully bounding the sum both above and below by an integral, using the trapezoid rule, shows that this estimate needs a correction factor proportional to $\sqrt n$. The constant of proportionality for this correction can be found from the Wallis product, which expresses $$\pi$$ as a limiting ratio of factorials and powers of two. The result of these corrections is Stirling's approximation: $$n!\sim\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\,.$$ Here, the $$\sim$$ symbol means that, as $$n$$ goes to infinity, the ratio between the left and right sides approaches one in the limit. Stirling's formula provides the first term in an asymptotic series that becomes even more accurate when taken to greater numbers of terms: $$ n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n \left(1 +\frac{1}{12n}+\frac{1}{288n^2} - \frac{139}{51840n^3} -\frac{571}{2488320n^4}+ \cdots \right).$$ An alternative version uses only odd exponents in the correction terms: $$ n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n \exp\left(\frac{1}{12n} - \frac{1}{360n^3} + \frac{1}{1260n^5} -\frac{1}{1680n^7}+ \cdots \right).$$ Many other variations of these formulas have also been developed, by Srinivasa Ramanujan, Bill Gosper, and others.

The binary logarithm of the factorial, used to analyze comparison sorting, can be very accurately estimated using Stirling's approximation. In the formula below, the $$O(1)$$ term invokes big O notation. $$\log_2 n! = n\log_2 n-(\log_2 e)n + \frac12\log_2 n + O(1).$$

Divisibility and digits
The product formula for the factorial implies that $$n!$$ is divisible by all prime numbers that are at most $n$, and by no larger prime numbers. More precise information about its divisibility is given by Legendre's formula, which gives the exponent of each prime $$p$$ in the prime factorization of $$n!$$ as $$\sum_{i=1}^\infty \left \lfloor \frac n {p^i} \right \rfloor=\frac{n - s_p(n)}{p - 1}.$$ Here $$s_p(n)$$ denotes the sum of the base-$p$ digits of $n$, and the exponent given by this formula can also be interpreted in advanced mathematics as the $5,040$-adic valuation of the factorial. Applying Legendre's formula to the product formula for binomial coefficients produces Kummer's theorem, a similar result on the exponent of each prime in the factorization of a binomial coefficient. Grouping the prime factors of the factorial into prime powers in different ways produces the multiplicative partitions of factorials.

The special case of Legendre's formula for $$p=5$$ gives the number of trailing zeros in the decimal representation of the factorials. According to this formula, the number of zeros can be obtained by subtracting the base-5 digits of $$n$$ from $$n$$, and dividing the result by four. Legendre's formula implies that the exponent of the prime $$p=2$$ is always larger than the exponent for $p=5$, so each factor of five can be paired with a factor of two to produce one of these trailing zeros. The leading digits of the factorials are distributed according to Benford's law. Every sequence of digits, in any base, is the sequence of initial digits of some factorial number in that base.

Another result on divisibility of factorials, Wilson's theorem, states that $$(n-1)!+1$$ is divisible by $$n$$ if and only if $$n$$ is a prime number. For any given integer $x$, the Kempner function of $$x$$ is given by the smallest $$n$$ for which $$x$$ divides $n!$. For almost all numbers (all but a subset of exceptions with asymptotic density zero), it coincides with the largest prime factor of $x$.

The product of two factorials, $m!\cdot n!$, always evenly divides $(m+n)!$. There are infinitely many factorials that equal the product of other factorials: if $$n$$ is itself any product of factorials, then $$n!$$ equals that same product multiplied by one more factorial, $(n-1)!$. The only known examples of factorials that are products of other factorials but are not of this "trivial" form are $9!=7!\cdot 3!\cdot 3!\cdot 2!$, $10!=7!\cdot 6!=7!\cdot 5!\cdot 3!$, and $16!=14!\cdot 5!\cdot 2!$. It would follow from the $40,320$ conjecture that there are only finitely many nontrivial examples.

The greatest common divisor of the values of a primitive polynomial of degree $$d$$ over the integers evenly divides $d!$.

Continuous interpolation and non-integer generalization

There are infinitely many ways to extend the factorials to a continuous function. The most widely used of these uses the gamma function, which can be defined for positive real numbers as the integral $$ \Gamma(z) = \int_0^\infty x^{z-1} e^{-x}\,dx.$$ The resulting function is related to the factorial of a non-negative integer $$n$$ by the equation $$ n!=\Gamma(n+1),$$ which can be used as a definition of the factorial for non-integer arguments. At all values $$x$$ for which both $$\Gamma(x)$$ and $$\Gamma(x-1)$$ are defined, the gamma function obeys the functional equation $$ \Gamma(n)=(n-1)\Gamma(n-1),$$ generalizing the recurrence relation for the factorials.

The same integral converges more generally for any complex number $$z$$ whose real part is positive. It can be extended to the non-integer points in the rest of the complex plane by solving for Euler's reflection formula $$\Gamma(z)\Gamma(1-z)=\frac{\pi}{\sin\pi z}.$$ However, this formula cannot be used at integers because, for them, the $$\sin\pi z$$ term would produce a division by zero. The result of this extension process is an analytic function, the analytic continuation of the integral formula for the gamma function. It has a nonzero value at all complex numbers, except for the non-positive integers where it has simple poles. Correspondingly, this provides a definition for the factorial at all complex numbers other than the negative integers. One property of the gamma function, distinguishing it from other continuous interpolations of the factorials, is given by the Bohr–Mollerup theorem, which states that the gamma function (offset by one) is the only log-convex function on the positive real numbers that interpolates the factorials and obeys the same functional equation. A related uniqueness theorem of Helmut Wielandt states that the complex gamma function and its scalar multiples are the only holomorphic functions on the positive complex half-plane that obey the functional equation and remain bounded for complex numbers with real part between 1 and 2.

Other complex functions that interpolate the factorial values include Hadamard's gamma function, which is an entire function over all the complex numbers, including the non-positive integers. In the $362,880$-adic numbers, it is not possible to continuously interpolate the factorial function directly, because the factorials of large integers (a dense subset of the $3,628,800$-adics) converge to zero according to Legendre's formula, forcing any continuous function that is close to their values to be zero everywhere. Instead, the $39,916,800$-adic gamma function provides a continuous interpolation of a modified form of the factorial, omitting the factors in the factorial that are divisible by $479,001,600$.

The digamma function is the logarithmic derivative of the gamma function. Just as the gamma function provides a continuous interpolation of the factorials, offset by one, the digamma function provides a continuous interpolation of the harmonic numbers, offset by the Euler–Mascheroni constant.

Computation
The factorial function is a common feature in scientific calculators. It is also included in scientific programming libraries such as the Python mathematical functions module and the Boost C++ library. If efficiency is not a concern, computing factorials is trivial: just successively multiply a variable initialized to $1$ by the integers up to $n$. The simplicity of this computation makes it a common example in the use of different computer programming styles and methods.

The computation of $$n!$$ can be expressed in pseudocode using iteration as define factorial(n): f := 1 for i := 1, 2, 3, ..., n: f := f * i return f or using recursion based on its recurrence relation as define factorial(n): if (n = 0) return 1 return n * factorial(n − 1) Other methods suitable for its computation include memoization, dynamic programming, and functional programming. The computational complexity of these algorithms may be analyzed using the unit-cost random-access machine model of computation, in which each arithmetic operation takes constant time and each number uses a constant amount of storage space. In this model, these methods can compute $$n!$$ in time $O(n)$, and the iterative version uses space $O(1)$. Unless optimized for tail recursion, the recursive version takes linear space to store its call stack. However, this model of computation is only suitable when $$n$$ is small enough to allow $$n!$$ to fit into a machine word. The values 12! and 20! are the largest factorials that can be stored in, respectively, the 32-bit and 64-bit integers. Floating point can represent larger factorials, but approximately rather than exactly, and will still overflow for factorials larger than $170!$.

The exact computation of larger factorials involves arbitrary-precision arithmetic, because of fast growth and integer overflow. Time of computation can be analyzed as a function of the number of digits or bits in the result. By Stirling's formula, $$n!$$ has $$b = O(n\log n)$$ bits. The Schönhage–Strassen algorithm can produce a $b$-bit product in time $O(b\log b\log\log b)$, and faster multiplication algorithms taking time $$O(b\log b)$$ are known. However, computing the factorial involves repeated products, rather than a single multiplication, so these time bounds do not apply directly. In this setting, computing $$n!$$ by multiplying the numbers from 1 to $n$ in sequence is inefficient, because it involves $$n$$ multiplications, a constant fraction of which take time $$O(n\log^2 n)$$ each, giving total time $O(n^2\log^2 n)$. A better approach is to perform the multiplications as a divide-and-conquer algorithm that multiplies a sequence of $$i$$ numbers by splitting it into two subsequences of $$i/2$$ numbers, multiplies each subsequence, and combines the results with one last multiplication. This approach to the factorial takes total time $O(n\log^3 n)$: one logarithm comes from the number of bits in the factorial, a second comes from the multiplication algorithm, and a third comes from the divide and conquer.

Even better efficiency is obtained by computing $S_{n}$ from its prime factorization, based on the principle that exponentiation by squaring is faster than expanding an exponent into a product. An algorithm for this by Arnold Schönhage begins by finding the list of the primes up to $n$, for instance using the sieve of Eratosthenes, and uses Legendre's formula to compute the exponent for each prime. Then it computes the product of the prime powers with these exponents, using a recursive algorithm, as follows: The product of all primes up to $$n$$ is an $$O(n)$$-bit number, by the prime number theorem, so the time for the first step is $$O(n\log^2 n)$$, with one logarithm coming from the divide and conquer and another coming from the multiplication algorithm. In the recursive calls to the algorithm, the prime number theorem can again be invoked to prove that the numbers of bits in the corresponding products decrease by a constant factor at each level of recursion, so the total time for these steps at all levels of recursion adds in a geometric series to $O(n\log^2 n)$. The time for the squaring in the second step and the multiplication in the third step are again $O(n\log^2 n)$, because each is a single multiplication of a number with $$O(n\log n)$$ bits. Again, at each level of recursion the numbers involved have a constant fraction as many bits (because otherwise repeatedly squaring them would produce too large a final result) so again the amounts of time for these steps in the recursive calls add in a geometric series to $O(n\log^2 n)$. Consequentially, the whole algorithm takes time $O(n\log^2 n)$, proportional to a single multiplication with the same number of bits in its result.
 * Use divide and conquer to compute the product of the primes whose exponents are odd
 * Divide all of the exponents by two (rounding down to an integer), recursively compute the product of the prime powers with these smaller exponents, and square the result
 * Multiply together the results of the two previous steps

Related sequences and functions
Several other integer sequences are similar to or related to the factorials:

 * Alternating factorial
 * The alternating factorial is the absolute value of the alternating sum of the first $$n$$ factorials, $\sum_{i = 1}^n (-1)^{n - i}i!$. These have mainly been studied in connection with their primality; only finitely many of them can be prime, but a complete list of primes of this form is not known.

 * Bhargava factorial
 * The Bhargava factorials are a family of integer sequences defined by Manjul Bhargava with similar number-theoretic properties to the factorials, including the factorials themselves as a special case.

 * Double factorial
 * The product of all the odd integers up to some odd positive integer $n$ is called the double factorial of $n$, and denoted by $n!!$. That is, $$(2k-1)!! = \prod_{i=1}^k (2i-1) = \frac{(2k)!}{2^k k!}.$$ For example, 9!! = 1 × 3 × 5 × 7 × 9 = 945. Double factorials are used in trigonometric integrals, in expressions for the gamma function at half-integers and the volumes of hyperspheres, and in counting binary trees and perfect matchings.
 * Exponential factorial
 * Just as triangular numbers sum the numbers from $$1$$ to $n$, and factorials take their product, the exponential factorial exponentiates. The exponential factorial is defined recursively as $a_0 = 1,\ a_n = n^{a_{n - 1}}$.|undefined For example, the exponential factorial of 4 is $$4^{3^{2^{1}}}=262144.$$ These numbers grow much more quickly than regular factorials.

 * Falling factorial
 * The notations $$(x)_{n}$$ or $$x^{\underline n}$$ are sometimes used to represent the product of the $$n$$ integers counting up to and including $x$, equal to $x!/(x-n)!$. This is also known as a falling factorial or backward factorial, and the $$(x)_{n}$$ notation is a Pochhammer symbol. Falling factorials count the number of different sequences of $$n$$ distinct items that can be drawn from a universe of $$x$$ items. They occur as coefficients in the higher derivatives of polynomials, and in the factorial moments of random variables.

 * Hyperfactorials
 * The hyperfactorial of $$n$$ is the product $$1^1\cdot 2^2\cdots n^n$$. These numbers form the discriminants of Hermite polynomials. They can be continuously interpolated by the K-function, and obey analogues to Stirling's formula and Wilson's theorem.

 * Jordan–Pólya numbers
 * The Jordan–Pólya numbers are the products of factorials, allowing repetitions. Every tree has a symmetry group whose number of symmetries is a Jordan–Pólya number, and every Jordan–Pólya number counts the symmetries of some tree.

 * Primorial
 * The primorial $$n\#$$ is the product of prime numbers less than or equal to $n$; this construction gives them some similar divisibility properties to factorials, but unlike factorials they are squarefree. As with the factorial primes $n!\pm 1$, researchers have studied primorial primes $n\#\pm 1$.

 * Subfactorial
 * The subfactorial yields the number of derangements of a set of $$n$$ objects. It is sometimes denoted $$!n$$, and equals the closest integer to $n!/e$.

 * Superfactorial
 * The superfactorial of $$n$$ is the product of the first $$n$$ factorials. The superfactorials are continuously interpolated by the Barnes G-function.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Factorial