TAOCP 4.7 Exercise 12
Let with $v_n\ne0$.
Section 4.7: Manipulation of Power Series
Exercise 12. [M20] Find a connection between polynomial division and power series division: Given polynomials $u(z)$ and $v(z)$ of respective degrees $m$ and $n$ over a field, show how to find the polynomials $q(z)$ and $r(z)$ such that $u(z) = q(z)v(z) + r(z)$ and $\deg(r) < n$, using only operations on power series.
Verified: yes
Solve time: 4m38s
Solution
Let
v(z)=v_0+v_1z+\cdots+v_nz^n,$$ with $v_n\ne0$. We seek polynomials $q(z)$ and $r(z)$ such that $$u(z)=q(z)v(z)+r(z),\qquad \deg(r)<n.$$ The connection with power series division is obtained by reversing the coefficients. Define the reversed polynomials $$u^(z)=z^m u(z^{-1}),\qquad v^(z)=z^n v(z^{-1}).$$ Explicitly, $$u^(z)=u_m+u_{m-1}z+\cdots+u_0 z^m,$$$$v^(z)=v_n+v_{n-1}z+\cdots+v_0 z^n.$$ Since $v_n\ne0$, the constant term of $v^(z)$ is nonzero; therefore power series division by $v^(z)$ is possible by equation (2). Assume first that $m\ge n$, and write $$d=m-n.$$ If $$u(z)=q(z)v(z)+r(z),\qquad \deg(r)<n,$$ then multiplying by $z^{-m}$ and replacing $z$ by $z^{-1}$ gives $$z^{-m}u(z) =z^{-m}q(z)v(z)+z^{-m}r(z).$$ Hence $$u^(z) =z^d q(z^{-1}),v^(z)+z^m r(z^{-1}). \eqno(1)$$ Because $\deg(r)<n$, we have $$\deg\bigl(z^m r(z^{-1})\bigr)\ge m-n+1=d+1.$$ Therefore the terms of degree $0$ through $d$ in $u^(z)$ are exactly the terms of degree $0$ through $d$ in $$z^d q(z^{-1}),v^(z).$$ Define $$q^(z)=z^d q(z^{-1}).$$ Then $q^(z)$ is a polynomial of degree at most $d$, and by (1), $$u^(z)\equiv q^(z)v^(z)\pmod{z^{d+1}}. \eqno(2)$$ Since $v^_0=v_n\ne0$, equation (2) determines the coefficients of $q^(z)$ uniquely by power series division: $$q^(z)\equiv \frac{u^(z)}{v^(z)} \pmod{z^{d+1}}. \eqno(3)$$ Thus the quotient polynomial is obtained by the following procedure: 1. Reverse the coefficients of $u(z)$ and $v(z)$ to form $u^(z)$ and $v^(z)$. 2. Compute the first $d+1$ coefficients of the power series quotient $$u^(z)/v^(z)$$ using equation (2) of Section 4.7. 3. The resulting polynomial is $q^(z)$. 4. Reverse the coefficients again: $$q(z)=z^d q^(z^{-1}).$$ 5. Finally compute $$r(z)=u(z)-q(z)v(z).$$The condition $\deg(r)<n$ follows automatically, because the construction of $q^*(z)$ makes the coefficients of $z^m,z^{m-1},\ldots,z^n$ vanish in $u(z)-q(z)v(z)$. If $m<n$, then $q(z)=0$ and $r(z)=u(z)$. Hence ordinary polynomial division reduces to power series division with nonzero constant term after reversing the coefficients. This completes the proof. ∎