Make _floordiv_() return the Euclidean quotient for power series over fields

[pjbruin]

There exists a method PowerSeries_poly.__floordiv__(), but it is not clear how it differs from ordinary division (see #15601 comment:43), or how it should differ mathematically.

We replace this method by a new method PowerSeries._floordiv_(), which returns the Euclidean quotient over fields and is a deprecated alias for _div_() over other rings.

CC: @jdemeyer

Component: algebra

Author: Peter Bruin

Branch/Commit: b7cd5cb

Reviewer: Bruno Grenet

Issue created by migration from https://trac.sagemath.org/ticket/20062

[pjbruin]

Branch: u/pbruin/20062-PowerSeries_floordiv

[pjbruin]

Commit: e9719f7

[bgrenet]

comment:2

I don't fully agree with your proposal: In (generic) implementations for elements of rings, one may need to have a __floordiv__ (which returns the same as __div__). That's why (I guess) there is a __floordiv__ in the class FieldElement. So I would not deprecate it, but rather simply make it an (non-deprecated) alias of __div__.

[pjbruin]

comment:3

Replying to @bgrenet:

I don't fully agree with your proposal: In (generic) implementations for elements of rings, one may need to have a __floordiv__ (which returns the same as __div__).

Why would this be necessary? If the user calls __floordiv__, he presumably does this for a reason, i.e. expects that it behaves differently from __div__...

That's why (I guess) there is a __floordiv__ in the class FieldElement.

Well, power series rings are not fields. There is also an implementation of _floordiv_ in RingElement, which explicitly raises an error saying unsupported operand parent(s) for '//'. In fact, this error is even raised when applying __floordiv__ to elements of RR:

sage: RR(1.2) // RR(2.3)
...
TypeError: unsupported operand parent(s) for '//': 'Real Field with 53 bits of precision' and 'Real Field with 53 bits of precision'

So I would not deprecate it, but rather simply make it an (non-deprecated) alias of __div__.

Then we should do this in general for ring elements; I don't really see the advantage of this...

In my opinion, it would make more sense to make sure that power series rings R over a field, or more generally all discrete valuation rings (R, v), are put into the category of Euclidean domains. Then floor division in R can be implemented using Euclidean division, so f * g = f / g if v(g) <= v(f) and f * g = 0 if v(g) > v(f). However, this has the disadvantage that it is not the same as the current __floordiv__, which (as far as I can see) is the same as __div__.

[bgrenet]

comment:4

Replying to @pjbruin:

Why would this be necessary? If the user calls __floordiv__, he presumably does this for a reason, i.e. expects that it behaves differently from __div__...

One case I very often encounter is the need of an "exact division", that is a division when you know in advance that the result is exact.

That's why (I guess) there is a __floordiv__ in the class FieldElement.

Well, power series rings are not fields. There is also an implementation of _floordiv_ in RingElement, which explicitly raises an error saying unsupported operand parent(s) for '//'. In fact, this error is even raised when applying __floordiv__ to elements of RR:

sage: RR(1.2) // RR(2.3)
...
TypeError: unsupported operand parent(s) for '//': 'Real Field with 53 bits of precision' and 'Real Field with 53 bits of precision'

Right. But this behavior for RR is currently being discussed in #15260.

So I would not deprecate it, but rather simply make it an (non-deprecated) alias of __div__.

Then we should do this in general for ring elements; I don't really see the advantage of this...

That's right, it is probably a bad idea to make __floordiv__ an alias of __div__ in this case.

In my opinion, it would make more sense to make sure that power series rings R over a field, or more generally all discrete valuation rings (R, v), are put into the category of Euclidean domains. Then floor division in R can be implemented using Euclidean division, so f * g = f / g if v(g) <= v(f) and f * g = 0 if v(g) > v(f). However, this has the disadvantage that it is not the same as the current __floordiv__, which (as far as I can see) is the same as __div__.

You're perfectly right. My two-cent on this would be as follows:

• __div__ should return an element of the fraction field, as it is the case for elements of ZZ or polynomials for instance; I find the current situation weird:

sage: R.<x> = QQ[[]]
sage: (1/(1+x)).parent()
Power Series Ring in x over Rational Field
sage: (1/x).parent()
Laurent Series Ring in x over Rational Field

while for instance for ZZ:

sage: (1/1).parent() is (1/2).parent()
True

• __floordiv__ in power series rings over a field should return the quotient in the euclidean division, since these rings are euclidean.

• __floordiv__ in power series rings over ZZ (say) should behave the same way as it behaves for polynomials over ZZ, that is return the quotient in the euclidean division (as over QQ) but reducing each coefficient modulo the leading coefficient of the divisor. For instance, 2-3*x-x<sup>2+O(x</sup>3)//(2+x) should equal 1-2*x+0*x<sup>2+O(x</sup>3).

[pjbruin]

comment:5

I tried to (1) add a method _floordiv_ to EuclideanDomains.ElementMethods, and (2) make DiscreteValuationRings a subcategory of EuclideanDomains. However, f // g then still complains that the parents do not support this operator. If I understand correctly, this is because RingElement._floordiv_ comes before EuclideanDomains.ElementMethods._floordiv_ in the method resolution order. We cannot remove the first one because it must be implemented in RingElement, being a cpdef method.

Jeroen, do you (as the author of e.g. #2034) perhaps know a way around this?

Edit: (2) was done in #20283.

[jdemeyer]

comment:6

Replying to @pjbruin:

I tried to (1) add a method _floordiv_ to EuclideanDomains.ElementMethods

I think that such category stuff should probably not be used for Cython methods, I'm not entirely surprised that it doesn't work.

In any case, I think there is not much point in implementing stuff if we haven't agreed on the semantics of //.

[pjbruin]

comment:7

After thinking about this a bit more, it still seems meaningful to me to have an operator // that is different from /, and that returns the "Euclidean" quotient in the case of power series over a field. (I am not sure what to do for power series over Z, for example).

However, both to warn users and because the "correct" // seems to be non-trivial to implement, it is probably good to start by deprecating the current behaviour where // behaves identically to /. Hence I am setting this ticket back to "needs review" and propose to do the "meaningful" reimplementation of // at a later time.