More capable method valuation for polynomials

[bgrenet]

This ticket aims at improving the method valuation for polynomials in two ways:

1. The method valuation for dense polynomials can be called in the following ways:

   • Without argument, return the largest power of the variable that divides the input polynomial.
   • With a polynomial (with the same parent) as argument, return the largest power of this polynomial which divides the input polynomial.

   I propose to allow another possible argument: If the argument is an element of the base ring of the parent, it returns the minimum of the valuations of the coefficients. This is consistent with PARI.

2. The method valuation for sparse polynomials is much less capable than the method for dense polynomials. I propose to have the same behaviors in both cases.

Depends on #19171

Component: commutative algebra

Keywords: polynomial

Work Issues: Rebase

Author: Bruno Grenet

Branch/Commit: u/roed/t19172_valuation @ aa040dc

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

[bgrenet]

Branch: u/bruno/t19172_valuation

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

9a189c7	#19171: New method divides
62df327	#19172: Improve valuation for dense polynomials
66709eb	#19172: Improve valuation for sparse polynomials
992ee7a	#19172: Add valuation for multipolynomials

[sagetrac-git]

Commit: 992ee7a

[sagetrac-git]

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

d03a75e	#19171: New method divides
ac43c02	19171: Use coerce_binop
0906dfd	19171: Add more involved example + move a line
04b0032	Merge branch 'develop' into 19171_divides_poly
f85a7e0	19171: conflict resolution
a0a5bad	Merge branch 'u/bruno/t19171_divides_poly' of git://trac.sagemath.org/sage into 19171_divides_poly
9a548ad	Merge branch '19171_divides_poly' into 19172_valuation

[sagetrac-git]

Changed commit from 992ee7a to 9a548ad

[bgrenet]

Changed keywords from none to polynomial

[mezzarobba]

comment:6

sage: R.<x,y,z> = ZZ[]
sage: p = 4*x*y + z^2 - 9*x + 39*z
sage: p.valuation(-2)
...
ValueError: You can only compute the valuation with respect to a integer larger than 1.

sage: R.<x,y,z> = QQ[]
sage: p = 4*x*y + z^2 - 9*x + 39*z
sage: p.valuation(1/2)
...
TypeError: no conversion of this rational to integer

[mezzarobba]

comment:7

I would be tempted to simplify the version in multi_polynomial.pyx roughly as follows (not tested!):

        if arg is None:
            ex = self.exponents()
            return tuple(min(e[i] for e in ex) for i in range(self.nvariables()))

        arg = self.parent().coerce(arg)

        if arg.is_constant():
            arg = arg.constant_coefficient()
            return min(c.valuation(arg) for c in self.coefficients())

        try:
            ind = self.parent().gens().index(arg)
        except ValueError:
            pass
        else:
            return min(e[ind] for e in self.exponents())

        if arg.nvariables() == 1:
            return self.polynomial(arg.variable(0)).valuation()

        k = 0
        tmp = arg
        while tmp.divides(self):
            k += 1
            tmp *= arg
        return k

Also, I wonder if actually performing the exact division (and replacing self with the quotient) at each loop turn wouldn't be better, but this is generic code any case, I don't think that it matters much.

[simon-king-jena]

comment:8

The pyflakes plugin rightfully complains about the fact that in this changeset

@@ -200,9 +200,17 @@ class Polynomial_generic_sparse(Polynomial):
             sage: R(0).valuation()
             +Infinity
         """
-        if not self.__coeffs:
+        if not self:
             return infinity
-        return ZZ(min(self.__coeffs))
+
+        if p is infinity:
+            return -self.degree()
+
+        if p is None:
+            c = self.__coeffs.keys()
+            return ZZ(min(self.__coeffs.keys()))
+
+        return Polynomial.valuation(self, p)
 

the variable c is defined but not used. In fact, the corresponding line can just be deleted. I can do it as a reviewer patch. Since the tests pass for the patchbots, I can then see if I give it a positive review (need to look more closely at the code first).

[simon-king-jena]

comment:9

Also I was told by Vincent Delecroix that it would be better (since this is a rather old ticket based on a very old branch) to rebase it on top of the latest develop (not merging develop, he said).

[simon-king-jena]

comment:10

The first commit that is shown for the branch of this ticket is named #19171: New method divides.

Do I understand correctly that this commit was originally intended for #19171, but didn't get merged after all? So, my review will about this one as well.

EDIT: It is rather strange that the topic of #19171 was "Add a method 'divide' to Polynomial", and the commit adding the "New method divides" was not merged.

[simon-king-jena]

comment:11

Not good. When trying to rebase on top of develop, there is a merge conflict with the commit from #19171

[simon-king-jena]

comment:12

What I am trying now is whether the suspicious commit is needed at all.

[simon-king-jena]

comment:13

Sorry, it gets too complicated. Leaving out the commit named "#19171: New method divides" didn't solve the problem, as the second commit didn't merge either.

So, I think I will not continue to try and rebase it, and I'd appreciate if the author did.

[simon-king-jena]

Work Issues: Rebase

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

71e424b	19172: Improve valuation for dense polynomials
693f229	19172: Improve valuation for sparse polynomials
3318489	#19172: Add valuation for multipolynomials

[sagetrac-git]

Changed commit from 9a548ad to 3318489

[bgrenet]

comment:15

Hi Simon, I've rebased on develop. It should be OK now.

[simon-king-jena]

Replying to @bgrenet:

I propose to allow another possible argument: If the argument is an element of the base ring of the parent, it returns the minimum of the valuations of the arguments. This is consistent with PARI.

I don't understand what that specification means. Valuation has two arguments, namely self and arg resp. p. So, if the argument (p?) is an element of the base ring of "the parent" (the parent of self?) then it returns the minimum of the valuations of the arguments (i.e., of self and of p --- but with respect to what shall the valuation of self be taken? And what do you do if the base ring of the parent does not support a valuation, so that the valuation of p is not defined?).
I am sure you mean something else, but this is what I understood from your specification.

[bgrenet]

comment:17

Replying to @simon-king-jena:

Replying to @bgrenet:

I propose to allow another possible argument: If the argument is an element of the base ring of the parent, it returns the minimum of the valuations of the arguments. This is consistent with PARI.

I don't understand what that specification means. Valuation has two arguments, namely self and arg resp. p. So, if the argument (p?) is an element of the base ring of "the parent" (the parent of self?) then it returns the minimum of the valuations of the arguments (i.e., of self and of p --- but with respect to what shall the valuation of self be taken? And what do you do if the base ring of the parent does not support a valuation, so that the valuation of p is not defined?).
I am sure you mean something else, but this is what I understood from your specification.

There was a typo: I meant "it returns the minimum of the valuations of the coefficients." So it means that if self is a polynomial over a ring R and p is an element of R, self.valuation(p) computes for each coefficient of self its valuation with respect to p and returns the minimum of these values. This is very convenient when working over QQ['x']['y'] and asking the valuation with respect to 'x', or even over ZZ['x'] and asking for the valuation with respect to any prime number.

Of course, this implies that the base ring must have a method valuation. The ticket is rather old so I don't have everything fresh in my memory, but do we have examples of rings that do not have such a method?

[roed314]

Changed branch from u/bruno/t19172_valuation to u/roed/t19172_valuation

[tscrim]

Changed commit from 3318489 to fddb76a

[tscrim]

comment:19

If you wanted to do some micro-optimizations, you can do:

               raise NotImplementedError
 
+       P = parent(p) # the function from sage.structure.element is faster
+
-       if is_FractionField(p.parent()):
+       if is_FractionField(P):
             if p.denominator().is_unit():
                 p = p.numerator()
+                P = parent(p)
             else:
                 raise TypeError("The denominator should be a unit.")
 
-        if self.base_ring().has_coerce_map_from(p.parent()):
-            return min(c.valuation(p) for c in self.coefficients())
+        if self._parent._base.has_coerce_map_from(P):
+            return min(self.get_unsafe(k).valuation(p)
+                       for k in range(self.degree()+1)
+                       if self.get_unsafe(k))
 
-        elif self.parent().has_coerce_map_from(p.parent()):
-            p = self.parent().coerce(p)
+        elif self._parent.has_coerce_map_from(P):
+            p = self._parent.coerce(p)
             k = 0
             while p.divides(self):
                 k += 1
-                self = self.__floordiv__(p)
+                self = self._floordiv_(p)  # Same parent

---

New commits:

9e7c501	Merge branch 'u/bruno/t19172_valuation' of git://trac.sagemath.org/sage into t/19172/valuation
fddb76a	Add a few more tests, fix plugin errors

[sagetrac-git]

Changed commit from fddb76a to aa040dc

[sagetrac-git]

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

aa040dc

Incorporate Travis' suggestions

[videlec]

comment:21

What is intended for the corner cases

sage: ZZ['x'].gen().valuation(1)
sage: ZZ['x'].zero().valuation(0)
sage: ZZ['x'].zero().valuation(1)

(the code is not careful enough: min of empty sequence or infinite loop)

The above must appear in doctests.

[videlec]

comment:22

The following if arg not in self.parent() is not a good idea as the method __contains__ is not supposed to be useful in any meaningful way. You could replace the whole block

        if arg not in self.parent():
            if self.parent().has_coerce_map_from(arg.parent()):
                arg = self.parent()(arg)
            else:
                raise TypeError("The parent of the polynomial {} is not {}".format(arg,self.parent()))

by the one line

arg = self.parent().coerce(arg)

[videlec]

comment:23

Similarly, if arg in self.base_ring(): is not good

sage: QQ.one() in ZZ
True

[videlec]

comment:24

For multivariate polynomials why not use the simpler template

if arg is None:
   ...

arg = parent.coerce(arg)
if arg.is_zero():
    ...
elif self.is_zero():
    ...
elif arg.is_constant():
    ...
elif arg.is_generator():
    ...
# etc