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

[sagetrac-msaaltink]

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>

Component: algebra

Author: Mark Saaltink

Branch: 4c2f792

Reviewer: Travis Scrimshaw

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

[sagetrac-msaaltink]

Branch: u/msaaltink/is_unit_can_give_wrong_results_in_mutlivariate_and_infinite_polynomial_rings_

[sagetrac-msaaltink]

New commits:

429dde8

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

[sagetrac-msaaltink]

Commit: 429dde8

[sagetrac-msaaltink]

Author: Mark Saaltink

[tscrim]

comment:3

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.

[sagetrac-msaaltink]

comment:4

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.

[tscrim]

comment:5

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

[sagetrac-git]

Changed commit from 429dde8 to c42072d

[sagetrac-git]

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

c42072d

Small speedup in is_unit for multivariate polynomials