Reducing the Coefficients of a Polynomial Modulo an Ideal

Annie Carter
67 ●1 ●2 ●9

I have a polynomial in two variables $t_1$ and $t_2$ (say $2t_1 + at_2$ ) defined over a ring which is itself a polynomial ring (say $\mathbf{Z}[a]$ ). I'd like to reduce the coefficients of the polynomial modulo an ideal of the latter ring (say $(2)$ or $(a)$ or $(2,a)$ ). When I execute

M.<a> = PolynomialRing(ZZ)
R.<t1,t2> = PolynomialRing(M)
m = M.ideal(a)
(2*t1 + a*t2).change_ring(QuotientRing(M,m))

I get 2*t1, as I would expect. On the other hand, the code

M.<a> = PolynomialRing(ZZ)
R.<t1,t2> = PolynomialRing(M)
m = M.ideal(2)
(2*t1 + a*t2).change_ring(QuotientRing(M,m))

gives me a type error ("polynomial must have unit leading coefficient"). And the input

M.<a> = PolynomialRing(ZZ)
R.<t1,t2> = PolynomialRing(M)
m = M.ideal(2,a)
(2*t1 + a*t2).change_ring(QuotientRing(M,m))

gives the output 2*t1 + abar*t2 rather than the 0 I would have expected. What should I do to get the outputs I would expect (namely 2*t1, abar*t2, and 0, respectively)?

add a comment

answered 6 years ago

rburing

10964 ●4 ●80 ●219 https://www.rburing.nl/

updated 6 years ago

The explanation can be found in the documentation for QuotientRing:

ASSUMPTION:

I has a method I.reduce(x) returning the normal form of elements $x \in R$ . In other words, it is required that I.reduce(x)==I.reduce(y) $\iff x-y \in I$ , and x-I.reduce(x) in I, for all $x,y \in R$ .

That is, elements of a QuotientRing are represented by normal forms (usually obtained by polynomial division).

We can see that $(2) \subset \mathbf{Z}[x]$ in Sage does not possess such a method:

R.<x> = ZZ[]
I = R.ideal(2)
I.reduce??

This shows the source code of I.reduce which is the default implementation lambda f: return f, which doesn't satisfy the property that QuotientRing assumes: e.g. I.reduce(2) != I.reduce(0) but $2 \in I$ .

The implementation of I.reduce is the same for I = R.ideal(2,x) which explains your last result.

Note that $\mathbf{Z}[x]$ is not a Euclidean ring because not every ideal is principal (e.g. the ideal $(2,x)$ is a non-principal), so it is impossible to have a normal form for elements in a quotient via naive polynomial division in $\mathbf{Z}[x]$ , in general. There is a theory of Groebner bases for univariate polynomial rings over PIDs which would apply to $\mathbf{Z}[x]$ , but it doesn't seem to be implemented in Sage.

Of course not all is lost, because the ideals you consider are nice enough, e.g. $\mathbf{Z}[x]/(2) \cong \mathbf{F}_2[x]$ and $\mathbf{Z}[x]/(2,x) \cong \mathbf{F}_2[x]/(x) \cong \mathbf{F}_2$ and the objects on the right-hand sides can be represented easily in Sage:

sage: (2*t1 + a*t2).change_ring(GF(2)[a])
a*t2
sage: (2*t1 + a*t2).change_ring(GF(2)[a].quotient(a))
0

Or, if you prefer the name abar for the image of a in the quotient:

sage: S.<abar> = GF(2)[]
sage: (2*t1 + a*t2).change_ring(S)
abar*t2
sage: (2*t1 + a*t2).change_ring(S.quotient(abar))
0

link

Comments

Is there any hope if the ring of coefficients has more than one variable? The application I'm interested in is when the coefficient ring has the form $\mathbf{Z}[a_1, \ldots, a_n]$ and I reduce modulo some power of a maximal ideal of the form $(p, a_1, \ldots, a_n)$ with $p$ a prime.

Annie Carter ( 6 years ago )

There is hope because such a quotient is a finite (coefficients and the exponent of each variable can be bounded) commutative ring, so it should be possible to do calculations in it. (For a power $k > 1$ of the maximal ideal it is not a domain because $p^k = 0$ whereas $p \neq 0$ .) It would be a good question to ask (e.g. on this site as a new question) how to represent this kind of ring inside Sage.

rburing ( 6 years ago )

So it seems a normal form for an element of $\mathbf{Z}[a_1,\ldots,a_n]/(p,a_1,\ldots,a_n)^k$ would be a polynomial of degree $\lt k$ in $a_1,\ldots,a_n$ where the coefficients of monomials of degree $d$ are reduced modulo $p^{k-d}$ . (Exercise: count how many such polynomials there are.) If this satisfies the desired properties (I guess so) then you could implement this as reduce (and if you make it a method for a custom class then you could use QuotientRing).

rburing ( 6 years ago )

add a comment

Reducing the Coefficients of a Polynomial Modulo an Ideal

1 Answer

Comments

Your Answer

Question Tools

Stats

Reducing the Coefficients of a Polynomial Modulo an Ideal savecancel

1 Answer

Comments

Your Answer

Question Tools

Stats

Reducing the Coefficients of a Polynomial Modulo an Ideal