\(x \to x + 1\) と taylor shift する線形作用素を \(E\) とします。すなわち、多項式 \(f(x)\) に対して、\((E f)(x) := f(x + 1)\) です。

差分作用素 \(E - 1\) を考えます。多項式 \(f(x)\) に対して、\(((E - 1) f)(x) = (E f - f)(x) = (E f)(x) - f(x) = f(x + 1) - f(x)\) です。

差分作用素は微分と近く、多項式に適用すると次数が下がります。

実際、

\[ f(x) = a_0 + a_1 \cdot x + a_2 \cdot x(x-1) + a_3 \cdot x(x-1)(x-2) \]

に対し、

\[ ((E - 1) f)(x) = a_1 + 2 \cdot a_2 \cdot x + 3 \cdot a_3 \cdot x(x-1) \]

となります。

したがって、差分作用素 \(E - 1\) を \(h(x)\) に \(N + 1\) 回適用すると、\(g(x)\) の成分を取り除くことができます。

\[ \begin{aligned} (E - 1)^{N + 1} h (x) &= (E - 1)^{N + 1} (2^x f (x)) + (E - 1)^{N + 1} g(x)\\ &= (E - 1)^{N + 1} (2^x f (x)) \end{aligned} \]

\(g(x)\) ではなく \(2^x f(x)\) の成分を取り除くことを考えます。

\[ \begin{aligned} (E - 2) (2^x f(x)) &= (2^{x+1} f(x + 1)) - 2 \cdot 2^x f(x) \\ &= 2^{x+1} (f(x + 1) - f(x)) \\ &= 2 \cdot 2^{x} \cdot (E - 1) f(x) \\ (E - 2)^2 (2^x f(x)) &= 2 \cdot (E - 2) \cdot 2^{x} \cdot (E - 1) f(x) \\ &= 2^2 \cdot 2^{x} \cdot (E - 1)^2 f(x) \\ \end{aligned} \]

となるので、線形作用素 \(E - 2\) を \(h(x)\) に \(N + 1\) 回適用すると、\(2^x f(x)\) の成分を取り除くことができます。

\[ \begin{aligned} (E - 2)^{N + 1} h(x) &= 2^{N+1} \cdot 2^x \cdot (E-1)^{N+1} f(x) = 0 \end{aligned} \]

\(E - 1\) と \(E - 2\) はどちらも \(E\) の多項式なので、入れ替えが可能です。

\[ (E - 1)(E - 2) f = (E^2 - 3E + 2) f = (E - 2)(E - 1) f \]

したがって、

\[ \begin{aligned} (E - 1)^{N + 1} (E - 2)^{N + 1} h(x) &= (E - 1)^{N + 1} (E - 2)^{N + 1} g(x) \\ &= (E - 2)^{N + 1} (E - 1)^{N + 1} g(x) \\ &= 0 \\ \end{aligned} \]

が得られます。

\((E - 1)^{N + 1} (E - 2)^{N + 1} h(x) = 0\) を展開することで、\(2N + 3\) 項間の線形漸化式が得られ、Bostan–Mori 法などでこの問題を解くことができます。

[余談] \(f, g\) の復元は \(O(N (\log N)^2)\) 時間で可能です。