Opened 4 years ago

Last modified 2 years ago

#19172 needs_review enhancement

More capable method `valuation` for polynomials

Reported by: bruno Owned by:
Priority: major Milestone: sage-8.1
Component: commutative algebra Keywords: polynomial
Cc: Merged in:
Authors: Bruno Grenet Reviewers:
Report Upstream: N/A Work issues:
Branch: u/bruno/t19172_valuation (Commits) Commit: 9a548adcf9a998a78254ba98df730b1311e9d559
Dependencies: #19171 Stopgaps:

Description

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 arguments. This is consistent with PARI.

  1. 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.

Change History (7)

comment:1 Changed 4 years ago by bruno

  • Branch set to u/bruno/t19172_valuation

comment:2 Changed 3 years ago by git

  • Commit set to 992ee7afc702ca261d25706efb103db27518483d

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

comment:3 Changed 2 years ago by git

  • Commit changed from 992ee7afc702ca261d25706efb103db27518483d to 9a548adcf9a998a78254ba98df730b1311e9d559

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

d03a75e#19171: New method divides
ac43c0219171: Use coerce_binop
0906dfd19171: Add more involved example + move a line
04b0032Merge branch 'develop' into 19171_divides_poly
f85a7e019171: conflict resolution
a0a5badMerge branch 'u/bruno/t19171_divides_poly' of git://trac.sagemath.org/sage into 19171_divides_poly
9a548adMerge branch '19171_divides_poly' into 19172_valuation

comment:4 Changed 2 years ago by bruno

  • Status changed from new to needs_review

comment:5 Changed 2 years ago by bruno

  • Keywords polynomial added
  • Milestone changed from sage-6.9 to sage-8.1

comment:6 Changed 2 years ago by mmezzarobba

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

comment:7 Changed 2 years ago by mmezzarobba

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.

Note: See TracTickets for help on using tickets.