multivariate polynomials lack the inverse_mod(...) method

[89f39f15-88e8-4e79-9bc0-0739a7fc497c]

Merge together with #13671, circular dependency

TAB-completion advertises that the method exists, but it is NotImplemented.

sage: R.<x,y> = QQ[]
sage: f = x+y
sage: f.inverse_mod(ideal(x,y))
Traceback (most recent call last)
...
NotImplementedError: 

This should not be hard, as soon as a Groebner basis of the ideal can be computed.

Merge together with #13671, circular dependency

Depends on #13671

CC: @malb @mstreng

Component: commutative algebra

Keywords: inverse modulo an ideal

Author: Charles Bouillaguet

Reviewer: Marco Streng

Merged: sage-5.5.beta2

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

[mstreng]

comment:2

Hi Charles,

If I understand correctly, then after #13671 is fixed, the following code will give "ValueError: polynomial is not in the ideal" rather than ArithmeticError: element is non-invertible. (And until #13671 is fixed, trying to invert non-invertible elements may trigger the corruption from #13671.)

XY = P.one().lift((self,) + tuple(B)) 
if XY == [0]*len(XY): 
    raise ArithmeticError, "element is non-invertible"

How about changing it to the following?

if not P.one() in P.ideal([self] + B):
    raise ArithmeticError, "element is non-invertible"
XY = P.one().lift((self,) + tuple(B)) 

Some other comments:

• The first block of examples misses the "::" needed for nice formatting of the html documentation.
• The line "returns an inverse of self modulo the ideal `I`" could use a little bit more information: that "I" should be an ideal of the parent P of self, and that the output is an element of P, and I suppose a capital letter at the start.

Best, Marco

[mstreng]

Author: Charles Bouillaguet

[mstreng]

Reviewer: Marco Streng

[89f39f15-88e8-4e79-9bc0-0739a7fc497c]

comment:3

Replying to @mstreng:

Hi Marco,

Thanks for your advice. I (think that I) implemented your suggestions.

I have a question though: is it necessary and/or desirable to check wether the second argument is actually an ideal? It seems that most functions do not, but is this the standard behavior?

[mstreng]

comment:4

The word OUTPUT is indented too much. You can also see what the documentation looks like with ./sage -docbuild reference html and looking at SAGEROOT/devel/sage-main/doc/output/html/en/reference/sage/rings/polynomial/multi_polynomial.html. Fix this, and this patch can get a positive review.

Note though that the check with "in" is very inefficient (so I'm sorry for suggesting it):

sage: R.<x1,x2> = QQ[]
sage: I = R.ideal(x2**2 + x1 - 2, x1**2 - 1) 
sage: f = x1 + 3*x2^2
sage: self = f
sage: P=R
sage: B = I.groebner_basis()
sage: timeit('(P.one() in P.ideal([self]+B))')
625 loops, best of 3: 1.23 ms per loop
sage: timeit('P.one().lift((self,)+tuple(B))')
625 loops, best of 3: 161 µs per loop

I haven't tried bigger examples, so I don't know what happens with them. Do you? Even if it were efficient, then it looks like, after computing the Groebner basis B, I assume some (Groebner basis?) precomputation involving [self]+B is done computed twice. For both these reasons, it would seem faster to do skip the check with "in", and put the line with "lift" inside a "try". But that would require #13671 to be fixed first. Alternatively: in which package is "lift" implemented? Doesn't that package have an "inverse_mod" method ready to wrap?

[89f39f15-88e8-4e79-9bc0-0739a7fc497c]

comment:5

Replying to @mstreng:

The word OUTPUT is indented too much. You can also see what the documentation looks like with ./sage -docbuild reference html and looking at SAGEROOT/devel/sage-main/doc/output/html/en/reference/sage/rings/polynomial/multi_polynomial.html. Fix this, and this patch can get a positive review.

Fixed (I also fixed another stupid docstring issue for another function)

Note though that the check with "in" is very inefficient (so I'm sorry for suggesting it)

Well, checking that P.one() belongs to [self]+B should in principe trigger the computation of a Groebner basis thereof. But performing the "lift" also requires a GB, so I assume that the whole operation computes a GB of [self]+B. It would be stupid if this happened TWICE though.

However, computing a GB of the ideal B was useless, so I removed it (but when you work in the quotient R/B, you most likely WILL need a GB of B at some point, I guess).

For both these reasons, it would seem faster to do skip the check with "in", and put the line with "lift" inside a "try". But that would require #13671 to be fixed first. Alternatively: in which package is "lift" implemented? Doesn't that package have an "inverse_mod" method ready to wrap?

Lift is implemented by singular. We could have a generic implementation based on multivariate polynomial division, but it would not make much sense, because all our operations on multivariate polynomial are handled by singular at this time.

I don't know if singular has the inverse_mod operation. I will check. However at this time, testing if 1 belongs to the ideal is necessary to work around the bug in lift exposed by #13671

[89f39f15-88e8-4e79-9bc0-0739a7fc497c]

comment:6

Replying to @sagetrac-Bouillaguet:

I don't know if singular has the inverse_mod operation. I will check. However at this time, testing if 1 belongs to the ideal is necessary to work around the bug in lift exposed by #13671

I checked out the Singular documentation : lift IS the right way to compute the inverse in R/I

[89f39f15-88e8-4e79-9bc0-0739a7fc497c]

comment:7

Last version of the patch tries to make the whitespace plugin of the patchbot happy

[89f39f15-88e8-4e79-9bc0-0739a7fc497c]

comment:8

Hi Marco,

Just a stupid question : should inverse_mod(...) be implemented in multi_polynomial.py or in multi_polynomial_element.py ???

I don't exactly understand the logic here...

Charles

[mstreng]

comment:9

Replying to @sagetrac-Bouillaguet:

should inverse_mod(...) be implemented in multi_polynomial.py or in multi_polynomial_element.py ???

I don't exactly understand the logic here...

Here's the logic, as far as I understand:

• multi_polynomial.pyx contains the base class MPolynomial
• multi_polynomial_element.py contains polynomials over arbitrary rings, in the form of the class MPolynomial_polydict
• multi_polynomial_libsingular.pyx contains fast polynomials via Singular, in the form of the class MPolynomial_libsingular

The lift function, which you use, currently only exists in MPolynomial_libsingular and MPolynomial_polydict.

The two classes MPolynomial_libsingular and MPolynomial_polydict inherit from the first (MPolynomial) and there is no more specific class from which they both inherit.

So if you put inverse_mod in multi_polynomial.pyx directly, without providing a "lift" method there as well, you run the risk of getting

AttributeError: '...' object has no attribute 'lift'

which isn't very helpful, as the word "lift" can mean dozens of things in mathematics.

So I think that leaves you with two options: either

• implement inverse_mod in both of MPolynomial_libsingular and MPolynomial_polydict (or only one of them if you don't care about the other and don't mind doing half a job)
• implement inverse_mod in MPolynomial, and give Mpolynomial a "lift" method with the same documentation as the "lift" method in the other two classes, but always raising NotImplementedError

The second option looks best to me, and you're already halfway with that.

[89f39f15-88e8-4e79-9bc0-0739a7fc497c]

comment:10

Here's the logic, as far as I understand:

• multi_polynomial.pyx contains the base class MPolynomial
• multi_polynomial_element.py contains polynomials over arbitrary rings, in the form of the class MPolynomial_polydict

Well, the logic behind this would be more obvious if multi_polynomial_element.py was in fact named multi_polynomial_polydict.py... But who am I to complain :) ?

The lift function, which you use, currently only exists in MPolynomial_libsingular and MPolynomial_polydict.

Well, the latter actually uses the former...

The two classes MPolynomial_libsingular and MPolynomial_polydict inherit from the first (MPolynomial) and there is no more specific class from which they both inherit.

So if you put inverse_mod in multi_polynomial.pyx directly, without providing a "lift" method there as well, you run the risk of getting

AttributeError: '...' object has no attribute 'lift'

which isn't very helpful, as the word "lift" can mean dozens of things in mathematics.

So I think that leaves you with two options: either

• implement inverse_mod in both of MPolynomial_libsingular and MPolynomial_polydict (or only one of them if you don't care about the other and don't mind doing half a job)
• implement inverse_mod in MPolynomial, and give Mpolynomial a "lift" method with the same documentation as the "lift" method in the other two classes, but always raising NotImplementedError

The second option looks best to me, and you're already halfway with that.

Done

[89f39f15-88e8-4e79-9bc0-0739a7fc497c]

comment:11

I modified the patch to depend on the repaired lift function. This makes more sense. The combination of both patches passes the long tests...

[89f39f15-88e8-4e79-9bc0-0739a7fc497c]

Dependencies: #13671

[mstreng]

comment:12

You fixed the output of a test for __invert__ in quotient_ring_element.py, but actually the whole test is incorrect.

The element x mod (x<sup>2+y</sup>2) has no inverse, and this is not because "extending the base field is implemented yet" as claimed in quotient_ring_element.py, neither is it because "extending the base field is not implemented yet". This element has no inverse, even if the base field is extended. This element is simply not invertible. Could you remove the words ", and extending the base field is implemented yet"?

[89f39f15-88e8-4e79-9bc0-0739a7fc497c]

patch adding the method

[89f39f15-88e8-4e79-9bc0-0739a7fc497c]

comment:13

Attachment: 13675_add_inversemod_method.patch.gz

Replying to @mstreng:

You fixed the output of a test for __invert__ in quotient_ring_element.py, but actually the whole test is incorrect.

The element x mod (x<sup>2+y</sup>2) has no inverse, and this is not because "extending the base field is implemented yet" as claimed in quotient_ring_element.py, neither is it because "extending the base field is not implemented yet". This element has no inverse, even if the base field is extended. This element is simply not invertible. Could you remove the words ", and extending the base field is implemented yet"?

Done. The incriminated doctest was here from before... and the culprit is... #9500.

[mstreng]

comment:14

Looks good!

[mstreng]

Description changed:

--- 
+++ 
@@ -1,3 +1,5 @@
+** Merge together with #13671, circular dependency **
+
 TAB-completion advertises that the method exists, but it is NotImplemented.

@@ -10,3 +12,6 @@

 This should not be hard, as soon as a Groebner basis of the ideal can be computed.
+
+** Merge together with #13671, circular dependency **
+

[jdemeyer]

Merged: sage-5.5.beta2