Hi everyone!

Today I'd like to write yet another blog about polynomials. Specifically, I will cover the relationship between polynomial interpolation and Chinese remainder theorem, and I will also highlight how it is useful when one needs an explicit meaningful solution for partial fraction decomposition.

Lagrange interpolation

It's quite well-known that the system

has a unique solution $$$P(x)$$$ among polynomials of degree at most $$$n$$$. A direct way to prove that $$$P(x)$$$ exists is through Lagrange's interpolation. To have a better grasp of it, let's recall that $$$P(x) \equiv P(x_0) \pmod{x-x_0}$$$, thus system becomes

From the Chinese remainder theorem follows that $$$P(x)$$$ is unique modulo $$$Q(x) = (x-x_0)\dots(x-x_n)$$$ and is explicitly given as

where $$$Q_i(x) = \frac{Q(x)}{x-x_i}$$$. Noteworthy, $$$Q_i(x_i) = Q'(x_i)$$$, as $$$Q'(x) = Q_0(x) + \dots + Q_n(x)$$$ and $$$Q_j(x_i)=0$$$ when $$$i \neq j$$$.

Partial fraction decomposition

The other well-known fact is that for $$$\deg P < \deg Q$$$, rational function

can be represented as the sum

where $$$\deg C_i < d_i$$$. A bit less well-known are the explicit formulas to compute $$$C_i(x)$$$ and their connection to Lagrange interpolation. To begin with, let's look on this expression in the case $$$d_0= \dots = d_n = 1$$$ and multiply both sides with $$$Q(x)$$$. What we obtain is

It is strikingly similar to the Lagrange interpolation expression, from which we may derive that

Thus, for monic square-free polynomial $$$Q(x)$$$ with $$$\deg P < \deg Q$$$ it holds that

Multiplicities

Let's now understand what's going on when $$$Q(x)$$$ have multiple roots. The corresponding system of equations would look like this:

Utilizing Chinese remainder theorem again, the solution to the whole system is given as

where $$$Q_i(x) = \frac{Q(x)}{(x-x_i)^{d_i}}$$$. Let's get back to partial fraction decomposition. If both parts are multiplied by $$$Q(x)$$$, we get

thus $$$C_i(x) = [P(x) \cdot Q_i^{-1}(x) \bmod (x-x_i)^{d_i}]$$$ and the final formula is as follows:

Shifted remainders

For $$$d_i=1$$$ we knew that $$$Q^{-1}(x)$$$ modulo $$$x-x_i$$$ is equial to the inverse of $$$Q(x_i)$$$. To compute $$$Q^{-1}(x) \bmod (x-x_i)^{d_i}$$$, we should change the basis from $$$1,x,x^2, \dots$$$ to $$$1, x-x_i, (x-x_i)^2,\dots$$$, so that $$$Q(x) = Q_{x_i}(x-x_i)$$$. Now, computing $$$Q^{-1}(x)$$$ modulo $$$(x-x_i)^{d_i}$$$ is the same as computing $$$Q^{-1}_{x_i}(x)$$$ modulo $$$x^{d_i}$$$ and changing the basis back to $$$1,x,x^2,\dots$$$, which is done as follows:

The latter sum can be computed for all $$$j$$$ as a convolution of the sequences $$$p_i i!$$$ and $$$\frac{a^{i-j}}{(i-j)!}$$$ in $$$O(n \log n)$$$.

Then, the whole partial fraction decomposition can be computed in $$$O(n \log^2 n)$$$ with divide and conquer technique similar to the polynomial evaluation. In fact, when $$$Q(x)$$$ is square-free it exactly is a polynomial evaluation, as it is enough to compute $$$P(x_i)$$$ and $$$Q'(x_i)$$$ for all $$$x_i$$$ to compute the partial fraction decomposition in this case.

Noteworthy, $$$O(n \log^2 n)$$$ algorithm to compute partial fraction decomposition was proposed in 1976 by H. T. Kung, who is also known as one of the authors of $$$O(n \log n)$$$ algorithm to compute inverse series of polynomial with Newton method (Sieveking-Kung algorithm).

Interpreting equivalence with multiplicities

We may reckon the Taylor expansion formula

Thus, we have the following equivalence:

So, equivalence modulo the polynomial which have multiple roots is, essentially, still equivalent to equalities on values in the roots of this polynomial, but not only of $$$P(x)$$$, but also its derivatives up to the multiplicity of the root.