Opened 4 years ago
Last modified 3 years ago
#23971 needs_info defect
Euclidean division in quadratic imaginary orders
Reported by:  saraedum  Owned by:  

Priority:  major  Milestone:  sage8.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, GitHub, GitLab)  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 4 years ago by
comment:2 followup: ↓ 4 Changed 4 years ago by
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 4 years ago by
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 4 years ago by
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 4 years ago by
comment:6 Changed 4 years ago by
 Branch set to u/jdemeyer/floordiv_in_orders_returns_a_number_field_element
comment:7 Changed 4 years ago by
 Commit set to c36aaff969295f404ef35f83927e5289df4d7542
 Dependencies set to #24079
comment:8 Changed 4 years ago by
 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 followups: ↓ 11 ↓ 12 ↓ 13 Changed 4 years ago by
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
returnparent(a/b)
when b dividesa
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 differentb
, 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__
andquo_rem
to match this implementation of floor division. This doesn't have to be on this ticket.
comment:10 Changed 4 years ago by
 Reviewers set to David Roe
 Status changed from needs_review to needs_work
comment:11 in reply to: ↑ 9 Changed 4 years ago by
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 ; followup: ↓ 14 Changed 4 years ago by
Replying to roed:
Julian suggested having
a//b
returnparent(a/b)
when b dividesa
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 4 years ago by
Replying to roed:
 Why did you choose to round to even? It would be more consistent with
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 ; followup: ↓ 15 Changed 4 years ago by
Replying to jdemeyer:
Replying to roed:
Julian suggested having
a//b
returnparent(a/b)
when b dividesa
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 ; followup: ↓ 16 Changed 4 years ago by
Replying to roed:
Say
a
andb
both have an orderR
as their parent. I meant thata//b
should returnR(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 4 years ago by
Replying to jdemeyer:
Replying to roed:
Say
a
andb
both have an orderR
as their parent. I meant thata//b
should returnR(a/b)
.OK, I see what you mean now. I guess a better approach would be:
a//b
returns either an order elementt
such thatN(a/b  t) < 1
or it raisesArithmeticError
. 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 nonimaginary quadratic case is probably beyond the scope of this ticket.
comment:17 Changed 4 years ago by
Unfortunately, this introduces an additional complication that the order is no longer guaranteed to be maximal...
comment:18 Changed 4 years ago by
 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 4 years ago by
 Status changed from needs_work to needs_review
comment:20 Changed 4 years ago by
 Dependencies #24079 deleted
comment:21 Changed 4 years ago by
 Commit changed from 0c1ceea7b0a0da0cb9c593052973aee76e114b0a to dd8dbfa3271dfc96e1b9e88b6c77d6658035f5c3
Branch pushed to git repo; I updated commit sha1. New commits:
dd8dbfa  Remove failing doctests

comment:22 followup: ↓ 23 Changed 3 years ago by
 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 readintentionally
 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)
ifa/b in R
?
comment:23 in reply to: ↑ 22 ; followup: ↓ 27 Changed 3 years ago by
Replying to saraedum:
 Why don't we implement my original proposal as well? I.e.,
a//b==R(a/b)
ifa/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 3 years ago by
 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 3 years ago by
 Status changed from needs_work to needs_review
comment:26 Changed 3 years ago by
 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 3 years ago by
Replying to jdemeyer:
Replying to saraedum:
 Why don't we implement my original proposal as well? I.e.,
a//b==R(a/b)
ifa/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 3 years ago by
 Status changed from needs_review to needs_info
This is tricky, since most orders in number fields are not Euclidean, so quotient with remainder doesn't make sense.