add exact division of power series by coefficient

[fchapoton]

as this is very useful for computations in combinatorics

CC: @tscrim @slel @kliem @kwankyu

Component: combinatorics

Author: Frédéric Chapoton, Jonathan Kliem, Travis Scrimshaw

Branch/Commit: 3525f06

Reviewer: Frédéric Chapoton, Jonathan Kliem

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

[fchapoton]

Branch: u/chapoton/34116

[fchapoton]

Commit: f8df808

[sagetrac-git]

Changed commit from f8df808 to eeb50ae

[sagetrac-git]

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

eeb50ae

add floordiv for power series for exact division by one coefficient

[fchapoton]

comment:3

bot is morally green, so please review

[tscrim]

comment:5

Sorry for losing track of this. I think we should error out if the RHS has degree > 0 rather than silently returning a wrong answer. The current behavior is to error out:

sage: R.<x> = PowerSeriesRing(QQ)
sage: 1 + x // (1 + 2*x)
[snip]
TypeError: unsupported operand parent(s) for //: 'Power Series Ring in x over Rational Field' and 'Power Series Ring in x over Rational Field'

A "better" way to do this IMO would be to implement this as an action of the base ring. This is faster as it would bypass the temporary object created by the coercion and it would continue to not work for any FPS.

[fchapoton]

comment:6

Thanks for the feedback.

As my rough proposal goes through coercion, raising an error would require to check if the coerced element comes from the base ring, which seems very ugly..

I would be happy to see any better solution. I have zero experience about actions, so it will not be easy for me to implement what you suggest. Also, does it make sense to implement a "division" as an action?

[tscrim]

comment:7

I do plan on getting to this, I haven't quite had the time to do it. I should be able to do it in the next few days.

[kliem]

comment:8

Sorry, for some reason my key is not working (and I cannot push). Here is a proposal how to modify the branch and use coercion:

diff --git a/src/sage/rings/power_series_poly.pyx b/src/sage/rings/power_series_poly.pyx
index dc0c599a2c..42c4a5602c 100644
--- a/src/sage/rings/power_series_poly.pyx
+++ b/src/sage/rings/power_series_poly.pyx
@@ -720,7 +720,7 @@ cdef class PowerSeries_poly(PowerSeries):
 
         return self._parent(self.truncate().inverse_series_trunc(prec), prec=prec)
 
-    def _floordiv_(self, c):
+    def _floor_division_by_coefficient_(self, c):
         """
         Perform the exact division of ``self`` by a coefficient ``c``.
 
@@ -748,10 +748,14 @@ cdef class PowerSeries_poly(PowerSeries):
         """
         prec = self.prec()
         return PowerSeries_poly(self._parent,
-                                self.__f // (<PowerSeries_poly>c).__f[0],
+                                self.__f // c,
                                 prec=prec,
                                 check=False)
 
+    cpdef _acted_upon_(self, other, bint self_on_left):
+        if self_on_left and other in self.base_ring():
+            return self._floor_division_by_coefficient_(other)
+
     def truncate(self, prec=infinity):
         """
         The polynomial obtained from power series by truncation at
diff --git a/src/sage/rings/power_series_ring.py b/src/sage/rings/power_series_ring.py
index 0000a2daa3..88b60ebbe0 100644
--- a/src/sage/rings/power_series_ring.py
+++ b/src/sage/rings/power_series_ring.py
@@ -1288,6 +1288,12 @@ class PowerSeriesRing_domain(PowerSeriesRing_generic, ring.IntegralDomain):
         laurent = self.laurent_series_ring()
         return laurent.change_ring(self.base_ring().fraction_field())
 
+    def _get_action_(self, other, op, self_is_left):
+        import operator
+        from sage.structure.coerce_actions import ActedUponAction
+        if op is operator.floordiv and self_is_left and other is self.base_ring():
+            # Floor division by coefficient.
+            return ActedUponAction(other, self, not self_is_left)
 
 class PowerSeriesRing_over_field(PowerSeriesRing_domain):
     _default_category = CompleteDiscreteValuationRings()

In addition one can coerce the base ring as done in src/sage/geometry/polyhedron/parent.py in PolyhedronParent._get_action_ with PrecomposedAction.

[kliem]

Changed commit from eeb50ae to none

[kliem]

Changed branch from u/chapoton/34116 to u/gh-kliem/34116

[kliem]

comment:9

Using a different machine has worked. Still don't know, why pushing to trac doesn't work, but github is fine.

[sagetrac-git]

Commit: 64bb118

[sagetrac-git]

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

dc976ec	add floordiv for power series for exact division by one coefficient
64bb118	rough draft on how to use coercion for exact division of power series by coefficient

[fchapoton]

comment:11

Our trac machine is stuck on a version of ubuntu that does not recognize the recent versions of RSA as imposed on ubuntu 22.04..

[kliem]

comment:12

Replying to @fchapoton:

Our trac machine is stuck on a version of ubuntu that does not recognize the recent versions of RSA as imposed on ubuntu 22.04..

Thanks for letting me know. So at least everything is fine on my machine.

What I don't like about this current approach is that only one action may exist. As long as their is only floor division, everything is fine, but if one wants to implement a different action with a different operator, one is stuck. (There are work arounds by first converting the base ring element to some artificial FloorDivision class, but that doesn't seem better).

[tscrim]

Changed author from Frédéric Chapoton to Frédéric Chapoton, Jonathan Kliem, Travis Scrimshaw

[tscrim]

comment:13

Thank you for doing this. This is roughly what I was thinking, but I have changed it into an explicit action class. I also fixed a bug where it was not allowing for things that also coerce into the base ring.

@kliem I am not quite sure what you are worried about, but it sounds like you want things to magically work without having to implement them. What I mean is if you have a different ring with a different action, it will need to be implemented by someone. I think we can easily revisit this.

---

New commits:

d5b890b	Implementing a direct action.
c8a57e0	Allowing actions from things that coercion into the base ring as well.

[tscrim]

Changed branch from u/gh-kliem/34116 to public/rings/floor_division_power_series-34116

[tscrim]

Changed commit from 64bb118 to c8a57e0

[fchapoton]

comment:14

Thanks ! Looks great to me. If everybody agree, please set to positive.

[fchapoton]

Reviewer: Frédéric Chapoton

[kliem]

comment:15

Replying to @tscrim:

Thank you for doing this. This is roughly what I was thinking, but I have changed it into an explicit action class. I also fixed a bug where it was not allowing for things that also coerce into the base ring.

@kliem I am not quite sure what you are worried about, but it sounds like you want things to magically work without having to implement them. What I mean is if you have a different ring with a different action, it will need to be implemented by someone. I think we can easily revisit this.

You have already solved the problem by the explicit action class. I wasn't aware that this exists.

The problem with _acted_upon_ is that in only allows one action from A on B. E.g. we would have fixed that ZZ acts on ZZ[['x']] always be floor division (and not by any other operation). With the explicit action class one can later define a different action (I can't come up with something atm, but I hope my thoughts come across).

---

New commits:

d5b890b	Implementing a direct action.
c8a57e0	Allowing actions from things that coercion into the base ring as well.

[kliem]

Changed reviewer from Frédéric Chapoton to Frédéric Chapoton, Jonathan Kliem

[kliem]

comment:16

As we are implementing floor division and not exact division, it would be good to have one example, where this is actually different from exact division.

Otherwise lgtm.

[tscrim]

comment:17

Replying to @kliem:

As we are implementing floor division and not exact division, it would be good to have one example, where this is actually different from exact division.

@fchapoton @kliem Can one of you add the example? I am just out the door for today (I need dinner). Otherwise I will do it tomorrow morning when I get back into my office.

[tscrim]

comment:18

Replying to @kliem:

Replying to @tscrim:

Thank you for doing this. This is roughly what I was thinking, but I have changed it into an explicit action class. I also fixed a bug where it was not allowing for things that also coerce into the base ring.

@kliem I am not quite sure what you are worried about, but it sounds like you want things to magically work without having to implement them. What I mean is if you have a different ring with a different action, it will need to be implemented by someone. I think we can easily revisit this.

You have already solved the problem by the explicit action class. I wasn't aware that this exists.

The problem with _acted_upon_ is that in only allows one action from A on B. E.g. we would have fixed that ZZ acts on ZZ[['x']] always be floor division (and not by any other operation). With the explicit action class one can later define a different action (I can't come up with something atm, but I hope my thoughts come across).

Ah, I see. Thanks for explaining. Typically though, _acted_upon_ is used for the * action as a replacement for the _lmul_ and _rmul_ in more legacy code.

[sagetrac-git]

Changed commit from c8a57e0 to 209d54f

[sagetrac-git]

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

209d54f

adding one example in power series

[fchapoton]

comment:20

I have added an illustrating example.

[tscrim]

comment:21

Thank you. Jonathan, is that sufficient for you?

[tscrim]

comment:22

Bot is (morally) green.

[sagetrac-git]

Changed commit from 209d54f to 3525f06

[sagetrac-git]

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

3525f06

add another test

[kliem]

comment:24

This is what I was referring to. If you think this is good, you can set it to positive review or modify it.

[tscrim]

comment:25

LGTM. Thanks.

[vbraun]

Changed branch from public/rings/floor_division_power_series-34116 to 3525f06