An Invitation to Formal Power Series

In a first course on abstract algebra students learn the difference between polynomial (real-valued) functions familiar from high school and formal polynomials defined over arbitrary fields. In courses on analysis they learn further that certain “well-behaved” functions possess a Taylor series expansion, i.e. a power series which converges in a neighborhood of a point. On the other hand, the formal world of power series (where no convergence questions are asked) is not so often addressed in undergraduate courses.

The purpose of these expository notes is to give a far-reaching introduction to formal power series without appealing to any analytic machinery (we only use an elementary discrete metric). In doing so, we go well beyond a dated account undertaken by Niven [31] in 1969 (for instance, Niven cites Euler’s pentagonal theorem without proof). An alternative approach with different emphases can be found in Tutte [40, 41]. To illustrate the usefulness of formal power series we offer several combinatorial applications including some deep partition identities due to Ramanujan and others. This challenges the statement “While the formal analogies with ordinary calculus are undeniably beautiful, strictly speaking one can’t go much beyond Euler that way…” from the introduction of the recent book by Johnson [20]. While most proofs presented here are not new, they are scattered in the literature spanning five decades and, up to my knowledge, cannot be found in a unified treatment. Our main source of inspiration is the accessible book by Hirschhorn [17] (albeit based on analytic reasoning) in combination with numerous articles cited when appropriate. I hope that the present notes may serve as the basis of seminars for undergraduate and graduate students alike. The prerequisites do not go beyond a basic abstract algebra course (from Sect. 7 on, some knowledge of algebraic and transcendental field extensions is assumed).

The material is organized as follows: In the upcoming section we define the ring of formal power series over an arbitrary field and discuss its basis properties. Thereafter, we introduce our toolkit consisting of compositions, derivations and exponentiations of power series. In Sect. 4 we first establish the binomial theorems of Newton and Gauss and later obtain Jacobi’s famous triple product identity, Euler’s pentagonal number theorem and the Rogers–Ramanujan identities. In the subsequent section we apply the methods to combinatorial problems to obtain a number of generating functions. Most notably, we prove Ramanujan’s partitions congruences (modulo 5 and 7) as well as his so-called “most beautiful” formula. Another section deals with Stirling numbers, permutations, Faulhaber’s formula and the Lagrange–Jacobi four-square theorem. In Sect. 7 we consider formal Laurent series in order to prove the Lagrange–Bürmann inversion formula and Puiseux’ theorem on the algebraic closure. In the following section, multivariate power series enter the picture. We give proofs of identities of Vieta, Girad–Newton and Waring on symmetric polynomials. We continue by developing multivariate versions of Leibniz’ differentiation rule, Faá di Bruno’s rule and the inverse function theorem. In the final section we go somewhat deeper by taking matrices into account. After establishing the Lagrange–Good inversion formula, we culminate by proving MacMahon’s master theorem. Along the way we indicate analytic counterparts, connections to other areas and insert a few exercises.

The sets of positive and non-negative integers are denoted by \(\mathbb{N}=\{1,2,\ldots \}\) and \(\mathbb{N}_{0}=\{0,1,\ldots \}\) respectively.

Note that \(1,X,X^{2},\ldots \) is a \(K\)-basis of \(K[X]\), but not of \(K[[X]]\). Indeed, \(K[[X]]\) has no countable basis. Opposed to a popular trend to rename \(X\) to \(q\) (as in [17]), we always keep \(X\) as “formal” as possible.

The above proof does not require \(K\) to be a field. It works more generally for integral domains and this is needed later in Definition 8.1. From now on we will usually omit the multiplication symbol ⋅ and apply multiplications always before additions. For example, \(\alpha \beta -\gamma \) is shorthand for \((\alpha \cdot \beta )+(-\gamma )\). The scalar multiplication is compatible with the ring multiplication, i.e. \(\lambda (\alpha \beta )=(\lambda \alpha )\beta =\alpha (\lambda \beta )\) for \(\alpha ,\beta \in K[[X]]\) and \(\lambda \in K\). This turns \(K[[X]]\) into a \(K\)-algebra.

The reader may know that every ideal of \(K[X]\) is principal. The next lemma implies that every proper ideal of \(K[[X]]\) is a power of \((X)\) (hence, \(K[[X]]\) is a discrete valuation ring with unique maximal ideal \((X)\)).

We now start forming infinite sums of power series. To justify this process we introduce a discrete norm, which behaves much simpler than the euclidean norm on ℂ, for instance.

The number 2 in Definition 2.7 can of course be replaced by any real number greater than 1. Note that \(\alpha \) is invertible if and only if \(|\alpha |=1\). The following lemma turns \(K[[X]]\) into an ultrametric space.

Note that \(K[[X]]\) is the completion of \(K[X]\) with respect to \(d\). In order words: power series can be regarded as Cauchy series of polynomials. For convergent sequences \((\alpha _{k})_{k}\) and \((\beta _{k})_{k}\) we have (as in any metric space with multiplication) The infinite sum can only converge if \((\alpha _{k})_{k}\) is a null sequence, that is, \(\lim _{k\to \infty}|\alpha _{k}|=0\). Surprisingly and in stark contrast to euclidean spaces, the converse is also true as we are about to see. This crucial fact makes the arithmetic of formal power series much simpler than the analytic counterpart.

We often regard finite sequences as null sequences by extending them silently by 0. Let \(\alpha _{1},\alpha _{2},\ldots \in K[[X]]\) be a null sequence and \(\alpha _{k}=\sum _{n=0}^{\infty }a_{k,n}X^{n}\) for \(k\ge 1\). For every \(n\ge 0\) only finitely many of the coefficients \(a_{1,n},a_{2,n},\ldots \) are non-zero. This shows that the coefficient of \(X^{n}\) in depends on only finitely many terms. The same reasoning applies to the \(\prod _{k=1}^{\infty}(1+\alpha _{k})\).

For \(\gamma \in K[[X]]\) and null sequences \((\alpha _{k})\), \((\beta _{k})\) it holds that \(\sum \alpha _{k}+\sum \beta _{k}=\sum (\alpha _{k}+\beta _{k})\) and \(\gamma \sum \alpha _{k}=\sum \gamma \alpha _{k}\) as expected. Moreover, a convergent sum does not depend on the order of summation. In fact, for every bijection \(\pi \colon \mathbb{N}\to \mathbb{N}\) and \(n\in \mathbb{N}\) there exists some \(N\in \mathbb{N}\) such that \(\pi (k)>n\) for all \(k>N\). Hence, \(\alpha _{\pi (1)},\alpha _{\pi (2)},\ldots \) is a null sequence. We often exploit this fact by interchanging summation signs (discrete Fubini’s theorem).

If \(\alpha \) is a polynomial, it is clear that \(\alpha (\beta )\) is a valid power series, while for \(\beta \in (X)\) the convergence of \(\alpha (\beta )\) is guaranteed by Lemma 2.10. In the following we will always assume that one of these conditions is fulfilled. Observe that \(|\alpha (\beta )|\le |\alpha |\) if \(\beta \in (X)\).

We warn the reader that in general Nevertheless, the last statement can be corrected for the exponential series (Lemma 3.6).

For \(\alpha \in K[[X]]^{\circ}\), we call the unique \(\beta \in K[[X]]^{\circ}\) with \(\alpha (\beta )=X=\beta (\alpha )\) the reverse of \(\alpha \). To avoid confusion with the inverse \(\alpha ^{-1}\) (which is not defined here), we refrain from introducing a symbol for the reverse.

It seems natural to define formal integrals as counterparts, but this is less useful, since in characteristic 0 we have \(\alpha =\beta \) if and only if \(\alpha '=\beta '\) and \(\alpha (0)=\beta (0)\).

In characteristic 0, derivatives provide a convenient way to extract coefficients of power series. For \(\alpha =\sum a_{n}X^{n}\in K[[X]]\) we see that \(\alpha ^{(0)}(0)=\alpha (0)=a_{0}\), \(\alpha '(0)=a_{1}\), \(\alpha ''(0)=2a_{2},\ldots ,\alpha ^{(n)}(0)=n!a_{n}\). Hence, Taylor’s theorem (more precisely, the Maclaurin series) holds Over arbitrary fields we are not allowed to divide by \(n!\). Alternatively, one may use the \(k\)-th Hasse derivative defined by (the integer \(\binom{n}{k}\) can be embedded in any field). Note that \(H^{k}(\alpha )=k!\alpha ^{(k)}\) and \(\alpha =\sum _{n=0}^{\infty }H^{n}(\alpha )(0)X^{n}\). In the following we restrict ourselves to complex power series.

The product rule implies the rather trivial factor rule \((\lambda \alpha )'=\lambda \alpha '\) for \(\lambda \in K\) as well as Leibniz’ rule for \(\alpha ,\beta \in K[[X]]\). A generalized version of the latter and a chain rule for higher derivatives are proven in Sect. 8.

The only reason why we called the power series \(\log (1+X)\) instead of \(\log (X)\) or just log is to keep the analogy to the natural logarithm (as an analytic function).

By Lemma 3.6, for every \(c,d\in K\) as expected. Consequently, \(\bigl(\sqrt[k]{1+\alpha}\bigr)^{k}=1+\alpha \) for \(k\in \mathbb{N}\), i.e. \(\sqrt[k]{1+\alpha}\) is a \(k\)-th root of \(1+\alpha \) with constant term 1. Suppose that \(\beta \in K[[X]]\) also satisfies \(\beta ^{k}=1+\alpha \). Then \(\beta ^{-1}\sqrt[k]{1+\alpha}\) has order \(\le k\) in \(K[[X]]^{\times}\). From Lemma 2.5 we conclude that \(\beta ^{-1}\sqrt[k]{1+\alpha}\) is constant, i.e. \(\beta =\beta (0)\sqrt[k]{1+\alpha}\). Consequently, \(\sqrt[k]{1+\alpha}\) is the unique \(k\)-th of \(1+\alpha \) with constant term 1.

The inexperienced reader may find the following exercise helpful.

The field ℚ can be embedded into any field \(K\) of characteristic 0. For \(c\in K\) and \(k\in \mathbb{N}\) we extend the definition of usual binomial coefficient by (it is useful to know that numerator and denominator both have exactly \(k\) factors). The next theorem is a vast generalization of the binomial theorem (take \(c\in \mathbb{N}\)) and the geometric series (take \(c=-1\)).

A striking application of Theorem 4.1 will be given in Theorem 6.12.

Since we do not call our indeterminant \(q\) (as in many sources), it makes no sense to introduce the \(q\)-Pochhammer symbol \((q;q)_{n}\). Instead we devise a non-standard notation in reminiscence of the binomial coefficient.

As for the binomial coefficients, we have and for all \(n\in \mathbb{N}_{0}\) and \(k\in \mathbb{Z}\). Moreover, . The familiar recurrence formula for binomial coefficients needs to be altered as follows.

Since and are polynomials, (4.2) shows inductively that all Gaussian coefficients are polynomials. We may therefore evaluate at \(X=1\). Indeed, (4.2) becomes the recurrence for the binomial coefficients if \(X=1\). Hence . This can be seen more directly by writing We will interpret the coefficients of in Theorem 5.4.

The next formulas resemble \((1+X)^{n}=\sum _{k=0}^{n}\binom{n}{k}X^{k}\) and \((1-X)^{-n}= \sum _{k=0}^{\infty}\binom{n+k-1}{k}X^{k}\) from Newton’s binomial theorem. The first is a finite sum, the second an infinite formal series arising from some sort of inverses. We will encounter many more such “dual pairs” in Theorem 6.9, Theorem 8.4 and (9.3), (9.4).

Using we obtain an infinite variant of Gauss’ theorem:

If \(\alpha \in (X)\), we can apply (4.5) with \(\alpha X^{-1}\) to obtain We are now in a position to derive one of the most powerful theorems on power series.

A (somewhat analytical) proof only making use of (4.4) can be found in [45]. There are numerous purely combinatorial proofs like [23, 27, 38, 39, 44, 46], which are meaningful for formal power series.

To obtain yet another triple product identity, we first consider a finite version due to Hirschhorn [15].

In an analytic framework, Theorem 4.13 can be derived from Theorem 4.9 (see [14, Theorem 357]). A combinatorial proof was given in [21].

As a preparation for the infamous Rogers–Ramanujan identities [35], we start again with a finite version due to Bressoud [7]. The impatient reader may skip these technical results and start right away with the applications in Sect. 5 (Theorem 4.15 is only needed in Theorem 5.5(v), (vi)).

The Rogers–Ramanujan identities were long believed to lie deeper within the theory of elliptic functions (Hardy [14, p. 385] wrote “No proof is really easy (and it would perhaps be unreasonable to expect an easy proof.”; Andrews [4, p. 105] wrote “…no doubt it would be unreasonable to expect a really easy proof.”). Meanwhile a great number of proofs were found, some of which are combinatorial (see [3] or the recent book [36]). An interpretation of these identities is given in Theorem 5.5 below. We point out that there are many “finite identities”, like Lemma 4.14, approaching the Rogers–Ramanujan identities (as there are many rational sequences approaching \(\sqrt{2}\)).

One can find many more interesting identities, like the quintuple product, along with comprehensive references (and analytic proofs) in Johnson [20].

In this section we bring to life all of the abstract theorems and identities of the previous section. If \(a_{0},a_{1},\ldots \) is a sequence of numbers usually arising from combinatorial context, the power series \(\alpha =\sum a_{n}X^{n}\) is called the generating function of \((a_{n})_{n}\). Although this seems pointless at first, power series manipulations often reveal explicit formulas for \(a_{n}\), which can hardly be seen by inductive arguments. We give a first impression with the most familiar generating functions.

We now focus on combinatorial objects which defy explicit formulas.

There is a remarkable connection between (iii), (iv) and (v) of Theorem 5.5: Numbers not divisible by 3 are of the form \(\pm 1+3k\), while odd numbers are of the form \(\pm 1+4k\).

Some of the statements in Theorem 5.5 permit nice combinatorial proofs utilizing Young diagrams (or Ferres diagrams). We refer the reader to the introductory book [5]. The following exercise (inspired by [5]) can be solved with formal power series.

The reader may have noticed that Euler’s pentagonal number theorem (4.10) is just the inverse of the generating function of \(p(n)\) from Theorem 5.4, i.e. and therefore for \(n\in \mathbb{N}\), where \(p(k):=0\) whenever \(k<0\). This leads to a recurrence formula

The generating functions we have seen so far all have integer coefficients. If \(\alpha ,\beta \in \mathbb{Z}[[X]]\) and \(d\in \mathbb{N}\), we write \(\alpha \equiv \beta \pmod{d}\), if all coefficients of \(\alpha -\beta \) are divisible by \(d\). This is compatible with the ring structure of \(\mathbb{Z}[[X]]\), namely if \(\alpha \equiv \beta \pmod{d}\) and \(\gamma \equiv \delta \pmod{d}\), then \(\alpha +\gamma \equiv \beta +\delta \pmod{d}\) and \(\alpha \gamma \equiv \beta \delta \pmod{d}\). Now suppose \(\alpha \in 1+(X)\). Then the proof of Lemma 2.5 shows \(\alpha ^{-1}\in \mathbb{Z}[[X]]\). In this case \(\alpha \equiv \beta \pmod{d}\) is equivalent to \(\alpha ^{-1}\equiv \beta ^{-1}\pmod{d}\). If \(d=p\) happens to be a prime, we have as in any commutative ring of characteristic \(p\).

With this preparation, we come to a remarkable discovery by Ramanujan [34].

Ramanujan has also discovered the congruence \(p(11n+6)\equiv 0\pmod{11}\) for all \(n\in \mathbb{N}_{0}\) (the reader finds the history of this and other results in [5, 17], for instance). This was believed to be more difficult to prove, until elementary proofs were found by Marivani [29], Hirschhorn [16] and others (see also [17, Sect. 3.5]). The details are however extremely tedious to verify by hand.

By the Chinese remainder theorem, two congruence of coprime moduli can be combined as in Ahlgren [1] (building on Ono [33]) has shown that in fact for every integer \(k\) coprime to 6 there is such a congruence modulo \(k\). Unfortunately, they do not look as nice as Theorem 5.9. For instance,

The next result explains the congruence modulo 5 and is known as Ramanujan’s “most beautiful” formula (since Theorem 4.15 was first discovered by Rogers).

Partitions can be generalized to higher dimensions. A plane partition of \(n\in \mathbb{N}\) is an \(n\times n\)-matrix \(\lambda =(\lambda _{ij})\) consisting of non-negative integers such that Ordinary partitions can be regarded as plane partitions with only one non-zero row. The number \(pp(n)\) of plane partitions of \(n\) has the fascinating generating function discovered by MacMahon (see [37, Corollary 7.20.3]).

We cannot resist to present a few more exciting combinatorial objects related to power series. Since literally hundreds of such combinatorial identities are known, our selection is inevitably biased by personal taste.

Unlike the binomial or Gaussian coefficients the Stirling numbers do not obey a symmetry as in Pascal’s triangle. While the generating functions of \(b(n)\) and have no particularly nice shape, there are close approximations which we are about to see.

Now we discuss permutations.

Since \(|S_{n}|=n!\), there is no need for a generating function of the number of permutations.

While the recurrences relations we have seen so far appear arbitrary, they can be explained in a unified way (see [24]).

It is time to present the next dual pair of formulas resembling Theorem 4.6.

For readers who still do not have enough, the next exercise might be of interest.

The cycle type of a permutation \(\sigma \in S_{n}\) is denoted by \((1^{a_{1}},\ldots ,n^{a_{n}})\), meaning that \(\sigma \) has precisely \(a_{k}\) cycles of length \(k\).

The following is a sibling to Glaisher’s theorem. For a non-negative real number \(r\) we denote the largest integer \(n\le r\) by \(n=\lfloor r\rfloor \).

We insert a well-known application of Bernoulli numbers.

Even though Faulhaber’s formula \(1^{d}+2^{d}+\cdots +n^{d}=\alpha (n)\) has not much to do with power series, there still is a dual formula, again featuring Bernoulli numbers: Strangely, no such formula is known to hold for odd negative exponents (perhaps because \(b_{2d+1}=0\)?). In fact, it is unknown if Apéry’s constant \(\sum _{k=1}^{\infty}\frac{1}{k^{3}}=1{,}202\ldots \) is transcendent.

We end this section with a power series proof of the famous four-square theorem.

Theorem 6.17 is best possible in the sense that every integers \(n\equiv 7\pmod{8}\) is not the sum of three squares since \(a^{2}+b^{2}+c^{2}\not \equiv 7\mod{8}\).

If \(n,m\in \mathbb{N}\) are sums of four squares, so is \(nm\) by the following identity of Euler (encoding the multiplicativity of the norm in Hamilton’s quaternion skew field): This reduces the proof of the first assertion (Lagrange’s) of Theorem 6.17 to the case where \(n\) is a prime.

Waring’s problem ask for the smallest number \(g(k)\) such that every positive integer is the sum of \(g(k)\) non-negative \(k\)-th powers. Hilbert proved that \(g(k)<\infty \) for all \(k\in \mathbb{N}\). We have \(g(1)=1\), \(g(2)=4\) (Theorem 6.17), \(g(3)=9\), \(g(4)=19\) and in general it is conjectured that (see [25]). Curiously, only the numbers \(23=2\cdot 2^{3}+7\cdot 1^{3}\) and \(239=2\cdot 4^{3}+4\cdot 3^{3}+3\cdot 1^{3}\) require nine cubes. It is even conjectured that every sufficiently large integer is a sum of only four non-negative cubes (see [11]).

Every integral domain \(R\) can be embedded into its field of fractions consisting of the formal fractions \(\frac{r}{s}\) where \(r,s\in R\) and \(s\ne 0\) (this is the smallest field containing \(R\) as a subring). For our ring \(K[[X]]\) these fractions have a more convenient shape.

If a Laurent series is a finite sum, it is naturally called a Laurent polynomial. The ring of Laurent polynomials is denoted by \(K[X,X^{-1}]\), but plays no role in the following. In analysis one allows double infinite sums, but then the product is no longer well defined as in \(\Bigl(\sum _{n=-\infty}^{\infty }X^{n}\Bigr)^{2}\).

Of course, we will view \(K[[X]]\) as a subring of \(K((X))\). In fact, \(K[[X]]\) is the valuation ring of \(K((X))\), i.e. \(K[[X]]=\{\alpha \in K((X)):|\alpha |\le 1\}\). The field \(K((X))\) should not be confused with the field of rational functions \(K(X)\), which is the field of fractions of \(K[X]\).

If \(\alpha \in K((X))\) and \(\beta \in K[[X]]^{\circ}\), the substitute \(\alpha (\beta )\) is still well-defined and Lemma 3.3 remains correct (\(\alpha \) deviates from a power series by only finitely many terms).

The residue is a \(K\)-linear map such that \(\operatorname{res}(\alpha ')=0\) for all \(\alpha \in K((X))\).

Since Theorem 7.5 is actually a statement about power series, it should be mentioned that \(\operatorname{res}(\alpha ^{-k})\) is just the coefficient of \(X^{k-1}\) in the power series \((X/\alpha )^{k}\). This interpretation will be used in our generalization to higher dimensions in Theorem 9.8.

Our next objective is the construction of the algebraic closure of \(\mathbb{C}((X))\). We need a well-known tool.

One can proceed to show that \(\beta \) and \(\gamma \) are uniquely determined in the situation of Lemma 7.7, but we do not need this in the following. Indeed, since \(R\) is a principal ideal domain, \(R[Y]\) is a factorial ring (also called unique factorization domain) by Gauss’ lemma. This means that every monic polynomial in \(R[Y]\) has a unique factorization into monic irreducible polynomials. For every irreducible factor \(\omega \) of \(\alpha \), \(\bar{\omega}\) either divides \(\alpha _{1}\) or \(\alpha _{2}\) (but not both). This determines the prime factorization of \(\beta \) and \(\gamma \) uniquely.

We have seen that invertible power series in \(\mathbb{C}[[X]]\) have arbitrary roots. On the other hand, \(X\) does not even have a square root in \(\mathbb{C}((X))\). This suggests to allow \(X\) not only to negative powers, but also to fractional powers.

It is straight-forward to check that \((K\{\{X\}\},+,\cdot )\) is a field. At this point we have established the following inclusions:

In Remark 4.7 and even more in the last two results it became clear that power series in more than one indeterminant make sense. We give proper definitions now.

Once we have convinced ourselves that Lemma 2.2 remains true when \(K\) is replaced by an integral domain, it becomes evident that also \(K[[X_{1},\ldots ,X_{n}]]\) is an integral domain. Likewise the norm \(|\alpha |\) still gives rise to a complete ultrametric (to prove \(|\alpha \beta |=|\alpha ||\beta |\) one may assume that \(\alpha \) and \(\beta \) are homogeneous polynomials) and the crucial Lemma 2.10 holds in \(K[[X_{1},\ldots ,X_{n}]]\) too. We stress that this metric is finer than the one induced from \(K[[X_{1},\ldots ,X_{n-1}]]\) as, for example, the sequence \((X_{1}^{k}X_{2})_{k}\) converges in the former, but not in the latter (with \(n=2\)). Moreover, a power series \(\alpha \) is invertible in \(K[[X_{1},\ldots ,X_{n}]]\) if and only if its constant term is non-zero. Indeed, after scaling, the constant term is 1 and converges.

Unlike \(K[X]\) or \(K[[X]]\), the multivariate rings are not principal ideal domains, but one can show that they are still factorial (see [26, Theorem IV.9.3]). We do not require this fact in the sequel.

The degree function equips \(K[X_{1},\ldots ,X_{n}]\) with a grading, i.e. we have and \(P_{d}P_{e}\subseteq P_{d+e}\) where \(P_{d}\) denotes the set of homogeneous polynomials of degree \(d\). In the following we will restrict ourselves mostly to polynomials of a special type. Note that if \(\alpha ,\beta _{1},\ldots ,\beta _{n}\in K[X_{1},\ldots ,X_{n}]\), we can substitute \(X_{i}\) by \(\beta _{i}\) in \(\alpha \) to obtain \(\alpha (\beta _{1},\ldots ,\beta _{n})\in K[X_{1},\ldots ,X_{n}]\). It is important that these substitutions happen simultaneously and not one after the other (more about this at the end of the section).

It is easy to see that the symmetric polynomials form a subring of \(K[X_{1},\ldots ,X_{n}]\).

Keep in mind that \(\sigma _{k}\), \(\tau _{k}\) and \(\rho _{k}\) depend on \(n\). All three sets of polynomials are homogeneous. The elementary and complete symmetric polynomials are special instances of Schur polynomials, which we do not attempt to define here.

When we specialize \(X_{1}=\cdots =X_{n}=1\) in Vieta’s theorem (as we may), we recover the generating functions of the binomial coefficients and the multiset counting coefficients in Example 5.1. When we substitute \(X_{k}=k\) for \(k=1,\ldots ,n\), we obtain a new formula for the Stirling numbers by virtue of Theorem 6.9.

It is easy to see that the grading by degree carries over to symmetric polynomials. The following theorem shows that the elementary symmetric polynomials are the building blocks of all symmetric polynomials.

From an algebraic point of view, Theorem 8.5 (applied to \(\alpha =0\)) states that the elementary symmetric polynomials \(\sigma _{1},\ldots ,\sigma _{n}\) are algebraically independent over \(K\), so they form a transcendence basis of \(K(X_{1},\ldots ,X_{n})\) (recall that \(K(X_{1},\ldots ,X_{n})\) has transcendence degree \(n\)). The identities in the next theorem express the \(\sigma _{i}\) recursively in terms of the \(\tau _{j}\) and in terms of the \(\rho _{j}\). So the latter sets of symmetric polynomials form transcendence bases too. It is no coincidence that \(\deg (\sigma _{k})=\deg (\tau _{k})=\deg (\rho _{k})=k\) for \(k\le n\). A theorem from invariant theory (in characteristic 0) implies that any algebraically independent, symmetric, homogeneous polynomials \(\lambda _{1},\ldots ,\lambda _{n}\) have degrees \(1,\ldots ,n\) in some order (see [19, Proposition 3.7]).

Now that we know that each of the \(\sigma _{i}\), \(\tau _{i}\) and \(\rho _{i}\) can be expressed by the other two sets of polynomials, it is natural to ask for explicit formulas. This is achieved by Waring’s formula. Here \(P(n)\) stands for the set of partitions of \(n\) as introduced in Definition 5.2.

We invite the reader to prove the other four transition formulas.

We leave polynomials to fully develop multivariate power series.

Note that \(\partial _{i}\) is a linear operator, which commutes with \(\partial _{j}\) for \(j=1,\ldots ,n\) (Schwarz’ theorem). Indeed, by linearity it suffices to check We need a fairly general form of the product rule.

Our next goal is the multivariate chain rule for (higher) derivatives. We equip \(K[[X_{1},\ldots ,X_{n}]]^{n}\) with the direct product ring structure and use the shorthand notation \(\alpha :=(\alpha _{1},\ldots ,\alpha _{n})\) and \(0:=(0,\ldots ,0)\). Write provided this is well-defined. It is not difficult to show that as in Lemma 3.3. It was remarked by M. Hardy [13] that Leibniz’ rule as well as the chain rule become slightly more transparent when we give up on counting multiplicities of derivatives as follows.

In this final section we enter a non-commutative world by making use of matrices. The ultimate goal is the master theorem found and named by MacMahon [28, Chapter II]. Since \(K[[X_{1},\ldots ,X_{n}]]\) can be embedded in its field of fractions, the familiar rules of linear algebra (over fields) remain valid in the ring \(K[[X_{1},\ldots ,X_{n}]]^{n\times n}\) of \(n\times n\)-matrices with coefficients in \(K[[X_{1},\ldots ,X_{n}]]\). In particular, the determinant of \(A=(\alpha _{ij})_{i,j}\) can be defined by Leibniz’ formula (not rule) It follows that \(\det (A(0))=\det (A)(0)\) by (8.5). Recall that the adjoint of \(A\) is defined by \(\operatorname{adj}(A):=\bigl((-1)^{i+j}\det (A_{ji})\bigr)_{i,j}\) where \(A_{ji}\) is obtained from \(A\) by deleting the \(j\)-th row and \(i\)-th column. Then where \(1_{n}\) denotes the identity \(n\times n\)-matrix. This shows that \(A\) is invertible if and only if \(\det (A)\) is invertible in \(K[[X_{1},\ldots ,X_{n}]]\), i.e. \(\det (A)\) has a non-zero constant term. Expanding the entries of \(A\) as \(\alpha _{ij}=\sum a^{(i,j)}_{k_{1},\ldots ,k_{n}}X_{1}^{k_{1}} \ldots X_{n}^{k_{n}}\) gives rise to a natural bijection Clearly, \(\Omega \) is a vector space isomorphism. To verify that it is even a ring isomorphism, it is enough to consider matrices \(A\), \(B\) with only one non-zero entry each. But then \(AB=0\) or \(AB\) is just the multiplication in \(K[[X_{1},\ldots ,X_{n}]]\). So we can now freely pass from one ring to the other, keeping in mind that we are dealing with power series with non-commuting coefficients! Allowing some flexibility, we can also expand \(A=\sum _{i} A_{i}X_{k}^{i}\) where \(k\) is fixed and \(A_{i}\in K[[X_{1},\ldots ,X_{k-1},X_{k+1},\ldots ,X_{n}]]^{n\times n}\). This suggests to define The sum and product differentiation rules remain correct, but the power rule \(\partial _{k}(A^{s})=s\partial _{k}(A)A^{s-1}\) (and in turn Leibniz’ rule) does not hold in general, since \(A\) might not commute with \(\partial _{k}A\).

The next two results are just warm-ups and are not needed later on.

If \(\operatorname{char}K=0\) and \(A\in K^{n\times n}[[X_{1},\ldots ,X_{n}]]\) has zero constant term, then \(\exp (A)=\sum _{k=0}^{\infty}\frac{A^{k}}{k!}\) converges in the topology induced by the norm. Since the constant term is \(1_{n}\), \(\exp (A)\) is invertible.

For \(n=1\) we have \(\alpha \in K[[X_{1},\ldots ,X_{n}]]^{\circ}\iff \alpha (0)=0\ne \alpha '(0)\iff \alpha \in (X)\setminus (X^{2})\), so our notation is consistent with Theorem 3.4. The following is a multivariate analog.

If \(\operatorname{char}K=0\) and \(\alpha _{1},\ldots ,\alpha _{n}\in K[X_{1},\ldots ,X_{n}]\) are polynomials such that \(\det (J(\alpha ))\in K^{\times}\), the Jacobi conjecture (put forward by Keller [22] in 1939) claims that there exist polynomials \(\beta _{1},\dots ,\beta _{n}\) such that \(\alpha \circ \beta =(X_{1},\ldots ,X_{n})\). This is still open even for \(n=2\) (see [42]).

An explicit formula for the reverse (i.e. the inverse with respect to ∘) is given by the following multivariate version of Theorem 7.5. To simplify the proof (which is still difficult) we restrict ourselves to those \(\beta \in K[[X_{1},\ldots ,X_{n}]]\) such that \(\beta _{i}\in X_{i}C_{1}\subseteq C_{0}\). Note that \(J(\beta )(0)=1_{n}\) here.

In an attempt to unify and generalize some dual pairs we have already found, we study the following setting. Let \(A=(a_{ij})\in K^{n\times n}\) and \(D=\operatorname{diag}(X_{1},\ldots ,X_{n})\). For \(I\subseteq N:=\{1,\ldots ,n\}\) let \(A_{I}:=(a_{ij})_{i,j\in I}\) and \(X_{I}=\prod _{i\in I}X_{i}\). Since the determinant is linear in every row, we obtain Altogether, where \(\det (A_{\varnothing})=1\) for convenience. The dual equation, discovered by Vere-Jones [43], uses the permanent \(\operatorname{per}(A)=\sum _{\sigma \in S_{n}}a_{1\sigma (1)}\ldots a_{n \sigma (n)}\) of \(A\): where \(I\) now runs through all tuples of elements in \(N\) (in contrast to the determinant, \(\operatorname{per}(A_{I})\) does not necessarily vanish if \(A_{I}\) has identical rows). We will derive (9.4) in Corollary 9.10 from the following result, which seems more amenable to applications.

A graph-theoretical proof of Theorem 9.9 was given by Foata and is presented in [8, Sect. 9.4]. There is also a short analytic argument which reduces the claim to the easy case where \(A\) is a triangular matrix.

We illustrate with some examples why MacMahon called Theorem 9.9 the master theorem (as he was a former major, I am tempted to called it the \(M^{4}\)-theorem).

We end with a short outlook. Power series with an infinite set of indeterminants \(\{X_{i}:i\in I\}\) can be defined by Moreover, power series in non-commuting indeterminants exists and form what is sometimes called the Magnus ring \(K\langle \langle X_{1},\ldots ,X_{n}\rangle \rangle \) (the polynomial version is the free algebra \(K\langle X_{1},\ldots ,X_{n}\rangle \)). The Lie bracket \([a,b]:=ab-ba\) turns \(K\langle \langle X_{1},\ldots ,X_{n}\rangle \rangle \) into a Lie algebra and fulfills Jacobi’s identity The functional equation for \(\exp (X)\) is replaced by the Baker–Campbell–Hausdorff formula in this context.

The reader might ask about formal Laurent series in multiple indeterminants. Although the field of fractions \(K((X_{1},\ldots ,X_{n}))\) certainly exists, its elements do not look like one might expect. For example, the inverse of \(X-Y\) could be \(\sum _{k=1}^{\infty }X^{-k}Y^{k-1}\) or \(-\sum _{k=1}^{\infty }X^{k-1}Y^{-k}\). The first series lies in \(K((X))((Y))\), but not in \(K((Y))((X))\). For the second series it is the other way around.