Polynomial division by a unit scalar unexpectedly changes the base ring

[maxale]

Steps To Reproduce

We have

sage: K.<x> = QQ[]
sage: (x / x.base_ring().one()).parent() == x.parent()
True

which is expected. But then a similar division in another polynomial ring changes the base ring to Fraction Field of the original one:

sage: R.<y> = K[]
sage: (y / y.base_ring().one()).parent() == y.parent()
False
sage: (y / y.base_ring().one()).parent()
Univariate Polynomial Ring in y over Fraction Field of Univariate Polynomial Ring in x over Rational Field
sage: y.parent()
Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field

Expected Behavior

Division by a unit scalar (ie. an invertible element of the base ring) should not change the base ring of polynomials.

Actual Behavior

Sometimes it is changed as shown by the example above.

Additional Information

No response

Environment

• OS: Ubuntu 24.04.1 LTS
• Sage Version: 10.6.beta1

Checklist

• I have searched the existing issues for a bug report that matches the one I want to file, without success.
• I have read the documentation and troubleshoot guide

[DaveWitteMorris]

This is a design choice, not a bug.

If I understand correctly, the suggestion is that when sage divides a polynomial f by a scalar c, it should first check whether c is a unit, and use that information to decide what the parent of the result should be. My first impression is that this a bad idea. That would be slower (and make the code more complicated). It would also mean that the parent of the result depends on the particular scalar, not just its parent. Such a varying parent can lead to problems, so the wisdom of changing a method that works to such a design is highly questionable.

If a user knows that c is a unit, and wants to retain the parent, then I think they should multiply by the inverse of c, instead of dividing by c: f * c.inverse_of_unit(). If they do this a lot, they might want to write a function divide_by_unit (or a function divide_by_possible_unit that tests whether the scalar is a unit), but I am not at all convinced that sage should do this for the user.

[maxale]

I agree that testing c for being a unit may bear too much overhead, and this is not what I request. Let me restate the issue as I view it:

I understand the division of polynomial f by a scalar c as the result of f.map_coefficients(lambda t: t/c). Continuing my example above, we do have x/x.base_ring().one() and x.map_coefficients(lambda t: t/x.base_ring().one()) producing (equal) polynomials with the same parent, but this is not the case for y:

sage: y.map_coefficients( lambda t: t/y.base_ring().one() ).parent()
Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field
sage: (y/y.base_ring().one()).parent()
Univariate Polynomial Ring in y over Fraction Field of Univariate Polynomial Ring in x over Rational Field

In my view, here y.map_coefficients( lambda t: t/y.base_ring().one() ) produces the result with correct parent, while y/y.base_ring().one() does not, and this is what I complain about.

[maxale]

Btw, it does look like a bug to me, not an enhancement. Please restore the bug label.

[DaveWitteMorris]

No, it's not a bug.

Sagemath is a collaborative effort. You may have a particular point of view (or a particular implementation in mind) that makes you think the program should behave a certain way, but please understand that there can be other reasonable viewpoints or implementations that represent different choices, not bugs.

In this particular case, I think division by a scalar is implemented as multiplication by the inverse of the scalar, because part of y.__truediv__?? is:

        # Try division of polynomial by a scalar
        if isinstance(left, Polynomial):
            R = (<Polynomial>left)._parent._base
            try:
                x = R.coerce(right)
                return left * ~x
            except TypeError:
                pass

This seems very reasonable to me, and I'm not at all convinced that your suggestion is better.

[nbruin]

The coercion framework bases its coercions on the parents; not on the particular values of the elements. So in your case, by dividing an element of R by an element in K needs a new parent, since not all elements of K have an inverse in K (or in R). The transcript below shows how the coercion model discovers what to do:

sage: K.<x>=QQ[]
sage: R.<y>=K[]
sage: coercion_model.explain(R,K,operator.truediv)
Action discovered.
    Right inverse action by Fraction Field of Univariate Polynomial Ring in x over Rational Field on Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field
    with precomposition on right by Coercion map:
      From: Univariate Polynomial Ring in x over Rational Field
      To:   Fraction Field of Univariate Polynomial Ring in x over Rational Field
Result lives in Univariate Polynomial Ring in y over Fraction Field of Univariate Polynomial Ring in x over Rational Field
Univariate Polynomial Ring in y over Fraction Field of Univariate Polynomial Ring in x over Rational Field

You could use euclidean division instead. It does not need to construct an inverse:

sage: parent(y//K(1))
Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field
sage: coercion_model.explain(R,K,operator.floordiv)
Coercion on right operand via
    Polynomial base injection morphism:
      From: Univariate Polynomial Ring in x over Rational Field
      To:   Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field
Arithmetic performed after coercions.
Result lives in Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field
Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field

The example with y/K(1) really can't behave differently, because the coercion system doesn't look at individual values. That's perhaps most concisely summarized by parent(1/1). In other words, the "expected behaviour" as listed: 'Division by a unit scalar (ie. an invertible element of the base ring) should not change the base ring of polynomials.' cannot be attained for scalar rings in which not all non-zero elements are units.

It looks like there is an inconsistency, though:

sage: coercion_model.explain(R,QQ,operator.truediv)
Action discovered.
    Right inverse action by Rational Field on Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field
Result lives in Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field
Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field

indicates that the coercion system is able to find an action of QQ on R, but it does not look like that is what is actually used:

sage: parent(y/QQ(1))
Univariate Polynomial Ring in y over Fraction Field of Univariate Polynomial Ring in x over Rational Field

The latter does seem like a reportable bug that is hopefully easy to fix. Perhaps you want to repurpose this issue for that?

[DaveWitteMorris]

I think the code snippet in my comment shows that __truediv__ coerces the scalar into the base ring of the polynomial ring (and then inverts it). It doesn't look for an action of QQ on R.

[nbruin]

Indeed, it does seem to do that. So one fix would be to remove that special case, because this example shows we may end up with the wrong parents: QQ does have an action on QQ['x']['y']; it is not necessary to treat this via the scalar multiplication of QQ['x'] on QQ['x']['y']. That might give a performance regression: the coercion framework tries very hard to cause a low overhead, but this workaround might have been put in for a reason. In that case it should be guarded a little more carefully so that in doesn't cause these too-general coercions.

Digging in the "blame" of those lines suggests the special case was there since very early on and that the proper use of the coercion system was tacked on afterwards. So there's a good chance that this code was just inherited and never properly reviewed when the coercion system got into its current state.

[nbruin]

Some simple timings indicate the "shortcut" of trying to coerce the scalar into the base ring and invert there doesn't seem to save much in time. In the case where the new parent needs to be constructed they seem to be equivalent:

sage: K.<x>=QQ[]
sage: R.<y>=K[]
sage: truediv = operator.truediv
sage: %timeit y/x
27.3 µs ± 1.6 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
sage: %timeit coercion_model.bin_op(y,x,truediv)
28.2 µs ± 79.4 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In the case where the action of a smaller ring means the parent doesn't need to be extended, we of course get way better performance:

sage: %timeit y/1
26.3 µs ± 105 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
sage: %timeit coercion_model.bin_op(y,1,truediv)
1.16 µs ± 8.37 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

And finally, if we're already working in a parent where x is invertible, the two methods are also about the same:

sage: K.<x>=FunctionField(QQ)
sage: R.<y>=K[]
sage: %timeit y/x
16.1 µs ± 115 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
sage: %timeit coercion_model.bin_op(y,x,truediv)
16.5 µs ± 447 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

So I expect that removal of the attempted scalar conversion can just be removed and that we get better behaviour and similar performance by just letting the coercion framework do its work.

[maxale]

Somewhat related issue #37544 with the parent ring scrambling.