#26421 closed defect (fixed)
Polynomial roots cannot be calculated over a ring of Laurent polynomials
Reported by:  Sebastian Oehms  Owned by:  

Priority:  major  Milestone:  sage9.1 
Component:  algebra  Keywords:  roots, factor, integral domain, Laurent polynomial 
Cc:  Travis Scrimshaw  Merged in:  
Authors:  Sebastian Oehms  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  196f1ce (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description
... even if the polynomial is linear or the roots are integers:
sage: R.<t> = LaurentPolynomialRing(ZZ) sage: P.<x> = PolynomialRing(R) sage: p = xt sage: p.roots() /home/sebastian/develop/sage/src/bin/sageipython:1: DeprecationWarning: content is deprecated. Please use content_ideal instead. See http://trac.sagemath.org/16613 for details. #!/usr/bin/env sagepython23  Traceback (most recent call last): ... TypeError: ideal() takes exactly 1 argument (2 given)
The calculation aborts, since the method ideal
of the class LaurentPolynomialRing_generic
is not implemented but invoked via content_ideal
which could be avoided or replaced by the function lcm
.
But there are further problems:
1) The method ideal
of the class LaurentPolynomialRing_generic
raises the wrong error, since it doesn't have the right number of arguments.
2) The correct NotImplementedError
would not be caught.
3) Factorization over some cases of integral domains is not implemented in the method factor
of the class Polynomial
(even though it should be possible using the field of fractions)
4) Just aesthetically: The deprecation of the method content
(#16613) has not been implemented properly (the warning can't be avoided by the user).
Change History (17)
comment:1 Changed 4 years ago by
Branch:  → u/soehms/poly_roots_laurent26421 

comment:2 followup: 3 Changed 4 years ago by
Commit:  → 556a7ea3b924072cccd8980657aa1a932a1798b0 

Status:  new → needs_review 
comment:3 followup: 4 Changed 4 years ago by
Component:  PLEASE CHANGE → algebra 

Replying to soehms:
The reason why I use
FractionField_generic
instead ofFractionField
in 3) is because the methodfraction_field
of the classLaurentPolynomialRing_generic
returns the fraction field of the corresponding polynomial ring instead of the fraction field of itself (which would be the default from the classCommutativeRing
). This causes coercion problems inbase_change
of the classFactorization
.
I am not sure about doing that. The reason has to do with units and normalization of fractions. Since x
is a unit, then implicitly 1/x
is different from (1/x)/1
. Also, what about classes that have a custom fraction_field
implementation? It feels like the wrong thing to do.
Some other quick comments:
 Please correct
:trac:`26421'
>:trac:`26421`
and check that trac:`26421` is fixed: + Check that :trac:`26421` is fixed::
 Do not have bare
except:
statements. List which errors you want to catch explicitly.
comment:4 followup: 5 Changed 4 years ago by
Replying to tscrim:
Thank you for your hints, Travis!
Replying to soehms:
The reason why I use
FractionField_generic
instead ofFractionField
in 3) is because ...I am not sure about doing that. The reason has to do with units and normalization of fractions. Since
x
is a unit, then implicitly1/x
is different from(1/x)/1
.
I really don't understand the argument, why the field of fraction over the corresponding polynomial ring is preferred. Even not after reading the original discussion about that:
https://trac.sagemath.org/ticket/15345#comment:13
Without the fraction_field
method in the Laurent polynomial class the following doctests change (like they have been resulting originally).
File "src/sage/rings/polynomial/polynomial_element.pyx", line 4184, in sage.rings.polynomial.polynomial_element.Polynomial.factor Failed example: factor(x^2  q^2) Expected: (x  q) * (x + q) Got: (1) * (x + q) * (x + q) ********************************************************************** File "src/sage/rings/polynomial/polynomial_element.pyx", line 4186, in sage.rings.polynomial.polynomial_element.Polynomial.factor Failed example: factor(x^2  q^2) Expected: (x  1/q) * (x + 1/q) Got: (q^2) * (q*x  1) * (q*x + 1)
Does this give a hint to the reason? Why is the current version of that doctests preferable?
Also, what about classes that have a custom
fraction_field
implementation? It feels like the wrong thing to do.
I agree! But how can I get the coercion work for the Laurent polynomial case?
sage: R.<t> = LaurentPolynomialRing(ZZ) sage: F = R.fraction_field() sage: ti = F(1/t) sage: R(ti) Traceback (most recent call last): ... TypeError: fraction must have unit denominator
 Do not have bare
except:
statements. List which errors you want to catch explicitly.
The bare except
in the factor
method I use because I don't want to change the previous behavior to much (which is a NotImplementedError
). So a change should only be in the case of success. I can change the pass
to an explicit raise
command, to make this clear.
The other occurrence in the roots
method I will erase, since a second try with lcm
(which should have been gcd
) doesn't make much sense.
comment:5 Changed 4 years ago by
Replying to soehms:
Replying to tscrim:
Replying to soehms:
The reason why I use
FractionField_generic
instead ofFractionField
in 3) is because ...I am not sure about doing that. The reason has to do with units and normalization of fractions. Since
x
is a unit, then implicitly1/x
is different from(1/x)/1
.I really don't understand the argument, why the field of fraction over the corresponding polynomial ring is preferred. Even not after reading the original discussion about that:
https://trac.sagemath.org/ticket/15345#comment:13
Without the
fraction_field
method in the Laurent polynomial class the following doctests change (like they have been resulting originally).File "src/sage/rings/polynomial/polynomial_element.pyx", line 4184, in sage.rings.polynomial.polynomial_element.Polynomial.factor Failed example: factor(x^2  q^2) Expected: (x  q) * (x + q) Got: (1) * (x + q) * (x + q) ********************************************************************** File "src/sage/rings/polynomial/polynomial_element.pyx", line 4186, in sage.rings.polynomial.polynomial_element.Polynomial.factor Failed example: factor(x^2  q^2) Expected: (x  1/q) * (x + 1/q) Got: (q^2) * (q*x  1) * (q*x + 1)Does this give a hint to the reason? Why is the current version of that doctests preferable?
Perhaps think about it this way, would you write x/1
or x
? Basically, you do not want units in the denominator, you would rather normalize that to 1
. So that is why I would say the current behavior is better in the latter example. I believe in terms of commutative algebra, the usual polynomial ring has a better category than Laurent polynomials, but I am not 100% sure of that aspect.
Something else that was going wrong was going between the two "different" fraction fields: the one for polynomials and for Laurent polynomials (see comment 3 on #15345). It makes things much easier when R[x]
and R[x,x^1]
both go to R(x)
.
Also, what about classes that have a custom
fraction_field
implementation? It feels like the wrong thing to do.I agree! But how can I get the coercion work for the Laurent polynomial case?
sage: R.<t> = LaurentPolynomialRing(ZZ) sage: F = R.fraction_field() sage: ti = F(1/t) sage: R(ti) Traceback (most recent call last): ... TypeError: fraction must have unit denominator
I would say that is a bug in the conversion of the Laurent polynomial ring (and deserves a separate ticket). It seems like it is not converting the denominator to self
before seeing if it a unit.
 Do not have bare
except:
statements. List which errors you want to catch explicitly.The bare
except
in thefactor
method I use because I don't want to change the previous behavior to much (which is aNotImplementedError
). So a change should only be in the case of success. I can change thepass
to an explicitraise
command, to make this clear.
By having a bare expect:
you are catching everything. Catch what you expect to be thrown as catching everything can further hide bugs. If you need to continue to propagate up an error, call raise
. You can also have different behaviors for different exceptions, e.g.,:
try: foo except ValueError: pass except TypeError: raise
comment:6 followup: 7 Changed 4 years ago by
Status:  needs_review → needs_work 

I still don't understand the change of the FractionField
in ticket #15345. I understand that we want to avoid units in the denominator. But IMO, this issue is an internal of the FractionField_generic class. Why should this be something special for Laurent polynomial rings (except that it should support some information of what is an normalized representation)? Furthermore, the issue in comment 3 seems not to be reproducible with recent code:
sage: R = LaurentPolynomialRing(ZZ, 'x') sage: T = PolynomialRing(ZZ, 'x') sage: R.gen() + T.gen() 2*x sage: F1 = FractionField(R) sage: import_statements('FractionField_generic') from sage.rings.fraction_field import FractionField_generic sage: from sage.rings.fraction_field import FractionField_generic sage: F2 = FractionField_generic(R) sage: R.gen() + F1.gen() 2*x sage: R.gen() + F2.gen() 2*x sage:
and all tests of ticket #15345 (under sage.rings) passed, when I removed the fraction_field
method from the Laurent polynomial ring. On the other hand, the coercion problem does not occur for the original field of fraction:
sage: R(F2(1/t)) x^1 sage: R(F1(1/t)) Traceback (most recent call last): ... TypeError: fraction must have unit denominator
I have opened ticket #26425 for the coercion problem. Concerning this ticket I will reduce the coefficients of my example to polynomials in t, such that they will work for R.fraction_field()
as well.
comment:7 Changed 4 years ago by
Replying to soehms:
I still don't understand the change of the
FractionField
in ticket #15345. I understand that we want to avoid units in the denominator. But IMO, this issue is an internal of the FractionField_generic class.
No, it is not. The field of fractions of Laurent polynomials means you have things like (1/x)/1
. Mathematically, this is not really an issue, but for a computer trying to sort things out consistently (e.g., for hashing and equality), it is more subtle. See below.
Why should this be something special for Laurent polynomial rings (except that it should support some information of what is an normalized representation)?
It is because it has a relatively large set of units and it does not work as well wrt things like the Euclidean algorithm IIRC. This is what leads to the issues with normalizations.
Furthermore, the issue in comment 3 seems not to be reproducible with recent code:
sage: R = LaurentPolynomialRing(ZZ, 'x') sage: T = PolynomialRing(ZZ, 'x') sage: R.gen() + T.gen() 2*x sage: F1 = FractionField(R) sage: from sage.rings.fraction_field import FractionField_generic sage: F2 = FractionField_generic(R) sage: R.gen() + F1.gen() 2*x sage: R.gen() + F2.gen() 2*x
That is good, it means the coercion framework has independently gotten more robust. However, the last part bit of this example shows the problem:
sage: p = (1/F2.gen()) / (2 + F2.gen()) sage: q = 1/(2*F2.gen() + F2.gen()^2) sage: q 1/(2*x + x^2) sage: p == q True sage: hash(p) == hash(q) False
Equal objects should have equal hashes (in this case, there is no coercion involved, it definitely should be consistent). This can cause very subtle problems with, e.g., dict
s.
comment:8 Changed 4 years ago by
Commit:  556a7ea3b924072cccd8980657aa1a932a1798b0 → d1a04f75148a23b28ecdd57a4aad4641ae38db4e 

Branch pushed to git repo; I updated commit sha1. New commits:
d1a04f7  FractionField_generic(R) > R.fraction_field() and minor corrections

comment:9 Changed 4 years ago by
Status:  needs_work → needs_review 

Now, I've got it! Thanks for your patients, Travis!
comment:10 followup: 12 Changed 3 years ago by
Sorry, lost track of this. Can you rebase? I will finish the review after that.
comment:11 Changed 3 years ago by
Commit:  d1a04f75148a23b28ecdd57a4aad4641ae38db4e → 9951556cbe22f832719de81c21ea8a7f5d4da88e 

comment:12 Changed 3 years ago by
comment:13 Changed 3 years ago by
Commit:  9951556cbe22f832719de81c21ea8a7f5d4da88e → 196f1cefcbd247c0419f0e499018406f93025fad 

Branch pushed to git repo; I updated commit sha1. New commits:
196f1ce  Merge branch 'u/soehms/poly_roots_laurent26421' of git://trac.sagemath.org/sage into poly_roots_laurent_26421

comment:14 Changed 3 years ago by
Milestone:  sage8.4 → sage9.1 

Reviewers:  → Travis Scrimshaw 
Status:  needs_review → positive_review 
Thank you. LGTM now.
comment:16 Changed 3 years ago by
Branch:  u/soehms/poly_roots_laurent26421 → 196f1cefcbd247c0419f0e499018406f93025fad 

Resolution:  → fixed 
Status:  positive_review → closed 
comment:17 Changed 3 years ago by
Commit:  196f1cefcbd247c0419f0e499018406f93025fad 

I do the following:
1) Correct the argument list of
ideal
.2) Catch
NotImplementedError
on invocation from the methodroots
viacontent_ideal
and inserted the use oflcm
in case of exception3) Implement the factorization over proper integral domains via the field of fraction in former cases of
NotImplementedError
.4) Correct the deprecated invocations of
content
The reason why I use
FractionField_generic
instead ofFractionField
in 3) is because the methodfraction_field
of the classLaurentPolynomialRing_generic
returns the fraction field of the corresponding polynomial ring instead of the fraction field of itself (which would be the default from the classCommutativeRing
). This causes coercion problems inbase_change
of the classFactorization
.New commits:
initial version