Understanding polynomial interpolation as a special case of Chinese Remainder Theorem

Question

As some background information:

Chinese Remainder Theorem: Let $R$ be a commutative ring and $\{I_k\}_{k\geq1}$ be pairwise coprime ideals in $R$. Chinese Remainder Theorem claims that $R/I_1\cap...\cap I_k\cong (R/I_1) \times...\times(R/I_k).$

Polynomial interpolation: claims that for pairwise distinct $\lambda_k$, $k=1,2,...,n$, $\lambda_i\in\mathbb{F}$ for some field. Then for $a_i$, $i=1,...,n,$ there exists a polynomial $p\in \mathbb{F}[x]$ such that $p(\lambda_i)=a_i$ for each i.

The proof I was given goes as follows:

Since $\lambda_k$ are pairwise distinct then $\langle X-\lambda_k\rangle$ are pairwise coprime. So we can apply CRT here to obtain: $\mathbb{F}[x]/\langle X-\lambda_1\rangle \cap...\cap \langle X-\lambda_n\rangle \cong (\mathbb{F}[x]/\langle X-\lambda_1\rangle) \times...\times(\mathbb{F}[x]/\langle X-\lambda_n\rangle).$ Then there is a polynomial $p(X)\in \mathbb{F}[x]/\langle X-\lambda_1\rangle\cap...\cap \langle X-\lambda_n\rangle$ such that p(X)$\in$ $a_i$+$\langle X-\lambda_i\rangle $ for each $i$.

My issue here lies within the last sentence (Italic one).

Firstly why does it even imply there exists $p(X)$ that has the declared property ($p(X)\in$ $a_i$+$\langle X-\lambda_i\rangle $ for each $i$)? Secondly why would such $p(X)$ has the required property in the theorem? Is it really as simple as $p(\lambda_k)\in a_i+\langle \lambda_i-\lambda_i\rangle=a_i?$

I hope I didnt explain this too messily and any help is much appreciated!

Answer 1

Clearer by CRT, which implies the evaluation map $\, f(x)\mapsto (f(\lambda_1),\ldots,f(\lambda_n))$ from $\,F[x]$ to $F^n$ is surjective (= onto), with kernel $\,I={\large \cap_i}(x-\lambda_i)\,[=\prod_i (x-\lambda_i)$ by here or here]. Being onto, there is some $\,f(x)\in F[x]\,$ which maps to $\,(a_1,\ldots,a_n),\,$ i.e $\,f(\lambda_i) = a_i,\,$ which is unique $\!\bmod I.\,$ Below shows how $\,\scr L = $ Lagrange interpolation is a special case of CRT.

$$\begin{align}f(\lambda_1)= a_1\!\!\!\overset{\rm\color{#0a0}{RT}\!\!\!}\iff\! f(x)&\equiv a_1\!\!\!\!\pmod{\!x \!-\! \lambda_1}\\ \vdots\qquad\qquad\qquad &\ \ \vdots\qquad\qquad \vdots\\ f(\lambda_n) = a_n\smash{\overset{\rm\color{#0a0}{RT}\!} \iff}\, f(x)&\equiv a_n\!\!\!\!\pmod{\!x \!-\!\lambda_n}\end{align} \!\!\!\!\overset{\rm\small CRT\!}\iff\! f(x)\equiv {\scr L}^{a}_{\lambda}(x)\!\!\pmod{\!{\smash{\small \prod_i}} (x\!-\!\lambda_i)}$$

where we used $\ {\rm\color{#0a0}{RT}}\!:\,\ f(\lambda) = (f(x)\,\bmod\, x-\lambda)\,\ $ [Polynomial Remainder Theorem].

Remark $ $ Further, the Lagrange interpolation formula is a special case of a CRT formula generalizing the integer CRT formula to pairwise coprime moduli $p_i$ in $F[x]$ (or any PID), viz.

$\qquad \begin{align} &f \equiv a_1\pmod{p_1}\\ &\ \ \ \ \vdots\qquad\qquad\ \ \vdots \\ &f \equiv a_k\pmod{p_k}\end{align}$ $\iff \left\{\begin{align} f \,\equiv\, &\sum_i\, a_i\:\! P_i\:\! (\color{#c00}{P_i^{-1}\bmod p_i})\!\pmod{\!P}\\ &\ {\rm for}\ \ P = p_1\cdots p_k,\ \ P_i = P/p_i\end{align}\right.$

Here we have that: $\ p_i = x\!-\!\lambda_i,\, $ $\, P_i = (x\!-\!\lambda_1)\cdots \rlap{\ \ ////}(x\!-\!\lambda_i)\cdots (x\!-\!\lambda_k)$

so $\,\color{#c00}{P_i^{-1}\bmod p_i} = \dfrac{1}{P_i}\bmod x\!-\!\lambda_i = \dfrac{1}{(\!\lambda_i\!-\!\lambda_1)\cdots \rlap{\ \ ////}(\lambda_i\!-\!\lambda_i)\cdots (\lambda_i\!-\!\lambda_k)} $

$${\rm so}\ \ f\, \equiv\, \sum_i a_i\,\dfrac{(x-\!\lambda_1)\cdots\:\!\rlap{\ \ ////}(x-\!\lambda_i)\cdots\:\! (x-\!\lambda_k)\ }{(\!\lambda_i\!-\!\lambda_1)\cdots \rlap{\ \ ////}(\lambda_i\!-\!\lambda_i)\cdots (\lambda_i\!-\!\lambda_k)}\ \ \ \ $$

so the above CRT formula specializes to the Lagrange interpolation formula (where again we used ${\rm\color{#0a0}{RT}}$ = Poly Remainder Theorem to deduce $\,P_i\bmod x\!-\!\lambda_i\,$ equals $P_i$ evaluated at $\,x = \lambda_i)$.

The prior linked post explains how the CRT formula follows from linearity once we have computed the orthogonal idempotents $\,e_i = P_i(P_i^{-1}\bmod p_i)\,$ satisfying $\,e_i\equiv 1\pmod{\!p_i},\,$ and $\,e_i \equiv 0\pmod{\!p_j},\, j\neq i\ $ (here writable more precisely in the language of product rings).

This answer proves why the (pairwise) coprime condition is necessary for a (CRT) product decomposition, e.g. there we show $\,\Bbb Z[x]/(x(c\!-\!x)) \cong \Bbb Z^2\!\iff c\mid 1$.

Answer 2

For the second question: it's almost that simple, though we can't write $p(\lambda_i) \in a_i+\langle \lambda_i-\lambda_i\rangle$, as this doesn't make sense.

Rather, write it in this form: $$p(X)=q(X)(X-\lambda_i) +a_i$$ to see $p(\lambda_i) =a_i$.

For the first question, take the unique correspondent of $$(a_1+\langle X-\lambda_1\rangle, \ \dots,\ a_n+\langle X-\lambda_n\rangle) \ \in\ \prod_i\Bbb F[X]/\langle X-\lambda_i\rangle$$ along the given isomorphism.