> I think all that Marco meant was that for a general ring, there may be > no algorithm to decide invertibility. In this ring, of course there > is.
Yes, but the NotImplemented exception was raised **in the case where a Groebner basis could be computed**, and I maintain that it is not the most adapted answer. I have written a patch, and I'm presently testing it. Charles > John > >> >> Let R be a polynomial ring, I be an ideal of R, and f be a non-zero element >> of R/I. >> >> To check whether f is invertible in R/I, we check whether 1 belongs to the >> ideal (I + <f>). If it is the case, then an inverse exist. Indeed, in this >> case, there exist g in R such that 1 = [something in I] + g*f. It follows >> that the class of g in R/I is the inverse of f. >> >> But this test in fact **decides** whether an inverse exist. If there exist a >> g such that f*g = 1 mod I, then by definition there exist two polynomials of >> R, say f' and g', such that f is the class of f' and g is the class of g' >> modulo I. Then in R we have f*g = 1 + [something in I]. This automatically >> implies that 1 belongs to the ideal (I + <f>). >> >> Thus, the current implementation should not return "ErrorNotImplemented", it >> should return "NonInvertible", because we KNOW that it is the case... >> >> This is now #13670. >> >> However, presently this test uses p.lift(…), and as you pointed out the >> answer becomes bogus as soon as one tries to invert something >> non-invertible…. >> >> This one is now #13671 . >> >> Cheers, >> --- >> Charles Bouillaguet >> http://www.lifl.fr/~bouillaguet/ >> >>>> *) Non-deterministic output of some (presumably deterministic) functions >>>> >>>> Here is an example : >>>> >>>> sage: R.<x1,x2> = QQ[] >>>> sage: I = R.ideal(x2**2 + x1 - 2, x1**2 - 1) >>>> sage: test = I.gen(0) + x2*I.gen(1) >>>> sage: (test).lift( I ) >>>> [1, x2] # this is correct >>>> >>>> sage: R.<x1,x2> = QQ[] >>>> sage: I = R.ideal(x2**2 + x1 - 2, x1**2 - 1) >>>> sage: test = I.gen(0) + x2*I.gen(1) >>>> sage: (test + 1).lift( I ) >>>> [0, 0] # this is correct >>> >>> No it isn't, the correct output would be ValueError, as (test+1) is >>> not in I. So this is a bug in the "lift" method. >>> >>>> >>>> sage: R.<x1,x2> = QQ[] >>>> sage: I = R.ideal(x2**2 + x1 - 2, x1**2 - 1) >>>> sage: test = I.gen(0) + x2*I.gen(1) >>>> sage: (test).lift( I ) >>>> [0, 0] # this is WRONG !!! should be [1, x2] >>>> >>>> It looks like this could be a caching issue, so I am not sure whether I >>>> need to open a new ticket for this, or if it is already "catch" by an >>>> already-opened ticket. >>> >>> It is some kind of corruption triggered by the abovementioned bug, so >>> it may vanish when that bug is fixed. >>> >>> Here is a shortened version of your input: >>> >>> sage: R.<x1,x2> = QQ[] >>> sage: I = R.ideal(x2**2 + x1 - 2, x1**2 - 1) >>> sage: test = I.gen(0) + x2*I.gen(1) >>> sage: test.lift(I) # correct >>> [1, x2] >>> sage: (test+1).lift(I) # invalid input, should give error >>> [0, 0] >>> sage: test.lift(I) # incorrect >>> [0, 0] >>> >>> >>> >>>> >>>> *) Segfault >>>> >>>> The same kind of problem allows a small piece of code to cause segfaults >>>> in SAGE (apparently in singular-related stuff) : >>>> >>>> sage: R.<x1,x2> = QQ[] >>>> sage: S = R.quotient_ring( R.ideal(x2**2 + x1 - 2, x1**2 - 1) ) >>>> sage: 1 / S(x1 + x2) # should raise NotImplementedError >>>> sage: >>>> sage: R.<x1,x2> = QQ[] >>>> sage: S = R.quotient_ring( R.ideal(x2**2 + x1 - 2, x1**2 - 1) ) >>>> sage: S.is_integral_domain() >>>> >>>> ---> BOOM >>>> >>>> *) bizarre output of p.lift(….) >>>> >>>> When R is a Polynomial Ring, I is an ideal of R, and p is a polynomial of >>>> I, then p.lift( I ) returns a polynomial combination of a (groebner) basis >>>> of I which is equal to p. However, when p is not in I, then p.lift( I ) >>>> returns [0,0,…,0]. I find this a bit strange. Should p.lift(…) raise an >>>> exception instead? This would be a change of specification, so I guess it >>>> should be discussed first… >>>> >>>> >>>> >>>> >>>> --- >>>> Charles Bouillaguet >>>> http://www.lifl.fr/~bouillaguet/ >>>> >>>> >>>> >>>> -- >>>> You received this message because you are subscribed to the Google Groups >>>> "sage-devel" group. >>>> To post to this group, send email to sage-devel@googlegroups.com. >>>> To unsubscribe from this group, send email to >>>> sage-devel+unsubscr...@googlegroups.com. >>>> Visit this group at http://groups.google.com/group/sage-devel?hl=en. >>>> >>>> >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "sage-devel" group. >>> To post to this group, send email to sage-devel@googlegroups.com. >>> To unsubscribe from this group, send email to >>> sage-devel+unsubscr...@googlegroups.com. >>> Visit this group at http://groups.google.com/group/sage-devel?hl=en. >>> >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "sage-devel" group. >> To post to this group, send email to sage-devel@googlegroups.com. >> To unsubscribe from this group, send email to >> sage-devel+unsubscr...@googlegroups.com. >> Visit this group at http://groups.google.com/group/sage-devel?hl=en. >> >> > > -- > You received this message because you are subscribed to the Google Groups > "sage-devel" group. > To post to this group, send email to sage-devel@googlegroups.com. > To unsubscribe from this group, send email to > sage-devel+unsubscr...@googlegroups.com. > Visit this group at http://groups.google.com/group/sage-devel?hl=en. > > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en.