Comparison in polynomial quotient rings

[nbruin]

see this sage-devel discussion:

sage: R = PolynomialRing(GF(4), ('x', 'y'))
sage: x, y = R.gens()
sage: I = R.ideal([x^2 + y^2, x + y^3])
sage: S = R.quotient(I, 'ab')
sage: a, b = S.gens()
sage: c, d, e = a + b^2, a*b, b^2
sage: c*(d + e) == c*d + c*e
False

The problem is QuotientRingElement._cmp_, where it is assumed that the reduction of an element with respect to an ideal I is a unique representative of its residue class modulo I. In general, it is not.

CC: @burcin @simon-king-jena @sagetrac-jakobkroeker @obtext

Component: algebra

Branch/Commit: u/nbruin/comparison_in_polynomial_quotient_rings @ 45d7f4e

Issue created by migration from https://trac.sagemath.org/ticket/20722

[nbruin]

Branch: u/nbruin/comparison_in_polynomial_quotient_rings

[nbruin]

Commit: 45d7f4e

[nbruin]

comment:2

First try. Seems to work for the most part, except for one doctest

            sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace')
            sage: I = F*[x*y+y*z,x^2+x*y-y*x-y^2]*F
            sage: Q = F.quo(I)
            sage: Q.0^4    # indirect doctest
            ArithmeticError: Can only subtract elements of the same degree

which I think is a bug in the implementation of Q: if you can only work in the homogeneous parts, it's a disjoint union of modules; not a ring, and it shouldn't have any business trying to use ring machinery.

---

New commits:

45d7f4e

trac 20722: Base QuotientRingElement._cmp_ on ideal membership

[nbruin]

comment:3

Input needed from some FreeAlgebra experts. Including Simon and Burcin.

[simon-king-jena]

comment:5

Replying to @nbruin:

Input needed from some FreeAlgebra experts. Including Simon and Burcin.

I thought that the letterplace implementation of free algebras does provide a normal form. Thus, there shouldn't be a problem involved here. Or am I missing something?

[nbruin]

comment:6

Replying to @simon-king-jena:

I thought that the letterplace implementation of free algebras does provide a normal form. Thus, there shouldn't be a problem involved here. Or am I missing something?

I don't think that normalform with respect to an ideal is defined in all text as something that is unique (EDIT: OK, I think it's part of the definition of Groebner basis that it is unique when taken with respect to a basis -- there is something to say for not letting equality testing in a quotient ring depend on finding a groebner basis for the ideal first though). Clearly, in the example in this ticket, this fails. Whether this is a bug in the relevant groebner basis/reduction code or whether this is an unfortunate feature of the definition of groebner basis used there, I don't know.

The test branch I wrote avoids depending on a normal form by testing if the difference of representatives lies in the ideal. On the FreeAlgebra test case, this leads to subtracting elements of unequal degree in the standard powering algorithm, which leads to an error.

The fact that you cannot subtract any two elements in FreeAlgebra is a bug in itself: it means its ring structure isn't fully implemented. It would be good to change this. If FreeAlgebras are always graded (and we only consider homogeneous ideals in them) then perhaps elements should be implemented as vectors of homogeneous elements, with component-wise addition and subtraction. Then the thing is actually a ring. Now it's just a disjoint union of modules tied together with multiplication morphisms. Or are FreeAlgebras certifiably only useful with the partial operations?

If we can regain unique NormalForm with respect to all ideals in all rings this code gets used for, we could hide the problem again by reverting the definition of equality testing. However, I think the "is difference in ideal" test is preferable anyway:

• you only need one reduction instead of two (although perhaps the elements are already in reduced form and hopefully the reduction algorithm detects that quickly)
• I expect positive answers to have a better chance of being quick, because showing an element does lie in an ideal often allows shortcuts (that I hope many reduction algorithms would find)

[sagetrac-tmonteil]

comment:9

Might this one be related : #24808 ?