Opened 9 years ago

Closed 9 years ago

#10625 closed defect (fixed)

inverse_mod for integer ring won't take an ideal as argument

Reported by: rbeezer Owned by: AlexGhitza
Priority: major Milestone: sage-4.6.2
Component: algebra Keywords:
Cc: davidloeffler Merged in: sage-4.6.2.alpha2
Authors: David Loeffler Reviewers: Rob Beezer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by davidloeffler)

The top level inverse_mod method for ring elements (in sage.structure.element.RingElement) mandates that inverse_mod should always take an ideal of the ring as its argument. The integer ring doesn't implement this correctly:

sage: ZZ(2).inverse_mod(ZZ.ideal(3))
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/storage/masiao/sage-4.6.2.alpha0/devel/sage-reviewing/sage/rings/<ipython console> in <module>()

/usr/local/sage/sage-4.6.1/local/lib/python2.6/site-packages/sage/rings/integer.so in sage.rings.integer.Integer.inverse_mod (sage/rings/integer.c:28740)()
   5161         cdef Integer ans = <Integer>PY_NEW(Integer)
   5162         if mpz_cmp_ui(m.value, 1) == 0:
-> 5163             return zero
   5164         sig_on()
   5165         r = mpz_invert(ans.value, self.value, m.value)

/usr/local/sage/sage-4.6.1/local/lib/python2.6/site-packages/sage/rings/integer.so in sage.rings.integer.as_Integer (sage/rings/integer.c:6052)()
    365         return <Integer>x
    366     else:
--> 367         return Integer(x)
    368 
    369 cdef class IntegerWrapper(Integer):

/usr/local/sage/sage-4.6.1/local/lib/python2.6/site-packages/sage/rings/integer.so in sage.rings.integer.Integer.__init__ (sage/rings/integer.c:7312)()
    678                         pass
    679                         
--> 680                 raise TypeError, "unable to coerce %s to an integer" % type(x)
    681 
    682     def __reduce__(self):

TypeError: unable to coerce <class 'sage.rings.ideal.Ideal_pid'> to an integer

This causes issues with the generic Smith form implementation applied to integer matrices. Here's the evidence, obtained by shipping in a sparse matrix - this should soon be fixed by sending sparse matrices to the working dense version. So if you test this use something like 4.6.1 or earlier.

sage: A = matrix(2,range(4), sparse=True)
sage: A.smith_form()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/home/sage/sage-4.6.1.alpha2/<ipython console> in <module>()

/home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-packages/sage/matrix/matrix2.so in sage.matrix.matrix2.Matrix.smith_form (sage/matrix/matrix2.c:37477)()

/home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-packages/sage/matrix/matrix2.so in sage.matrix.matrix2._smith_onestep (sage/matrix/matrix2.c:42366)()

/home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-packages/sage/matrix/matrix2.so in sage.matrix.matrix2._smith_onestep (sage/matrix/matrix2.c:42181)()

/home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-packages/sage/matrix/matrix2.so in sage.matrix.matrix2._generic_clear_column (sage/matrix/matrix2.c:41049)()

/home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-packages/sage/rings/integer.so in sage.rings.integer.Integer.inverse_mod (sage/rings/integer.c:28740)()

/home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-packages/sage/rings/integer.so in sage.rings.integer.as_Integer (sage/rings/integer.c:6052)()

/home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-packages/sage/rings/integer.so in sage.rings.integer.Integer.__init__ (sage/rings/integer.c:7312)()

TypeError: unable to coerce <class 'sage.rings.ideal.Ideal_pid'> to an integer

Attachments (1)

trac_10625-inverse_mod_ideal_of_zz.patch (1.5 KB) - added by davidloeffler 9 years ago.
patch against 4.6.2.alpha0

Download all attachments as: .zip

Change History (6)

comment:1 Changed 9 years ago by davidloeffler

  • Description modified (diff)
  • Summary changed from Generic smith form of a matrix fails on integer matrix to inverse_mod for integer ring won't take an ideal as argument

I don't mean to seem hostile, but: I wrote the generic Smith and Hermite form code, and I used no assumptions on the methods of the ring elements other than those mandated by the docstrings of the top-level sage.structure.element.RingElement class. The problem is that the Integer class doesn't play by the rules (because it's so routine to confuse an ideal of ZZ with its non-negative generator).

So the solution is not to change the Smith form code, but to add a couple of lines to Integer.inverse_mod to make it consistent with the general ring element template.

Changed 9 years ago by davidloeffler

patch against 4.6.2.alpha0

comment:2 Changed 9 years ago by davidloeffler

  • Status changed from new to needs_review

Here's the required 2-line patch.

comment:3 Changed 9 years ago by rbeezer

Hi David,

Thanks for the explanation, and the patch (and the review on #10626). I spent several hours tracking down a number field doctest-failure to this "problem" with a sparse matrix being shipped to the generic routine. At that point, I was just puzzled by the failure of the generic code to behave properly on a simple example and did not dig any deeper. In retrospect, a post to sage-devel might have been a better course, but I knew you would know what was up. So thanks again for the explanation and the fix.

I'll work up a review of this later today.

Rob

comment:4 Changed 9 years ago by rbeezer

  • Authors set to David Loeffler
  • Reviewers set to Rob Beezer
  • Status changed from needs_review to positive_review

Passes all tests on 4.6.1.alpha3, rectifies problem at #10626, and looks good. Positive review.

comment:5 Changed 9 years ago by jdemeyer

  • Merged in set to sage-4.6.2.alpha2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.