Formal power series Information & Formal power series Links at HealthHaven.com

In mathematics, formal power series are devices that make it possible to employ much of the analytical machinery of power series in settings that do not have natural notions of convergence. They are also useful, especially in combinatorics, for providing compact representations of sequences and multisets, and for finding closed formulas for recursively defined sequences; this is known as the method of generating functions.

[edit] Informal introduction

A formal power series can be loosely thought of as a polynomial 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. 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. However, as a formal power series, we may ignore this completely; all that is relevant is the sequence of coefficients [1, −3, 5, −7, 9, −11, ...]. In other words, a formal power series is just an object that records a sequence of coefficients.

Arithmetic 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):

$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⁵ 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.

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⁻¹. Now we can define division of formal power series by defining B / A to be the product B A⁻¹, provided that the inverse of A exists. For example, one can use the definition of multiplication above to verify the familiar formula

$\frac{1}{1 + x} = 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 for a formal power series in one variable extracts the coefficient of xⁿ, and is written e.g. [xⁿ] A, so that [x²] A = 5 and [x⁵] A = −11. Other examples include

$[x^3] B = 4, \quad [x^2] ( x + 3 x^2 y^3 + 10 y^6) = 3 y^3,\text{ and } [x^2 y^3] ( x + 3 x^2 y^3 + 10 y^6) = 3$

and

$[x^n] \frac{1}{1+x} = (-1)^n \text{ and } [x^n] \frac{x}{(1-x)^2} = n.$

Similarly, many other operations that are carried out on polynomials can be extended to the formal power series setting, as explained below.

[edit] The ring of formal power series

The set of all formal power series in X with coefficients in a commutative ring R form another ring that is written R[[X]], and called the ring of formal power series over $R$ in the variable $X$ .

[edit] Definition of the formal power series ring

One can characterize R[[X]] abstractly as the completion of the polynomial ring R[X] 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.

[edit] Ring structure

As a set, R[[X]] can be constructed as the set R^N of all infinite sequences in R. One defines addition of two such sequences by

$\left( a_n \right) + \left( b_n \right) = \left( a_n + b_n \right)$

and multiplication by

$\left( a_n \right) \times \left( b_n \right) = \left( \sum_{k=0}^n a_k b_{n-k} \right).$

This type of product is called the Cauchy product of the two sequences of coefficients, and is a sort of discrete convolution. With these operations, R^N becomes a commutative ring with zero element (0, 0, 0, ...) and multiplicative identity (1, 0, 0,...).

If we identify the element a of R with the sequence (a, 0, 0, ...) and define X := (0, 1, 0, 0, ...), then using the above definitions of addition and multiplication, we find that every sequence with only finitely many nonzero terms can be written as the finite sum

$(a_0, a_1, a_2, \ldots, a_N, 0, 0, \ldots) = a_0 + a_1 X + \cdots + a_N X^N = \sum_{n=0}^N a_n X^n.$

[edit] Topological structure

We would like to extend the above formula to a similar one for arbitrary sequences in R^N, that is, we would like

$(a_0, a_1, a_2, a_3, \ldots) = \sum_{n=0}^\infty a_n X^n \qquad (1)$

to hold. However, for the infinite sum on the right to make sense, we need a notion of convergence in R^N, which involves introducing a topology on R^N. There are several equivalent ways to define the appropriate topology.

We may give R^N the product topology, where each copy of R is given the discrete topology.
We may introduce a metric (or "distance function"). For sequences (a_n) and (b_n) in R^N, let us define

$d((a_n), (b_n)) = 2^{-k},\,\!$

where k is the smallest natural number such that a_k ≠ b_k; if there is no such k, then the two sequences are identical, so we set their distance to be zero.

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₀ is zero.

All of these definitions of the topology amount to declaring that two sequences (a_n) and (b_n) are "close" if their first few terms agree; the more terms agree, the closer they are.

Now we can make sense of equation (1); the partial sums of the infinite sum certainly converge to the sequence on the left hand side. In fact, any rearrangement of the series converges to the same limit.

One must check that 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]].

[edit] Universal property

The ring R[[X]] may be characterized by the following universal property. 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 Φ : R[[X]] → S with the following properties:

Φ is an R-algebra homomorphism
Φ is continuous
Φ(X) = x.

[edit] Operations on formal power series

[edit] Inverting series

The series

$\sum_{n=0}^\infty a_n X^n$

in R[[X]] is invertible in R[[X]] if and only if its constant coefficient a₀ is invertible in R. This is necessary, as the constant term of the product is $a 0 b 0$ , and sufficient, via the explicit formula:

$\begin{align}b_0 &= \frac{1}{a_0}\\ b_n &= -\frac{1}{a_0} \sum_{i=1}^n a_i b_{n-i}\qquad \text{for } n \ge 1 \end{align}$

An important special case is that the geometric series formula is valid in R[[X]]:

$\left( 1 - X \right)^{-1} = \sum_{n \ge 0} 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 it is not divisible by X. This says that $K [[X]]$ is a discrete valuation ring with uniformizing parameter X.

[edit] Extracting coefficients

The coefficient extraction operator applied to a formal power series

$f(X) = \sum_{n=0}^\infty a_n X^n$

in $X\,$ is written

$\left[ X^m \right] f(X)$

and extracts the coefficient of $X^m\,$ , so that

$\left[ X^m \right] f(X) = \left[ X^m \right] \sum_{n=0}^\infty a_n X^n = a_m.$

[edit] Composition of series

Given formal power series

$f(X) = \sum_{n=1}^\infty a_n X^n = a_1 X + a_2 X^2 + \cdots$

and

$g(X) = \sum_{n=0}^\infty b_n X^n = b_0 + b_1 X + b_2 X^2 + \cdots,$

one may form the composition

$g(f(X)) = \sum_{n=0}^\infty b_n (f(X))^n = \sum_{n=0}^\infty c_n X^n,$

where the coefficients c_n are determined by "expanding out" the powers of f(X):

$c_n:=\sum_{k\in\N, \vert j\vert=n} g_k f_{j_1}..f_{j_k}.$

Here the sum is extended over all (k,j) with $k\in\N$ and $j\in\N_+^k$ with $| j | : = j 1 + .. + j k = 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.

A point here is that this operation is only valid when f(X) has no constant term, so that the series for g(f(X)) converges in the topology of R[[X]]. In other words, each c_n depends on only a finite number of coefficients of f(X) and g(X).

[edit] Example

(We assume in this example that the ring R has characteristic 0.) If we denote by exp(X) the formal power series

$\exp(X) = 1 + X + \frac{X^2}{2!} + \frac{X^3}{3!} + \frac{X^4}{4!} + \cdots,$

then the expression

$\exp(\exp(X) - 1) = 1 + X + X^2 + \frac{5X^3}6 + \frac{5X^4}8 + \cdots$

makes perfect sense as a formal power series. However, the statement

$\exp(\exp(X)) = e \exp(\exp(X) - 1) = e + eX + eX^2 + \frac{5eX^3}6 + \cdots$

is not a valid application of the composition operation for formal power series. Rather, it is confusing the notions of convergence in R[[X]] and convergence in R; indeed, the ring R may not even contain any number e with the appropriate properties.

[edit] Composition inverse

Any formal series $\textstyle f(X)=\sum_k f_k X^k \in R[[X]]$ with $f 0 = 0$ has a composition inverse $\textstyle g(X)=\sum_k g_k X^k$ provided $f 1$ is an invertible element of R. The coefficients are found recursively from the above formula for the coefficients of a composition, equating them with those of the composition identity X (that is 1 at degree 0 and 0 at positive degree) . In the case when the coefficient ring is a field of characteristic 0, the Lagrange inversion formula (see below) provides a powerful tool to compute the coefficients of g, as well as the coefficients of the (multiplicative) powers of g.

[edit] Formal differentiation of series

Given a formal power series

$f = \sum_{n\geq 0} a_n X^n$

in R[[X]], we define its formal derivative, denoted Df or $f\,^'$ , by

$Df = \sum_{n \geq 1} a_n n X^{n-1}.$

The symbol D is called the formal differentiation operator. The motivation behind this definition is that it simply mimics term-by-term differentiation of a polynomial.

This operation is R-linear:

$D(af + bg) = a Df + b 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 of calculus. For example, the product rule is valid:

$D(fg) = f(Dg) + (Df) g; \,\!$

and the chain rule works as well:

$D(f\circ g ) = \left( Df\circ g\right) Dg, \,\!$

whenever the appropriate compositions of series are defined (see above under composition of series).

In a sense, all formal power series are Taylor series. Indeed, for the f defined above, we find that

$(D^k f)(0) = k! a_k, \,\!$

where D^k denotes the kth formal derivative (that is, the result of formally differentiating k times).

[edit] Algebraic properties of the formal power series ring

R[[X]] is an associative algebra over R which contains the ring R[X] 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 ideals 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 ∩ R is a maximal ideal of R and M is generated as an ideal by X and M ∩ R.

Several algebraic properties of R are inherited by R[[X]]:

if R is a local ring, then so is R[[X]]
if R is Noetherian, then so is R[[X]]; this is a version of the Hilbert basis theorem
if R is an integral domain, then so is R[[X]]
if R = K is a field, then K[[X]] is a discrete valuation ring.

[edit] Topological properties of the formal power series ring

The metric space (R[[X]], d) is complete.

The ring R[[X]] is compact if and only if R is finite. This follows from Tychonoff's theorem and the characterisation of the topology on R[[X]] as a product topology.

[edit] 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 numbers, 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_{n \ge 0} \frac{(-1)^n} {(2n+1)!} X^{2n+1}$

$\cos(X) := \sum_{n \ge 0} \frac{(-1)^n} {(2n)!} X^{2n}$

Then one can show that

$\sin^2(X) + \cos^2(X) = 1 \,$

and

$\frac{\partial}{\partial X} \sin(X) = \cos(X)$

as well as

$\sin (X+Y) = \sin(X) \cos(Y) + \cos(X) \sin(Y)\,$

(the latter being valid in the ring Q[[X,Y]]).

In algebra, the ring K[[X₁, ..., X_r]] (where K is a field) is often used as the "standard, most general" complete local ring over K.

[edit] Interpreting formal power series as functions

In mathematical analysis, every convergent power series defines a function with values in the real or complex numbers. Formal power series can also be interpreted as functions, but one has to be careful with the domain and codomain. If f=∑a_n Xⁿ is an element of R[[X]], 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, then we can define

$f(x) = \sum_{n\ge 0} a_n x^n.$

This latter 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²−X) and f( (1 − X)⁻¹ − 1) are all well defined for any formal power series f∈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^{-1} = \sum_{n \ge 0} a^{-n-1} (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 theorem.

[edit] Generalizations

[edit] Formal Laurent series

A formal Laurent series over a ring R is defined in a similar way to a formal power series, except that we also allow terms of negative degree, like in classical Laurent series. Of particular interest are formal Laurent series of finite order, that is series of the form

$f = \sum_{n\in\Z} a_n X^n$

where $a n = 0$ for all but finitely many negative indices n, because multiplication of such series can then be defined. Indeed, similarly to the definition for formal power series, the coefficient of $X k$ of two series with respective sequences of coefficients $(a_n)_{n\in\Z}$ and $(b_n)_{n\in\Z}$ is

$\sum_{i\in\Z}a_ib_{k-i},$

which sum is effectively finite because of the assumed vanishing of coefficients at sufficiently negative indices, and which sum zero for sufficiently negative k for the same reason.

For a non-zero formal Laurent series of finite order, the minimum integer n such that a_n≠0 is called the order of f, denoted ord(f). (The designation "of finite order" here means "not of order −∞", since the only order one could naturally attribute to the zero series is +∞.) The formal Laurent series of finite order form the ring of formal Laurent series over R, denoted by R((X)). It is a topological ring, and its relationship to formal power series is analogous to the relationship between power series and Laurent series.

If R = K is a field, then K((X)) is in fact a field, which may alternatively be obtained as the field of fractions of the integral domain K[[X]].

One may define formal differentiation for formal Laurent series in a natural way (term-by-term). Precisely, the formal derivative of the formal Laurent series f above is

$Df = \sum_{n\in\Z} na_{n-1} X^n$

which is again an element of K((X)). Notice that if f≠0 and K is a field of characteristic 0 one has

$\mathrm{ord}(f\,^')=\mathrm{ord}(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.

[edit] Formal residue

Assume that R is a field K of characteristic 0. Then the map

$D:K((X))\to K((X))$

is a K-derivation that verifies

$\ker\,D=K$

$\mathrm{im}\,D=\{f\in K((X)) : [X^{-1}]f=0\}.$

The latter shows that the coefficient of X⁻¹ in ƒ is of particular interest; it is called formal residue of ƒ and denoted Res(ƒ). The map

$\mathrm{Res} :K((X))\to K \,$

is K-linear, and by the above observation one has an exact sequence

$0 \rightarrow K \rightarrow K((X)) \xrightarrow{D} K((X)) \;\xrightarrow{ \mathrm{Res} }\; K \rightarrow 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 ƒ and g in K((X))

i. $\mathrm{Res}(f\,^')=0;\,$

ii. $\mathrm{Res}(fg\,^')=-\mathrm{Res}(f\,^'g);\,$

iii. $\mathrm{Res}(f\,^'/f)=\mathrm{ord}(f),\qquad \forall f\neq0;\,$

iv. $\mathrm{Res}\left(( f\circ g) g\,^'\right) = \mathrm{ord}(g)\mathrm{Res}(f)\qquad \mathrm{if}\; \mathrm{ord}(g)>0;\,$

v. $[X^n]f(X)=\mathrm{Res}\left(X^{-n-1}f(X)\right).\,$

Property (i) is part of the exact sequence above. Property (ii) follows from (i) as applied to (ƒg)' = ƒg' + ƒ'g. Property (iii): any ƒ can be written in the form ƒ = x^mg, with m = ord(ƒ) and ord(g) = 0: then ƒ'/ƒ = mX ⁻¹ + g'/g. Since ord(g) = 0, the element g is invertible in K[[X]] ⊂ im(D) = ker(Res), whence Res(ƒ'/ƒ) = m. Property (iv): Since ker(Res) ⊂ im(D), we can write ƒ = ƒ₋₁ X ⁻¹ + F' , with F∈ K[[X]]. Consequently, (ƒ $\scriptstyle\circ$ g) g' = f₋₁ g⁻¹ g' + (F' $\scriptstyle\circ$ g) g' = ƒ₋₁ g'/g + (F $\scriptstyle\circ$ g)' and (iv) follows from (i) and (iii). Property (v) is clear from the definition.

[edit] The Lagrange inversion formula

As mentioned above, any formal series $f\in K[[X]]$ with $f 0 = 0$ and $f_1\neq0$ has a composition inverse $g\in K[[X]]$ . The following relation between the coefficients of $g (X) n$ and $f (X) - k$ holds ('Lagrange inversion formula"):

$\textstyle k[X^k] g^n=n[X^{-n}]f^{-k}.$

In particular, for n=1 and all k≥1,

$[X^k] g=\frac{1}{k} \mathrm{Res}\left( f^{-k}\right).$

Since the proof of the Lagrange inversion formula is a very short computation, it is worth reporting it here. By the above rules of calculus,

$k[X^k] g^n =k\mathrm{Res}\left( g^n X^{-k-1} \right) =k\mathrm{Res}\left(X^n f^{-k-1}f\,'\right) =-\mathrm{Res}\left(X^n (f^{-k})^'\right)$ $=\mathrm{Res}\left(\left(X^n\right)' f^{-k}\right) =n\mathrm{Res}\left(X^{n-1}f^{-k}\right) =n[X^{-n}]f^{-k}.$

[edit] Power series in several variables

It is relatively straightforward to extend the above ideas to define a formal power series ring over R in r variables, denoted R[[X₁,...,X_r]]. Elements of this ring may be expressed uniquely in the form

$\sum_{\mathbf{n}\in\Bbb{N}^r} a_\mathbf{n} \mathbf{X^n}$

where now n = (n₁,...,n_r) ∈ N^r, and Xⁿ denotes the monomial X₁^n₁...X_r^n_r. This sum converges for any choice of the coefficients a_n∈R, and the order of summation is immaterial.

[edit] Definition

One possible definition of R[[X₁,...,X_r]] is to take the completion of the polynomial ring R[X₁,...,X_r] in r variables with respect to the I-adic topology, where I is the ideal of R[X₁,...,X_r] generated by X₁,...,X_r. That is, I is the ideal consisting of polynomials with zero constant term.

Alternatively, one may proceed in a similar way to the more explicit discussion given above for the single-variable case, giving the ring structure first in terms of "multi-dimensional" sequences, and then defining the topology.

The topology on R[[X₁,...,X_r]] is the J-adic topology, where J is the ideal of R[[X₁,...,X_r]] generated by X₁,...,X_r. That is, J is the ideal consisting of series with zero constant term. Therefore, two series are considered "close" if their first few terms agree, where "first few" means terms whose total degree n₁ + ... + n_r is small.

[edit] Warning

Although R[[X₁, X₂]] and R[[X₁]][[X₂]] are isomorphic as rings, they do not carry the same topology. For example, the sequence of elements

$f_n = X_1^n, \quad n \geq 1$

converges to zero in R[[X₁, X₂]] as n → ∞; however, in the ring R[[X₁]][[X₂]], it does not converge, since the copy of R[[X₁]] embedded in R[[X₁]][[X₂]] has been given the discrete topology.

[edit] Operations

All of the operations defined for series in one variable may be extended to the several variables case.

Addition is carried out term-by-term.
Multiplication is carried out simply by "multiplying out" the series.
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 only if the constant term of g is zero.

In the case of the formal derivative, there are now r different partial derivative operators, which differentiate with respect to each of the r variables. They all commute with each other, as they do for continuously differentiable functions.

[edit] Universal property

In the several variables case, the universal property characterizing R[[X₁, ..., 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₁, ..., x_r are elements of I, then there is a unique Φ : R[[X₁, ..., X_n]] → S with the following properties:

Φ is an R-algebra homomorphism
Φ is continuous
Φ(X_i) = x_i for i = 1, ..., r.

[edit] 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 < b if and only if a + c < b + c for all c. Let I be a well-ordered subset of G, meaning I contains no infinite descending chain. Consider the set consisting of

$\sum_{i \in I} 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.

Various properties of R transfer to R((G)). If R is a field, then so is R((G)). If R is an ordered field, 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, 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.

[edit] Examples and related topics

Bell series are used to study the properties of multiplicative arithmetic functions

Contents

[edit] Informal introduction

[edit] The ring of formal power series

[edit] Definition of the formal power series ring

[edit] Ring structure

[edit] Topological structure

[edit] Universal property

[edit] Operations on formal power series

[edit] Inverting series

[edit] Extracting coefficients

[edit] Composition of series

[edit] Example

[edit] Composition inverse

[edit] Formal differentiation of series

[edit] Algebraic properties of the formal power series ring

[edit] Topological properties of the formal power series ring

[edit] Applications

[edit] Interpreting formal power series as functions

[edit] Generalizations

[edit] Formal Laurent series

[edit] Formal residue

[edit] The Lagrange inversion formula

[edit] Power series in several variables

[edit] Definition

[edit] Warning

[edit] Operations

[edit] Universal property

[edit] Replacing the index set by an ordered abelian group

[edit] Examples and related topics