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](https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Over_univariate_polynomial_rings_and_Euclidean_domains), 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$.



Can a polynomial be evaluated from evaluations of partial interpolations? (Or: can the unique solution of congruences be written in a certain way?)
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.


