> Sure. So we have 4 (?) possible outcomes: > > 1. Inverse exists and we can compute it: return the inverse > 2. We can compute that the inverse does not exist: ZeroDivisionError > 3. We can compute that the inverse exists but cannot find the inverse: > NotImplementedError > 4. We cannot determine invertibility: NotImplementedError > > For your rings, and (for example) in Z/nZ, we would be in cases 1 or 2. For > a completely general abstract ring: case 4. I added Case 3 later, but have > not yet come up with an example.
In fact, it seems weird to handle the polynomial case inside rings/quotient_ring_element.py This file actually implements the computation of the inverse of a polynomial modulo a polynomial ideal, and it seems (to me at least) that this is not the right place for this. This should be implemented in rings/polynomial/multi_polynomial.pyx, as the inverse_mod() method. The existence of this method is advertised by the TAB-completion, but it is in fact NotImplemented. Thus, #13675 which adds this method awaits review :) Then, as a second step, I suggest to remove this bizarre code from rings/quotient_ring_element.py Charles PS : John, how could I construct an example for case 4? > John > > 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. > > > > > -- > 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.
