Degree of the zero polynomial ring for `LaurentPolynomialRing`

[Giacomo Pope]

While chasing various bugs which appeared in the CI, I ended up adding a small method for computing random elements for the LaurentPolynomialRing class.

When writing randomised testing I got myself confused about the degree of the zero polynomial. For the univariate and multivariate polynomial rings, we currently use that the degree for 0 (both R(0).degree() as well as R(0).degree(x)) is -1. This is unambiguous for the case of these types.

However for the LaurentPolynomialRings, a polynomial with negative valuation is very natural. For example the following code snippet shows the ambiguity.

sage: L.<x> = LaurentPolynomialRing(QQ)
sage: f = (1/x); f
x^-1
sage: f.degree()
-1
sage: L.zero().degree()
-1

I don't feel familiar enough with the mathematics here and the usual use cases in sage to offer a PR "fixing" this, or whether it even needs fixing. However, I got confused so I thought maybe others might get confused and someone on this list might have a suggestion.

I think the "usual" suggestion would be to have the degree as -infty, but then there's a question about whether this should be done for other polynomial rings...

I made an issue for this on GitHub too:

https://github.com/sagemath/sage/issues/37491

[Martin R]

LazyLaurentSeriesRing(QQ) currently gives +Infinity.

[Giacomo Pope]

This is not what I see on the current beta:

sage: R.<x> = LaurentSeriesRing(QQ)
sage: R.zero().degree()
-1
sage: R.<x> = LazyLaurentSeriesRing(QQ)
sage: R.zero().degree()
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[4], line 1
----> 1 R.zero().degree()

File ~/sage/sage/src/sage/structure/element.pyx:489, in sage.structure.element.Element.__getattr__()
    487         AttributeError: 'LeftZeroSemigroup_with_category.element_class' object has no attribute 'blah_blah'...
    488     """
--> 489     return self.getattr_from_category(name)
    490
    491 cdef getattr_from_category(self, name) noexcept:

File ~/sage/sage/src/sage/structure/element.pyx:502, in sage.structure.element.Element.getattr_from_category()
    500     else:
    501         cls = P._abstract_element_class
--> 502     return getattr_from_other_class(self, cls, name)
    503
    504 def __dir__(self):

File ~/sage/sage/src/sage/cpython/getattr.pyx:357, in sage.cpython.getattr.getattr_from_other_class()
    355     dummy_error_message.cls = type(self)
    356     dummy_error_message.name = name
--> 357     raise AttributeError(dummy_error_message)
    358 cdef PyObject* attr = instance_getattr(cls, name)
    359 if attr is NULL:

AttributeError: 'LazyLaurentSeriesRing_with_category.element_class' object has no attribute 'degree'

[Martin R]

Sorry, I confused it with valuation, but I guess it is still a related question.

[Giacomo Pope]

Ahh ok, thank you. Considering the following output I think a PR to make the degree of zero for these Laurent classes -Infinity is reasonable?

```

sage: R.<x> = LaurentSeriesRing(QQ)

sage: R.zero().valuation()
+Infinity
sage: R.zero().degree()
-1
sage:
sage: R.<x> = LaurentPolynomialRing(QQ)
sage: R.zero().valuation()
+Infinity
sage: R.zero().degree()
-1
sage:

sage: R.<x> = LazyLaurentSeriesRing(QQ)

sage: R.zero().valuation()
+Infinity
sage: R.zero().degree()

# Errors

[Martin R]

Yes, I'd say so.

[Dima Pasechnik]

in the polynomial case, the usual convention is deg(0)=-infinity

I don't know why Sage uses -1 instead:
R.<x,y>=QQ[]
f=0*x*y
f.degree()

gives -1.

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/c9c805f9-fbd0-4591-8729-002f3ad90fa1n%40googlegroups.com.

[Giacomo Pope]

Not a "maths" why, but I know anything which uses singular currently returns -1 because of the following snippet

cdef long singular_polynomial_deg(poly *p, poly *x, ring *r) noexcept:
    cdef long _deg, deg
    cdef int dummy

    deg = -1
    _deg = -1
    if p == NULL:
        return -1
    ...

I don't know the history of this choice or what we should be doing generally. -1 for polynomials with only positive degree seems like a computer science workaround, but for the LaurentPolynomialRing it just seems wrong?

[Nils Bruin]

On Wednesday 28 February 2024 at 08:03:45 UTC-8 Giacomo Pope wrote:

I don't know the history of this choice or what we should be doing generally. -1 for polynomials with only positive degree seems like a computer science workaround, but for the LaurentPolynomialRing it just seems wrong?

I think it's more than just a CS workaround. It has its roots in dimension considerations: the space of polynomials of degree at most d is (d+1)-dimensional. WIth that convention, 0 having degree -1 makes perfect sense.

For deg = - ord_infty it should definitely be -oo, though, and for Laurent polynomials the dimension argument doesn't work.

[Dima Pasechnik]

On Wed, Feb 28, 2024 at 5:00 PM Nils Bruin <nbr...@sfu.ca> wrote:

On Wednesday 28 February 2024 at 08:03:45 UTC-8 Giacomo Pope wrote:

I don't know the history of this choice or what we should be doing generally. -1 for polynomials with only positive degree seems like a computer science workaround, but for the LaurentPolynomialRing it just seems wrong?

I think it's more than just a CS workaround. It has its roots in dimension considerations: the space of polynomials of degree at most d is (d+1)-dimensional. WIth that convention, 0 having degree -1 makes perfect sense.

well, it's the convention used in Singular.

But GAP and Macaulay2 use -infinity.

The arguments for -infinity:

1) degree of the product should be the sum of degrees; so it's got to be infinite.

2) it should be -infinity, to make sense of the rule that if you do division f/g with remainder r,

the degree of the remainder should be less than the deg(r)<=deg(f), but if r=0 then the only way

to get this is to use -infinity.

Dima

 

For deg = - ord_infty it should definitely be -oo, though, and for Laurent polynomials the dimension argument doesn't work.

--

You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/ac40d2e7-5e71-43e1-8914-869081f9bdd9n%40googlegroups.com.

[Giacomo Pope]

There seem to be two things we could do here:

1. Have some form of vote / discussion on whether the degree of the zero polynomial should *ever* be -1
2. Modify the degree calls for the LaurentSeries and LaurentPolynomialRing (maybe other Laurent* which I am unfamiliar with) to have the zero polynomial have degree -Infinity.

Option 1 may be cleaner in the long run, but I assume will cause issues for more people in the short term. Option 2 seems fairly harmless and there's no good argument for degree -1 in this case.

If anyone is interested in option 2, I will find time to make a PR to do this, but I will not start this work without other people's input as this is not code I am familiar with using and so I don't know what people could be relying on.

[Oscar Benjamin]

I recently reviewed cases in the sympy polys code that handle the
degree of a zero polynomial:
https://github.com/sympy/sympy/pull/25784

My conclusion is that it is sometimes useful that deg(0) < deg(p) for
p != 0 but otherwise it is not really possible to use the value of
deg(0) for anything meaningful in practice. Generally if deg(p) is
needed then the zero polynomial needs special handling that no
particular value of deg(0) helps with. I would prefer that deg(0) = -1
just so that the deg() function has a well defined type.

For Laurent polynomials I am not sure that I would define a degree()
method or if I did that it would be defined as the exponent of the
leading term. It isn't clear to me when that notion of degree would be
useful: it doesn't seem like it would generalise the ways that degree
is typically used for ordinary polynomials.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/6d95b253-fb17-4e2f-a61c-c723737774e8n%40googlegroups.com.

[John Cremona]

There may be case for leaving deg(0) undefined both for polynomials and Laurent polynomials (and power series and Laurent series): it's at best a shorthand (pace Nils' comment about dimensions) and needs to be handled separately in code.  So calling deg(0) could raise a ValueError or ArithmeticError (just as "factor(0)" does)?

John

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAHVvXxRe119u%3Dy-xk1O-BvWH_f1xxnHsuQCzZm_4xYRD-_NEFw%40mail.gmail.com.

[Dima Pasechnik]

On Thu, Feb 29, 2024 at 4:34 PM Oscar Benjamin <oscar.j....@gmail.com> wrote:

I recently reviewed cases in the sympy polys code that handle the
degree of a zero polynomial:
https://github.com/sympy/sympy/pull/25784

My conclusion is that it is sometimes useful that deg(0) < deg(p) for
p != 0 but otherwise it is not really possible to use the value of
deg(0) for anything meaningful in practice. Generally if deg(p) is
needed then the zero polynomial needs special handling that no
particular value of deg(0) helps with. I would prefer that deg(0) = -1
just so that the deg() function has a well defined type.

How about using something like https://github.com/NeilGirdhar/extended_int ?

(Even better, do a PEP to have such a thing in Python proper...)

In old, totally duck-typed, Python this didn't really matter, but nowadays it does make

a perfect sense.

 

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAHVvXxRe119u%3Dy-xk1O-BvWH_f1xxnHsuQCzZm_4xYRD-_NEFw%40mail.gmail.com.

[Nils Bruin]

On Thursday 29 February 2024 at 11:15:21 UTC-8 Dima Pasechnik wrote:

How about using something like https://github.com/NeilGirdhar/extended_int ?

(Even better, do a PEP to have such a thing in Python proper...)

In old, totally duck-typed, Python this didn't really matter, but nowadays it does make

a perfect sense.

At the moment, I think most degree functions do their best to return sage Integer objects; mainly so that coercion works well with them. So whatever solution we use should probably be based on objects that naturally live in the sage hierarchy. We do have an infinity object in sage and it already gets used for valuations.

Incidentally:

 sage: R.<x>=LaurentSeriesRing(QQ)
sage: z=R(0)
sage: z.valuation()
+Infinity
sage: z.degree()
-1

I don't quite know why laurent series have a degree defined at all, but they're keeping to the deg(0)=-1 convention.

Incidentally:

sage: A.<x>=QQ[]
sage: B.<y>=LaurentPolynomialRing(QQ)
sage: x.valuation(oo)
-1
sage: y.valuation(oo)
1

so polynomial rings have a valuation (that will return +oo when appropriate), but on LaurentPolynomialRing this gets silently broken: the argument simply gets ignored and the valuation at 0 is returned. So I guess you can get a well-behaving degree with

f=0*y

-f(1/y).valuation()

[Martin R]

I'd be OK with raising an exception or with -oo, but it should be uniform, and I think it should be the same for polynomials, Laurent polynomials and in the same spirit for degree and valuation.

It might be best to raise an exception, because this ensures that the zero polynomial gets special treatment.

Martin

[Gareth Ma]

I lean towards setting it to -∞.

While we are at this, how should `R.random_element` be called? The method currently takes a `degree` argument, which is a tuple of lower and upper bound, and if the user sets the lower bound to -1, then `0` is a possible outcome. Would the user call it with `degree=(-oo, upper_bound)` instead in the future?

Best regards,
Gareth

--

You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/ec50bffa-37ef-4bee-9095-09e738be1842n%40googlegroups.com.

[Gareth Ma]

And that will be a problem when `R` is a laurent polynomial ring.

[Dima Pasechnik]

On 1 March 2024 09:07:26 GMT, 'Martin R' via sage-devel <sage-...@googlegroups.com> wrote:
>I'd be OK with raising an exception or with -oo, but it should be uniform,
>and I think it should be the same for polynomials, Laurent polynomials and
>in the same spirit for degree and valuation.
>
>It might be best to raise an exception, because this ensures that the zero
>polynomial gets special treatment.

Exceptions are expensive, performance-wise, and using them as a regular means of controlling the flow of the algorithm execution is not a good idea.
A simple if/then/else is much cheaper.

Dima

[John Cremona]

On Fri, 1 Mar 2024 at 10:04, Dima Pasechnik <dim...@gmail.com> wrote:

On 1 March 2024 09:07:26 GMT, 'Martin R' via sage-devel <sage-...@googlegroups.com> wrote:
>I'd be OK with raising an exception or with -oo, but it should be uniform,
>and I think it should be the same for polynomials, Laurent polynomials and
>in the same spirit for degree and valuation.
>
>It might be best to raise an exception, because this ensures that the zero
>polynomial gets special treatment.

Exceptions are expensive, performance-wise, and using them as a regular means of controlling the flow of the algorithm execution is not a good idea.
A simple  if/then/else  is much cheaper.

Isn't this suggestion to have f.degree() raise an exception when f is zero, but also then that any code which needs the degree to treat 0 as a special case (where that makes sense)?   To it would be the caller's responsibility to do that with a test of f.is_zero() or whatever, rather than by seeing if an exception is triggered.

John

 

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/D20DACD9-8D5A-48F4-81F5-141CF0181BA1%40gmail.com.

[Dima Pasechnik]

On Fri, Mar 1, 2024 at 10:24 AM John Cremona <john.c...@gmail.com> wrote:

On Fri, 1 Mar 2024 at 10:04, Dima Pasechnik <dim...@gmail.com> wrote:

On 1 March 2024 09:07:26 GMT, 'Martin R' via sage-devel <sage-...@googlegroups.com> wrote:
>I'd be OK with raising an exception or with -oo, but it should be uniform,
>and I think it should be the same for polynomials, Laurent polynomials and
>in the same spirit for degree and valuation.
>
>It might be best to raise an exception, because this ensures that the zero
>polynomial gets special treatment.

Exceptions are expensive, performance-wise, and using them as a regular means of controlling the flow of the algorithm execution is not a good idea.
A simple  if/then/else  is much cheaper.

Isn't this suggestion to have f.degree() raise an exception when f is zero, but also then that any code which needs the degree to treat 0 as a special case (where that makes sense)?   To it would be the caller's responsibility to do that with a test of f.is_zero() or whatever, rather than by seeing if an exception is triggered.

Letting degree(0) throw an exception means that every place where you want to test whether the degree of fg satisfies something needs a testing whether f or g is 0, in order to avoid an exception.

OTOH, setting the degree of 0 to be -oo has an obvious advantage: it automaticlly gives mathematically correct degree of fg, by using degree(fg)=degree(f)+degree(g), regardless of f or g being 0. And checking the degree is (or at least ought to be) faster than comparing for equality to 0.

Yes, it requires a change of the mental picture somehow. But same applies for e.g. using projective setting instead of affine one in geometry: you don't need to throw a mental exception as soon as you get parallel lines :-)

Dima

 

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAD0p0K45r2ishqx4kzEwuVF9%3DYDtojjteBn3snKMkGj8ijb72g%40mail.gmail.com.

[John Cremona]

On Fri, 1 Mar 2024 at 11:03, Dima Pasechnik <dim...@gmail.com> wrote:

On Fri, Mar 1, 2024 at 10:24 AM John Cremona <john.c...@gmail.com> wrote:

On Fri, 1 Mar 2024 at 10:04, Dima Pasechnik <dim...@gmail.com> wrote:

On 1 March 2024 09:07:26 GMT, 'Martin R' via sage-devel <sage-...@googlegroups.com> wrote:
>I'd be OK with raising an exception or with -oo, but it should be uniform,
>and I think it should be the same for polynomials, Laurent polynomials and
>in the same spirit for degree and valuation.
>
>It might be best to raise an exception, because this ensures that the zero
>polynomial gets special treatment.

Exceptions are expensive, performance-wise, and using them as a regular means of controlling the flow of the algorithm execution is not a good idea.
A simple  if/then/else  is much cheaper.

Isn't this suggestion to have f.degree() raise an exception when f is zero, but also then that any code which needs the degree to treat 0 as a special case (where that makes sense)?   To it would be the caller's responsibility to do that with a test of f.is_zero() or whatever, rather than by seeing if an exception is triggered.

Letting degree(0) throw an exception means that every place where you want to test whether the degree of fg satisfies something needs a testing whether f or g is 0, in order to avoid an exception.

Fair enough.  I had been assuming that for the types we are talking about testing for equality with 0 would be fast, but perhaps it is not.

 

OTOH, setting the degree of 0 to be -oo has an obvious advantage: it automaticlly gives mathematically correct degree of fg, by using degree(fg)=degree(f)+degree(g), regardless of f or g being 0. And checking the degree is (or at least ought to be) faster than comparing for equality to 0.

It's a little dangerous to talk of -oo being "mathematically correct", but I have given this definition myself in undergraduate course (and for the reason you give) so that's ok, especially as in Sage we do have -oo as a possible return value and no requiremt for the value to always be of the same type (e.g. Integer).

 

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAAWYfq0zF8ARVr_FbbKd7WAhM8t6cBSqegXZzKsSSx1Au5mFMw%40mail.gmail.com.

[Oscar Benjamin]

On Fri, 1 Mar 2024 at 11:15, John Cremona <john.c...@gmail.com> wrote:
>
> On Fri, 1 Mar 2024 at 11:03, Dima Pasechnik <dim...@gmail.com> wrote:
>>
>> On Fri, Mar 1, 2024 at 10:24 AM John Cremona <john.c...@gmail.com> wrote:
>>>
>>> On Fri, 1 Mar 2024 at 10:04, Dima Pasechnik <dim...@gmail.com> wrote:
>>>>
>>>>
>>>>
>>>> On 1 March 2024 09:07:26 GMT, 'Martin R' via sage-devel <sage-...@googlegroups.com> wrote:
>>>> >I'd be OK with raising an exception or with -oo, but it should be uniform,
>>>> >and I think it should be the same for polynomials, Laurent polynomials and
>>>> >in the same spirit for degree and valuation.
>>>> >
>>>> >It might be best to raise an exception, because this ensures that the zero
>>>> >polynomial gets special treatment.
>>>>
>>>> Exceptions are expensive, performance-wise, and using them as a regular means of controlling the flow of the algorithm execution is not a good idea.
>>>> A simple if/then/else is much cheaper.
>>>
>>>
>>> Isn't this suggestion to have f.degree() raise an exception when f is zero, but also then that any code which needs the degree to treat 0 as a special case (where that makes sense)? To it would be the caller's responsibility to do that with a test of f.is_zero() or whatever, rather than by seeing if an exception is triggered.
>>
>>
>> Letting degree(0) throw an exception means that every place where you want to test whether the degree of fg satisfies something needs a testing whether f or g is 0, in order to avoid an exception.
>
>
> Fair enough. I had been assuming that for the types we are talking about testing for equality with 0 would be fast, but perhaps it is not.

If p.degree() can do this quickly then there is no reason that some
other function couldn't be made to return the equivalent of p.degree()
< 0 quickly. It would sometimes be a bit awkward though for deg(0) to
raise an exception. I see examples of code in sympy where e.g. the
degrees of polynomials are reduced in a loop and having deg(0) < 0
naturally captures the the control flow that is needed.

>> OTOH, setting the degree of 0 to be -oo has an obvious advantage: it automaticlly gives mathematically correct degree of fg, by using degree(fg)=degree(f)+degree(g), regardless of f or g being 0. And checking the degree is (or at least ought to be) faster than comparing for equality to 0.

Do you see examples where arithmetic with degree(0) is used in practice?

When I looked for these in the sympy code I didn't find any even
though the -oo convention was used. I just don't think it comes up in
real code.

> It's a little dangerous to talk of -oo being "mathematically correct", but I have given this definition myself in undergraduate course (and for the reason you give) so that's ok, especially as in Sage we do have -oo as a possible return value and no requiremt for the value to always be of the same type (e.g. Integer).

There might not be any "requirement" for degree() to return objects of
the same type but from a computational perspective it is generally
better to use well defined types. Python allows mixing types up but
that doesn't make it a good idea to do so especially in performance
sensitive code.

--
Oscar

[Martin R]

On Friday 1 March 2024 at 12:15:36 UTC+1 John Cremona wrote:

On Fri, 1 Mar 2024 at 11:03, Dima Pasechnik <dim...@gmail.com> wrote:

On Fri, Mar 1, 2024 at 10:24 AM John Cremona <john.c...@gmail.com> wrote:

On Fri, 1 Mar 2024 at 10:04, Dima Pasechnik <dim...@gmail.com> wrote:

On 1 March 2024 09:07:26 GMT, 'Martin R' via sage-devel <sage-...@googlegroups.com> wrote:
>I'd be OK with raising an exception or with -oo, but it should be uniform,
>and I think it should be the same for polynomials, Laurent polynomials and
>in the same spirit for degree and valuation.
>
>It might be best to raise an exception, because this ensures that the zero
>polynomial gets special treatment.

Exceptions are expensive, performance-wise, and using them as a regular means of controlling the flow of the algorithm execution is not a good idea.
A simple  if/then/else  is much cheaper.

Isn't this suggestion to have f.degree() raise an exception when f is zero, but also then that any code which needs the degree to treat 0 as a special case (where that makes sense)?   To it would be the caller's responsibility to do that with a test of f.is_zero() or whatever, rather than by seeing if an exception is triggered.

Exactly, sorry for being unclear.  try - except would certainly be out of place in this case.

Letting degree(0) throw an exception means that every place where you want to test whether the degree of fg satisfies something needs a testing whether f or g is 0, in order to avoid an exception.

Yes indeed - unless you already know that the polynomial is non-zero.

 

Fair enough.  I had been assuming that for the types we are talking about testing for equality with 0 would be fast, but perhaps it is not.

I just found that Polynomial.is_zero checks whether degree is negative, and degree is `return smallInteger(len(self._coeffs) - 1)`, for flint polynomials it is `return smallInteger(fmpq_poly_degree(self._poly))`.  So, indeed, either change would come with a cost.

OTOH, setting the degree of 0 to be -oo has an obvious advantage: it automaticlly gives mathematically correct degree of fg, by using degree(fg)=degree(f)+degree(g), regardless of f or g being 0. And checking the degree is (or at least ought to be) faster than comparing for equality to 0.

It's a little dangerous to talk of -oo being "mathematically correct", but I have given this definition myself in undergraduate course (and for the reason you give) so that's ok, especially as in Sage we do have -oo as a possible return value and no requiremt for the value to always be of the same type (e.g. Integer).

I would rather say that "-1" is in some cases "mathematically incorrect", in particular for Laurent polynomials :-)

To make it clear, I am not against -oo, I find -1 quite problematic (for user facing code, and because I really want uniformity for polynomials and Laurent polynomials and their series variants), and I think that raising an exception should be best performance-wise, but probably most work.

Best wishes,

Martin

[Oscar Benjamin]

What exactly is the "mathematically correct" meaning of "degree" for
Laurent polynomials?

I haven't seen other examples where this is defined except Matlab
which defines it differently from Sage:

https://uk.mathworks.com/help/wavelet/ref/laurentpolynomial.degree.html

The Matlab definition is basically that deg(p(x)*x^m) = deg(p(x)).
This means that for nonzero Laurent polynomials the degree is always
nonnegative. Here deg(x^m) = 0 i.e. the degree of a unit is always 0.

I haven't thought much about this but this definition of degree seems
consistent with the notion of degree as a Euclidean function that can
define Euclidean division. In the sympy polynomial code all uses of
degree are in the polynomial division, gcd and factor code because the
main use of degree is in defining division.

Oscar

[Dima Pasechnik]

a natural way to program long division of univariate polynomial n by univariate polynomial d,

to get n=dq+r can folllow Wikipedia's https://en.wikipedia.org/wiki/Polynomial_long_division#Pseudocode

There they have the condion 

while r ≠ 0 and degree(r) ≥ degree(d) do

 

which with the convention degree(0)=-oo can be simplified to

while degree(r) ≥ degree(d) do

 

here of course any negative degree(0) will work, e.g. -1, not only -oo.

It seems that exactly the same algorithm will work (I didn't check this!) for Laurent polynomials (they still form a Euclidean domain), and there you better set degree(0)=-oo, otherwise it's going to be a problem.

 

Dima

> It's a little dangerous to talk of -oo being "mathematically correct", but I have given this definition myself in undergraduate course (and for the reason you give) so that's ok, especially as in Sage we do have -oo as a possible return value and no requiremt for the value to always be of the same type (e.g. Integer).

There might not be any "requirement" for degree() to return objects of
the same type but from a computational perspective it is generally
better to use well defined types. Python allows mixing types up but
that doesn't make it a good idea to do so especially in performance
sensitive code.

--
Oscar

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAHVvXxRDh1y6h3PiRZNAzT50DJAfgLGMxzhdMVrV1SiNWHO24w%40mail.gmail.com.

[Nils Bruin]

On Friday 1 March 2024 at 04:26:43 UTC-8 Dima Pasechnik wrote:

 

It seems that exactly the same algorithm will work (I didn't check this!) for Laurent polynomials (they still form a Euclidean domain), and there you better set degree(0)=-oo, otherwise it's going to be a problem.

I think it's been established that LaurentPolynomialRing(QQ,'x').zero().degree() == -1 is problematic. With the definition that (1/x).degree() == -1 it clearly is.

I think the question is more: do we have enough evidence that setting degree(0) == -oo for *all* polynomial rings is significantly better (if better at all) that it's worth the pain and incompatibilities that would ensue from changing the rest of sage as well? That's not so clear to me. From the perspective of multivariate polynomials, the whole valuation interpretation of "degree" goes out of the window, so there "-1" is largely available and quite possibly used extensively by the underlying libraries.

I guess one could see what happens if the change is made to Laurent polynomials (and Laurent series as well, perhaps?). Based on how that goes one could re-evaluate degrees of 0 polynomials in other polynomial rings.

Alternatively, we could deprecate degree on them in favour of using valuation-inspired terms instead, where the extension val(0)=oo is more universal. As Oscar's example in Matlab shows, the concept of degree gets (mis)used for other, more implementation-oriented definitions as well, so perhaps the term should just be avoided for Laurent polynomials.

[Martin R]

Could you expand on 'the whole valuation interpretation of "degree" goes out of the window'?  What do you mean with "valuation interpretation"?

Is raising an exception out of the question?

[Giacomo Pope]

Following this discussion, I have made a draft PR to change the degree for *only* the LaurentPolynomialRing and I will see if the CI detects anything.

https://github.com/sagemath/sage/pull/37513

I agree that if we change the LaurentPolynomialRing we should also change the `LaurentSeriesRing`, at the moment `LazyLaurentSeriesRing` has no method `degree()` but *does* have a `valuation()` method... so this is odd.

[Martin R]

I don't understand - `degree` doesn't make much sense for Laurent series - there is no way to determine the degree of a LaurentSeries and no way to determine the degree of a LazyLaurentSeries with one minor exception - which is when it is known that the series terminates, but that's rare.

[Dima Pasechnik]

On Fri, Mar 1, 2024 at 5:11 PM Nils Bruin <nbr...@sfu.ca> wrote:

On Friday 1 March 2024 at 04:26:43 UTC-8 Dima Pasechnik wrote:

 

It seems that exactly the same algorithm will work (I didn't check this!) for Laurent polynomials (they still form a Euclidean domain), and there you better set degree(0)=-oo, otherwise it's going to be a problem.

I think it's been established that LaurentPolynomialRing(QQ,'x').zero().degree() == -1 is problematic. With the definition that (1/x).degree() == -1 it clearly is.

I think the question is more: do we have enough evidence that setting degree(0) == -oo for *all* polynomial rings is significantly better (if better at all) that it's worth the pain and incompatibilities that would ensue from changing the rest of sage as well? That's not so clear to me. From the perspective of multivariate polynomials, the whole valuation interpretation of "degree" goes out of the window, so there "-1" is largely available and quite possibly used extensively by the underlying libraries.

IMHO deg(0)=-1 was chosen by Singular long time ago for purely practical programming reasons: in C++ one has to jump  through too many hoops in order to add +oo/-oo to Z, as a type (and it was much harder still in old-style C++ than it is now). (probably similarly for sympy).

As I mentioned, both Macaulay2 and GAP have convertion deg(0)=-oo.

For multivariate Laurent series total degree, indeed, makes little sense, one has to talk about vectors of degrees. Perhaps for an n-variate Laurent series one should choose deg(0)=(-oo,-oo,...,-oo).

Dima

 

I guess one could see what happens if the change is made to Laurent polynomials (and Laurent series as well, perhaps?). Based on how that goes one could re-evaluate degrees of 0 polynomials in other polynomial rings.

Alternatively, we could deprecate degree on them in favour of using valuation-inspired terms instead, where the extension val(0)=oo is more universal. As Oscar's example in Matlab shows, the concept of degree gets (mis)used for other, more implementation-oriented definitions as well, so perhaps the term should just be avoided for Laurent polynomials.

--

You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/60c42d22-28dc-4221-96a0-b174585c9c23n%40googlegroups.com.

[Dima Pasechnik]

On Fri, Mar 1, 2024 at 5:58 PM 'Martin R' via sage-devel <sage-...@googlegroups.com> wrote:

I don't understand - `degree` doesn't make much sense for Laurent series - there is no way to determine the degree of a LaurentSeries and no way to determine the degree of a LazyLaurentSeries with one minor exception - which is when it is known that the series terminates, but that's rare.

with series (power series, or formal Laurent series) the degree is naturally the minimal degree,

not the maximal one. (for a non-0 series; ought to be -oo for 0).

On Friday 1 March 2024 at 18:49:15 UTC+1 Giacomo Pope wrote:

Following this discussion, I have made a draft PR to change the degree for *only* the LaurentPolynomialRing and I will see if the CI detects anything.

https://github.com/sagemath/sage/pull/37513

I agree that if we change the LaurentPolynomialRing we should also change the `LaurentSeriesRing`, at the moment `LazyLaurentSeriesRing` has no method `degree()` but *does* have a `valuation()` method... so this is odd.

On Friday, March 1, 2024 at 5:29:53 PM UTC Martin R wrote:

Could you expand on 'the whole valuation interpretation of "degree" goes out of the window'?  What do you mean with "valuation interpretation"?

Is raising an exception out of the question?

On Friday 1 March 2024 at 18:11:40 UTC+1 Nils Bruin wrote:

On Friday 1 March 2024 at 04:26:43 UTC-8 Dima Pasechnik wrote:

 

It seems that exactly the same algorithm will work (I didn't check this!) for Laurent polynomials (they still form a Euclidean domain), and there you better set degree(0)=-oo, otherwise it's going to be a problem.

I think it's been established that LaurentPolynomialRing(QQ,'x').zero().degree() == -1 is problematic. With the definition that (1/x).degree() == -1 it clearly is.

I think the question is more: do we have enough evidence that setting degree(0) == -oo for *all* polynomial rings is significantly better (if better at all) that it's worth the pain and incompatibilities that would ensue from changing the rest of sage as well? That's not so clear to me. From the perspective of multivariate polynomials, the whole valuation interpretation of "degree" goes out of the window, so there "-1" is largely available and quite possibly used extensively by the underlying libraries.

I guess one could see what happens if the change is made to Laurent polynomials (and Laurent series as well, perhaps?). Based on how that goes one could re-evaluate degrees of 0 polynomials in other polynomial rings.

Alternatively, we could deprecate degree on them in favour of using valuation-inspired terms instead, where the extension val(0)=oo is more universal. As Oscar's example in Matlab shows, the concept of degree gets (mis)used for other, more implementation-oriented definitions as well, so perhaps the term should just be avoided for Laurent polynomials.

--

You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/b6ede155-fb29-4607-be7b-b028ce39e973n%40googlegroups.com.

[Martin R]

On Friday 1 March 2024 at 19:03:35 UTC+1 Dima Pasechnik wrote:

On Fri, Mar 1, 2024 at 5:58 PM 'Martin R' via sage-devel <sage-...@googlegroups.com> wrote:

I don't understand - `degree` doesn't make much sense for Laurent series - there is no way to determine the degree of a LaurentSeries and no way to determine the degree of a LazyLaurentSeries with one minor exception - which is when it is known that the series terminates, but that's rare.

with series (power series, or formal Laurent series) the degree is naturally the minimal degree,

not the maximal one. (for a non-0 series; ought to be -oo for 0).

I am very much against this.  I realise that this is a convention one uses in mathematics, but here it would be extremely confusing: in the lazy series code we use valuation a lot, and it must mean lowest degree, but we also use the degree of polynomials and Laurent polynomials and we must distinguish between the two.

Martin

[Nils Bruin]

On Friday 1 March 2024 at 09:49:15 UTC-8 Giacomo Pope wrote:

Following this discussion, I have made a draft PR to change the degree for *only* the LaurentPolynomialRing and I will see if the CI detects anything.

https://github.com/sagemath/sage/pull/37513

I agree that if we change the LaurentPolynomialRing we should also change the `LaurentSeriesRing`, at the moment `LazyLaurentSeriesRing` has no method `degree()` but *does* have a `valuation()` method... so this is odd.

OK, let's keep it that way then! I don't think there is a notion on LaurentSeriesRing that deserves the name "degree". Sorry about mixing that one in. I thought it existed. And I think it does:

 sage: R.<x>=LaurentSeriesRing(QQ)
sage: z=R(0)
sage: z.valuation()
+Infinity
sage: z.degree()
-1

but if it's not documented, perhaps we can just ignore it.

[Giacomo Pope]

As an aside, the univariate LaurentPolynomialRing had a notion of `valuation` but the multivariate one didn't...

In the PR: https://github.com/sagemath/sage/pull/37490 I added random elements but also a notion of valuation() for the multivariate case and just made it act similarly to the univariate one.

[Martin R]

I don't get it - are my previous messages invisible?

1st Message: I don't understand - `degree` doesn't make much sense for Laurent series - there is no way to determine the degree of a LaurentSeries and no way to determine the degree of a LazyLaurentSeries with one minor exception - which is when it is known that the series terminates, but that's rare.

2nd Message: I am very much against this.  I realise that this is a convention one uses in mathematics, but here it would be extremely confusing: in the lazy series code we use valuation a lot, and it must mean lowest degree, but we also use the degree of polynomials and Laurent polynomials and we must distinguish between the two.

I feel a bit ignored,

Martin

[Travis Scrimshaw]

Some quick data points:

- The general graded modules (and hence algebras) code raises an error for `0` since it is defined there by the direct summand the element belongs to (and `0` belongs to all of them.

- For polynomials, it is very useful to have a single check `f.degree() > k` for some `k`. Having error messages or check `f.is_zero()` first makes things more complicated.

- Comparisons of integers to `-infinity` is (relatively) expensive. Although this happening frequently seems unlikely.

Martin, note that Dima is calling degree with a min/max qualifier added in front. I think this is leading to some confusion and cross-talk. However, I think it is better to have easily separable terms "valuation" and "degree" (which exist for polynomials).

Best,

Travis

[John Cremona]

Mathematically, the degree of a nonzero polynomial is the negative of  its valuation at infinity, i.e. the valuation for which 1/x is a uniformiser.

--

You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/6a9a6131-8c51-4760-9fad-897e220bfd1fn%40googlegroups.com.