Opened 6 years ago

Last modified 20 months 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: Rebase
Branch: u/bruno/t19172_valuation (Commits, GitHub, GitLab) Commit: 331848976b65c64ca362aca5babcb18e24db9dd9
Dependencies: #19171 Stopgaps:

Status badges

Description (last modified by bruno)

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.

  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 (17)

comment:1 Changed 6 years ago by bruno

  • Branch set to u/bruno/t19172_valuation

comment:2 Changed 5 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 4 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 4 years ago by bruno

  • Status changed from new to needs_review

comment:5 Changed 4 years ago by bruno

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

comment:6 Changed 4 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 4 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.

comment:8 Changed 21 months ago by SimonKing

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

comment:9 Changed 21 months ago by SimonKing

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

comment:10 Changed 21 months ago by SimonKing

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.

Last edited 21 months ago by SimonKing (previous) (diff)

comment:11 Changed 21 months ago by SimonKing

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

comment:12 Changed 21 months ago by SimonKing

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

comment:13 Changed 21 months ago by SimonKing

  • Status changed from needs_review to needs_work
  • Work issues set to Rebase

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.

comment:14 Changed 20 months ago by git

  • Commit changed from 9a548adcf9a998a78254ba98df730b1311e9d559 to 331848976b65c64ca362aca5babcb18e24db9dd9

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

71e424b19172: Improve valuation for dense polynomials
693f22919172: Improve valuation for sparse polynomials
3318489#19172: Add valuation for multipolynomials

comment:15 Changed 20 months ago by bruno

  • Status changed from needs_work to needs_review

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

comment:16 in reply to: ↑ description ; follow-up: Changed 20 months ago by SimonKing

Replying to bruno:

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.

comment:17 in reply to: ↑ 16 Changed 20 months ago by bruno

  • Description modified (diff)

Replying to SimonKing:

Replying to bruno:

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?

Note: See TracTickets for help on using tickets.