Univariate quotient ring returning wrong results

[Florent Hivert]

Dear all,

In some circumstance polynomial ring quotients returns wrong results: the
following quotient by a single polynomial works correctly:

sage: R.<x> = PolynomialRing(ZZ)
sage:
sage: S.<xbar> = R.quotient(x^2+x+1)
sage: xbar^2
-xbar - 1
sage: xbar^2 + x + 1 == 0
True

whereas quotient by several polynomial is wrong:

sage: S.<xbar> = R.quotient((x^2+x+1, x^2))
sage: xbar^2
xbar^2
sage: xbar^2 + x + 1 == 0
False

The reason is that the default implementation of reduce in ideal.py is

def reduce(self, f):
return f # default

and is *not* overloaded for those kinds of polynomials. I'd rather replace
that with

raise NotImplementedError

leading

sage: R.<x> = PolynomialRing(ZZ)
sage: S.<xbar> = R.quotient((x^2+x+1, x^2))

to raise a NotImplementedError. Do you all agree with this behavior ? Is there
a simple way to fix that, knowing that "multivariate" polynomials in one
variable correctly implement the feature:

sage: R.<x> = PolynomialRing(ZZ, 1)
sage: S.<xbar> = R.quotient((x^2+x+1, x^2))
sage: xbar^2 + x + 1 == 0
True

Thanks for any advice.

Cheers,

Florent

[Charles Bouillaguet]

If I am not mistaken, any ideal I = <f_1, …, f_r> of R[x] is spanned by a **single** polynomial (which is the gcd of the f_i). So, in your examples, the ideal spanned by x^2 and x^2+x+1 is in fact R[x], because their gcd is one.

Then reduction should just be the remainder of the division by the single generator of the ideal...

(this is of course only true with polynomial in one variables)

Charles

> Thanks for any advice.
>
> Cheers,
>
> Florent
>

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To post to this group, send email to sage-...@googlegroups.com.
> To unsubscribe from this group, send email to sage-devel+...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel?hl=en.
>
>

[Volker Braun]

A univariate polynomial ring over a field is a PID, but not if its over a general ring. E.g. <2,x> in ZZ[x] can't be generated by a single polynomial.

[Maarten Derickx]

+1 It's better to raise an error then to fail silently. 

If it turns out that a lot of doctest break because of this change it is maybe good to instead create a method called reduce_unique, or add a keyword unique to reduce. Here reduce_unique should have the additional property that I.reduce_unique(f)==I.reduce_unique(g) if and only if f = g mod I.

[mmarco]

I think that the general way to go would be to compute a groebner
basis of the ideal we are quotienting by, and then always reduce by
this GB. If i am not mistaken, that is the way that quotients of
multivariate polynomial rings are implemented.

There could be some rings over which we have no groebner basis
algorithm... but i think in those cases there is simply no way to work
with the quotient properly.