Algorithm for writing an image of a polynomial in a quotient ring in terms of a given basis of the quotient ring.

Question

I need to calculate the equivariant Chern classes of certain vector bundles on the classifying spaces of complex algebraic groups. In order to do this I am looking for a way to do the following calculation with polynomial rings. Presumably there are built-in functions for calculations of this type in one or several computer algebra systems. But I do not know what these are, and I would be grateful for any hints or information, especially on how to implement what I'm after using free and/or common math software.

Let $R=\mathbb{Q}[x_1,\ldots, x_n]$ be a polynomial ring over the rationals, and let $I = (p_1, \ldots, p_m) \subset R$ be an ideal. Suppose the quotient $R/I$ has finite dimension over $\mathbb{Q}$, and we are given a basis $\{b_1,\ldots, b_k\}$ of $R/I$ over $\mathbb{Q}$. (The elements of the basis are given as their representatives in $R$.) The problem I need to do is as follows:

Given a polynomial $p\in R$, write its image in $R/I$ as $\sum_{i=1}^k a_i b_i$ where all $a_i\in\mathbb{Q}$.

Answer 1

Choose a monomial ordering; then the normal basis $\operatorname{NB}(I) = \mathbb{M} \setminus \operatorname{LM}(I)$ is a basis of the quotient $\mathbb{Q}$-vector space $\mathbb{Q}[x_1,\ldots,x_i]/I$, where $\operatorname{LM}(I) = \{\operatorname{LM}(f) \mid f \in I, f \neq 0\}$ and $\operatorname{LM}(f)$ denotes the leading monomial of $f \in \mathbb{Q}[x_1,\ldots,x_n]$ with respect to the chosen monomial ordering. The image of an element $p \in \mathbb{Q}[x_1,\ldots,x_n]$ in the quotient ring $\mathbb{Q}[x_1,\ldots,x_n]/I$ can be expressed as a linear combination of elements in $\operatorname{NB}(I)$ by taking its normal form $\operatorname{NF}(p, I)$.

Compute a Groebner basis $G = \{g_1, \ldots, g_r\}$ of $I$ with respect to the monomial ordering. Then the normal basis $\operatorname{NB}(I) = \mathbb{M} \setminus \operatorname{LM}(I)$ can be computed effectively using $\operatorname{LM}(I) = \langle \operatorname{LM}(g_1), \ldots \operatorname{LM}(g_r) \rangle$. The normal form $\operatorname{NF}(p, I)$ can be computed effectively using multivariate polynomial division of $p$ by $\{g_1,\ldots,g_r\}$.

Choose some ordering of $\operatorname{NB}(I)$ so it becomes an ordered basis. For each of your elements $b_i \in \mathbb{Q}[x_1,\ldots,x_n]$, compute the normal form $\operatorname{NF}(b_i, I)$ using the Groebner basis, and let $v_i$ be its vector of coefficients with respect to $\operatorname{NB}(I)$ in the chosen ordering. Then the matrix $C = (v_1, \ldots, v_k)$ is the change-of-basis matrix from your basis $b_1,\ldots,b_k$ to $\operatorname{NB}(I)$.

To express the image of $p \in \mathbb{Q}[x_1,\ldots,x_n]$ in $\mathbb{Q}[x_1,\ldots,x_n]/I$ as a linear combination of $b_i$, first compute its normal form $\operatorname{NF}(p, I)$ using the Groebner basis, take its vector of coefficients $v$ with respect to $\operatorname{NB}(I)$, and do the change of basis $C^{-1}v$ to get a vector of coefficients with respect to $b_1,\ldots,b_k$.

---

Illustration in SageMath:

R.<x,y,z> = PolynomialRing(QQ, order='lex')
I = R.ideal([x^2+y^2+z^2-4, x^2+2*y^2-5, x*z-1])
G = I.groebner_basis()
NB = I.normal_basis()
my_B = [x^3*y, x^2*y, x*y, y, x^3, x^2, x, 1]
C = Matrix(QQ, len(NB))
for i, f in enumerate(my_B):
    g = R(f).reduce(G)
    v_i = [g.monomial_coefficient(m) for m in NB]
    C.set_column(i, v_i)
p = R.random_element()
p_red = p.reduce(G)
v = vector(QQ, [p_red.monomial_coefficient(m) for m in NB])
a = C.solve_right(v)
p - sum(a_i*b_i for a_i, b_i in zip(a, my_B)) in I