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 left as an exercise.
Finally, to interpret the set of equations with multiplicities, we may reckon
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.