Opened 5 years ago

# Euclidean division in quadratic imaginary orders

Reported by: Owned by: saraedum major sage-8.1 number fields Jeroen Demeyer David Roe, Julian Rüth N/A u/jdemeyer/floordiv_in_orders_returns_a_number_field_element 1ccb1ba157361a7b70fe7cf2d22163666f3bd838

### Description

The result of a `//` should remain in the same ring, but it currently does not:

```sage: (GaussianIntegers()(1)//1).parent()
Number Field in I with defining polynomial x^2 + 1
```

This is caused by order elements inheriting from `FieldElement` which makes the assumption that `_floordiv_` and `_div_` are the same.

### comment:1 Changed 5 years ago by roed

This is tricky, since most orders in number fields are not Euclidean, so quotient with remainder doesn't make sense.

### comment:2 follow-up: ↓ 4 Changed 5 years ago by jdemeyer

Well, the correct behaviour would be to do the right thing in the imaginary quadratic orders which are naturally Euclidean and raise an exception otherwise.

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

For me it would be sufficient for `a//b` to be `parent(a/b)` and raise an exception (NotImplemented??) if that is not in the same ring.

### comment:4 in reply to: ↑ 2 Changed 5 years ago by roed

Well, the correct behaviour would be to do the right thing in the imaginary quadratic orders which are naturally Euclidean and raise an exception otherwise.

There are other orders which are norm Euclidean (some real quadratic orders for example). See http://www.fen.bilkent.edu.tr/~franz/publ/survey.pdf

Of course, it's computationally more difficult to find a remainder when the unit group is nontrivial.

### comment:5 Changed 5 years ago by jdemeyer

• Authors set to Jeroen Demeyer

### comment:6 Changed 5 years ago by jdemeyer

• Branch set to u/jdemeyer/floordiv_in_orders_returns_a_number_field_element

### comment:7 Changed 5 years ago by jdemeyer

• Commit set to c36aaff969295f404ef35f83927e5289df4d7542
• Dependencies set to #24079

New commits:

 ​1d56994 `Simplify number field division` ​c36aaff `Implement Euclidean division in number fields`

### comment:8 Changed 5 years ago by jdemeyer

• Status changed from new to needs_review
• Summary changed from floordiv in orders returns a number field element to Euclidean division in quadratic imaginary orders

### comment:9 follow-ups: ↓ 11 ↓ 12 ↓ 13 Changed 5 years ago by roed

First, the patchbot is unhappy: there's a strange merge failure on Cygwin, complaining about `CONFLICT (content): Merge conflict in src/sage/parallel/map_reduce.py` (which I don't understand, since other merges into `8.1.beta8` succeeded), and a test failure in `sage/structure/element.pyx`.

Some thoughts on the code:

• Julian suggested having `a//b` return `parent(a/b)` when b divides `a` and raise an error otherwise. This makes sense for any integral domain, and I think it's a good idea: so often this is what we want for floor division. It's a bit strange to have different behavior for different `b`, but we already do this to some extent: `b=0` will always raise an error.
• Why did you choose to round to even? It would be more consistent with `QQ` to round down.
• I think we should also implement `__mod__` and `quo_rem` to match this implementation of floor division. This doesn't have to be on this ticket.

### comment:10 Changed 5 years ago by roed

• Reviewers set to David Roe
• Status changed from needs_review to needs_work

### comment:11 in reply to: ↑ 9 Changed 5 years ago by jdemeyer

First, the patchbot is unhappy: there's a strange merge failure on Cygwin, complaining about `CONFLICT (content): Merge conflict in src/sage/parallel/map_reduce.py`

That happens on every ticket, it must be a problem with that bot.

### comment:12 in reply to: ↑ 9 ; follow-up: ↓ 14 Changed 5 years ago by jdemeyer

Julian suggested having `a//b` return `parent(a/b)` when b divides `a` and raise an error otherwise.

Surely, you made a mistake somewhere in this sentence (`a//b` should not return a ring!). And I can't guess what you meant.

### comment:13 in reply to: ↑ 9 Changed 5 years ago by jdemeyer

• Why did you choose to round to even? It would be more consistent with `QQ` to round down.

Consistency with `QQ` was not a goal here. I guess it could be done but then it becomes less obvious to generalize to all number field elements. You cannot just round down the first component (the `x` in `x + y sqrt(D)`) in all cases. So either we would need to round down `x` only when `y` is zero or an integer, but that seems like needless complication to me.

Besides, I like the idea that `x // y` gives the closest possible order element to `x / y`.

### comment:14 in reply to: ↑ 12 ; follow-up: ↓ 15 Changed 5 years ago by roed

Julian suggested having `a//b` return `parent(a/b)` when b divides `a` and raise an error otherwise.

Surely, you made a mistake somewhere in this sentence (`a//b` should not return a ring!). And I can't guess what you meant.

Say `a` and `b` both have an order `R` as their parent. I meant that `a//b` should return `R(a/b)`.

### comment:15 in reply to: ↑ 14 ; follow-up: ↓ 16 Changed 5 years ago by jdemeyer

Say `a` and `b` both have an order `R` as their parent. I meant that `a//b` should return `R(a/b)`.

OK, I see what you mean now. I guess a better approach would be: `a//b` returns either an order element `t` such that `N(a/b - t) < 1` or it raises `ArithmeticError`. That would generalize both the Euclidean division and the exact division.

### comment:16 in reply to: ↑ 15 Changed 5 years ago by roed

Say `a` and `b` both have an order `R` as their parent. I meant that `a//b` should return `R(a/b)`.

OK, I see what you mean now. I guess a better approach would be: `a//b` returns either an order element `t` such that `N(a/b - t) < 1` or it raises `ArithmeticError`. That would generalize both the Euclidean division and the exact division.

Agreed: I think that's the optimal solution. Figuring out what that `t` is in the non-imaginary quadratic case is probably beyond the scope of this ticket.

### comment:17 Changed 5 years ago by jdemeyer

Unfortunately, this introduces an additional complication that the order is no longer guaranteed to be maximal...

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

• Commit changed from c36aaff969295f404ef35f83927e5289df4d7542 to 0c1ceea7b0a0da0cb9c593052973aee76e114b0a

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

 ​0c1ceea `Implement Euclidean division in number fields`

### comment:19 Changed 5 years ago by jdemeyer

• Status changed from needs_work to needs_review

### comment:20 Changed 5 years ago by jdemeyer

• Dependencies #24079 deleted

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

• Commit changed from 0c1ceea7b0a0da0cb9c593052973aee76e114b0a to dd8dbfa3271dfc96e1b9e88b6c77d6658035f5c3

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

 ​dd8dbfa `Remove failing doctests`

### comment:22 follow-up: ↓ 23 Changed 4 years ago by saraedum

• Reviewers changed from David Roe to David Roe, Julian Rüth
• Status changed from needs_review to needs_work

• `intentially` should read `intentionally`
• The patchbot (coverage) is unhappy about the removal of the floordiv example
• There are some failing doctests it seems
• Why don't we implement my original proposal as well? I.e., `a//b==R(a/b)` if `a/b in R`?

### comment:23 in reply to: ↑ 22 ; follow-up: ↓ 27 Changed 4 years ago by jdemeyer

• Why don't we implement my original proposal as well? I.e., `a//b==R(a/b)` if `a/b in R`?

What do you mean exactly? I thought I did implement that, but it seems that you don't agree.

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

• Commit changed from dd8dbfa3271dfc96e1b9e88b6c77d6658035f5c3 to c87a6260bffb68b3b6342d50da39c0ee1cb363ba

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

 ​c87a626 `Implement Euclidean division in number fields`

### comment:25 Changed 4 years ago by jdemeyer

• Status changed from needs_work to needs_review

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

• Commit changed from c87a6260bffb68b3b6342d50da39c0ee1cb363ba to 1ccb1ba157361a7b70fe7cf2d22163666f3bd838

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

 ​1ccb1ba `Implement Euclidean division in number fields`

### comment:27 in reply to: ↑ 23 Changed 4 years ago by saraedum

• Why don't we implement my original proposal as well? I.e., `a//b==R(a/b)` if `a/b in R`?
This ticket was originally not only about quadratic imaginary orders (I think you changed the scope at some point.) I think that `a//b` should always return `a/b` if that is in the original ring…I really just want `a//1` not to fail.