Better normalization for fraction field elements

[JohnCremona]

Normalize the leading coefficient of the denominator to one when reducing elements of fraction fields of univariate polynomial rings over fields. Doing so

• often leads to more readable results,
• helps limiting coefficient blow-up during computations with fractions over complicated base fields (e.g., elements of ℚ(x,y)(t)), typically leading to much better performance,
• makes hashing more (though not 100%) reliable, see the original description and the comments below.

The following further desirable improvements, out of the scope of this ticket, are dealt with at #26339:

• clearing denominators in the numerator and denominator instead of making the leading coefficient of the denominator monic when that makes sense (i.e., for printing, and perhaps for computations in nested rational function fields, but making it fast enough requires some work),
• also normalizing the leading coefficients over non-fields where that makes sense (see also discussion at Broken fraction field of rational polynomial ring #16993).

Original description:

If K is a field then K(u), the function field, has a reduce() method which cancels the gcd but does not put into a canonical form by (for example) dividing through by the leading coefficient of the denominator to make the denominator monic. This means that equal elements may have different hashes, and hence that putting function field elements into a set does not work as a mathematician would expect. For example:

sage: Ku.<u> = FractionField(PolynomialRing(QQ,'u'))
sage: a = 27*u^2+81*u+243
sage: b = 27*u-81
sage: c = u^2 + 3*u + 9
sage: d = u-3
sage: s = a/b
sage: t = c/d
sage: s==t
True
sage: len(Set([s,t]))
2

CC: @tscrim @cheuberg @Etn40ff @sagetrac-jakobkroeker @bhutz @slel

Component: algebra

Author: Robert Bradshaw, Erik Massop, Marc Mezzarobba

Branch: af91bf5

Reviewer: Julian Rüth

Merged: sage-8.4.beta2

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

[sagetrac-emassop]

comment:1

The normalization would already be much better if PolynomialRing(QQ, 'u') had a 'better' gcd, like the one implemented for QQ in #10771, which would yield gcd(27*u^2+81*u+243, 27*u-81)==27. However the gcd from flint in src/sage/rings/polynomial/polynomial_rational_flint.pyx is monic.

Ku could also figure out that it is also FractionField(PolynomialRing(ZZ, 'u')), which has a better reduce.

[robertwb]

Branch: u/robertwb/ticket/16268

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

289d3aa

Fix hash for unreduced fraction field elements.

[sagetrac-git]

Commit: 289d3aa

[sagetrac-git]

Changed commit from 289d3aa to f7266ca

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

f7266ca

Fix hash for unreduced fraction field elements.

[JohnCremona]

comment:5

Thanks, Robert, I will review this. I had already started by patching the reduce function but had not yet discoivered where the automatic calling of reduction was actually happening. Your solution -- keeping reduce() and normalise() separate -- looks better.

[robertwb]

Author: Robert Bradshaw

[sagetrac-emassop]

comment:7

As of yet the documentation at normalize is incorrect. It reads "Returns a normalized representation of self". However it does not return anything.

Also, shouldn't normalize in FractionFieldElement throw a not-implemented-exception or so? Or at least have a warning in its documentation that it might not actually normalize? For instance in FractionField(PolynomialRing(QQ, 'x,y')), calling reduce is still insufficient to do the normalization.

[sagetrac-emassop]

Changed branch from u/robertwb/ticket/16268 to u/emassop/ticket/16268