Opened 4 years ago

Closed 3 years ago

Last modified 3 years ago

#26421 closed defect (fixed)

Polynomial roots cannot be calculated over a ring of Laurent polynomials

Reported by: Sebastian Oehms Owned by:
Priority: major Milestone: sage-9.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:

Status badges

Description

... even if the polynomial is linear or the roots are integers:

sage: R.<t> = LaurentPolynomialRing(ZZ)
sage: P.<x> = PolynomialRing(R)
sage: p = x-t
sage: p.roots()
/home/sebastian/develop/sage/src/bin/sage-ipython:1: DeprecationWarning: content is deprecated. Please use content_ideal instead.
See http://trac.sagemath.org/16613 for details.
  #!/usr/bin/env sage-python23
---------------------------------------------------------------------------
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 Sebastian Oehms

Branch: u/soehms/poly_roots_laurent-26421

comment:2 Changed 4 years ago by Sebastian Oehms

Commit: 556a7ea3b924072cccd8980657aa1a932a1798b0
Status: newneeds_review

I do the following:

1) Correct the argument list of ideal.

2) Catch NotImplementedError on invocation from the method roots via content_ideal and inserted the use of lcm in case of exception

3) 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 of FractionField in 3) is because the method fraction_field of the class LaurentPolynomialRing_generic returns the fraction field of the corresponding polynomial ring instead of the fraction field of itself (which would be the default from the class CommutativeRing). This causes coercion problems in base_change of the class Factorization.


New commits:

556a7eainitial version

comment:3 in reply to:  2 ; Changed 4 years ago by Travis Scrimshaw

Component: PLEASE CHANGEalgebra

Replying to soehms:

The reason why I use FractionField_generic instead of FractionField in 3) is because the method fraction_field of the class LaurentPolynomialRing_generic returns the fraction field of the corresponding polynomial ring instead of the fraction field of itself (which would be the default from the class CommutativeRing). This causes coercion problems in base_change of the class Factorization.

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 in reply to:  3 ; Changed 4 years ago by Sebastian Oehms

Replying to tscrim:

Thank you for your hints, Travis!

Replying to soehms:

The reason why I use FractionField_generic instead of FractionField 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 implicitly 1/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 in reply to:  4 Changed 4 years ago by Travis Scrimshaw

Replying to soehms:

Replying to tscrim:

Replying to soehms:

The reason why I use FractionField_generic instead of FractionField 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 implicitly 1/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 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.

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 Changed 4 years ago by Sebastian Oehms

Status: needs_reviewneeds_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 in reply to:  6 Changed 4 years ago by Travis Scrimshaw

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., dicts.

comment:8 Changed 4 years ago by git

Commit: 556a7ea3b924072cccd8980657aa1a932a1798b0d1a04f75148a23b28ecdd57a4aad4641ae38db4e

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

d1a04f7FractionField_generic(R) -> R.fraction_field() and minor corrections

comment:9 Changed 4 years ago by Sebastian Oehms

Status: needs_workneeds_review

Now, I've got it! Thanks for your patients, Travis!

comment:10 Changed 3 years ago by Travis Scrimshaw

Sorry, lost track of this. Can you rebase? I will finish the review after that.

comment:11 Changed 3 years ago by git

Commit: d1a04f75148a23b28ecdd57a4aad4641ae38db4e9951556cbe22f832719de81c21ea8a7f5d4da88e

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

0facd2fMerge branch 'public/4618' of git://trac.sagemath.org/sage into puiseux_series_4618
9951556Merge branch 'u/soehms/poly_roots_laurent-26421' of git://trac.sagemath.org/sage into poly_roots_laurent_26421

comment:12 in reply to:  10 Changed 3 years ago by Sebastian Oehms

Replying to tscrim:

Sorry, lost track of this.

No problem!

Can you rebase?

I hope that it's no problem that I merged it on top of #4618 which is closed, right now!

I will finish the review after that.

Great!

comment:13 Changed 3 years ago by git

Commit: 9951556cbe22f832719de81c21ea8a7f5d4da88e196f1cefcbd247c0419f0e499018406f93025fad

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

196f1ceMerge branch 'u/soehms/poly_roots_laurent-26421' of git://trac.sagemath.org/sage into poly_roots_laurent_26421

comment:14 Changed 3 years ago by Travis Scrimshaw

Milestone: sage-8.4sage-9.1
Reviewers: Travis Scrimshaw
Status: needs_reviewpositive_review

Thank you. LGTM now.

comment:15 Changed 3 years ago by Sebastian Oehms

Thanks!

comment:16 Changed 3 years ago by Volker Braun

Branch: u/soehms/poly_roots_laurent-26421196f1cefcbd247c0419f0e499018406f93025fad
Resolution: fixed
Status: positive_reviewclosed

comment:17 Changed 3 years ago by Sebastian Oehms

Commit: 196f1cefcbd247c0419f0e499018406f93025fad

While I had a look at ticket #25227 I realized a bug in the above implementation. Therefore, I opened ticket #29266 for a fix!

Last edited 3 years ago by Sebastian Oehms (previous) (diff)
Note: See TracTickets for help on using tickets.