> 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 + ). 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 + ).
> >>
> >> 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. = 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. = 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. = 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. = 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. = 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. = 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
> >
