On 31 October 2012 13:39, Charles Bouillaguet <charles.bouillag...@gmail.com > wrote:
> > > 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. > > 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. 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.
