Opened 3 years ago

Closed 3 years ago

Last modified 21 months ago

#22454 closed defect (fixed)

is_unit can give wrong results in multivariate and infinite polynomial rings.

Reported by: msaaltink Owned by:
Priority: minor Milestone: sage-7.6
Component: algebra Keywords:
Cc: Merged in:
Authors: Mark Saaltink Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 4c2f792 (Commits) Commit:
Dependencies: Stopgaps:

Description

There are 6 different definitions of is_unit for polynomials over commutative rings in sage/rings/polynomial/:

infinite_polynomial_element.py:428:    def is_unit(self):
multi_polynomial_element.py:914:    def is_unit(self):
multi_polynomial_libsingular.pyx:3092:    def is_unit(self):
pbori.pyx:3593:    def is_unit(BooleanPolynomial self):
polynomial_element_generic.py:962:    def is_unit(self):
polynomial_element.pyx:5041:    def is_unit(self):

Of these, pbori.pyx, polynomial_element_generic.py and polynomial_element.pyx correctly apply the following fact:

EXERCISE (Atiyah-McDonald?, Ch 1): Let A[x] be a polynomial ring in one variable. Then f=\sum a_i x^i \in A[x] is a unit if and only if a_0 is a unit and a_1,\ldots, a_n are nilpotent.

(This fact is also noted in Dummit and Foote, "Abstract Algebra", 1991, Section 7.3 Exercise 33).

infinite_polynomial_element.py, multi_polynomial_element.py, multi_polynomial_libsingular.pyx have incorrect implementations and can give incorrect results:

sage: _.<x> = InfinitePolynomialRing(Zmod(4))
sage: p = (1 + 2*x[0])
sage: p*p
1
sage: p.is_unit()
False
sage: p.is_unit.__module__
'sage.rings.polynomial.infinite_polynomial_element'


sage: _.<x,y> = Zmod(4)[]
sage: p = 1+2*x
sage: p*p
1
sage: p.is_unit()
False
sage: type(p)
<type 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular'>
sage: p.is_unit
<built-in method is_unit of sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular object at 0x7fde1d743780>

Change History (11)

comment:1 Changed 3 years ago by msaaltink

  • Branch set to u/msaaltink/is_unit_can_give_wrong_results_in_mutlivariate_and_infinite_polynomial_rings_

comment:2 Changed 3 years ago by msaaltink

  • Authors set to Mark Saaltink
  • Commit set to 429dde814708ad2b01c04b5ab667756d635d58c5
  • Status changed from new to needs_review
  • Summary changed from is_unit can give wrong results in mutlivariate and infinite polynomial rings. to is_unit can give wrong results in multivariate and infinite polynomial rings.

New commits:

429dde8Trac 22454 - fixed is_unit and implemented is_nilpotent for multivariate and infinite polynomials.

comment:3 Changed 3 years ago by tscrim

For is_unit in multi_polynomial.pyx, I would do:

        if not self.constant_coefficient().is_unit():
            return False
        from polydict import ETuple
        cdef dict d = self.dict()
        cdef ETuple zero_key = ETuple([0]*self.parent().ngens())
        if zero_key in d:
            d.pop(zero_key)
        return all(d[k].is_nilpotent() for k in d)

for speed.

comment:4 Changed 3 years ago by msaaltink

Good idea. I ran some timings with a polynomial (that was in fact a unit) over Zmod(125):

sage: len(p.coefficients())
249002
sage: %timeit p.is_unit()
1 loop, best of 3: 2.22 s per loop
sage: %timeit p.dict()
1 loop, best of 3: 1.69 s per loop

So around 76% of the time is taken to construct the dictionary. I'll bet the best efficiency gains would be had by avoiding that step, but it would be messy and would repeat code.

With your version of the code, I got about a 2% improvement in runtime:

sage: %timeit p.is_unit()
1 loop, best of 3: 2.18 s per loop

I tried another small change:

        if not self.constant_coefficient().is_unit():
            return False
        cdef dict d = self.dict()
        cdef ETuple zero_key = ETuple([0]*self.parent().ngens())
        d.pop(zero_key, None)
        return all(d[k].is_nilpotent() for k in d)

This gives about a 6% speed improvement:

sage: %timeit p.is_unit()
1 loop, best of 3: 2.09 s per loop

I'll look for anything else I can do for efficiency, then push the changes.

comment:5 Changed 3 years ago by tscrim

You probably would need to write a helper method _nonconstant_coeff_iter that would likely be implementation dependent, but uses the underlying structure of the polynomial; i.e., compare the dict methods of an element of ZZ['z']['x,y'] and QQ['x,y']. Although this might be a bit overkill for this ticket. Here, you can get some (micro)speed by

sage: from sage.rings.polynomial.polydict import ETuple
sage: n = 5
sage: z = int(0)
sage: %timeit [ETuple({}, int(n)) for _ in range(1000)]
1000 loops, best of 3: 724 µs per loop
sage: %timeit [ETuple([z]*n) for _ in range(1000)]
1000 loops, best of 3: 902 µs per loop
sage: n = int(300)
sage: %timeit [ETuple({}, int(n)) for _ in range(1000)]
1000 loops, best of 3: 685 µs per loop
sage: %timeit [ETuple([z]*n) for _ in range(1000)]
100 loops, best of 3: 3.83 ms per loop

comment:6 Changed 3 years ago by git

  • Commit changed from 429dde814708ad2b01c04b5ab667756d635d58c5 to c42072d33bfef2db3b69013f45585d454e089624

Branch pushed to git repo; I updated commit sha1. New commits:

c42072dSmall speedup in is_unit for multivariate polynomials

comment:7 Changed 3 years ago by tscrim

If you could make the one additional change to use:

cdef ETuple zero_key = ETuple({}, int(self.parent().ngens()))

then you can set a positive review on my behalf.

comment:8 Changed 3 years ago by git

  • Commit changed from c42072d33bfef2db3b69013f45585d454e089624 to 4c2f79266e38b6312eb5041575bfc73bf6e6f47c

Branch pushed to git repo; I updated commit sha1. New commits:

4c2f792Reviewer comment: better way to create a zero ETuple.

comment:9 Changed 3 years ago by msaaltink

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

tscrim: Done. I looked at ETuple and see that this call goes to a simpler code path. As you showed above, it is indeed a bit faster. Thanks for the review.

comment:10 Changed 3 years ago by vbraun

  • Branch changed from u/msaaltink/is_unit_can_give_wrong_results_in_mutlivariate_and_infinite_polynomial_rings_ to 4c2f79266e38b6312eb5041575bfc73bf6e6f47c
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:11 Changed 21 months ago by enriqueartal

  • Commit 4c2f79266e38b6312eb5041575bfc73bf6e6f47c deleted
Note: See TracTickets for help on using tickets.