Better normalization for fraction field elements #16268

JohnCremona · 2014-04-29T15:00:38Z

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

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

sagetrac-emassop · 2014-04-29T16:29:25Z

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 · 2014-04-30T08:03:56Z

Branch: u/robertwb/ticket/16268

sagetrac-git · 2014-04-30T08:11:44Z

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 · 2014-04-30T08:11:44Z

Commit: 289d3aa

sagetrac-git · 2014-04-30T08:14:14Z

Changed commit from 289d3aa to f7266ca

sagetrac-git · 2014-04-30T08:14:14Z

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 · 2014-04-30T08:15:14Z

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 · 2014-04-30T08:15:35Z

Author: Robert Bradshaw

sagetrac-emassop · 2014-04-30T12:42:35Z

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 · 2014-05-02T13:58:34Z

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

JohnCremona · 2014-05-02T14:15:02Z

Changed commit from f7266ca to cdf1163

JohnCremona · 2014-05-02T14:15:02Z

comment:9

What is happening here? There are/were two commits by Robert Bradshaw but suddenly the branch name has changed to an emassop name. I assume that this means the emassop is doing something, so I will hold back.

New commits:

`cdf1163`	`Fix documentation of normalize`

sagetrac-emassop · 2014-05-02T15:27:30Z

comment:10

I changed the documentation to not say "return". Then did git trac push, but apparently something went wrong, since it only changed the branch name without picking up on the new commithash (and hence the summary of my commit). I was hoping trac-user "git" would pick it up with some delay, but apparently not.

I'm not going to change more, as I'm unfamiliar with the conventions about what normalize in FractionFieldElement should do when its not actually guaranteeing that numerator and denominator are the same for a == b after calling normalize on both.

sagetrac-git · 2014-05-04T18:32:11Z

Changed commit from cdf1163 to a4221ed

sagetrac-git · 2014-05-04T18:32:11Z

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

`9387fe2`	`Fix doctest`
`a4221ed`	`More careful hashing of FractionFieldElement`

sagetrac-emassop · 2014-05-04T19:11:30Z

comment:12

I couldn't help myself and hacked a bit on this.

Removed normalize from generic FractionFieldElement, as I don't think it can live up to the behaviour in its documentation. For instance (2x)/(2x+1) and (-2x)/(-2x-1) in Q(ZZ[x]) did not have the same normalisation. I doubt this can be fixed for general rings.
Removed call to reduce for non-exact rings, as reduces' documentation says "Automatically called for exact rings, but because it may be numerically unstable for inexact rings it must be called manually in that case."
Raise NotImplementedError in generic FractionFieldElement.__hash__ except when the denominator is 1. In this exceptional case the hash necessarily agrees with the hash of the corresponding element of the integral domain and therefore can be computed without any trouble.

I (re)implemented hashing for elements of Q(R[X]) with R an integral domain, by passing from Q(R[X]) to Q(Q(R)[X]), reducing to the case of this bug. I haven't pushed this, as I don't like the architecture in my patch and that should probably be a separate bug anyway. There should probably be separate bug reports for many kinds of rings.

rwst · 2014-05-10T09:51:55Z

comment:14

patchbot:

sage -t --long src/sage/tests/book_schilling_zabrocki_kschur_primer.py  # 28 doctests failed
sage -t --long src/sage/combinat/sf/macdonald.py  # 8 doctests failed
sage -t --long src/sage/algebras/iwahori_hecke_algebra.py  # 1 doctest failed
sage -t --long src/sage/combinat/sf/sfa.py  # 8 doctests failed
sage -t --long src/sage/combinat/k_tableau.py  # 2 doctests failed
sage -t --long src/sage/schemes/projective/projective_morphism.py  # 1 doctest failed
sage -t --long src/sage/matrix/matrix2.pyx  # 6 doctests failed
sage -t --long src/sage/combinat/sf/k_dual.py  # 52 doctests failed
sage -t --long src/sage/rings/function_field/function_field.py  # 32 doctests failed
sage -t --long src/sage/combinat/sf/llt.py  # 49 doctests failed
sage -t --long src/sage/schemes/elliptic_curves/ell_point.py  # 8 doctests failed
sage -t --long src/sage/combinat/sf/new_kschur.py  # 10 doctests failed
sage -t --long src/sage/combinat/sf/jack.py  # 72 doctests failed
sage -t --long src/sage/rings/polynomial/multi_polynomial_ideal.py  # Killed due to terminate
sage -t --long src/sage/combinat/sf/sf.py  # 15 doctests failed
sage -t --long src/sage/combinat/sf/hall_littlewood.py  # 39 doctests failed
sage -t --long src/sage/modules/free_module_element.pyx  # 4 doctests failed
sage -t --long src/sage/modules/free_module.py  # 2 doctests failed
sage -t --long src/sage/combinat/cluster_algebra_quiver/cluster_seed.py  # 32 doctests failed
sage -t --long src/sage/schemes/toric/ideal.py  # 1 doctest failed
sage -t --long src/sage/categories/pushout.py  # 2 doctests failed
sage -t --long src/sage/categories/quotient_fields.py  # 3 doctests failed
sage -t --long src/sage/matrix/strassen.pyx  # 2 doctests failed
sage -t --long src/sage/calculus/wester.py  # 1 doctest failed
sage -t --long src/sage/algebras/quatalg/quaternion_algebra_element.pyx  # 6 doctests failed
sage -t --long src/sage/schemes/plane_conics/con_field.py  # 5 doctests failed
sage -t --long src/sage/combinat/free_module.py  # 2 doctests failed
sage -t --long src/sage/combinat/species/recursive_species.py  # 1 doctest failed
sage -t --long src/sage/rings/function_field/function_field_ideal.py  # 18 doctests failed
sage -t --long src/sage/combinat/sf/dual.py  # 4 doctests failed
sage -t --long src/sage/rings/function_field/function_field_order.py  # 6 doctests failed
sage -t --long src/sage/combinat/species/product_species.py  # 1 doctest failed
sage -t --long src/sage/combinat/species/species.py  # 2 doctests failed
sage -t --long src/sage/modules/matrix_morphism.py  # 1 doctest failed
sage -t --long src/sage/rings/function_field/function_field_element.pyx  # 10 doctests failed
sage -t --long src/sage/modules/free_quadratic_module.py  # 1 doctest failed
sage -t --long src/sage/rings/polynomial/polynomial_element_generic.py  # 1 doctest failed
sage -t --long src/sage/rings/fraction_field_element.pyx  # 3 doctests failed
sage -t --long src/sage/matrix/tests.py  # 2 doctests failed
sage -t --long src/sage/categories/function_fields.py  # 1 doctest failed
sage -t --long src/sage/combinat/species/sum_species.py  # 1 doctest failed
sage -t --long src/sage/rings/function_field/constructor.py  # 2 doctests failed

sagetrac-emassop · 2014-06-09T19:36:35Z

comment:15

#15297 is related

sagetrac-emassop · 2014-09-16T14:18:56Z

comment:17

#16993 is related.

saraedum · 2018-07-03T15:34:21Z

Reviewer: Julian Rüth

mezzarobba · 2018-07-03T16:40:02Z

comment:59

Thank you!

vbraun · 2018-08-09T21:32:25Z

comment:60

Merge conflict

mezzarobba · 2018-08-14T13:56:05Z

comment:61

Replying to @vbraun:

Merge conflict

Should be fixed. Back to needs_review mainly for the patchbot; there shouldn't be any nontrivial changes to review.

sagetrac-git · 2018-08-14T14:07:38Z

Changed commit from db762fc to af91bf5

sagetrac-git · 2018-08-14T14:07:38Z

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

`fda2c7d`	`Adding documentation and fixing minor issues`
`dc2df56`	`Merge branch 't/21994/quo_rem_revision' into t/23218/ramified_extensions_of_general_p_adic_rings_and_fields`
`e7a5b08`	`Reduce further after remove`
`e639fae`	`Add keyword reduce_relative in cremove`
`bbdbbdc`	`Merge branch 'u/caruso/ramified_extensions_of_general_p_adic_rings_and_fields' of git://trac.sagemath.org/sage into t/23218/ramified_extensions_of_general_p_adic_rings_and_fields`
`319f6d4`	`Remove the debugging method _unit`
`88f8bbf`	`Merge branch 'u/caruso/ramified_extensions_of_general_p_adic_rings_and_fields' of git://trac.sagemath.org/sage into t/23218/ramified_extensions_of_general_p_adic_rings_and_fields`
`109ded9`	`Merge branch 't/23218/ramified_extensions_of_general_p_adic_rings_and_fields' into t/24843/padic_prints`
`a736db8`	`Fixing doctests due to changes in polynomial printing`
`af91bf5`	`Merge '/u/roed/padic_prints' into fractions_normalize`

vbraun · 2018-08-25T11:01:33Z

Changed branch from u/mmezzarobba/16268-normalize_fractions to af91bf5

mkoeppe · 2018-09-14T04:35:34Z

Changed commit from af91bf5 to none

mkoeppe · 2018-09-14T04:35:34Z

comment:65

#16993 should probably be closed as a dup of this ticket.

Also, should there be a follow-up ticket for the desirable further improvements mentioned in the ticket description?

mezzarobba · 2018-09-22T14:41:37Z

comment:66

Replying to @mkoeppe:

#16993 should probably be closed as a dup of this ticket.

Yes, thanks, I had forgotten to do that.

Also, should there be a follow-up ticket for the desirable further improvements mentioned in the ticket description?

Please go ahead if you want to open additional tickets and/or work on these improvements. (I have little time to work on them myself at the moment, unfortunately, but feel free to ping me if some follow-up ticket needs review.)

mkoeppe · 2018-09-22T19:18:34Z

comment:67

Follow-up ticket at #26339

slel · 2018-12-28T09:25:44Z

Merged: sage-8.4.beta2

JohnCremona added this to the sage-6.2 milestone Apr 29, 2014

JohnCremona added c: algebra labels Apr 29, 2014

robertwb added the s: needs review label Apr 30, 2014

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.2, sage-6.3 May 6, 2014

rwst added s: needs work and removed s: needs review labels May 10, 2014

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.3, sage-6.4 Aug 10, 2014

mezzarobba added s: positive review and removed s: needs review labels Jul 3, 2018

vbraun added s: needs work and removed s: positive review labels Aug 9, 2018

mezzarobba added s: needs review and removed s: needs work labels Aug 14, 2018

mezzarobba added s: positive review and removed s: needs review labels Aug 15, 2018

vbraun removed the s: positive review label Aug 25, 2018

vbraun closed this as completed in f60348f Aug 25, 2018

This comment has been minimized.

Sign in to view

slel modified the milestones: sage-8.3, sage-8.4 Dec 28, 2018

simon-king-jena mentioned this issue Feb 26, 2019

Broken fraction field of rational polynomial ring #16993

Closed

mezzarobba mentioned this issue Jan 29, 2023

Improve basic operations with fraction field elements #25318

Open

mkoeppe mentioned this issue Jan 29, 2023

Better normalization for fraction field elements - follow up #26339

Open

mezzarobba mentioned this issue Mar 15, 2023

A computation straightforward in Mathematica and almost impossible in sage #35221

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Better normalization for fraction field elements #16268

Better normalization for fraction field elements #16268

JohnCremona commented Apr 29, 2014

sagetrac-emassop mannequin commented Apr 29, 2014

robertwb commented Apr 30, 2014

sagetrac-git mannequin commented Apr 30, 2014

sagetrac-git mannequin commented Apr 30, 2014

sagetrac-git mannequin commented Apr 30, 2014

sagetrac-git mannequin commented Apr 30, 2014

JohnCremona commented Apr 30, 2014

robertwb commented Apr 30, 2014

sagetrac-emassop mannequin commented Apr 30, 2014

sagetrac-emassop mannequin commented May 2, 2014

JohnCremona commented May 2, 2014

JohnCremona commented May 2, 2014

sagetrac-emassop mannequin commented May 2, 2014

sagetrac-git mannequin commented May 4, 2014

sagetrac-git mannequin commented May 4, 2014

sagetrac-emassop mannequin commented May 4, 2014

rwst commented May 10, 2014

sagetrac-emassop mannequin commented Jun 9, 2014

sagetrac-emassop mannequin commented Sep 16, 2014

saraedum commented Jul 3, 2018

mezzarobba commented Jul 3, 2018

vbraun commented Aug 9, 2018

mezzarobba commented Aug 14, 2018

sagetrac-git mannequin commented Aug 14, 2018

sagetrac-git mannequin commented Aug 14, 2018

vbraun commented Aug 25, 2018

mkoeppe commented Sep 14, 2018

mkoeppe commented Sep 14, 2018

This comment has been minimized.

mezzarobba commented Sep 22, 2018

mkoeppe commented Sep 22, 2018

This comment has been minimized.

slel commented Dec 28, 2018

Better normalization for fraction field elements #16268

Better normalization for fraction field elements #16268

Comments

JohnCremona commented Apr 29, 2014

sagetrac-emassop mannequin commented Apr 29, 2014

robertwb commented Apr 30, 2014

sagetrac-git mannequin commented Apr 30, 2014

sagetrac-git mannequin commented Apr 30, 2014

sagetrac-git mannequin commented Apr 30, 2014

sagetrac-git mannequin commented Apr 30, 2014

JohnCremona commented Apr 30, 2014

robertwb commented Apr 30, 2014

sagetrac-emassop mannequin commented Apr 30, 2014

sagetrac-emassop mannequin commented May 2, 2014

JohnCremona commented May 2, 2014

JohnCremona commented May 2, 2014

sagetrac-emassop mannequin commented May 2, 2014

sagetrac-git mannequin commented May 4, 2014

sagetrac-git mannequin commented May 4, 2014

sagetrac-emassop mannequin commented May 4, 2014

rwst commented May 10, 2014

sagetrac-emassop mannequin commented Jun 9, 2014

sagetrac-emassop mannequin commented Sep 16, 2014

saraedum commented Jul 3, 2018

mezzarobba commented Jul 3, 2018

vbraun commented Aug 9, 2018

mezzarobba commented Aug 14, 2018

sagetrac-git mannequin commented Aug 14, 2018

sagetrac-git mannequin commented Aug 14, 2018

vbraun commented Aug 25, 2018

mkoeppe commented Sep 14, 2018

mkoeppe commented Sep 14, 2018

This comment has been minimized.

mezzarobba commented Sep 22, 2018

mkoeppe commented Sep 22, 2018

This comment has been minimized.

slel commented Dec 28, 2018