Opened 7 years ago

Closed 3 years ago

# Better normalization for fraction field elements

Reported by: Owned by: cremona minor sage-8.4 algebra tscrim, cheuberg, etn40ff, jakobkroeker, bhutz, slelievre sage-8.4.beta2 Robert Bradshaw, Erik Massop, Marc Mezzarobba Julian Rüth N/A af91bf5

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

### comment:1 Changed 7 years ago by emassop

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.

### comment:2 Changed 7 years ago by robertwb

• Branch set to u/robertwb/ticket/16268
• Created changed from 04/29/14 15:00:38 to 04/29/14 15:00:38
• Modified changed from 04/29/14 16:29:25 to 04/29/14 16:29:25

### comment:3 Changed 7 years ago by git

• Commit set to 289d3aa124bd5a03349f14f0520e4b8d2845dd84

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

 ​289d3aa `Fix hash for unreduced fraction field elements.`

### comment:4 Changed 7 years ago by git

• Commit changed from 289d3aa124bd5a03349f14f0520e4b8d2845dd84 to f7266ca383db2783ba0d485ac5c9ab5da6c6d614

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

 ​f7266ca `Fix hash for unreduced fraction field elements.`

### comment:5 follow-up: ↓ 23 Changed 7 years ago by cremona

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.

### comment:6 Changed 7 years ago by robertwb

• Authors set to Robert Bradshaw
• Status changed from new to needs_review

### comment:7 Changed 7 years ago by emassop

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.

### comment:8 Changed 7 years ago by emassop

• Branch changed from u/robertwb/ticket/16268 to u/emassop/ticket/16268

### comment:9 Changed 7 years ago by cremona

• Commit changed from f7266ca383db2783ba0d485ac5c9ab5da6c6d614 to cdf116327b93b5d29282c98d40042440d068ce44

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`

### comment:10 Changed 7 years ago by emassop

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.

### comment:11 Changed 7 years ago by git

• Commit changed from cdf116327b93b5d29282c98d40042440d068ce44 to a4221ed3e1d16d38b271316b01b91344fb195746

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

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

### comment:12 Changed 7 years ago by emassop

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.

### comment:13 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

### comment:14 Changed 7 years ago by rws

• Status changed from needs_review to needs_work

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
```

### comment:15 Changed 7 years ago by emassop

#15297 is related

### comment:16 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

### comment:17 Changed 7 years ago by emassop

#16993 is related.

### comment:18 Changed 7 years ago by emassop

Also, I sadly don't currently have time to work on this. In fact, I don't think I'll have time until spring.

### comment:19 Changed 7 years ago by tscrim

• Cc tscrim added

### comment:20 Changed 7 years ago by cheuberg

• Cc cheuberg added

### comment:21 Changed 6 years ago by etn40ff

• Cc etn40ff added

### comment:22 Changed 4 years ago by jakobkroeker

• Cc jakobkroeker added

ping

### comment:23 in reply to: ↑ 5 Changed 3 years ago by mmezzarobba

• Authors changed from Robert Bradshaw to Robert Bradshaw, Erik Massop, Marc Mezzarobba
• Branch changed from u/emassop/ticket/16268 to u/mmezzarobba/16268-normalize_fractions
• Commit changed from a4221ed3e1d16d38b271316b01b91344fb195746 to 2d96533bde07fbbbce3a490dd786bbf7a9ffae53
• Status changed from needs_work to needs_review

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.

IMO having `reduce()` normalize the leading coefficient is actually a better choice, because it helps limiting coefficient blow-up in computations with rational functions.

Here is another attempt that does that. See the commit messages for more information. (Addendum: this fixes #16933. Fixing #15297 in full generality requires more work, but could be done as a follow-up.)

New commits:

 ​3d96f14 `Fix hash for unreduced fraction field elements.` ​fb8a382 `Fix documentation of normalize` ​2f7a320 `Fix doctest` ​198c059 `More careful hashing of FractionFieldElement` ​3e4fc0c `slightly simplify/robustify FractionFieldElement.reduce()` ​b418d40 `FractionFieldElement: merge reduce() and normalize()` ​c45d34f `Tweak fraction field element hashing` ​aa73340 `Small optimization in FracFieldElt richcmp()` ​e3a2da4 `#16268 boring doctest updates` ​2d96533 `#16268 other doctest updates`
Version 1, edited 3 years ago by mmezzarobba (previous) (next) (diff)

### comment:24 Changed 3 years ago by git

• Commit changed from 2d96533bde07fbbbce3a490dd786bbf7a9ffae53 to 0830684d5a260960d215d52ed42ef932fa987e9e

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

 ​0830684 `#16268 other doctest updates`

### comment:25 Changed 3 years ago by git

• Commit changed from 0830684d5a260960d215d52ed42ef932fa987e9e to b504f8e593367ae9c955b515965930d750674044

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

 ​39b7ad3 `FractionFieldElement: merge reduce() and normalize()` ​efd5979 `Tweak fraction field element hashing` ​1db6427 `Small optimization in FracFieldElt richcmp()` ​7adce21 `#16268 boring doctest updates` ​b504f8e `#16268 other doctest updates`

### comment:26 follow-up: ↓ 27 Changed 3 years ago by git

• Commit changed from b504f8e593367ae9c955b515965930d750674044 to fb113639b4c3e4ff7de67a8f8edcd67ffb3141c5

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

 ​77dc9e1 `FractionFieldElement: merge reduce() and normalize()` ​a25ab99 `Tweak fraction field element hashing` ​0f310bc `Small optimization in FracFieldElt richcmp()` ​00104f5 `#16268 boring doctest updates` ​fb11363 `#16268 other doctest updates`

### comment:27 in reply to: ↑ 26 Changed 3 years ago by mmezzarobba

 ​77dc9e1 `FractionFieldElement: merge reduce() and normalize()`

Replaced a nbsp by a plain ascii space; all tests passed before.

### comment:28 follow-up: ↓ 29 Changed 3 years ago by git

• Commit changed from fb113639b4c3e4ff7de67a8f8edcd67ffb3141c5 to 3cf5014d43785fd384204981ead86702a3ea1662

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

 ​daec622 `#16268 boring doctest updates` ​3cf5014 `#16268 other doctest updates`

### comment:29 in reply to: ↑ 28 Changed 3 years ago by mmezzarobba

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

 ​daec622 `#16268 boring doctest updates` ​3cf5014 `#16268 other doctest updates`

Updated an optional test.

### comment:30 Changed 3 years ago by git

• Commit changed from 3cf5014d43785fd384204981ead86702a3ea1662 to b031e3e49c50a31dbe298b58f4178fd5f96d08b2

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

 ​259843a `Fix hash for unreduced fraction field elements.` ​3197980 `Fix documentation of normalize` ​ff7be78 `Fix doctest` ​9edad32 `More careful hashing of FractionFieldElement` ​6a2fbd7 `slightly simplify/robustify FractionFieldElement.reduce()` ​c16d55a `FractionFieldElement: merge reduce() and normalize()` ​7c8a45a `Tweak fraction field element hashing` ​5a78e11 `Small optimization in FracFieldElt richcmp()` ​0f17da0 `#16268 boring doctest updates` ​b031e3e `#16268 other doctest updates`

### comment:31 Changed 3 years ago by git

• Commit changed from b031e3e49c50a31dbe298b58f4178fd5f96d08b2 to 8cff798aace0fe8d69b6fcdc3bf2054b6f71fcd0

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

 ​c1f928f `#16268 boring doctest updates` ​8cff798 `#16268 other doctest updates`

### comment:32 Changed 3 years ago by mmezzarobba

• Status changed from needs_review to needs_work

### comment:33 Changed 3 years ago by git

• Commit changed from 8cff798aace0fe8d69b6fcdc3bf2054b6f71fcd0 to 544a8dfb4bf1e385592d444062867ce2f4987232

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

 ​544a8df `fix normalization of leading coefficients`

### comment:34 Changed 3 years ago by git

• Commit changed from 544a8dfb4bf1e385592d444062867ce2f4987232 to 75ddc0dee1104e6970d02352ea2aafc3262c0f49

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

 ​75ddc0d `fix normalization of leading coefficients`

### comment:35 Changed 3 years ago by mmezzarobba

• Status changed from needs_work to needs_review

### comment:36 Changed 3 years ago by mmezzarobba

• Cc bhutz added

The only nontrivial doctest update in the last commit should be the one in `endPN_automorphism_group.three_stable_points()`; I think it is correct, but it would be nice if someone who actually understands what it is about could double-check.

### comment:37 Changed 3 years ago by bhutz

Yes, the doc test change in three_stable_points is fine.

### comment:38 follow-up: ↓ 40 Changed 3 years ago by emassop

In c16d55a247b21d6c46d00f603ca21d7d6d64db19, "EXAMPLES::" became "EXAMPLES:". IIRC double colons are needed to use the examples in a doctest, or at least for formatting of the documentation (per https://devguide.python.org/documenting/#source-code). Please put the double colons back.

In 7c8a45abecdf5224c9f0a324447ba69db22057b5 hashes are computed for inexact rings without reduction. This means that python-equal fraction field elements can have distinct hashes, violating the preconditions of hashing in python. I would prefer to err on the side of caution and raise an exception rather than introducing a pathway for bugs that will be hard to find. If you decide to go the other way, please consider removing 198c0596630bb4ecc200e62c55715441e6f38d5c from the history as its intended effect is completely undone.

### comment:39 Changed 3 years ago by vdelecroix

• Milestone changed from sage-6.4 to sage-8.3

### comment:40 in reply to: ↑ 38 Changed 3 years ago by mmezzarobba

In c16d55a247b21d6c46d00f603ca21d7d6d64db19, "EXAMPLES::" became "EXAMPLES:". IIRC double colons are needed to use the examples in a doctest, or at least for formatting of the documentation (per https://devguide.python.org/documenting/#source-code). Please put the double colons back.

They are still there, after the introductory sentence instead of the "EXAMPLES:" heading.

In 7c8a45abecdf5224c9f0a324447ba69db22057b5 hashes are computed for inexact rings without reduction. This means that python-equal fraction field elements can have distinct hashes, violating the preconditions of hashing in python. I would prefer to err on the side of caution and raise an exception rather than introducing a pathway for bugs that will be hard to find. If you decide to go the other way, please consider removing 198c0596630bb4ecc200e62c55715441e6f38d5c from the history as its intended effect is completely undone.

I don't like that either. But over an inexact ring, the precondition of hashing would be violated anyway, because of the round-off errors during the computation of the reduction and the equality test. So what I'm suggesting in order to move forward is to keep the broken hash in this case, to be closer to bug-for-bug compatibility with the historic implementation...

This issue with equality appears almost everywhere in Sage, and unfortunately, I think we have to live with it. The only real fix IMO would be to drop the use of `==` for mathematical equality, define it to mean “syntactic” equality of the data structures (after normalization when relevant) instead, and introduce a separate method for mathematical equality. But that's not going to happen without a Sage fork at least, I guess...

### comment:41 follow-up: ↓ 42 Changed 3 years ago by emassop

Regarding EXAMPLES: Ah, I didn't notice that. Sorry.

Regarding hashing: How about emitting a warning? (sage.misc.superseded.warning?) Then computations keep working bug-for-bug, but the user is at least made aware that something may be going wrong. I can't recall if there was a policy for or against this.

I am aware that in general sage does not guarantee "`x == y` implies `hash(x) == hash(y)`", but if I recall correctly, it did strive to uphold this implication when `x` and `y` have the same parent.

A point on API: Although I can believe that always making the denominator monic is a good thing, merging `normalize` into `reduce` means that there no longer is a method that guarantees a normal form. Instead `reduce` now maybe normalizes the numerator and denominator or maybe not, depending on the implementation. Would it perhaps make sense to have a bool `_normalized` (instead of or in addition to `_reduced`) that gets set when `reduce` has succeeded at normalization? This doesn't have to be done as part of this bug though.

### comment:42 in reply to: ↑ 41 ; follow-up: ↓ 43 Changed 3 years ago by mmezzarobba

Regarding hashing: How about emitting a warning? (sage.misc.superseded.warning?) Then computations keep working bug-for-bug, but the user is at least made aware that something may be going wrong. I can't recall if there was a policy for or against this.

I'll try that and look again at the test failures to see what makes sense.

I am aware that in general sage does not guarantee "`x == y` implies `hash(x) == hash(y)`", but if I recall correctly, it did strive to uphold this implication when `x` and `y` have the same parent.

Yes. But even that is not always possible, unfortunately.

A point on API: Although I can believe that always making the denominator monic is a good thing, merging `normalize` into `reduce` means that there no longer is a method that guarantees a normal form. Instead `reduce` now maybe normalizes the numerator and denominator or maybe not, depending on the implementation.

Depending whether we are working with univariate rational function over a field or not, actually, isn't it?

Would it perhaps make sense to have a bool `_normalized` (instead of or in addition to `_reduced`) that gets set when `reduce` has succeeded at normalization? This doesn't have to be done as part of this bug though.

I'm not sure. This is also related to the issue of provinding a normal form for more general fraction field elements (starting with rational functions over non-fields, I guess), and hence I agree that this would best be kept for another ticket.

### comment:43 in reply to: ↑ 42 ; follow-up: ↓ 44 Changed 3 years ago by emassop

Regarding hashing: How about emitting a warning? (sage.misc.superseded.warning?) Then computations keep working bug-for-bug, but the user is at least made aware that something may be going wrong. I can't recall if there was a policy for or against this.

I'll try that and look again at the test failures to see what makes sense.

Thanks, I'll wait for the result.

A point on API: Although I can believe that always making the denominator monic is a good thing, merging `normalize` into `reduce` means that there no longer is a method that guarantees a normal form. Instead `reduce` now maybe normalizes the numerator and denominator or maybe not, depending on the implementation.

Depending whether we are working with univariate rational function over a field or not, actually, isn't it?

Would it perhaps make sense to have a bool `_normalized` (instead of or in addition to `_reduced`) that gets set when `reduce` has succeeded at normalization? This doesn't have to be done as part of this bug though.

I'm not sure. This is also related to the issue of providing a normal form for more general fraction field elements (starting with rational functions over non-fields, I guess), and hence I agree that this would best be kept for another ticket.

With the current implementation "is this a univariate rational function over a field" is the criterion, yes. The point is that the criterion changes when the implementation changes, and no one will know except by looking at the code for their specific kind of base ring.

(For instance the present normalization easily generalizes to the multivariate case by looking at the leading coefficient for some monomial order.)

I was hoping for a convincing argument on why making `reduce` more powerful is better than keeping `normalize` around, as my initial preference would be towards `normalize` because I generally prefer explicit over implicit.

### comment:44 in reply to: ↑ 43 Changed 3 years ago by mmezzarobba

I'll try that and look again at the test failures to see what makes sense.

Thanks, I'll wait for the result.

Ok, the only failures I'm seeing are in `src/sage/modular/modform_hecketriangle/` and apparently come from the fact that `FormsRingElement` inherits from `UniqueRepresentation` but is sometimes called on fractions with floating-point coefficients. I guess it would be possible to port it to `UniqueFactory` and somehow preprocess the arguments to avoid the warning.

However, I wonder if it wouldn't be better to keep `__hash__()` as it is now, and have `==` over inexact rings return `True` only when the fractions are equal without reduction. Then, hashing would be consistent with equality, the (arguably valid) use case of indexing a table by inexact fractions would work without warning, and hashing wouldn't break the promise that fractions over inexact ring are not automatically reduced. For `==`, this would consistent with the semantics of equality in “difficult” cases like interval arithmetic and symbolic expressions, where `a == b` may return `False` in cases where `a` and `b` are actually equal but that could not be verified. (Not for `!=`, though, but I don't see what we could do about that.)

What do you think?

With the current implementation "is this a univariate rational function over a field" is the criterion, yes. The point is that the criterion changes when the implementation changes, and no one will know except by looking at the code for their specific kind of base ring.

(For instance the present normalization easily generalizes to the multivariate case by looking at the leading coefficient for some monomial order.)

I was hoping for a convincing argument on why making `reduce` more powerful is better than keeping `normalize` around, as my initial preference would be towards `normalize` because I generally prefer explicit over implicit.

Essentially, I agree with you. I'm just saying that I'd rather keep that question for later, and address it once we have a way of normalizing in more general situations, probably along the lines of what you suggested at #16993.

### comment:45 Changed 3 years ago by mmezzarobba

FWIW, all tests pass with

```}}}diff --git a/src/sage/modular/modform_hecketriangle/graded_ring_element.py b/src/sage/modular/modform_hecketriangle/graded_ring_element.py
index be3b1e614b..5b41348c07 100644```
 a class FormsRingElement(six.with_metaclass( sage: MeromorphicModularFormsRing()(-1/x) == MeromorphicModularFormsRing()(1/(-x)) True sage: MeromorphicModularFormsRing(base_ring=CC)(-1/x) == MeromorphicModularFormsRing()(1/(-x)) True False """ if op not in [op_EQ, op_NE]: return NotImplemented
• ## src/sage/rings/fraction_field_element.pyx

```diff --git a/src/sage/rings/fraction_field_element.pyx b/src/sage/rings/fraction_field_element.pyx
index 3013a7b3af..3b221ddf4b 100644```
 a cdef class FractionFieldElement(FieldElement): True """ cdef FractionFieldElement other = other_ if ((op == Py_EQ or op == Py_NE) and self.__denominator == other.__denominator): return richcmp(self.__numerator, other.__numerator, op) else: return richcmp( self.__numerator * other.__denominator, self.__denominator * other.__numerator, op) if (op == Py_EQ or op == Py_NE): if self.__denominator == other.__denominator: return richcmp(self.__numerator, other.__numerator, op) elif not self._parent.is_exact(): # over inexact rings, compare unreduced representations return op == Py_NE return richcmp( self.__numerator * other.__denominator, self.__denominator * other.__numerator, op) def valuation(self, v=None): """ cdef class FractionFieldElement_1poly_field(FractionFieldElement): if op == Py_EQ or op == Py_NE: if self.__denominator == other.__denominator: return richcmp(self.__numerator, other.__numerator, op) elif self._is_reduced and other._is_reduced: elif (self._is_reduced and other._is_reduced or not self._parent.is_exact()): return op == Py_NE return richcmp( self.__numerator * other.__denominator,

### comment:46 Changed 3 years ago by git

• Commit changed from 75ddc0dee1104e6970d02352ea2aafc3262c0f49 to 86b3b56b2bfd64a57f3a82dd022f5bd70b11b622

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

 ​56b9292 `Fix hash for unreduced fraction field elements.` ​7b1017d `Fix documentation of normalize` ​98b1301 `Fix doctest` ​7281516 `More careful hashing of FractionFieldElement` ​862604c `slightly simplify/robustify FractionFieldElement.reduce()` ​7f3c093 `FractionFieldElement: merge reduce() and normalize()` ​b273531 `Tweak fraction field element hashing` ​a21cb63 `#16268 boring doctest updates` ​80c421d `#16268 other doctest updates` ​86b3b56 `fix normalization of leading coefficients`

### comment:47 Changed 3 years ago by mmezzarobba

Rebased on the last beta due to a minor conflict.

### comment:48 follow-up: ↓ 49 Changed 3 years ago by git

• Commit changed from 86b3b56b2bfd64a57f3a82dd022f5bd70b11b622 to 3a3d32fb60b4c5177c7ce0824076d78aeb90184c

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

 ​3ff950c `Fix hash for unreduced fraction field elements.` ​2bdd265 `Fix documentation of normalize` ​bef8c4f `Fix doctest` ​305c98f `More careful hashing of FractionFieldElement` ​d524b75 `slightly simplify/robustify FractionFieldElement.reduce()` ​9a9d4de `FractionFieldElement: merge reduce() and normalize()` ​59c558c `Tweak fraction field element hashing` ​afc6a05 `#16268 boring doctest updates` ​7dfe3c3 `#16268 other doctest updates` ​3a3d32f `fix normalization of leading coefficients`

### comment:49 in reply to: ↑ 48 Changed 3 years ago by mmezzarobba

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

Rebased and fixed minor test failure.

### comment:50 Changed 3 years ago by git

• Commit changed from 3a3d32fb60b4c5177c7ce0824076d78aeb90184c to 5d4a6890e27f84afb6aa8d713117dfcb0c5a702b

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

 ​40e22a0 `Fix documentation of normalize` ​fc57a23 `Fix doctest` ​21375ea `More careful hashing of FractionFieldElement` ​03d91ab `slightly simplify/robustify FractionFieldElement.reduce()` ​610e585 `FractionFieldElement: merge reduce() and normalize()` ​8aa61d5 `Tweak fraction field element hashing` ​e01d960 `#16268 boring doctest updates` ​1bd6279 `#16268 other doctest updates` ​1f6b0b6 `fix normalization of leading coefficients` ​5d4a689 `additional doctest update after #25440`

### comment:51 Changed 3 years ago by mmezzarobba

Rebased on 8.3.beta5 to add a minor doctest update.

### comment:52 follow-up: ↓ 53 Changed 3 years ago by saraedum

This seems wrong:

```-            ((1 + O(2)))/((1 + O(2^5))*x)
+            ((1 + O(2)))/((1 + O(2))*x)
```

But let's discuss this at #25318.

### comment:53 in reply to: ↑ 52 ; follow-up: ↓ 54 Changed 3 years ago by mmezzarobba

This seems wrong:

```-            ((1 + O(2)))/((1 + O(2^5))*x)
+            ((1 + O(2)))/((1 + O(2))*x)
```

But let's discuss this at #25318.

Why? Isn't it the same result, just written in a different way?

### comment:54 in reply to: ↑ 53 Changed 3 years ago by saraedum

Oops, sorry. I guess you're right.

This seems wrong:

```-            ((1 + O(2)))/((1 + O(2^5))*x)
+            ((1 + O(2)))/((1 + O(2))*x)
```

But let's discuss this at #25318.

Why? Isn't it the same result, just written in a different way?

### comment:55 Changed 3 years ago by git

• Commit changed from 5d4a6890e27f84afb6aa8d713117dfcb0c5a702b to dcd92b72b863663c4306018735c8df9bd0213d73

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

 ​a1cd059 `Fix documentation of normalize` ​9d108cc `Fix doctest` ​47cf425 `More careful hashing of FractionFieldElement` ​1d8546f `slightly simplify/robustify FractionFieldElement.reduce()` ​f220ba1 `FractionFieldElement: merge reduce() and normalize()` ​d57e934 `Tweak fraction field element hashing` ​db40831 `#16268 boring doctest updates` ​2955aa9 `#16268 other doctest updates` ​069cca8 `fix normalization of leading coefficients` ​dcd92b7 `additional doctest update after #25440`

### comment:56 Changed 3 years ago by git

• Commit changed from dcd92b72b863663c4306018735c8df9bd0213d73 to db762fc4082cf6af913a7637b895f970a7492a74

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

 ​2850652 `Fix documentation of normalize` ​26c87d3 `Fix doctest` ​78b5990 `More careful hashing of FractionFieldElement` ​e768973 `slightly simplify/robustify FractionFieldElement.reduce()` ​029346f `FractionFieldElement: merge reduce() and normalize()` ​80f18f0 `Tweak fraction field element hashing` ​1153b5d `#16268 boring doctest updates` ​b71ab2d `#16268 other doctest updates` ​e663dbe `fix normalization of leading coefficients` ​db762fc `additional doctest update after #25440`

### comment:57 Changed 3 years ago by mmezzarobba

• Description modified (diff)
• Summary changed from Better normalization for function field elements to Better normalization for fraction field elements

### comment:58 Changed 3 years ago by saraedum

• Reviewers set to Julian Rüth

If you are confident that the output in the doctests is still correct (I did not check all of them) then feel free to set this to positive review.

### comment:59 Changed 3 years ago by mmezzarobba

• Status changed from needs_review to positive_review

Thank you!

### comment:60 follow-up: ↓ 61 Changed 3 years ago by vbraun

• Status changed from positive_review to needs_work

Merge conflict

### comment:61 in reply to: ↑ 60 Changed 3 years ago by mmezzarobba

• Status changed from needs_work to needs_review

Merge conflict

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

### comment:62 Changed 3 years ago by git

• Commit changed from db762fc4082cf6af913a7637b895f970a7492a74 to af91bf5f1dad1ab5bbb6fb376bb5c408bc85974e

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`

### comment:63 Changed 3 years ago by mmezzarobba

• Status changed from needs_review to positive_review

### comment:64 Changed 3 years ago by vbraun

• Branch changed from u/mmezzarobba/16268-normalize_fractions to af91bf5f1dad1ab5bbb6fb376bb5c408bc85974e
• Resolution set to fixed
• Status changed from positive_review to closed

### comment:65 follow-up: ↓ 66 Changed 3 years ago by mkoeppe

• Commit af91bf5f1dad1ab5bbb6fb376bb5c408bc85974e deleted

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

### comment:66 in reply to: ↑ 65 Changed 3 years ago by mmezzarobba

• Description modified (diff)

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

### comment:67 Changed 3 years ago by mkoeppe

Follow-up ticket at #26339

### comment:68 Changed 2 years ago by slelievre

• Cc slelievre added
• Description modified (diff)
• Merged in set to sage-8.4.beta2
• Milestone changed from sage-8.3 to sage-8.4
Note: See TracTickets for help on using tickets.