Ask Your Question

Reducing the Coefficients of a Polynomial Modulo an Ideal

asked 2018-10-19 03:16:14 +0100

Annie Carter gravatar image

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)?

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2018-10-22 21:18:23 +0100

rburing gravatar image

updated 2018-10-23 00:48:59 +0100

The explanation can be found in the documentation for QuotientRing:


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)

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])
sage: (2*t1 + a*t2).change_ring(GF(2)[a].quotient(a))

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)
sage: (2*t1 + a*t2).change_ring(S.quotient(abar))
edit flag offensive delete link more



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 gravatar imageAnnie Carter ( 2018-10-22 23:18:12 +0100 )edit

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 gravatar imagerburing ( 2018-10-23 00:21:46 +0100 )edit

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 gravatar imagerburing ( 2018-10-23 12:16:38 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2018-10-19 03:16:14 +0100

Seen: 1,539 times

Last updated: Oct 23 '18