Polynomial roots cannot be calculated over a ring of Laurent polynomials

[Sebastian Oehms]

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

[Sebastian Oehms]

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:

​556a7ea

initial version

[Travis Scrimshaw]

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.

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

[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

[Sebastian Oehms]

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.

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

[git]

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

​d1a04f7

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

[Sebastian Oehms]

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

[Travis Scrimshaw]

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

[git]

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

[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!

[git]

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

[Travis Scrimshaw]

Thank you. LGTM now.

[Sebastian Oehms]

Thanks!

[Sebastian Oehms]

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