Skip to content

Introduction to Polynomials & Generating Functions

Polynomials and Generating Functions

Manipulating polynomials with finite/infinite terms is an important topic in OI mathematics, especially in generating functions.

Polynomial algorithms based on the Fast Fourier Transform empower competitive programmers to directly manipulate generating functions.

Basic Concepts

For a summation expression \(\sum a_nx^n\), if it is a finite sum, it is called a polynomial, denoted as \(f(x)=\sum_{n=0}^m a_nx^n\).

A summation with countably many terms is called a series. In the series \(\sum_{n=0}^\infty a_nx^n\), each term is a non-negative integer power function multiplied by a constant coefficient. Such a series is called a power series.

When studying polynomial arithmetic, we first consider simpler polynomials. The concept of power series is only used for ease of understanding. In mathematical analysis, the convergence/divergence of power series is further studied.

General definitions of rings, fields, and their derived structures can be found in Basic Concepts of Abstract Algebra.

For a general ring \(R\), define the polynomial ring \(R[x]\) over \(R\).

Each element \(f\) is called a polynomial over \(R\), which can be represented 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 directly define a polynomial as a coefficient sequence. It can also be written as

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

Here, we consider \(x\) merely as a formal symbol, an identifier for coefficient positions.

If we allow infinitely many terms, i.e.,

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

we obtain the formal power series ring \(R[[x]]\), where each element \(f\) is called a formal power series, hereafter simply referred to as a power series.

Degree of a Polynomial

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

Multiplication of Polynomials

The core operation is the multiplication of 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 distributive over addition. If \(R\) is a commutative ring or a unital ring, multiplication also has commutativity and an identity element.

If \(R\) has \(2^n\)-th roots of unity, the Fast Fourier Transform allows us to compute the product of two degree-\(2^n\) polynomials in \(O(n2^n)\) time instead of \(O(2^{2n})\).

Composition

Define the power of an element \(f\) in \(R[[x]]\) as

\[ f^1=f,f^k=f^{k-1}\times f \]

Based on this, define the composition of elements \(f,g\) in \(R[[x]]\) as

\[ (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 that limits over \(R\) are not involved.

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

When FFT is applicable, composition of finite-term polynomials has an \(O((n\log n)^{1.5})\) algorithm, but its constant factor is large. In practice, an \(O(n^2)\) "block FFT" algorithm often performs better.

Derivative

Even though general rings may not 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{ copies of } f_k} \]

The basic differentiation rules—sum rule, product rule, 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 into an infinite series. The reciprocal exists if and only if the constant term is non-zero, and the reciprocal also has a non-zero constant term.

Thus, for a formal power series \(f\), if \(f_0\not=0\), its multiplicative inverse \(f^{-1}\) is another formal power series satisfying

\[ f\times f^{-1}=f^{-1}\times f=1 \]

Expanding this using the definition of formal power series multiplication gives a 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} \]

Directly computing the first \(n\) terms via recurrence is \(O(n^2)\). Using FFT yields an \(O(n\log n)\) algorithm.

Note

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

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 as a polynomial within that range, generally called a Taylor expansion. If expanded at \(0\), it is also called a Maclaurin expansion.

If it is infinitely differentiable, a power series expansion is possible. The most common expansions are still at \(0\).

In complex analysis, some functions cannot be expanded as Taylor series at singular points but can be expanded as Laurent series.

The following equalities hold only when the power series converges; they do not hold when it diverges. Only the expansions are given here, without discussing convergence domains.

The two basic expansions are for 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 are often derived from these two. For example, sine and cosine 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 \]

Logarithmic, arctangent, and arcsine functions are obtained via 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

The compositional inverse is the generalization of the inverse function concept to the formal power series ring.

For a formal power series \(f\) satisfying \(f_0=0\) and \(f_1\not=0\), its compositional inverse is a formal power series \(g\) satisfying \(g(f(x))=f(g(x))=x\). By Lagrange inversion, for any integers \(n,k\) we have

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

where \([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)\).

Obviously, \(g(x)\) divides \(f(x)\) if and only if all roots of \(g(x)\) are roots of \(f(x)\), and their multiplicities in \(g(x)\) do not exceed those in \(f(x)\).

Quotient and Remainder of Polynomials

For polynomials \(f(x), g(x)\), there exist unique \(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 of \(f(x)\) divided by \(g(x)\), and \(R(x)\) the remainder.

Modulo Polynomials

Modulo polynomials form a subring of the polynomial ring, obtained by dividing the polynomial ring by a congruence equivalence relation.

In the division with remainder mentioned above, the polynomial \(f(x)\) is congruent to its remainder \(R(x)\) modulo the polynomial \(g(x)\).

\[ f(x) \equiv R(x) \pmod{g(x)} \]

This congruence also means that for any root \(x_0\) of \(g(x)\), substituting into \(f(x)\) and \(R(x)\) yields the same value:

\[ f(x_0)=R(x_0) \]

Moreover, if the root \(x_0\) has multiplicity \(k\) in \(g(x)\), i.e., \((x-x_0)^k\) divides \(g(x)\), then for any integer \(t\) with \(0 \le t < k\), we have:

\[ f^{t}(x_0)=R^{t}(x_0) \]

Here the notation denotes the \(t\)-th derivative.

Modulo polynomial congruence can 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\), so the modulo \(x^n\) operation is equivalent to "truncation", cutting off the infinite power series to the first \(n\) terms, directly discarding higher-order information.

In some specific cases, other polynomials can be used as the modulus, as 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}\), compute

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

Interpolation of a polynomial means: given \(n+1\) points

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

find an \(n\)-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 coefficient representation and point-value representation. Multi-point evaluation converts coefficient representation to point-value representation; interpolation converts point-value representation to coefficient representation.

Note

From the perspective of power series, multi-point evaluation "compresses" infinite-term information into a finite point-value representation, thus losing some information, while interpolation restores it to the coefficient representation of corresponding degree.

Common evaluation and interpolation in programming, such as Discrete Fourier Transform (and its inverse), etc., choose \(n+1\) points each with multiplicity \(1\), i.e., all distinct, avoiding the need for derivatives.

This "compression" only guarantees agreement at the \(n+1\) points. According to the earlier explanation of modulo polynomial congruence, if a power series \(f(x)\) is evaluated at points \(x_0\) to \(x_n\) and then interpolated to obtain polynomial \(R(x)\), then constructing the polynomial:

\[ g(x)=(x-x_0)\ldots(x-x_n) \]

we have:

\[ 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 via evaluation and interpolation is exactly the remainder. Therefore, in this case, if the power series can be evaluated at the roots, it can be taken modulo a polynomial. A counterexample is:

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

which cannot be evaluated at \(x=1\), so the series \(1+x+x^2+x^3+\ldots\) cannot be taken modulo the polynomial \(x-1\).

Since any derivative of a power series always exists at \(0\), modulo \(x^n\) can always be computed, consistent with the "truncation" meaning above. Discrete Fourier Transform (and its inverse) corresponds to modulo the polynomial \(x^n-1\).

Factorization and Euclidean Algorithm

Many results from elementary number theory can be generalized to polynomials.

Over the complex field, by the Fundamental Theorem of Algebra, for an \(n\)-degree polynomial \(f\), the equation

\[ f(x)=0 \]

has exactly \(n\) solutions (counting multiplicities).

Thus, \(f(x)\) can be uniquely factorized over the complex field as

\[ 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{ are distinct} \]

Analogous to the greatest common divisor of positive integers, we can define the greatest common divisor (gcd) of polynomials. It can be computed using the Euclidean algorithm:

\[ \gcd(f,0)=f,\gcd(f,g)=\gcd(g,f\bmod g) \]

This property can be generalized to more general settings:

For the polynomial ring \(P[x]\) over any field \(P\),
polynomials can be uniquely factorized, and the Euclidean algorithm can compute the greatest common divisor. Note that for polynomials over general rings, this conclusion may not hold.

When the Euclidean algorithm works, the extended Euclidean algorithm can give a particular solution \((P(x),Q(x))\) to the indeterminate equation

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

and use Bézout's theorem to determine the solvability of

\[ f(x)P(x)+g(x)Q(x)=h(x) \]

HALF-GCD allows us to compute polynomial gcd in \(O(n\log^2 n)\) time.

Multiplicative Inverse Modulo a Polynomial

In the sense of modulo a polynomial \(h(x)\), a power series \(f(x)\) sometimes has an inverse. The inverse is the remainder of the reciprocal of the power series \(f(x)\) modulo the polynomial \(h(x)\).

This definition is equivalent to: for a polynomial \(f(x)\), if there exists \(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 is applicable, 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 \(h(x)\), then the obtained \(g(x)\) and \(f(x)\) are inverses of each other.

Considering the concept of "truncation", the inverse modulo \(x^n\) is usually denoted as \(f^{-1}(x)\), which is also the default inverse concept used later. Unless specified otherwise, the modulus for an inverse is \(x^n\).

Note

One question is: can we use various interpolation transforms to directly solve for the "inverse", e.g., compute:

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

The answer is no, this cannot be done. According to the earlier explanation, using Discrete Fourier Transform (and its inverse) directly here computes the inverse modulo the polynomial \(x^n-1\), not the usual inverse modulo \(x^n\). Moreover, since the original polynomial may be \(0\) at some evaluation points, this computation may not even be feasible.

Generating Functions

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

There are many different kinds of generating functions, but most can be expressed in a single 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

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用