Introduction to Polynomials and Generating Functions

Polynomials and generating functions

Manipulating finite- and infinite-term polynomials is an important topic in OI mathematics, especially in the study of generating functions.

Polynomial algorithms based on the fast Fourier transform give algorithm-competition contestants the ability to manipulate generating functions directly.

Basic concepts

For the sum $\sum a_nx^n$, if it has finitely many terms, it is called a polynomial and denoted by $f(x)=\sum_{n=0}^m a_nx^n$.

A sum with countably many terms is called a series. In the sum $\sum_{n=0}^\infty a_nx^n$, every term is a constant coefficient times a nonnegative integer power of the variable; a series of this form is called a power series.

When studying polynomial arithmetic, we first consider the simpler polynomial case; the concept of a power series is used only for convenience. Mathematical analysis further studies the convergence and divergence of power series.

For general definitions of rings, fields, and their derived structures, see Basic concepts of abstract algebra.

For a general ring $R$, define the polynomial ring over $R$, denoted $R[x]$.

Each element $f$ is called a polynomial over $R$ and can be written as

$$f=\left<f_0,f_1,f_2,\cdots,f_n\right>\quad(f_0,f_1,f_2,\cdots,f_n\in R)$$

In other words, we define a polynomial directly as a sequence of coefficients. It can also be written as

$$f(x)=f_0+f_1x+f_2x^2+\cdots+f_nx^n$$

Here, $x$ is regarded merely as a formal symbol, an identifier for the positions of the coefficients.

If we also allow infinitely many terms, namely

$$f(x)=f_0+f_1x+f_2x^2+\cdots$$

we obtain the formal power series ring $R[[x]]$. Each element $f$ is called a formal power series, abbreviated to power series below.

Degree of a polynomial

For a polynomial $f(x)$, the degree of its highest-degree term is called the degree of the polynomial, denoted by $\operatorname{deg}{f}$.

Polynomial multiplication

The most fundamental operation is multiplying two polynomials. Given polynomials $f(x)$ and $g(x)$:

$$\begin{alignedat}{3} f(x)&=a_0+a_1x+\dots+a_nx^n\quad \quad &(1)\\ g(x)&=b_0+b_1x+\dots+b_mx^m\quad \quad &(2) \end{alignedat}$$

To compute the polynomial $Q(x)=f(x)\cdot g(x)$:

$$\boxed {Q(x) = \sum \limits_ {i = 0} ^ n \sum \limits_ {j = 0 } ^ m a_i b_j x ^ {i + j}} = c_0 + c_1 x + \dots + c_ {n + m} x ^ {n + m}$$

Multiplication of polynomials or power series is associative and distributes over addition. If $R$ is a commutative ring or a ring with identity, multiplication also has commutativity and an identity element, respectively.

If $R$ contains a $2^n$-th root of unity, the fast Fourier transform allows us to compute, in $O(n2^n)$ time instead of $O(2^{2n})$ time, the product of two degree-$2^n$ polynomials.

Composition

In $R[[x]]$, define the powers of an element $f$ by

$$f^1=f,f^k=f^{k-1}\times f$$

Based on this, for elements of $R[[x]]$ denoted $f,g$, define their composition by

$$(f\circ g)(x)=f(g(x))=f_0+\sum_{k=1}^{+\infty}f_kg^k(x)$$

We stipulate that $f\circ g$ exists if and only if $f$ has finitely many terms or $g_0=0$, so no limits over $R$ are involved.

$\circ$ is associative (whenever both $(f\circ g)\circ h$ and $f\circ (g\circ h)$ exist), but not commutative. When $R$ is a ring with identity, $\circ$ has the identity element $1\times x$.

Polynomial composition (and compositional inversion) can be performed in $\Theta(n\log^2 n)$ time. The method was proposed by Yasunori Kinoshita and Li Baitian in 2024; see Formal power series composition | compositional inversion.

Derivative

Although a general ring may not even have limits,
we can still define the formal derivative of a formal power series as

$$\left(\sum_{k=0}^{+\infty}f_kx^k\right)'=\sum_{k=1}^{+\infty}kf_kx^{k-1}$$

where

$$kf_k=\underbrace{f_k+f_k+\cdots+f_k}_{k \text{个} f_k}$$

The basic differentiation rules—the sum rule, product rule, and chain rule (when composition is allowed)—remain valid.

If division is allowed in $R$, we can similarly define the formal indefinite integral of a formal power series.

Multiplicative inverse

From the example

$$\dfrac{1}{1-x}=1+x+x^2+\cdots$$

we see that the reciprocal of a polynomial can be expanded as an infinite series. A reciprocal exists if and only if the constant term is not $0$, and its reciprocal also has a constant term not equal to $0$.

Thus, for a formal power series $f$ with $f_0\not=0$, define its multiplicative inverse $f^{-1}$ to be another formal power series satisfying

$$f\times f^{-1}=f^{-1}\times f=1$$

Expanding this equation using formal power series multiplication gives the recurrence for the coefficients of $f^{-1}$:

$$f^{-1}_0=\dfrac{1}{f_0},f^{-1}_n=\dfrac{-1}{f_0}\sum_{k=0}^{n-1}f^{-1}_kf_{n-k}$$

Computing the first $n$ terms directly from the recurrence takes $O(n^2)$ time; using the FFT gives an $O(n\log n)$ algorithm.

Note

It is easy to see that the reciprocal of $f(x)$ is the infinite Maclaurin expansion of $\frac{1}{f(x)}$ (the Taylor expansion at $x=0$).

Common power-series expansions

In mathematical analysis, a univariate function that is differentiable to some order at a point or on an interval can be expanded into a polynomial over the corresponding range. This is generally called a Taylor expansion; an expansion at $0$ is also called a Maclaurin expansion.

If a function is infinitely differentiable, it can be expanded as a power series. The most common expansion point is still $0$.

In complex analysis, some functions cannot be Taylor-expanded at a singularity but can be expanded in a Laurent series.

The following equalities hold only when the power series converge; they do not hold when the series diverge. We give only the expansions and do not discuss their domains of convergence.

The two basic expansions are those of the exponential and power functions:

$$\mathrm{e}^x=1+x+\frac{1}{2!}x^2+\ldots+\frac{1}{n!}x^n+\ldots$$ $$(1+x)^a=1+ax+\frac{a(a-1)}{2!}x^2+\ldots+\frac{a(a-1)\ldots(a-n+1)}{n!}x^n+\ldots$$

More expansions can often be derived by transforming these two. For example, the trigonometric functions are obtained by substituting complex numbers into the exponential function:

$$\cos x=1-\frac{1}{2!}x^2+\frac{1}{4!}x^4+\ldots+\frac{(-1)^n}{(2n)!}x^{2n}+\ldots$$ $$\sin x=x-\frac{1}{3!}x^3+\frac{1}{5!}x^5+\ldots+\frac{(-1)^n}{(2n+1)!}x^{2n+1}+\ldots$$

The logarithm, arctangent, and arcsine functions are obtained by integration:

$$\frac{1}{1+x}=1-x+x^2+\ldots+{(-1)}^n x^n+\ldots$$ $$\ln(1+x)=x-\frac{1}{2}x^2+\frac{1}{3}x^3+\ldots+\frac{{(-1)}^{n-1}}{n}x^n+\ldots$$ $$\frac{1}{1+x^2}=1-x^2+x^4+\ldots+{(-1)}^n x^{2n}+\ldots$$ $$\arctan x=x-\frac{1}{3}x^3+\frac{1}{5}x^5+\ldots+\frac{{(-1)}^{n}}{2n+1}x^{2n+1}+\ldots$$ $$\frac{1}{\sqrt{1+x}}=1-\frac{1}{2}x+\frac{3}{8}x^2+\ldots+{(-1)}^n\frac{(2n)!}{{(n!)}^2 4^n} x^{n}+\ldots$$ $$\frac{1}{\sqrt{1-x^2}}=1+\frac{1}{2}x^2+\frac{3}{8}x^4+\ldots+\frac{(2n)!}{{(n!)}^2 4^n} x^{2n}+\ldots$$ $$\arcsin x=x+\frac{1}{6}x^3+\frac{3}{40}x^5+\ldots+\frac{(2n)!}{{(n!)}^2(2n+1)4^n} x^{2n+1}+\ldots$$

Compositional inverse

Compositional inversion is the extension of the concept of an inverse function to the formal power series ring.

For a formal power series with $f_0=0$ and $f_1\not=0$, denoted $f$, its compositional inverse is the formal power series satisfying $g(f(x))=f(g(x))=x$, denoted $g$. Lagrange inversion gives, for any integers $n,k$,

$$n[x^n]f^k=k[x^{n-k}]\left(\dfrac{x}{g}\right)^n$$

Here, $[x^k]f(x)$ denotes the coefficient of $f(x)$ at $x^k$.

Polynomial divisibility

For polynomials $f(x)$ and $g(x)$, if there exists a polynomial $h(x)$ such that

$$f(x)=g(x)h(x)$$

then $g(x)$ divides $f(x)$.

It is clear that $g(x)$ divides $f(x)$ if and only if every root of $g(x)$ is a root of $f(x)$, with multiplicity in $g(x)$ no greater than the corresponding multiplicity in $f(x)$.

Polynomial remainders and quotients

For polynomials $f(x), g(x)$, there are unique polynomials $Q(x), R(x)$ satisfying

$$\begin{aligned} f(x) &= Q(x) g(x) + R(x) \\ \operatorname{deg}{R} &< \operatorname{deg}{g} \end{aligned}$$

When $\operatorname{deg}{f} \ge \operatorname{deg}{g}$, we have $\operatorname{deg}{Q} = \operatorname{deg}{f} - \operatorname{deg}{g}$; otherwise, $Q(x) = 0$. We call $Q(x)$ the quotient, with $g(x)$ as the divisor and $f(x)$ as the dividend, and call $R(x)$ the remainder, with $g(x)$ as the divisor and $f(x)$ as the dividend.

Polynomial congruences

Polynomial congruence is the subring of a polynomial ring obtained by quotienting the polynomial ring by the equivalence relation of congruence.

In the polynomial division with remainder discussed above, $f(x)$ and its remainder $R(x)$ are congruent modulo the polynomial $g(x)$.

$$f(x) \equiv R(x) \pmod{g(x)}$$

This congruence also means that, for the polynomial $g(x)$, substituting any root $x_0$ into $f(x)$ and $R(x)$ gives the same value:

$$f(x_0)=R(x_0)$$

Moreover, if $x_0$ is a root of the polynomial $g(x)$ with multiplicity $k$, meaning that $(x-x_0)^k$ divides $g(x)$, then for every integer at least $0$ and less than $k$, denoted by $t$,

$$f^{t}(x_0)=R^{t}(x_0)$$

Here, the notation denotes the $t$-th derivative.

Polynomial congruence can also be applied to power series. An infinite power series can be congruent to a finite polynomial modulo a specific polynomial. For example:

$$1+x+x^2+x^3+\ldots \equiv 1+x+\ldots+x^{n-1} \pmod{x^n}$$

Clearly, all remaining terms are divisible by $x^n$. Therefore, operating modulo $x^n$ is equivalent to truncation: truncate the power series to its first $n$ terms, directly discarding all higher-order information.

In some specific cases, we can also work modulo other polynomials; the corresponding cases are explained below.

Multi-point evaluation and interpolation of polynomials

Multi-point evaluation of a polynomial means, given a polynomial $f(x)$ and $n$ points $x_{1}, x_{2}, \dots, x_{n}$, computing

$$f(x_{1}), f(x_{2}), \dots, f(x_{n})$$

Polynomial interpolation means, given $n+1$ points

$$(x_{0}, y_{0}), (x_{1}, y_{1}), \dots, (x_{n}, y_{n})$$

finding an $n$-th degree polynomial $f(x)$ such that all $n+1$ points lie on $f(x)$.

The essence of these two operations is converting a polynomial between its coefficient representation and point-value representation. Multi-point evaluation converts the coefficient representation into the point-value representation, while interpolation converts the point-value representation into the coefficient representation.

Note

From the viewpoint of power series, multi-point evaluation compresses the information in infinitely many terms into finitely many point values, and therefore loses some information; interpolation restores the coefficient representation up to the corresponding degree.

In common programming applications of evaluation and interpolation, such as the discrete Fourier transform and its inverse, the selected $n+1$ points all have multiplicity $1$, that is, they are pairwise distinct, avoiding the need for derivatives.

This kind of compression guarantees agreement only at the $n+1$ selected points. According to the explanation of polynomial congruence above, if a power series $f(x)$ is evaluated at points $x_0$ through $x_n$ and then interpolated to obtain a polynomial $R(x)$, define

$$g(x)=(x-x_0)\ldots(x-x_n)$$

Then

$$f(x) \equiv R(x) \pmod{g(x)}$$

Since the degree of $R(x)$ is strictly less than that of $g(x)$, the $R(x)$ obtained through evaluation and interpolation is the remainder. Thus, in this situation, if the power series can be evaluated at the roots, it can be reduced modulo a polynomial. A counterexample is

$$\frac{1}{1-x}=1+x+x^2+x^3+\ldots$$

It cannot be evaluated at $x=1$, so the series $1+x+x^2+x^3+\ldots$ cannot be reduced modulo the polynomial $x-1$.

Since every derivative of a power series has a value at $0$, reduction modulo $x^n$ can always be computed, consistent with the meaning of truncation above. The discrete Fourier transform and its inverse correspond to reduction modulo the polynomial $x^n-1$.

Factorization and Euclidean algorithm

Many results from elementary number theory generalize to polynomials.

Over the complex numbers, the fundamental theorem of algebra implies that for an $n$-th degree polynomial $f$, the equation

$$f(x)=0$$

has exactly $n$ solutions, counting repeated roots according to their multiplicity.

Therefore, over the complex numbers, $f(x)$ has the unique factorization

$$a(x-x_1)^{c_1}(x-x_2)^{c_2}\cdots(x-x_m)^{c_m}$$ $$c_1+c_2+\cdots+c_m=n,x_1,x_2,\cdots,x_m \text{ 互不相同}$$

Analogous to the greatest common divisor of positive integers, this gives the polynomial greatest common divisor (gcd). It can be computed with the Euclidean algorithm:

$$\gcd(f,0)=f,\gcd(f,g)=\gcd(g,f\bmod g)$$

This property generalizes to a more general setting:

For any field $P$, the polynomial ring $P[x]$ satisfies:
every polynomial has a unique factorization, and the greatest common divisor can be computed with the Euclidean algorithm.
Note that this conclusion need not hold for polynomials over a general ring.

When the Euclidean algorithm applies, the extended Euclidean algorithm gives the following Diophantine equation

$$f(x)P(x)+g(x)Q(x)=\gcd(f(x),g(x))$$

A particular solution is $(P(x),Q(x))$, and Bézout's identity can be used to determine whether the Diophantine equation

$$f(x)P(x)+g(x)Q(x)=h(x)$$

is solvable.

HALF-GCD allows polynomial Euclidean algorithms to be computed in $O(n\log^2 n)$ time.

Multiplicative inverse modulo a polynomial

Modulo a polynomial $h(x)$, a power series $f(x)$ sometimes has an inverse. The inverse is the remainder obtained by reducing the reciprocal of $f(x)$ modulo $h(x)$.

Equivalently, for a polynomial $f(x)$, if there exists a $g(x)$ satisfying

$$\begin{aligned} f(x) g(x) & \equiv 1 \pmod{h(x)} \end{aligned}$$

then $g(x)$ is called the inverse element of $f(x)$ modulo $h(x)$. When the polynomial Euclidean algorithm applies, the inverse exists if and only if $\gcd(f,g)=1$.

The inverse modulo a polynomial $h(x)$ is always unique. If the degree of $f(x)$ is also less than that of $h(x)$, then the resulting $g(x)$ and $f(x)$ are mutual inverses.

In terms of truncation, the inverse modulo $x^n$ is generally denoted by $f^{-1}(x)$, and this is also the default meaning of inverse below. Unless otherwise specified, the modulus of an inverse is $x^n$.

Note

One might ask whether various interpolation transforms can be used to solve for the inverse directly, for example by computing:

$$IDFT\left(\frac{DFT(1)}{DFT(f(x))}\right)$$

The answer is no. According to the explanation above, the inverse obtained directly using the discrete Fourier transform and its inverse here is the inverse modulo the polynomial $x^n-1$, not the usual inverse modulo $x^n$. Moreover, because the original polynomial may be $0$ at some point values, this computation may not be possible.

Generating functions

A generating function, also called a mother function, is a formal power series whose coefficients can provide information about a sequence.

Generating functions come in many kinds, but most can be written in the unified form

$$F(x)=\sum_n a_nk_n(x)$$

where $k_n(x)$ is called the kernel function. Different kernel functions lead to different generating functions with different properties. For example:

1. Ordinary generating function: $k_n(x)=x^n$.
2. Exponential generating function: $k_n(x)=\dfrac{x^n}{n!}$.
3. Dirichlet generating function: $k_n(x)=\dfrac{1}{n^x}$.

References and further reading

• Picks's Blog
• Miskcoo's Space
• Polynomial ring - Wikipedia
• Formal power series - Wikipedia
• 《The theoretical framework for generating-function computation in informatics competitions》