Consider the polynomial algebra \({\mathbb Q}\[x\]\) and assume that we divide this polynomial algebra with an ideal generated by a single polynomial \[ f(x) = x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0 \] One important part of constructing the quotient algebra is to determine how to resolve monomials of the form \(x^m\) when \(m\geq n\). Today, I will write a simple recursive function which calculates such resolutions.
Notice that the quotient algebra \({\mathbb Q}\[x\]/\left<f\right\>\) has a basis of the form \(\{1,x,\ldots,x^{n-1}\}\), and therefore, monomials in this basis are already in their lowest form and do not reduce. However, monomials of higher degree must reduce as in the quotient algebra \(x^n\) must be replaced with \[ - a_{n-1} x^{n-1} - \cdots - a_1 x - a_0 \] because in the quotient algebra we have the equality \(f(x)=0\).
I will consider this resolution as a function \(res\colon {\mathbb N}\times \{0,1,\ldots,n-1\}\to {\mathbb Q}\) where \(res(m,j)\) returns the coeffient of the monomial \(x^j\) in the resolution of a monomial \(x^m\). I will define the function recursively. One set of base cases is already given: when \(m<n\) we have \[ res(m,k) = \begin{cases} 1 & \text{ if } m=k<n\\ 0 & \text{ otherwise } \end{cases} \] Now, consider the simplest resolution: the resolution of the monomial \(x^n\). Its resolution is simply \[ x^n \mapsto - a_{n-1}x^{n-1} - \cdots - a_1 x - a_0 \] which means when \(m = n \> k\) we get \(res(n,k) = -a_k\). In general, \[\begin{align} x^m \mapsto & - x^{m-n}\sum_{i=0}^{n-1} a_i x^i \ & = \sum_{i=0}^{n-1} - a_ix^{m-(n-i)} \end{align}\] This means we have the recurrence relation described as \[ res(m,k) = \begin{cases} - \sum_{i=1}^n a_{n-i}res(m-i,k) & \text{ if } 0\leq k<n\\ 0 &\text{ otherwise} \end{cases} \] when \(m\>n\)
So, here is a lisp implementation of the solution. The parameters I
will pass to the function are as follows: m is the degree
of the monomial \(x^m\) to be resolved,
k is the coefficient of the monomial \(x^k\) in the resolution of \(x^m\), and finally, coeff is
the list of coefficients of the polynomial \(f(x) = x^n + a_{n-1} x^{n-1} +
\cdots + a_1 x + a_0\) except the coefficient of the leading
monomial which is always \(1\).
(defun resolve (m k coeff)
(let ((n (length coeff)))
(cond ((or (< k 0) (>= k n)) 0)
((equal m n) (* -1 (aref coeff k)))
((< m n) (if (equal m k) 1 0))
(t (* -1 (loop for i from 1 to n
sum (* (aref coeff (- n i))
(resolve (- m i) k coeff))))))))
RESOLVELet me test it
(defvar coeff #(1 2 1 2 1))
(defvar n (length coeff))
(time (loop for i from 0 below n collect (resolve 29 i coeff)))
(-865 -58 -685 -453 0)
Evaluation took:
7.499 seconds of real time
7.494859 seconds of total run time (7.493860 user, 0.000999 system)
99.95% CPU
20,945,834,112 processor cycles
0 bytes consedThe time complexity of the function as is, is quite terrible. Below, I will re-implement the function using memoization:
(defparameter resolve-table (make-hash-table :test 'equal))
(defun resolve-lookup (m k coeff)
(gethash (list m k coeff) resolve-table))
(defun resolve-push (m k coeff val)
(setf (gethash (list m k coeff) resolve-table) val))
(defun resolve (m k coeff)
(let ((n (length coeff)))
(cond ((or (< k 0) (>= k n)) 0)
((equal m n) (* -1 (aref coeff k)))
((< m n) (if (equal m k) 1 0))
(t (or (resolve-lookup m k coeff)
(resolve-push m k coeff (* -1
(loop for i from 1 to n
sum (* (aref coeff (- n i))
(resolve (- m i) k coeff))))))))))
RESOLVELet me test it again:
(time (loop for i from 0 below n collect (resolve 29 i coeff)))
(-865 -58 -685 -453 0)
Evaluation took:
0.000 seconds of real time
0.000000 seconds of total run time (0.000000 user, 0.000000 system)
100.00% CPU
341,806 processor cycles
20,456 bytes consed