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:  sage8.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: 
Description (last modified by )
This ticket aims at improving the method valuation
for polynomials in two ways:
 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.
 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
 Branch set to u/bruno/t19172_valuation
comment:2 Changed 5 years ago by
 Commit set to 992ee7afc702ca261d25706efb103db27518483d
comment:3 Changed 4 years ago by
 Commit changed from 992ee7afc702ca261d25706efb103db27518483d to 9a548adcf9a998a78254ba98df730b1311e9d559
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

comment:4 Changed 4 years ago by
 Status changed from new to needs_review
comment:5 Changed 4 years ago by
 Keywords polynomial added
 Milestone changed from sage6.9 to sage8.1
comment:6 Changed 4 years ago by
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
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
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
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
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.
comment:11 Changed 21 months ago by
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
What I am trying now is whether the suspicious commit is needed at all.
comment:13 Changed 21 months ago by
 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
 Commit changed from 9a548adcf9a998a78254ba98df730b1311e9d559 to 331848976b65c64ca362aca5babcb18e24db9dd9
comment:15 Changed 20 months ago by
 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 ; followup: ↓ 17 Changed 20 months ago by
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
 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
andarg
resp.p
. So, if the argument (p
?) is an element of the base ring of "the parent" (the parent ofself
?) then it returns the minimum of the valuations of the arguments (i.e., ofself
and ofp
 but with respect to what shall the valuation ofself
be taken? And what do you do if the base ring of the parent does not support a valuation, so that the valuation ofp
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?
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
#19171: New method divides
#19172: Improve valuation for dense polynomials
#19172: Improve valuation for sparse polynomials
#19172: Add valuation for multipolynomials