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.