Opened 4 years ago
Last modified 21 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:  
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:
 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.
 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
 Branch set to u/bruno/t19172_valuation
comment:2 Changed 3 years ago by
 Commit set to 992ee7afc702ca261d25706efb103db27518483d
comment:3 Changed 21 months 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 21 months ago by
 Status changed from new to needs_review
comment:5 Changed 21 months ago by
 Keywords polynomial added
 Milestone changed from sage6.9 to sage8.1
comment:6 Changed 21 months 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 21 months 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.
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