HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, a formal series is an infinite sum that is considered independently from any notion of
convergence Convergence may refer to: Arts and media Literature *''Convergence'' (book series), edited by Ruth Nanda Anshen *Convergence (comics), "Convergence" (comics), two separate story lines published by DC Comics: **A four-part crossover storyline that ...
, and can be manipulated with the usual algebraic operations on series (addition, subtraction, multiplication, division, partial sums, etc.). A formal power series is a special kind of formal series, of the form \sum_^\infty a_nx^n=a_0+a_1x+ a_2x^2+\cdots, where the a_n, called ''coefficients'', are numbers or, more generally, elements of some ring, and the x^n are formal powers of the symbol x that is called an indeterminate or, commonly, a variable. Hence, power series can be viewed as a generalization of
polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
s where the number of terms is allowed to be infinite, and differ from usual power series by the absence of convergence requirements, which implies that a power series may not represent a function of its variable. Formal power series are in one to one correspondence with their
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...
s of coefficients, but the two concepts must not be confused, since the operations that can be applied are different. A formal power series with coefficients in a ring R is called a formal power series over R. The formal power series over a ring R form a ring, commonly denoted by R x. (It can be seen as the -adic completion of the
polynomial ring In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates (traditionally also called variables) with coefficients in another ring, ...
R in the same way as the -adic integers are the -adic completion of the ring of the integers.) Formal powers series in several indeterminates are defined similarly by replacing the powers of a single indeterminate by monomials in several indeterminates. Formal power series are widely used in
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
for representing sequences of integers as generating functions. In this context, a
recurrence relation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
between the elements of a sequence may often be interpreted as a differential equation that the generating function satisfies. This allows using methods of
complex analysis Complex analysis, traditionally known as the theory of functions of a complex variable, is the branch of mathematical analysis that investigates functions of complex numbers. It is helpful in many branches of mathematics, including algebraic ...
for combinatorial problems (see analytic combinatorics).


Introduction

A formal power series can be loosely thought of as an object that is like a
polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
, but with infinitely many terms. Alternatively, for those familiar with power series (or Taylor series), one may think of a formal power series as a power series in which we ignore questions of
convergence Convergence may refer to: Arts and media Literature *''Convergence'' (book series), edited by Ruth Nanda Anshen *Convergence (comics), "Convergence" (comics), two separate story lines published by DC Comics: **A four-part crossover storyline that ...
by not assuming that the variable ''X'' denotes any numerical value (not even an unknown value). For example, consider the series A = 1 - 3X + 5X^2 - 7X^3 + 9X^4 - 11X^5 + \cdots. If we studied this as a power series, its properties would include, for example, that its radius of convergence is 1 by the Cauchy–Hadamard theorem. However, as a formal power series, we may ignore this completely; all that is relevant is the sequence of
coefficient In mathematics, a coefficient is a Factor (arithmetic), multiplicative factor involved in some Summand, term of a polynomial, a series (mathematics), series, or any other type of expression (mathematics), expression. It may be a Dimensionless qu ...
s , −3, 5, −7, 9, −11, ... In other words, a formal power series is an object that just records a sequence of coefficients. It is perfectly acceptable to consider a formal power series with the
factorial In mathematics, the factorial of a non-negative denoted is the Product (mathematics), product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times ...
s , 1, 2, 6, 24, 120, 720, 5040, ... as coefficients, even though the corresponding power series diverges for any nonzero value of ''X''. Algebra on formal power series is carried out by simply pretending that the series are polynomials. For example, if :B = 2X + 4X^3 + 6X^5 + \cdots, then we add ''A'' and ''B'' term by term: :A + B = 1 - X + 5X^2 - 3X^3 + 9X^4 - 5X^5 + \cdots. We can multiply formal power series, again just by treating them as polynomials (see in particular
Cauchy product In mathematics, more specifically in mathematical analysis, the Cauchy product is the discrete convolution of two infinite series. It is named after the French mathematician Augustin-Louis Cauchy. Definitions The Cauchy product may apply to infin ...
): :AB = 2X - 6X^2 + 14X^3 - 26X^4 + 44X^5 + \cdots. Notice that each coefficient in the product ''AB'' only depends on a ''finite'' number of coefficients of ''A'' and ''B''. For example, the ''X''5 term is given by :44X^5 = (1\times 6X^5) + (5X^2 \times 4X^3) + (9X^4 \times 2X). For this reason, one may multiply formal power series without worrying about the usual questions of absolute, conditional and uniform convergence which arise in dealing with power series in the setting of
analysis Analysis (: analyses) is the process of breaking a complex topic or substance into smaller parts in order to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle (38 ...
. Once we have defined multiplication for formal power series, we can define multiplicative inverses as follows. The multiplicative inverse of a formal power series ''A'' is a formal power series ''C'' such that ''AC'' = 1, provided that such a formal power series exists. It turns out that if ''A'' has a multiplicative inverse, it is unique, and we denote it by ''A''−1. Now we can define division of formal power series by defining ''B''/''A'' to be the product ''BA''−1, provided that the inverse of ''A'' exists. For example, one can use the definition of multiplication above to verify the familiar formula :\frac = 1 - X + X^2 - X^3 + X^4 - X^5 + \cdots. An important operation on formal power series is coefficient extraction. In its most basic form, the coefficient extraction operator ^n/math> applied to a formal power series A in one variable extracts the coefficient of the nth power of the variable, so that ^2=5 and ^5=-11. Other examples include :\begin \left ^3\right(B) &= 4, \\ \left ^2 \right(X + 3 X^2 Y^3 + 10 Y^6) &= 3Y^3, \\ \left ^2Y^3 \right( X + 3 X^2 Y^3 + 10 Y^6) &= 3, \\ \left ^n \right\left(\frac \right) &= (-1)^n, \\ \left ^n \right\left(\frac \right) &= n. \end Similarly, many other operations that are carried out on polynomials can be extended to the formal power series setting, as explained below.


The ring of formal power series

If one considers the set of all formal power series in ''X'' with coefficients in a
commutative ring In mathematics, a commutative ring is a Ring (mathematics), ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring prope ...
''R'', the elements of this set collectively constitute another ring which is written R X, and called the ring of formal power series in the variable ''X'' over ''R''.


Definition of the formal power series ring

One can characterize R X abstractly as the completion of the
polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
ring R /math> equipped with a particular metric. This automatically gives R X the structure of a topological ring (and even of a complete metric space). But the general construction of a completion of a metric space is more involved than what is needed here, and would make formal power series seem more complicated than they are. It is possible to describe R X more explicitly, and define the ring structure and topological structure separately, as follows.


Ring structure

As a set, R X can be constructed as the set R^\N of all infinite sequences of elements of R, indexed by the
natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
s (taken to include 0). Designating a sequence whose term at index n is a_n by (a_n), one defines addition of two such sequences by :(a_n)_ + (b_n)_ = \left( a_n + b_n \right)_ and multiplication by :(a_n)_ \times (b_n)_ = \left( \sum_^n a_k b_ \right)_. This type of product is called the
Cauchy product In mathematics, more specifically in mathematical analysis, the Cauchy product is the discrete convolution of two infinite series. It is named after the French mathematician Augustin-Louis Cauchy. Definitions The Cauchy product may apply to infin ...
of the two sequences of coefficients, and is a sort of discrete
convolution In mathematics (in particular, functional analysis), convolution is a operation (mathematics), mathematical operation on two function (mathematics), functions f and g that produces a third function f*g, as the integral of the product of the two ...
. With these operations, R^\N becomes a commutative ring with zero element (0,0,0,\ldots) and multiplicative identity (1,0,0,\ldots). The product is in fact the same one used to define the product of polynomials in one indeterminate, which suggests using a similar notation. One embeds R into R X by sending any (constant) a \in R to the sequence (a,0,0,\ldots) and designates the sequence (0,1,0,0,\ldots) by X; then using the above definitions every sequence with only finitely many nonzero terms can be expressed in terms of these special elements as :(a_0, a_1, a_2, \ldots, a_n, 0, 0, \ldots) = a_0 + a_1 X + \cdots + a_n X^n = \sum_^n a_i X^i; these are precisely the polynomials in X. Given this, it is quite natural and convenient to designate a general sequence (a_n)_ by the formal expression \textstyle\sum_a_i X^i, even though the latter ''is not'' an expression formed by the operations of addition and multiplication defined above (from which only finite sums can be constructed). This notational convention allows reformulation of the above definitions as :\left(\sum_ a_i X^i\right)+\left(\sum_ b_i X^i\right) = \sum_(a_i+b_i) X^i and :\left(\sum_ a_i X^i\right) \times \left(\sum_ b_i X^i\right) = \sum_ \left(\sum_^n a_k b_\right) X^n. which is quite convenient, but one must be aware of the distinction between formal summation (a mere convention) and actual addition.


Topological structure

Having stipulated conventionally that one would like to interpret the right hand side as a well-defined infinite summation. To that end, a notion of convergence in R^\N is defined and a
topology Topology (from the Greek language, Greek words , and ) is the branch of mathematics concerned with the properties of a Mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformat ...
on R^\N is constructed. There are several equivalent ways to define the desired topology. * We may give R^\N the
product topology In topology and related areas of mathematics, a product space is the Cartesian product of a family of topological spaces equipped with a natural topology called the product topology. This topology differs from another, perhaps more natural-seemin ...
, where each copy of R is given the
discrete topology In topology, a discrete space is a particularly simple example of a topological space or similar structure, one in which the points form a , meaning they are '' isolated'' from each other in a certain sense. The discrete topology is the finest to ...
. * We may give R^\N the I-adic topology, where I=(X) is the ideal generated by X, which consists of all sequences whose first term a_0 is zero. * The desired topology could also be derived from the following metric. The distance between distinct sequences (a_n), (b_n) \in R^, is defined to be d((a_n), (b_n)) = 2^, where k is the smallest
natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
such that a_k\neq b_k; the distance between two equal sequences is of course zero. Informally, two sequences (a_n) and (b_n) become closer and closer if and only if more and more of their terms agree exactly. Formally, the sequence of partial sums of some infinite summation converges if for every fixed power of X the coefficient stabilizes: there is a point beyond which all further partial sums have the same coefficient. This is clearly the case for the right hand side of (), regardless of the values a_n, since inclusion of the term for i=n gives the last (and in fact only) change to the coefficient of X^n. It is also obvious that the limit of the sequence of partial sums is equal to the left hand side. This topological structure, together with the ring operations described above, form a topological ring. This is called the ring of formal power series over R and is denoted by R X. The topology has the useful property that an infinite summation converges if and only if the sequence of its terms converges to 0, which just means that any fixed power of X occurs in only finitely many terms. The topological structure allows much more flexible usage of infinite summations. For instance the rule for multiplication can be restated simply as :\left(\sum_ a_i X^i\right) \times \left(\sum_ b_i X^i\right) = \sum_ a_i b_j X^, since only finitely many terms on the right affect any fixed X^n. Infinite products are also defined by the topological structure; it can be seen that an infinite product converges if and only if the sequence of its factors converges to 1 (in which case the product is nonzero) or infinitely many factors have no constant term (in which case the product is zero).


Alternative topologies

The above topology is the finest topology for which :\sum_^\infty a_i X^i always converges as a summation to the formal power series designated by the same expression, and it often suffices to give a meaning to infinite sums and products, or other kinds of limits that one wishes to use to designate particular formal power series. It can however happen occasionally that one wishes to use a coarser topology, so that certain expressions become convergent that would otherwise diverge. This applies in particular when the base ring R already comes with a topology other than the discrete one, for instance if it is also a ring of formal power series. In the ring of formal power series \Z X Y, the topology of above construction only relates to the indeterminate Y, since the topology that was put on \Z X has been replaced by the discrete topology when defining the topology of the whole ring. So :\sum_^\infty XY^i converges (and its sum can be written as \tfrac); however :\sum_^\infty X^i Y would be considered to be divergent, since every term affects the coefficient of Y. This asymmetry disappears if the power series ring in Y is given the product topology where each copy of \Z X is given its topology as a ring of formal power series rather than the discrete topology. With this topology, a sequence of elements of \Z X Y converges if the coefficient of each power of Y converges to a formal power series in X, a weaker condition than stabilizing entirely. For instance, with this topology, in the second example given above, the coefficient of Yconverges to \tfrac, so the whole summation converges to \tfrac. This way of defining the topology is in fact the standard one for repeated constructions of rings of formal power series, and gives the same topology as one would get by taking formal power series in all indeterminates at once. In the above example that would mean constructing \Z X,Y and here a sequence converges if and only if the coefficient of every monomial X^iY^j stabilizes. This topology, which is also the I-adic topology, where I=(X,Y) is the ideal generated by X and Y, still enjoys the property that a summation converges if and only if its terms tend to 0. The same principle could be used to make other divergent limits converge. For instance in \R X the limit :\lim_\left(1+\frac\right)^ does not exist, so in particular it does not converge to :\exp(X) = \sum_\frac. This is because for i\geq 2 the coefficient \tbinom/n^i of X^i does not stabilize as n\to \infty. It does however converge in the usual topology of \R, and in fact to the coefficient \tfrac of \exp(X). Therefore, if one would give \R X the product topology of \R^\N where the topology of \R is the usual topology rather than the discrete one, then the above limit would converge to \exp(X). This more permissive approach is not however the standard when considering formal power series, as it would lead to convergence considerations that are as subtle as they are in
analysis Analysis (: analyses) is the process of breaking a complex topic or substance into smaller parts in order to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle (38 ...
, while the philosophy of formal power series is on the contrary to make convergence questions as trivial as they can possibly be. With this topology it would ''not'' be the case that a summation converges if and only if its terms tend to 0.


Universal property

The ring R X may be characterized by the following
universal property In mathematics, more specifically in category theory, a universal property is a property that characterizes up to an isomorphism the result of some constructions. Thus, universal properties can be used for defining some objects independently fro ...
. If S is a commutative associative algebra over R, if I is an ideal of S such that the I-adic topology on S is complete, and if x is an element of I, then there is a ''unique'' \Phi: R X\to S with the following properties: * \Phi is an R-algebra homomorphism * \Phi is continuous * \Phi(X)=x.


Operations on formal power series

One can perform algebraic operations on power series to generate new power series. (Several previous editions as well.)


Power series raised to powers

For any
natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
, the th power of a formal power series is defined recursively by \beginS^1&=S\\ S^n&=S\cdot S^\quad\text n>1.\end If is invertible in the ring of coefficients, one can prove that in the expansion \Big( \sum_^\infty a_k X^k \Big)^ = \sum_^\infty c_m X^m, the coefficients are given by c_0 = a_0^n and c_m = \frac \sum_^m (kn - m+k) a_ c_ for m \geq 1 if is invertible in the ring of coefficients. In the case of formal power series with complex coefficients, its complex powers are well defined for series with constant term equal to . In this case, f^ can be defined either by composition with the binomial series , or by composition with the exponential and the logarithmic series, f^ = \exp(\alpha\log(f)), or as the solution of the differential equation (in terms of series) f(f^)' = \alpha f^ f' with constant term ; the three definitions are equivalent. The exponent rules (f^\alpha)^\beta = f^ and f^\alpha g^\alpha = (fg)^\alpha easily follow for formal power series .


Multiplicative inverse

The series :A = \sum_^\infty a_n X^n \in R X is invertible in R X if and only if its constant coefficient a_0 is invertible in R. This condition is necessary, for the following reason: if we suppose that A has an inverse B = b_0 + b_1 x + \cdots then the constant term a_0b_0 of A \cdot B is the constant term of the identity series, i.e. it is 1. This condition is also sufficient; we may compute the coefficients of the inverse series B via the explicit recursive formula :\begin b_0 &= \frac,\\ b_n &= -\frac \sum_^n a_i b_, \ \ \ n \geq 1. \end An important special case is that the
geometric series In mathematics, a geometric series is a series (mathematics), series summing the terms of an infinite geometric sequence, in which the ratio of consecutive terms is constant. For example, 1/2 + 1/4 + 1/8 + 1/16 + ⋯, the series \tfrac12 + \tfrac1 ...
formula is valid in R X: :(1 - X)^ = \sum_^\infty X^n. If R=K is a field, then a series is invertible if and only if the constant term is non-zero, i.e. if and only if the series is not divisible by X. This means that K X is a discrete valuation ring with uniformizing parameter X.


Division

The computation of a quotient f/g=h : \frac =\sum_^\infty c_n X^n, assuming the denominator is invertible (that is, a_0 is invertible in the ring of scalars), can be performed as a product f and the inverse of g, or directly equating the coefficients in f=gh: :c_n = \frac\left(b_n - \sum_^n a_k c_\right).


Extracting coefficients

The coefficient extraction operator applied to a formal power series :f(X) = \sum_^\infty a_n X^n in ''X'' is written : \left X^m \rightf(X) and extracts the coefficient of ''Xm'', so that : \left X^m \rightf(X) = \left X^m \right\sum_^\infty a_n X^n = a_m.


Composition

Given two formal power series :f(X) = \sum_^\infty a_n X^n = a_1 X + a_2 X^2 + \cdots :g(X) = \sum_^\infty b_n X^n = b_0 + b_1 X + b_2 X^2 + \cdots such that a_0=0, one may form the ''composition'' :g(f(X)) = \sum_^\infty b_n (f(X))^n = \sum_^\infty c_n X^n, where the coefficients ''c''''n'' are determined by "expanding out" the powers of ''f''(''X''): :c_n:=\sum_ b_k a_ a_ \cdots a_. Here the sum is extended over all (''k'', ''j'') with k\in\N and j\in\N_+^k with , j, :=j_1+\cdots+j_k=n. Since a_0=0, one must have k\le n and j_i\le n for every i. This implies that the above sum is finite and that the coefficient c_n is the coefficient of X^n in the polynomial g_n(f_n(X)), where f_n and g_n are the polynomials obtained by truncating the series at x^n, that is, by removing all terms involving a power of X higher than n. A more explicit description of these coefficients is provided by Faà di Bruno's formula, at least in the case where the coefficient ring is a field of characteristic 0. Composition is only valid when f(X) has ''no constant term'', so that each c_n depends on only a finite number of coefficients of f(X) and g(X). In other words, the series for g(f(X)) converges in the
topology Topology (from the Greek language, Greek words , and ) is the branch of mathematics concerned with the properties of a Mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformat ...
of R X.


Example

Assume that the ring R has characteristic 0 and the nonzero integers are invertible in R. If one denotes by \exp(X) the formal power series :\exp(X) = 1 + X + \frac + \frac + \frac + \cdots, then the equality :\exp(\exp(X) - 1) = 1 + X + X^2 + \frac6 + \frac8 + \cdots makes perfect sense as a formal power series, since the constant coefficient of \exp(X) - 1 is zero.


Composition inverse

Whenever a formal series :f(X)=\sum_k f_k X^k \in R X has ''f''0 = 0 and ''f''1 being an invertible element of ''R'', there exists a series :g(X)=\sum_k g_k X^k that is the composition inverse of f, meaning that composing f with g gives the series representing the identity function x = 0 + 1x + 0x^2+ 0x^3+\cdots. The coefficients of g may be found recursively by using the above formula for the coefficients of a composition, equating them with those of the composition identity ''X'' (that is 1 at degree 1 and 0 at every degree greater than 1). In the case when the coefficient ring is a field of characteristic 0, the Lagrange inversion formula (discussed below) provides a powerful tool to compute the coefficients of ''g'', as well as the coefficients of the (multiplicative) powers of ''g''.


Formal differentiation

Given a formal power series :f = \sum_ a_n X^n \in R X, we define its
formal derivative In mathematics, the formal derivative is an operation on elements of a polynomial ring or a ring of formal power series that mimics the form of the derivative from calculus. Though they appear similar, the algebraic advantage of a formal deriv ...
, denoted ''Df'' or ''f'' ′, by : Df = f' = \sum_ a_n n X^. The symbol ''D'' is called the formal differentiation operator. This definition simply mimics term-by-term differentiation of a polynomial. This operation is ''R''-
linear In mathematics, the term ''linear'' is used in two distinct senses for two different properties: * linearity of a '' function'' (or '' mapping''); * linearity of a '' polynomial''. An example of a linear function is the function defined by f(x) ...
: :D(af + bg) = a \cdot Df + b \cdot Dg for any ''a'', ''b'' in ''R'' and any ''f'', ''g'' in R X. Additionally, the formal derivative has many of the properties of the usual
derivative In mathematics, the derivative is a fundamental tool that quantifies the sensitivity to change of a function's output with respect to its input. The derivative of a function of a single variable at a chosen input value, when it exists, is t ...
of calculus. For example, the product rule is valid: :D(fg) \ =\ f \cdot (Dg) + (Df) \cdot g, and the
chain rule In calculus, the chain rule is a formula that expresses the derivative of the Function composition, composition of two differentiable functions and in terms of the derivatives of and . More precisely, if h=f\circ g is the function such that h ...
works as well: :D(f\circ g ) = ( Df\circ g ) \cdot Dg, whenever the appropriate compositions of series are defined (see above under composition of series). Thus, in these respects formal power series behave like Taylor series. Indeed, for the ''f'' defined above, we find that :(D^k f)(0) = k! a_k, where ''D''''k'' denotes the ''k''th formal derivative (that is, the result of formally differentiating ''k'' times).


Formal antidifferentiation

If R is a ring with characteristic zero and the nonzero integers are invertible in R, then given a formal power series :f = \sum_ a_n X^n \in R X, we define its formal antiderivative or formal indefinite integral by : D^ f = \int f\ dX = C + \sum_ a_n \frac. for any constant C \in R. This operation is ''R''-
linear In mathematics, the term ''linear'' is used in two distinct senses for two different properties: * linearity of a '' function'' (or '' mapping''); * linearity of a '' polynomial''. An example of a linear function is the function defined by f(x) ...
: :D^(af + bg) = a \cdot D^f + b \cdot D^g for any ''a'', ''b'' in ''R'' and any ''f'', ''g'' in R X. Additionally, the formal antiderivative has many of the properties of the usual antiderivative of calculus. For example, the formal antiderivative is the right inverse of the formal derivative: :D(D^(f)) = f for any f \in R X.


Properties


Algebraic properties of the formal power series ring

R X is an associative algebra over R which contains the ring R /math> of polynomials over R; the polynomials correspond to the sequences which end in zeros. The Jacobson radical of R X is the ideal generated by X and the Jacobson radical of R; this is implied by the element invertibility criterion discussed above. The
maximal ideal In mathematics, more specifically in ring theory, a maximal ideal is an ideal that is maximal (with respect to set inclusion) amongst all ''proper'' ideals. In other words, ''I'' is a maximal ideal of a ring ''R'' if there are no other ideals ...
s of R X all arise from those in R in the following manner: an ideal M of R X is maximal if and only if M\cap R is a maximal ideal of R and M is generated as an ideal by X and M\cap R. Several algebraic properties of R are inherited by R X: * if R is a
local ring In mathematics, more specifically in ring theory, local rings are certain rings that are comparatively simple, and serve to describe what is called "local behaviour", in the sense of functions defined on algebraic varieties or manifolds, or of ...
, then so is R X (with the set of non units the unique maximal ideal), * if R is
Noetherian In mathematics, the adjective Noetherian is used to describe objects that satisfy an ascending or descending chain condition on certain kinds of subobjects, meaning that certain ascending or descending sequences of subobjects must have finite leng ...
, then so is R X (a version of the Hilbert basis theorem), * if R is an
integral domain In mathematics, an integral domain is a nonzero commutative ring in which the product of any two nonzero elements is nonzero. Integral domains are generalizations of the ring of integers and provide a natural setting for studying divisibilit ...
, then so is R X, and * if K is a field, then K X is a discrete valuation ring.


Topological properties of the formal power series ring

The metric space (R X, d) is complete. The ring R X is
compact Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to: * Interstate compact, a type of agreement used by U.S. states * Blood compact, an ancient ritual of the Philippines * Compact government, a t ...
if and only if ''R'' is finite. This follows from
Tychonoff's theorem In mathematics, Tychonoff's theorem states that the product of any collection of compact topological spaces is compact with respect to the product topology. The theorem is named after Andrey Nikolayevich Tikhonov (whose surname sometimes is tra ...
and the characterisation of the topology on R X as a product topology.


Weierstrass preparation

The ring of formal power series with coefficients in a complete local ring satisfies the Weierstrass preparation theorem.


Applications

Formal power series can be used to solve recurrences occurring in number theory and combinatorics. For an example involving finding a closed form expression for the
Fibonacci number In mathematics, the Fibonacci sequence is a Integer sequence, sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted . Many w ...
s, see the article on Examples of generating functions. One can use formal power series to prove several relations familiar from analysis in a purely algebraic setting. Consider for instance the following elements of \Q X: : \sin(X) := \sum_ \frac X^ : \cos(X) := \sum_ \frac X^ Then one can show that :\sin^2(X) + \cos^2(X) = 1, :\frac \sin(X) = \cos(X), :\sin (X+Y) = \sin(X) \cos(Y) + \cos(X) \sin(Y). The last one being valid in the ring \Q X, Y. For ''K'' a field, the ring K X_1, \ldots, X_r is often used as the "standard, most general" complete local ring over ''K'' in algebra.


Interpreting formal power series as functions

In
mathematical analysis Analysis is the branch of mathematics dealing with continuous functions, limit (mathematics), limits, and related theories, such as Derivative, differentiation, Integral, integration, measure (mathematics), measure, infinite sequences, series ( ...
, every convergent power series defines a function with values in the real or
complex Complex commonly refers to: * Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe ** Complex system, a system composed of many components which may interact with each ...
numbers. Formal power series over certain special rings can also be interpreted as functions, but one has to be careful with the domain and
codomain In mathematics, a codomain, counter-domain, or set of destination of a function is a set into which all of the output of the function is constrained to fall. It is the set in the notation . The term '' range'' is sometimes ambiguously used to ...
. Let :f = \sum a_n X^n \in R X, and suppose S is a commutative associative algebra over R, I is an ideal in S such that the I-adic topology on S is complete, and x is an element of I. Define: :f(x) = \sum_ a_n x^n. This series is guaranteed to converge in S given the above assumptions on x. Furthermore, we have : (f+g)(x) = f(x) + g(x) and : (fg)(x) = f(x) g(x). Unlike in the case of bona fide functions, these formulas are not definitions but have to be proved. Since the topology on R X is the (X)-adic topology and R X is complete, we can in particular apply power series to other power series, provided that the arguments don't have constant coefficients (so that they belong to the ideal (X)): f(0), f(X^2-X) and f((1-X)^-1) are all well defined for any formal power series f \in R X. With this formalism, we can give an explicit formula for the multiplicative inverse of a power series f whose constant coefficient a=f(0) is invertible in R: :f^ = \sum_ a^ (a-f)^n. If the formal power series g with g(0)=0 is given implicitly by the equation :f(g) =X where f is a known power series with f(0)=0, then the coefficients of g can be explicitly computed using the Lagrange inversion formula.


Generalizations


Formal Laurent series

The formal Laurent series over a ring R are defined in a similar way to a formal power series, except that we also allow finitely many terms of negative degree. That is, they are the series that can be written as :f = \sum_^\infty a_n X^n for some integer N, so that there are only finitely many negative n with a_n \neq 0. (This is different from the classical
Laurent series In mathematics, the Laurent series of a complex function f(z) is a representation of that function as a power series which includes terms of negative degree. It may be used to express complex functions in cases where a Taylor series expansio ...
of
complex analysis Complex analysis, traditionally known as the theory of functions of a complex variable, is the branch of mathematical analysis that investigates functions of complex numbers. It is helpful in many branches of mathematics, including algebraic ...
.) For a non-zero formal Laurent series, the minimal integer n such that a_n\neq 0 is called the ''order'' of f and is denoted \operatorname(f). (The order ord(0) of the zero series is +\infty.) For instance, X^ + \frac 1 2 X^ + \frac 1 3 X^ + \frac 1 4 + \frac 1 5 X + \frac 1 6 X^2 + \frac 1 7 X^3 + \frac 1 8 X^4 + \dots is a formal Laurent series of order –3. Multiplication of such series can be defined. Indeed, similarly to the definition for formal power series, the coefficient of X^k of two series with respective sequences of coefficients \ and \ is \sum_a_ib_. This sum has only finitely many nonzero terms because of the assumed vanishing of coefficients at sufficiently negative indices. The formal Laurent series form the ring of formal Laurent series over R, denoted by R((X)). It is equal to the localization of the ring R X of formal power series with respect to the set of positive powers of X. If R=K is a field, then K((X)) is in fact a field, which may alternatively be obtained as the
field of fractions In abstract algebra, the field of fractions of an integral domain is the smallest field in which it can be embedded. The construction of the field of fractions is modeled on the relationship between the integral domain of integers and the fie ...
of the
integral domain In mathematics, an integral domain is a nonzero commutative ring in which the product of any two nonzero elements is nonzero. Integral domains are generalizations of the ring of integers and provide a natural setting for studying divisibilit ...
K X. As with R X, the ring R((X)) of formal Laurent series may be endowed with the structure of a topological ring by introducing the metric d(f,g)=2^. (In particular, \operatorname(0) = +\infty implies that d(f,f)=2^ = 0.) One may define formal differentiation for formal Laurent series in the natural (term-by-term) way. Precisely, the formal derivative of the formal Laurent series f above is f' = Df = \sum_ na_n X^, which is again a formal Laurent series. If f is a non-constant formal Laurent series and with coefficients in a field of characteristic 0, then one has \operatorname(f')= \operatorname(f)-1. However, in general this is not the case since the factor n for the lowest order term could be equal to 0 in R.


Formal residue

Assume that K is a field of characteristic 0. Then the map :D\colon K((X))\to K((X)) defined above is a K- derivation that satisfies :\ker D=K :\operatorname D= \left \. The latter shows that the coefficient of X^ in f is of particular interest; it is called ''formal residue of f'' and denoted \operatorname(f). The map :\operatorname : K((X))\to K is K-linear, and by the above observation one has an exact sequence :0 \to K \to K((X)) \overset K((X)) \;\overset\; K \to 0. Some rules of calculus. As a quite direct consequence of the above definition, and of the rules of formal derivation, one has, for any f, g\in K((X))
  1. \operatorname(f')=0;
  2. \operatorname(fg')=-\operatorname(f'g);
  3. \operatorname(f'/f)=\operatorname(f),\qquad \forall f\neq 0;
  4. \operatorname\left(( g\circ f) f'\right) = \operatorname(f)\operatorname(g), if \operatorname(f)>0;
  5. ^n(X)=\operatorname\left(X^f(X)\right).
Property (i) is part of the exact sequence above. Property (ii) follows from (i) as applied to (fg)'=f'g+fg'. Property (iii): any f can be written in the form f=X^mg, with m=\operatorname(f) and \operatorname(g)=0: then f'/f = mX^+g'/g. \operatorname(g)=0 implies g is invertible in K X\subset \operatorname(D) = \ker(\operatorname), whence \operatorname(f'/f)=m. Property (iv): Since \operatorname(D) = \ker(\operatorname), we can write g=g_X^+G', with G \in K((X)). Consequently, (g\circ f)f'= g_f^f'+(G'\circ f)f' = g_f'/f + (G \circ f)' and (iv) follows from (i) and (iii). Property (v) is clear from the definition.


The Lagrange inversion formula

As mentioned above, any formal series f \in K X with ''f''0 = 0 and ''f''1 ≠ 0 has a composition inverse g \in K X. The following relation between the coefficients of ''gn'' and ''f''−''k'' holds (""): :k ^kg^n=n ^^. In particular, for ''n'' = 1 and all ''k'' ≥ 1, : ^kg=\frac \operatorname\left( f^\right). Since the proof of the Lagrange inversion formula is a very short computation, it is worth reporting one proof here. Noting \operatorname(f) =1 , we can apply the rules of calculus above, crucially Rule (iv) substituting X \rightsquigarrow f(X), to get: : \begin k ^kg^n & \ \stackrel=\ k\operatorname\left( g^n X^ \right) \ \stackrel=\ k\operatorname\left(X^n f^f'\right) \ \stackrel=\ -\operatorname\left(X^n (f^)'\right) \\ & \ \stackrel=\ \operatorname\left(\left(X^n\right)' f^\right) \ \stackrel=\ n\operatorname\left(X^f^\right) \ \stackrel=\ n ^^. \end Generalizations. One may observe that the above computation can be repeated plainly in more general settings than ''K''((''X'')): a generalization of the Lagrange inversion formula is already available working in the \Complex((X))-modules X^\Complex((X)), where α is a complex exponent. As a consequence, if ''f'' and ''g'' are as above, with f_1=g_1=1, we can relate the complex powers of ''f'' / ''X'' and ''g'' / ''X'': precisely, if α and β are non-zero complex numbers with negative integer sum, m=-\alpha-\beta\in\N, then :\frac ^mleft( \frac \right)^\alpha=-\frac ^mleft( \frac \right)^\beta. For instance, this way one finds the power series for complex powers of the Lambert function.


Power series in several variables

Formal power series in any number of indeterminates (even infinitely many) can be defined. If ''I'' is an index set and ''XI'' is the set of indeterminates ''Xi'' for ''i''∈''I'', then a monomial ''X''''α'' is any finite product of elements of ''XI'' (repetitions allowed); a formal power series in ''XI'' with coefficients in a ring ''R'' is determined by any mapping from the set of monomials ''X''''α'' to a corresponding coefficient ''c''''α'', and is denoted \sum_\alpha c_\alpha X^\alpha. The set of all such formal power series is denoted R X_I, and it is given a ring structure by defining :\left(\sum_\alpha c_\alpha X^\alpha\right)+\left(\sum_\alpha d_\alpha X^\alpha \right)= \sum_\alpha (c_\alpha+d_\alpha) X^\alpha and :\left(\sum_\alpha c_\alpha X^\alpha\right)\times\left(\sum_\beta d_\beta X^\beta\right)=\sum_ c_\alpha d_\beta X^


Topology

The topology on R X_I is such that a sequence of its elements converges only if for each monomial ''X''α the corresponding coefficient stabilizes. If ''I'' is finite, then this the ''J''-adic topology, where ''J'' is the ideal of R X_I generated by all the indeterminates in ''XI''. This does not hold if ''I'' is infinite. For example, if I=\N, then the sequence (f_n)_ with f_n = X_n + X_ + X_ + \cdots does not converge with respect to any ''J''-adic topology on ''R'', but clearly for each monomial the corresponding coefficient stabilizes. As remarked above, the topology on a repeated formal power series ring like R X Y is usually chosen in such a way that it becomes isomorphic as a topological ring to R X,Y.


Operations

All of the operations defined for series in one variable may be extended to the several variables case. * A series is invertible if and only if its constant term is invertible in ''R''. * The composition ''f''(''g''(''X'')) of two series ''f'' and ''g'' is defined if ''f'' is a series in a single indeterminate, and the constant term of ''g'' is zero. For a series ''f'' in several indeterminates a form of "composition" can similarly be defined, with as many separate series in the place of ''g'' as there are indeterminates. In the case of the formal derivative, there are now separate
partial derivative In mathematics, a partial derivative of a function of several variables is its derivative with respect to one of those variables, with the others held constant (as opposed to the total derivative, in which all variables are allowed to vary). P ...
operators, which differentiate with respect to each of the indeterminates. They all commute with each other.


Universal property

In the several variables case, the universal property characterizing R X_1, \ldots, X_r becomes the following. If ''S'' is a commutative associative algebra over ''R'', if ''I'' is an ideal of ''S'' such that the ''I''-adic topology on ''S'' is complete, and if ''x''1, ..., ''xr'' are elements of ''I'', then there is a ''unique'' map \Phi: R X_1, \ldots, X_r \to S with the following properties: * Φ is an ''R''-algebra homomorphism * Φ is continuous * Φ(''X''''i'') = ''x''''i'' for ''i'' = 1, ..., ''r''.


Non-commuting variables

The several variable case can be further generalised by taking ''non-commuting variables'' ''Xi'' for ''i'' ∈ ''I'', where ''I'' is an index set and then a monomial ''X''α is any
word A word is a basic element of language that carries semantics, meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no consensus among linguist ...
in the ''XI''; a formal power series in ''XI'' with coefficients in a ring ''R'' is determined by any mapping from the set of monomials ''X''α to a corresponding coefficient ''c''α, and is denoted \textstyle\sum_\alpha c_\alpha X^\alpha . The set of all such formal power series is denoted ''R''«''XI''», and it is given a ring structure by defining addition pointwise :\left(\sum_\alpha c_\alpha X^\alpha\right)+\left(\sum_\alpha d_\alpha X^\alpha\right)=\sum_\alpha(c_\alpha+d_\alpha)X^\alpha and multiplication by :\left(\sum_\alpha c_\alpha X^\alpha\right)\times\left(\sum_\alpha d_\alpha X^\alpha\right)=\sum_ c_\alpha d_\beta X^ \cdot X^ where · denotes concatenation of words. These formal power series over ''R'' form the Magnus ring over ''R''.


On a semiring

Given an
alphabet An alphabet is a standard set of letter (alphabet), letters written to represent particular sounds in a spoken language. Specifically, letters largely correspond to phonemes as the smallest sound segments that can distinguish one word from a ...
\Sigma and a
semiring In abstract algebra, a semiring is an algebraic structure. Semirings are a generalization of rings, dropping the requirement that each element must have an additive inverse. At the same time, semirings are a generalization of bounded distribu ...
S. The formal power series over S supported on the language \Sigma^* is denoted by S\langle\langle \Sigma^*\rangle\rangle. It consists of all mappings r:\Sigma^*\to S, where \Sigma^* is the
free monoid In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero ...
generated by the non-empty set \Sigma. The elements of S\langle\langle \Sigma^*\rangle\rangle can be written as formal sums :r = \sum_ (r,w)w. where (r,w) denotes the value of r at the word w\in\Sigma^*. The elements (r,w)\in S are called the coefficients of r. For r\in S\langle\langle \Sigma^*\rangle\rangle the support of r is the set :\operatorname(r)=\ A series where every coefficient is either 0 or 1 is called the characteristic series of its support. The subset of S\langle\langle \Sigma^*\rangle\rangle consisting of all series with a finite support is denoted by S\langle \Sigma^*\rangle and called polynomials. For r_1, r_2\in S\langle\langle \Sigma^*\rangle\rangle and s\in S, the sum r_1+r_2 is defined by :(r_1+r_2,w)=(r_1,w)+(r_2,w) The (Cauchy) product r_1\cdot r_2 is defined by :(r_1\cdot r_2,w) = \sum_(r_1,w_1)(r_2,w_2) The Hadamard product r_1\odot r_2 is defined by :(r_1\odot r_2,w)=(r_1,w)(r_2,w) And the products by a scalar sr_1 and r_1s by :(sr_1,w)=s(r_1,w) and (r_1s,w)=(r_1,w)s, respectively. With these operations (S\langle\langle \Sigma^*\rangle\rangle,+,\cdot,0,\varepsilon) and (S\langle \Sigma^*\rangle, +,\cdot,0,\varepsilon) are semirings, where \varepsilon is the empty word in \Sigma^*. These formal power series are used to model the behavior of weighted automata, in
theoretical computer science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...
, when the coefficients (r,w) of the series are taken to be the weight of a path with label w in the automata.


Replacing the index set by an ordered abelian group

Suppose G is an ordered abelian group, meaning an abelian group with a total ordering < respecting the group's addition, so that a if and only if a+c for all c. Let I be a
well-order In mathematics, a well-order (or well-ordering or well-order relation) on a set is a total ordering on with the property that every non-empty subset of has a least element in this ordering. The set together with the ordering is then calle ...
ed subset of G, meaning I contains no infinite descending chain. Consider the set consisting of :\sum_ a_i X^i for all such I, with a_i in a commutative ring R, where we assume that for any index set, if all of the a_i are zero then the sum is zero. Then R((G)) is the ring of formal power series on G; because of the condition that the indexing set be well-ordered the product is well-defined, and we of course assume that two elements which differ by zero are the same. Sometimes the notation R^G is used to denote R((G)). Various properties of R transfer to R((G)). If R is a field, then so is R((G)). If R is an
ordered field In mathematics, an ordered field is a field together with a total ordering of its elements that is compatible with the field operations. Basic examples of ordered fields are the rational numbers and the real numbers, both with their standard ord ...
, we can order R((G)) by setting any element to have the same sign as its leading coefficient, defined as the least element of the index set I associated to a non-zero coefficient. Finally if G is a divisible group and R is a
real closed field In mathematics, a real closed field is a field F that has the same first-order properties as the field of real numbers. Some examples are the field of real numbers, the field of real algebraic numbers, and the field of hyperreal numbers. Def ...
, then R((G)) is a real closed field, and if R is algebraically closed, then so is R((G)). This theory is due to Hans Hahn, who also showed that one obtains subfields when the number of (non-zero) terms is bounded by some fixed infinite cardinality.


Examples and related topics

* Bell series are used to study the properties of multiplicative arithmetic functions * Formal groups are used to define an abstract group law using formal power series * Puiseux series are an extension of formal Laurent series, allowing fractional exponents * Rational series


See also

* Ring of restricted power series * International Conference on Formal Power Series and Algebraic Combinatorics


Notes


References

* *
Nicolas Bourbaki Nicolas Bourbaki () is the collective pseudonym of a group of mathematicians, predominantly French alumni of the École normale supérieure (Paris), École normale supérieure (ENS). Founded in 1934–1935, the Bourbaki group originally intende ...
: ''Algebra'', IV, §4. Springer-Verlag 1988.


Further reading

* W. Kuich. Semirings and formal power series: Their relevance to formal languages and automata theory. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 1, Chapter 9, pages 609–677. Springer, Berlin, 1997, * Droste, M., & Kuich, W. (2009). Semirings and Formal Power Series. ''Handbook of Weighted Automata'', 3–28. * {{DEFAULTSORT:Formal Power Series Abstract algebra Ring theory Enumerative combinatorics Series (mathematics)