Opened 2 years ago

Last modified 17 months ago

#23971 needs_info defect

Euclidean division in quadratic imaginary orders

Reported by: saraedum Owned by:
Priority: major Milestone: sage-8.1
Component: number fields Keywords:
Cc: Merged in:
Authors: Jeroen Demeyer Reviewers: David Roe, Julian Rüth
Report Upstream: N/A Work issues:
Branch: u/jdemeyer/floordiv_in_orders_returns_a_number_field_element (Commits) Commit: 1ccb1ba157361a7b70fe7cf2d22163666f3bd838
Dependencies: Stopgaps:

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.

Change History (28)

comment:1 Changed 2 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: Changed 2 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 2 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 2 years ago by roed

Replying to 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.

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 2 years ago by jdemeyer

  • Authors set to Jeroen Demeyer

comment:6 Changed 2 years ago by jdemeyer

  • Branch set to u/jdemeyer/floordiv_in_orders_returns_a_number_field_element

comment:7 Changed 2 years ago by jdemeyer

  • Commit set to c36aaff969295f404ef35f83927e5289df4d7542
  • Dependencies set to #24079

New commits:

1d56994Simplify number field division
c36aaffImplement Euclidean division in number fields

comment:8 Changed 2 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: Changed 2 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 2 years ago by roed

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

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

Replying to 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

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

comment:12 in reply to: ↑ 9 ; follow-up: Changed 2 years ago by jdemeyer

Replying to 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.

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

Replying to roed:

  • 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: Changed 2 years ago by roed

Replying to jdemeyer:

Replying to 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: Changed 2 years ago by jdemeyer

Replying to 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.

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

Replying to jdemeyer:

Replying to 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 2 years ago by jdemeyer

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

comment:18 Changed 2 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:

0c1ceeaImplement Euclidean division in number fields

comment:19 Changed 2 years ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:20 Changed 2 years ago by jdemeyer

  • Dependencies #24079 deleted

comment:21 Changed 2 years ago by git

  • Commit changed from 0c1ceea7b0a0da0cb9c593052973aee76e114b0a to dd8dbfa3271dfc96e1b9e88b6c77d6658035f5c3

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

dd8dbfaRemove failing doctests

comment:22 follow-up: Changed 18 months ago by saraedum

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

Sorry, I had somehow forgotten about this ticket. Some comments:

  • 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: Changed 17 months ago by jdemeyer

Replying to saraedum:

  • 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 17 months 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:

c87a626Implement Euclidean division in number fields

comment:25 Changed 17 months ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:26 Changed 17 months 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:

1ccb1baImplement Euclidean division in number fields

comment:27 in reply to: ↑ 23 Changed 17 months ago by saraedum

Replying to jdemeyer:

Replying to saraedum:

  • 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.

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.

comment:28 Changed 17 months ago by saraedum

  • Status changed from needs_review to needs_info
Note: See TracTickets for help on using tickets.