Opened 9 years ago

Closed 4 years ago

# Better normalization for fraction field elements

Reported by: Owned by: John Cremona minor sage-8.4 algebra Travis Scrimshaw, Clemens Heuberger, Salvatore Stella, Jakob Kroeker, Ben Hutz, Samuel Lelièvre 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

• 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 9 years ago by Erik Massop

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 9 years ago by Robert Bradshaw

Branch: → u/robertwb/ticket/16268 Apr 29, 2014, 3:00:38 PM → Apr 29, 2014, 3:00:38 PM Apr 29, 2014, 4:29:25 PM → Apr 29, 2014, 4:29:25 PM

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

Commit: → 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 9 years ago by git

Commit: 289d3aa124bd5a03349f14f0520e4b8d2845dd84 → 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 9 years ago by John 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 9 years ago by Robert Bradshaw

Authors: → Robert Bradshaw new → needs_review

### comment:7 Changed 9 years ago by Erik Massop

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 9 years ago by Erik Massop

Branch: u/robertwb/ticket/16268 → u/emassop/ticket/16268

### comment:9 Changed 9 years ago by John Cremona

Commit: f7266ca383db2783ba0d485ac5c9ab5da6c6d614 → 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 9 years ago by Erik Massop

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 9 years ago by git

Commit: cdf116327b93b5d29282c98d40042440d068ce44 → a4221ed3e1d16d38b271316b01b91344fb195746

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

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

### comment:12 Changed 9 years ago by Erik Massop

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 9 years ago by For batch modifications

Milestone: sage-6.2 → sage-6.3

### comment:14 Changed 9 years ago by Ralf Stephan

Status: needs_review → 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 8 years ago by Erik Massop

#15297 is related

### comment:16 Changed 8 years ago by For batch modifications

Milestone: sage-6.3 → sage-6.4

### comment:17 Changed 8 years ago by Erik Massop

#16993 is related.

### comment:18 Changed 8 years ago by Erik Massop

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

ping

### comment:23 in reply to:  5 Changed 5 years ago by Marc Mezzarobba

Authors: Robert Bradshaw → Robert Bradshaw, Erik Massop, Marc Mezzarobba u/emassop/ticket/16268 → u/mmezzarobba/16268-normalize_fractions a4221ed3e1d16d38b271316b01b91344fb195746 → 2d96533bde07fbbbce3a490dd786bbf7a9ffae53 needs_work → 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 #16993. 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`
Last edited 5 years ago by Marc Mezzarobba (previous) (diff)

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

Commit: 2d96533bde07fbbbce3a490dd786bbf7a9ffae53 → 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 5 years ago by git

Commit: 0830684d5a260960d215d52ed42ef932fa987e9e → 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 5 years ago by git

Commit: b504f8e593367ae9c955b515965930d750674044 → 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 5 years ago by Marc Mezzarobba

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

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

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

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 5 years ago by Marc Mezzarobba

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 5 years ago by git

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 5 years ago by git

Commit: b031e3e49c50a31dbe298b58f4178fd5f96d08b2 → 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 5 years ago by Marc Mezzarobba

Status: needs_review → needs_work

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

Commit: 8cff798aace0fe8d69b6fcdc3bf2054b6f71fcd0 → 544a8dfb4bf1e385592d444062867ce2f4987232

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

 ​544a8df `fix normalization of leading coefficients`

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

Commit: 544a8dfb4bf1e385592d444062867ce2f4987232 → 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 5 years ago by Marc Mezzarobba

Status: needs_work → needs_review

### comment:36 Changed 5 years ago by Marc Mezzarobba

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 5 years ago by Ben Hutz

Yes, the doc test change in three_stable_points is fine.

### comment:38 follow-up:  40 Changed 5 years ago by Erik Massop

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 5 years ago by Vincent Delecroix

Milestone: sage-6.4 → sage-8.3

### comment:40 in reply to:  38 Changed 5 years ago by Marc Mezzarobba

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 5 years ago by Erik Massop

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 5 years ago by Marc Mezzarobba

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 5 years ago by Erik Massop

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 5 years ago by Marc Mezzarobba

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 5 years ago by Marc Mezzarobba

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 5 years ago by git

Commit: 75ddc0dee1104e6970d02352ea2aafc3262c0f49 → 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 5 years ago by Marc Mezzarobba

Rebased on the last beta due to a minor conflict.

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

Commit: 86b3b56b2bfd64a57f3a82dd022f5bd70b11b622 → 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 5 years ago by Marc Mezzarobba

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

Rebased and fixed minor test failure.

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

Commit: 3a3d32fb60b4c5177c7ce0824076d78aeb90184c → 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 4 years ago by Marc Mezzarobba

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

### comment:52 follow-up:  53 Changed 4 years ago by Julian Rüth

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 4 years ago by Marc Mezzarobba

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 4 years ago by Julian Rüth

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 4 years ago by git

Commit: 5d4a6890e27f84afb6aa8d713117dfcb0c5a702b → 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 4 years ago by git

Commit: dcd92b72b863663c4306018735c8df9bd0213d73 → 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 4 years ago by Marc Mezzarobba

Description: modified (diff) Better normalization for function field elements → Better normalization for fraction field elements

### comment:58 Changed 4 years ago by Julian Rüth

Reviewers: → 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 4 years ago by Marc Mezzarobba

Status: needs_review → positive_review

Thank you!

### comment:60 follow-up:  61 Changed 4 years ago by Volker Braun

Status: positive_review → needs_work

Merge conflict

### comment:61 in reply to:  60 Changed 4 years ago by Marc Mezzarobba

Status: needs_work → 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 4 years ago by git

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 4 years ago by Marc Mezzarobba

Status: needs_review → positive_review

### comment:64 Changed 4 years ago by Volker Braun

Branch: u/mmezzarobba/16268-normalize_fractions → af91bf5f1dad1ab5bbb6fb376bb5c408bc85974e → fixed positive_review → closed

### comment:65 follow-up:  66 Changed 4 years ago by Matthias Köppe

#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 4 years ago by Marc Mezzarobba

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 4 years ago by Matthias Köppe

Follow-up ticket at #26339

### comment:68 Changed 4 years ago by Samuel Lelièvre

Cc: Samuel Lelièvre added modified (diff) → sage-8.4.beta2 sage-8.3 → sage-8.4
Note: See TracTickets for help on using tickets.