Ask Your Question
2

Reducing the Coefficients of a Polynomial Modulo an Ideal

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

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
1

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

rburing gravatar image

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

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
edit flag offensive delete link more

Comments

1

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 +0200 )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 +0200 )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 +0200 )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

Stats

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

Seen: 1,827 times

Last updated: Oct 23 '18