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.

I'll use this opportunity to ask: are there any CP problems out there where you receive the roots of the denominator? I feel like usually these things are given in an indirect way so we don't have the roots.

They're not given directly usually, yes. Somewhat natural way to give them would be to say that you somehow work with $$$P(a),P'(a),\dots,P^{(d-1)}(a)$$$, then you would know that $$$(x-a)^d$$$ is involved. On the other hand, I do not recall any problems that does it as well.