Can a polynomial be evaluated from evaluations of partial interpolations? (Or: can the unique solution of congruences be written in a certain way?)

Question

Formally, let $K$ be a field, $a \in K[x]$, $D \subseteq K$, and $E = \{(x_i, a(x_i)) \mid x_i \in D\}$ be distinct evaluations of $a$ where $\lvert E\rvert > \operatorname{deg}(a)$ (so $E$ uniquely determines $a$).

Suppose that $D$, $E$ are partitioned into disjoint subsets $D = \bigcup D_j$, $E = \bigcup E_j$, where $E_j = \{ (x,y) \mid x \in D_j\}$. Then each subset $E_j$ can be interpolated to a degree $\lvert E_j\rvert-1$ polynomial $a_j$.

Is there a "Lagrange-like coefficient" polynomial $\ell_j$, a function of $D$ and $D_j$ but independent of $a_j$ and $E_j$, which can be used to write $a = \sum a_j*\ell_j$?

Or more generally, does there exist $b_j$, $\ell_j$ such that $a = \sum b_j * \ell_j$, where $\ell_j$ is dependent on $D$ and $D_j$ and independent of $a_j$ and $E_j$, and $b_j$ is only dependent on $E_j$ and independent of $D_k$ where $k \ne j$?

The motivation is that with such a representation, $a(0)$ can be written as $\sum b_j(0)*\ell_j(0)$; specifically, $b_j$ is only a function of $E_j$, and $\ell_j$ is only a function of the evaluation domain $D$; therefore, all the $b_j(0)$ values can be computed before $D$ is determined, and combined to get $a(0)$ without having $a_j$.

The following almost works: let $p_j(x) = \prod_{i \in E_j} (x - x_i)$. Then by the Chinese Remainder Theorem, the system of congruences $p \equiv a_j \pmod{p_j}$ has a unique solution $a$ of the appropriate degree, and $a = \sum b_j*q_j$ where $q_j$ is dependent only on $D$ and $D_j$, and not $E_j$.

However, $b_j$ is the remainder of $(a_j * s_j) / p_j$ for a polynomial $s_j$ dependent on $D_k$, $k \ne j$, and therefore $b_j$ is dependent on both $D$ and $E_j$. Therefore, $b_j(0)$ cannot be computed from only $a_j(0)$ and $D$, or from only $E_j$.

Answer 1

No. The interpolating polynomial is a weighted sum $a(x) = \sum_{x_i} a(x_i) P_i(x)$ and the independence of the $a(x_i)$ from each other imposes the independence of the $P_i$ from each other, which isn't consistent with your desired decomposition.

A short counter-example will give the intuition. Take $D_1 = \{1, 2\}, D_2 = \{k\}$. Then the Lagrange form of the interpolating polynomial is $$a(x) = a(1)\frac{(x-2)(x-k)}{(1-2)(1-k)} + a(2)\frac{(x-1)(x-k)}{(2-1)(2-k)} + a(k)\frac{(x-1)(x-2)}{(k-1)(k-2)}$$

Suppose $a(x) = a_1 \ell_1 + a_2 \ell_2$. $$a(x) = \left(a(1)\frac{(x-2)}{(1-2)} + a(2)\frac{(x-1)}{(2-1)}\right)\ell_1 + a(k) \ell_2$$ Since $a(1)$ and $a(2)$ are independent, we have $\ell_1 = \frac{x-k}{1-k}$ and $\ell_1 = \frac{x-k}{2-k}$, giving a contradiction.

If we try the more general approach, $a(x) = b_1 \ell_1 + b_2 \ell_2$, the independence constraints require $$a(1)\frac{(x-2)(x-k)}{(1-2)(1-k)} + a(2)\frac{(x-1)(x-k)}{(2-1)(2-k)} = b_1 \ell_1$$ where $b_1$ is independent of $k$ and $\ell_1$ is independent of $a(1)$ and $a(2)$. But the factors $\frac{a(1)}{1-k}$ and $\frac{a(2)}{2-k}$ of the two terms on the left make the separation impossible.