#22454 closed defect (fixed)
is_unit can give wrong results in multivariate and infinite polynomial rings.
Reported by:  msaaltink  Owned by:  

Priority:  minor  Milestone:  sage7.6 
Component:  algebra  Keywords:  
Cc:  Merged in:  
Authors:  Mark Saaltink  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  4c2f792 (Commits, GitHub, GitLab)  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 (AtiyahMcDonald?, 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 <builtin method is_unit of sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular object at 0x7fde1d743780>
Change History (11)
comment:1 Changed 5 years ago by
 Branch set to u/msaaltink/is_unit_can_give_wrong_results_in_mutlivariate_and_infinite_polynomial_rings_
comment:2 Changed 5 years ago by
 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.
comment:3 Changed 5 years ago by
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 5 years ago by
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 5 years ago by
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 5 years ago by
 Commit changed from 429dde814708ad2b01c04b5ab667756d635d58c5 to c42072d33bfef2db3b69013f45585d454e089624
Branch pushed to git repo; I updated commit sha1. New commits:
c42072d  Small speedup in is_unit for multivariate polynomials

comment:7 Changed 5 years ago by
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 5 years ago by
 Commit changed from c42072d33bfef2db3b69013f45585d454e089624 to 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 5 years ago by
 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 5 years ago by
 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 4 years ago by
 Commit 4c2f79266e38b6312eb5041575bfc73bf6e6f47c deleted
New commits:
Trac 22454  fixed is_unit and implemented is_nilpotent for multivariate and infinite polynomials.