Polynomial roots cannot be calculated over a ring of Laurent polynomials #26421

soehms · 2018-10-06T07:01:49Z

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

The method ideal of the class LaurentPolynomialRing_generic raises the wrong error, since it doesn't have the right number of arguments.
The correct NotImplementedError would not be caught.
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)
Just aesthetically: The deprecation of the method content (fix content of polynomials #16613) has not been implemented properly (the warning can't be avoided by the user).

CC: @tscrim

Component: algebra

Keywords: roots, factor, integral domain, Laurent polynomial

Author: Sebastian Oehms

Branch: 196f1ce

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/26421

The text was updated successfully, but these errors were encountered:

soehms · 2018-10-06T07:28:39Z

Branch: u/soehms/poly_roots_laurent-26421

soehms · 2018-10-06T07:33:37Z

Commit: 556a7ea

soehms · 2018-10-06T07:33:37Z

comment:2

I do the following:

Correct the argument list of ideal.
Catch NotImplementedError on invocation from the method roots via content_ideal and inserted the use of lcm in case of exception
Implement the factorization over proper integral domains via the field of fraction in former cases of NotImplementedError.
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:

`556a7ea`	`initial version`

tscrim · 2018-10-06T07:48:01Z

comment:3

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.

soehms · 2018-10-06T19:04:12Z

comment:4

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:

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

tscrim · 2018-10-06T23:45:08Z

comment:5

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:

#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

soehms · 2018-10-07T09:42:18Z

comment:6

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.

tscrim · 2018-10-07T10:35:16Z

comment:7

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.

sagetrac-git · 2018-10-07T21:42:13Z

Changed commit from 556a7ea to d1a04f7

sagetrac-git · 2018-10-07T21:42:13Z

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

`d1a04f7`	`FractionField_generic(R) -> R.fraction_field() and minor corrections`

soehms · 2018-10-07T21:43:31Z

comment:9

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

tscrim · 2020-01-28T00:10:39Z

comment:10

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

sagetrac-git · 2020-01-28T20:22:33Z

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

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

sagetrac-git · 2020-01-28T20:22:33Z

Changed commit from d1a04f7 to 9951556

soehms · 2020-01-28T20:28:05Z

comment:12

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!

sagetrac-git · 2020-01-28T21:29:03Z

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

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

sagetrac-git · 2020-01-28T21:29:03Z

Changed commit from 9951556 to 196f1ce

tscrim · 2020-01-29T05:09:49Z

Reviewer: Travis Scrimshaw

tscrim · 2020-01-29T05:09:49Z

comment:14

Thank you. LGTM now.

soehms · 2020-01-29T10:41:10Z

comment:15

Thanks!

vbraun · 2020-01-31T23:49:51Z

Changed branch from u/soehms/poly_roots_laurent-26421 to 196f1ce

soehms · 2020-03-01T20:33:34Z

Changed commit from 196f1ce to none

soehms · 2020-03-01T20:33:34Z

comment:17

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

soehms added this to the sage-8.4 milestone Oct 6, 2018

soehms added p: major / 3 labels Oct 6, 2018

soehms added the s: needs review label Oct 6, 2018

tscrim added the c: algebra label Oct 6, 2018

soehms added s: needs work and removed s: needs review labels Oct 7, 2018

soehms added s: needs review and removed s: needs work labels Oct 7, 2018

tscrim modified the milestones: sage-8.4, sage-9.1 Jan 29, 2020

tscrim added s: positive review and removed s: needs review labels Jan 29, 2020

vbraun removed the s: positive review label Jan 31, 2020

vbraun closed this as completed in 7940111 Jan 31, 2020

This was referenced Mar 1, 2020

More polynomials should know that they are irreducible #25227

Open

Bugfix concerning ticket #26421 #29266

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Polynomial roots cannot be calculated over a ring of Laurent polynomials #26421

Polynomial roots cannot be calculated over a ring of Laurent polynomials #26421

soehms commented Oct 6, 2018

soehms commented Oct 6, 2018

soehms commented Oct 6, 2018

soehms commented Oct 6, 2018

tscrim commented Oct 6, 2018

soehms commented Oct 6, 2018

tscrim commented Oct 6, 2018

soehms commented Oct 7, 2018

tscrim commented Oct 7, 2018

sagetrac-git mannequin commented Oct 7, 2018

sagetrac-git mannequin commented Oct 7, 2018

soehms commented Oct 7, 2018

tscrim commented Jan 28, 2020

sagetrac-git mannequin commented Jan 28, 2020

sagetrac-git mannequin commented Jan 28, 2020

soehms commented Jan 28, 2020

sagetrac-git mannequin commented Jan 28, 2020

sagetrac-git mannequin commented Jan 28, 2020

tscrim commented Jan 29, 2020

tscrim commented Jan 29, 2020

soehms commented Jan 29, 2020

vbraun commented Jan 31, 2020

soehms commented Mar 1, 2020

soehms commented Mar 1, 2020

Polynomial roots cannot be calculated over a ring of Laurent polynomials #26421

Polynomial roots cannot be calculated over a ring of Laurent polynomials #26421

Comments

soehms commented Oct 6, 2018

soehms commented Oct 6, 2018

soehms commented Oct 6, 2018

soehms commented Oct 6, 2018

tscrim commented Oct 6, 2018

soehms commented Oct 6, 2018

tscrim commented Oct 6, 2018

soehms commented Oct 7, 2018

tscrim commented Oct 7, 2018

sagetrac-git mannequin commented Oct 7, 2018

sagetrac-git mannequin commented Oct 7, 2018

soehms commented Oct 7, 2018

tscrim commented Jan 28, 2020

sagetrac-git mannequin commented Jan 28, 2020

sagetrac-git mannequin commented Jan 28, 2020

soehms commented Jan 28, 2020

sagetrac-git mannequin commented Jan 28, 2020

sagetrac-git mannequin commented Jan 28, 2020

tscrim commented Jan 29, 2020

tscrim commented Jan 29, 2020

soehms commented Jan 29, 2020

vbraun commented Jan 31, 2020

soehms commented Mar 1, 2020

soehms commented Mar 1, 2020