Opened 6 years ago

Closed 6 years ago

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

Reported by: Owned by: Mark Saaltink minor sage-7.6 algebra Mark Saaltink Travis Scrimshaw N/A 4c2f792

### 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>


### comment:1 Changed 6 years ago by Mark Saaltink

Branch: → u/msaaltink/is_unit_can_give_wrong_results_in_mutlivariate_and_infinite_polynomial_rings_

### comment:2 Changed 6 years ago by Mark Saaltink

Authors: → Mark Saaltink → 429dde814708ad2b01c04b5ab667756d635d58c5 new → needs_review is_unit can give wrong results in mutlivariate and infinite polynomial rings. → is_unit can give wrong results in multivariate and infinite polynomial rings.

New commits:

 ​429dde8 Trac 22454 - fixed is_unit and implemented is_nilpotent for multivariate and infinite polynomials.

### comment:3 Changed 6 years ago by Travis Scrimshaw

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 6 years ago by Mark Saaltink

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 6 years ago by Travis Scrimshaw

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 6 years ago by git

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

 ​c42072d Small speedup in is_unit for multivariate polynomials

### comment:7 Changed 6 years ago by Travis Scrimshaw

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 6 years ago by git

Commit: c42072d33bfef2db3b69013f45585d454e089624 → 4c2f79266e38b6312eb5041575bfc73bf6e6f47c

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

 ​4c2f792 Reviewer comment: better way to create a zero ETuple.

### comment:9 Changed 6 years ago by Mark Saaltink

Reviewers: → Travis Scrimshaw needs_review → 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 6 years ago by Volker Braun

Branch: u/msaaltink/is_unit_can_give_wrong_results_in_mutlivariate_and_infinite_polynomial_rings_ → 4c2f79266e38b6312eb5041575bfc73bf6e6f47c → fixed positive_review → closed

### comment:11 Changed 4 years ago by Enrique Artal Bartolo

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