ZeroDivisionError while reducing a polynomial w.r.t. the zero ideal

[maxale]

The following code produces ZeroDivisionError:

K.<x,y> = AA[]
K.ideal([]).reduce(x+1)

Interestingly, the error goes away if K.<x,y> = AA[] is replaced with K.<x> = AA[] or with K.<x,y> = QQ[].

CC: @tscrim

Component: algebra

Author: Dave Morris, Kwankyu Lee

Branch/Commit: 0b16491

Reviewer: Kwankyu Lee, Dave Morris

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

[nbruin]

comment:1

sage: K.<x,y> = AA[]
....: I=K.ideal([])
sage: I.gens()
[0]

so the generic code in sage/rings/polynomial/multi_polynomial_ideal.py probably chokes on a zero generator. The behaviour of I.gens() is the same for QQ[], so I suspect the reduction code should simply skip over zero generators to be consistent with the other backends.

[DaveWitteMorris]

Branch: public/34105

[DaveWitteMorris]

Commit: 48248d6

[DaveWitteMorris]

Author: Dave Morris

[DaveWitteMorris]

comment:3

The first commit fixes the error by skipping zero monomials (and adds a doctest). The second commit cleans up the code a bit.

---

New commits:

1aafc3c	trac 34105 fix ZeroDivisionError
48248d6	minor refactoring

[maxale]

comment:4

Btw, it's not directly related to this bug report, but I see a discrepancy in .gens() for univariate and multivariate ideals. In the former case, it returns a tuple and the latter case it returns a list:

sage: K.<x> = QQ[]
....: K.ideal().gens()
(0,)
sage: K.<x,y> = QQ[]
....: K.ideal().gens()
[0]

Shouldn't it be always a tuple?

[DaveWitteMorris]

comment:5

I opened #34120 to discuss the issue in comment:4.

[kwankyu]

comment:6

Why did you remove this?

    lI = len(I)
    I = list(I)  

The code is for performance.

[DaveWitteMorris]

Changed branch from public/34105 to public/34105r1

[DaveWitteMorris]

Changed commit from 48248d6 to 03d0ae2

[DaveWitteMorris]

comment:8

Thanks for your comments!

The code looked unpythonic to me, and I wasn't thinking about performance. Indeed, I don't know python well enough to understand most performance issues, but I can understand that having I = list(I) outside of the loop is more efficient.

Instead of for gi in I:, the code let lI = len(I) (outside of the loop) and then used the very unpythonic

for i in range(lI):
    gi = I[i]

I suppose that is also for performance (because the compiler does not know that the length of I is constant), so I reverted that change, too.

Part of the reason I made changes is that p -= quot*I[i] seemed poor. Even though my other attempts at improvement should be reverted, it seems to me this should be changed to p -= quot * gi. (Indeed, gi was specifically defined to be a more efficient replacement for I[i].) But I am not fluent in python, so I will certainly do whatever you think is best about this.

(PS: I also rebased on 9.7b5 and fixed a whitespace issue -- I had spaces at the start of three blank lines.)

---

New commits:

12697fe	trac 34105 fix ZeroDivisionError
03d0ae2	minor refactoring

[kwankyu]

comment:9

Changing I[i] to gi is certainly an improvement.

On the other hand, I think that this if gilm and P.monomial_divides(gilm, plm): is not a real solution of the issue. As gilm is the leading monomial of a polynomial, it should be nonzero by definition, and it should not be necessary to check if it is so.

The real problem is that R.zero_ideal().gens() returns the list of a zero polynomial. Mathematically zero (polynomial) is never a generator. Hence the proper solution would be to fix the gens() method of the ideal so that it returns an empty tuple (or list) for a zero ideal.

It is surprising to me that sage still has this bug, thinking the maturity of sage...

[DaveWitteMorris]

comment:10

I don't agree that this is a bug or mathematical error (because I seem to use terminology differently than you do), but the documentation should be clarified. For me, a generating set of an ideal is analogous to a spanning set of a vector space: there is no assumption that the set is irredundant or does not contain zero.

The docstring of I.gens says: "This is usually the set of generators provided during object creation" and I think that is the right thing to do, because it is very fast, and simplifying the list of generators could be expensive. (Probably the method gens_reduced should provide a good generating set, instead of just wrapping gens.) For example, I think the following output is fine:

sage: K.<x,y> = AA[]
sage: K.ideal([x, x^2, 0, 0, x*y]).gens()
[x, x^2, 0, 0, x*y]

On the other hand, the docstring of I.gens also says "Return a set of generators / a basis of this ideal." I think the mention of "a basis" is confusing and should be deleted. I don't know even know what it means to say that a set is a "basis" of an ideal, but I notice that ideals have a basis method that is a wrapper for gens.

A related issue is that I'm not so sure that the zero polynomial has a leading monomial:

sage: K(0).lm()
0

Perhaps this should return None (or raise ValueError), but returning 0 does seem reasonable.

[DaveWitteMorris]

comment:11

I forgot to mention a point on which I think we agree: the gens of the ideal generated by [] should be [], not [0].

[kwankyu]

comment:12

Replying to @DaveWitteMorris:

I forgot to mention a point on which I think we agree: the gens of the ideal generated by [] should be [], not [0].

Yes. The zero ideal is generated by an empty set of generators. Hence R.zero_ideal().gens() should always return an empty tuple.

It may be related with the fact that K(0).lm() returns 0. I think it is also reasonable that this would raise an error.

For this ticket, we may skip gi if it is a zero polynomial, instead of checking gilm is nonzero, if we allow a zero generator but assume leading monomial is nonzero.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

0b16491

Remove zeros from generator set

[sagetrac-git]

Changed commit from 03d0ae2 to 0b16491

[kwankyu]

comment:15

Setting zero element as the sole generator for a zero ideal seems pervasive in sage.

The simplest solution for this ticket seems removing zeros for reduction.

[kwankyu]

Changed author from Dave Morris to Dave Morris, Kwankyu Lee

[kwankyu]

Reviewer: Kwankyu Lee, Dave Morris

[kwankyu]

comment:17

Is the solution okay with you?

[DaveWitteMorris]

comment:18

Yes, thanks for making the change. It is better than my original fix.

The patchbot failures are known random failures (#32773 and #33907) so I consider the patchbot to be green.

[kwankyu]

comment:19

Thanks!

[vbraun]

Changed branch from public/34105r1 to 0b16491