Ideals of $\mathbb Z[x]$

[Thrashophil]

Steps To Reproduce

R.<x> = ZZ[]
I = R.ideal(1-2*x,2)
I.is_trivial()

Expected Behavior

The output should be True instead of False because we have $1=(1−2x)+2x∈I$.

Actual Behavior

The output is False.

Additional Information

No response

Environment

- **OS**: EndeavourOS (Linux 6.6.16-1-lts x86_64)
- **Sage Version**: 10.2

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

[yyyyx4]

This ideal inherits its comparison function from Ideal_generic._richcmp_(), which compares the sets of generators (?!) instead of comparing the actual ideal.

[grhkm21]

I laughed

sage: R.<x> = ZZ[]
....: R.ideal(1) == R.ideal(1, 2)
False

[tscrim]

It is perfectly fair for == to compare two ideals in a non-mathematical way. You don't necessarily want to invoke hard computational tests for things that could be trivial. How would you expect it to work in that level of generality?

This is basically a(nother) case of not having a good way to say "IDK", and so it simply returns False. So this isn't really a bug IMO but a missing feature.

[yyyyx4]

It is perfectly fair for == to compare two ideals in a non-mathematical way.

I disagree: As the existence of this issue demonstrates, it is unexpected and causes confusion. If we wanted to compare the generators, we'd compare the generators.

You don't necessarily want to invoke hard computational tests for things that could be trivial.

I'm not sure what this refers to, can you elaborate?

This is basically a(nother) case of not having a good way to say "IDK", and so it simply returns False. So this isn't really a bug IMO but a missing feature.

The generally accepted way to communicate "IDK" is to throw a NotImplementedError, not to run some arbitrary fallback that returns a reasonably-looking value but doesn't actually do what everyone would expect.

On a related note, there really should be a distinction between mathematically meaningful comparisons and simple comparisons for programming purposes, cf. #35546 (comment).

[tscrim]

It is perfectly fair for == to compare two ideals in a non-mathematical way.

I disagree: As the existence of this issue demonstrates, it is unexpected and causes confusion. If we wanted to compare the generators, we'd compare the generators.

Surprising behavior does not imply wrong behavior. Of course, it should be avoided, but we need to accept it sometimes. Here, there are two issues: (1) Sometimes one needs to be careful with False results to differentiate between "cannot prove" and "actually false" but it is very difficult to explain this in all the places one should be careful. (2) We cannot easily communicate that we cannot do the computation here.

You don't necessarily want to invoke hard computational tests for things that could be trivial.

I'm not sure what this refers to, can you elaborate?

This might invoke a full Grobner basis computation when you simply want to check they are more trivially not equal. Of course, there are alternatives in this specific case, but there are uses for == diverging from a natural mathematical definition:

sage: R.<x> = PolynomialRing(ZZ, implementation='FLINT')
sage: S.<x> = PolynomialRing(ZZ, implementation='NTL')
sage: R == S
False

There is also the issue that Python stipulates that X == Y should imply hash(X) == hash(Y)... To have that, we really would need to create a GB to hash the ideal. (Although mpolynomial ring ideals take an easy way out and just hash to 0.)

This is basically a(nother) case of not having a good way to say "IDK", and so it simply returns False. So this isn't really a bug IMO but a missing feature.

The generally accepted way to communicate "IDK" is to throw a NotImplementedError, not to run some arbitrary fallback that returns a reasonably-looking value but doesn't actually do what everyone would expect.

That is not true. SR and lazy series, for example, behave in this way. There is also an important distinction between IDK because the computation is hard versus IDK because there nothing implemented at all.

Would you really want generic ideals to raise an error anytime they cannot compare in the strict mathematical sense? Then they couldn't be used as keys for dicts either. These would be the consequences I can immediately think of, but there are likely many more that would render these generic implementations completely unusable.

On a related note, there really should be a distinction between mathematically meaningful comparisons and simple comparisons for programming purposes, cf. #35546 (comment).

Defining natural comparisons is hard. There can be many different versions that have different uses. We usually just have to chose one, explain what it is, and explain how to use other choices. It also shows up in subtle ways in different methods.

[YijunYuan]

It is perfectly fair for == to compare two ideals in a non-mathematical way. You don't necessarily want to invoke hard computational tests for things that could be trivial. How would you expect it to work in that level of generality?

This is basically a(nother) case of not having a good way to say "IDK", and so it simply returns False. So this isn't really a bug IMO but a missing feature.

It is OK to do math in a non-mathematical way?

All you need is a NotImplementedError, but you insist on returning a False.

You can't fake an answer instead of admitting the inability.

Similar issue: #36266

[YijunYuan]

The most important thing is that it is not the responsibility of any common user of SageMath to distinguish whether it is a real False in the mathematical sense or it is just a sign that SageMath is giving up.

[tscrim]

#36266 is a different issue (it seems nobody has changed the implementation with the appropriate category from a very quick look).

Python doesn't allow for trilean logic (which I would like to have, but others have tried and found it complicated from what I heard), and raising an error propagates breakage that might otherwise be okay (in fact, would make large amounts of things like, e.g., symbolics unusable).

On the contrary, a good mathematician would look for a certificate (in this case, something in one ideal that isn't in the other). Even more so, things can be fully implemented but can lead to "wrong" results because a different convention is used in Sage than the user did for their conjectures (this is from a true story). This is why we believe in open source; we can look at the code and see how things like == are implemented.

Forgive the Clinton-esque comment, but it depends on what the definition of == is. Perhaps it was too colloquial for me to have said "non-mathematical". More precisely, defining == on ideals by comparing generators is a valid notion of equality (clearly a reflexive, symmetric, transitive relation), but it doesn't give the "standard" notion of equality of sets.

TL;DR False is valid here.

[tscrim]

For comparison:

sage: R.<x> = PolynomialRing(ZZ, 1)
sage: I = R.ideal([1-2*x, 2])
sage: I.is_trivial()
True

This is because it uses the (lib)singular implementation, which has the GB implemented (and so the comparisons of ideals as sets through __richcmp__).

[YijunYuan]

On the contrary, a good mathematician would look for a certificate (in this case, something in one ideal that isn't in the other). Even more so, things can be fully implemented but can lead to "wrong" results because a different convention is used in Sage than the user did for their conjectures (this is from a true story).

Let's say the current implementation of == is reasonable (which I doubt). The bottom line here is that every ambiguous behavior like this should be well-documented. However, SageMath's document sucks haven't done this.

This is why we believe in open source; we can look at the code and see how things like == are implemented.

Not every user is a good programmer. Even so, USERS should only be exposed to documentation and the open (in the software engineering sense) interface of this software. To them, there is no clear line between "feature" and "bug".

[tscrim]

On the contrary, a good mathematician would look for a certificate (in this case, something in one ideal that isn't in the other). Even more so, things can be fully implemented but can lead to "wrong" results because a different convention is used in Sage than the user did for their conjectures (this is from a true story).

Let's say the current implementation of == is reasonable (which I doubt). The bottom line here is that every ambiguous behavior like this should be well-documented. However, SageMath's document sucks.

Let me apologize that this community of volunteers has not produced sufficient documentation that meets your high expectations. You are welcome to try and improve it.

This is why we believe in open source; we can look at the code and see how things like == are implemented.

Not every user is a good programmer. Even so, USERS should only be exposed to documentation and the open (in the software engineering sense) interface of this software. To them, there is no clear line between "feature" and "bug".

In principle, I agree with you except the last part. If a user cannot understand the difference of desired behavior and undesired behavior, then I believe they will likely have difficulties understanding difficult mathematics that can have far more subtle points. In this case though, one doesn't need to be a good programmer to understand what the comparison code is doing.

That being said, this here is definitely a case where we can improve our documentation by saying the generic implementation uses only the generators for comparisons.

[YijunYuan]

Let me apologize that this community of volunteers has not produced sufficient documentation that meets your high expectations. You are welcome to try and improve it.

I should apologize for the inappropriate word sucks. It is offensive.

[yyyyx4]

The biggest issue is that the generic implementation does something entirely different from the specialized implementations. What comparison of ideals should be doing is ultimately a matter of opinion (although I do have a very strong opinion on this), but the fact that specialized implementations behave differently from the generic fallback is definitely harmful. It means, for example, that comparison suddenly starts returning wildly different results if you change the code to a slightly different base ring (or even just a different implementation of the same base ring). Subtle details like that are certainly not transparent to most users, and they would realistically cause lots of bugs/suffering even if they were properly documented. There should be a clear specification of what comparison does, and all implementations should either adhere to it or give up and throw a NotImplementedError. (In fact, the same should ideally hold for all other functions in Sage!)

[yyyyx4]

Responding to some of your earlier comments @tscrim (please don't interpret my writing style as antagonistic, I'm just trying to communicate my point as clearly as possible):

(2) We cannot easily communicate that we cannot do the computation here.

In which way is a NotImplementedError not a good way of communicating that we cannot do the computation?

This might invoke a full Grobner basis computation when you simply want to check they are more trivially not equal. Of course, there are alternatives in this specific case, but there are uses for == diverging from a natural mathematical definition:

Again, if users wanted to compare the generators, they would compare the generators. An implementation of comparing the actual ideals can still have a fast path to check for equal generating sets. If computing a Gröbner basis is what it takes to properly compare two ideals, then so be it.

sage: R.<x> = PolynomialRing(ZZ, implementation='FLINT')
sage: S.<x> = PolynomialRing(ZZ, implementation='NTL')
sage: R == S
False

This example is about comparing rings, not ideals, which is an entirely different question: By construction Sage will only compare ideals with the same base ring (possibly by applying a coercion).

There is also the issue that Python stipulates that X == Y should imply hash(X) == hash(Y)... To have that, we really would need to create a GB to hash the ideal. (Although mpolynomial ring ideals take an easy way out and just hash to 0.)

If that's what it takes, so be it. If users are happy with hashing a set of generators, they can hash the generators.

Would you really want generic ideals to raise an error anytime they cannot compare in the strict mathematical sense?

Yes!

Defining natural comparisons is hard. There can be many different versions that have different uses. We usually just have to chose one, explain what it is, and explain how to use other choices. It also shows up in subtle ways in different methods.

I agree that there exist cases where no single obvious notion of comparison exists. Ideals, however, have exactly one such notion, and it is to compare them as subsets of the ring.

[tscrim]

I concur that having subclasses not performing the same comparison is an issue. The other side is that we want to actually be able to use the generic class when there is no known algorithm to compare otherwise. (There are generic GB algorithms, but they might not even terminate in more general settings.) By making the equality comparison raise a NotImplementedError, you are effectively paralyzing the class since it cannot be used, e.g., as keys in a dict. In some sense, you’re arguing for turning it into an abstract class instead of a generic class.

Another case to consider: the ideals may have a GB algorithm that runs for forever, but we don’t know ahead of time if this is true or not. Should they error out? Run for some fixed finite time and then error our if they still don’t know?

Running further with that argument that IDK => error: Note that if things that we don’t know how to compare raise errors, then this should also be the case for SR and lazy series. However, we have very good use cases for this to not happen, which could equally apply to the generic ideals. (Martin and I had very long discussions about this for lazy series; we ultimately decided to have an option to trigger errors when we could not prove equality with the default being to not error out.) The same could be true for generic ideals, but there we cannot have such a global option.

I know I am reiterating stuff I said before, but I think it is important. I also think those concerns outweigh the consequences of having subclass comparisons differ from the generic comparisons as we have many other important cases where IDK means returning False. Another example would be real fields (with finite precision), where we cannot (easily) differentiate between 0 and something very close to 0 but not supposed to be.

Note that my example with == of polynomial rings is to show an example in Sage that doesn’t have any reasonable mathematical justification, but is important for Sage (equal-but-not-identical parents are much harder to deal with).

I agree with you about the user’s wanting to check generators, then that is what they should explicitly check.

I am happy to have this discussion, and having @yyyyx4, @YijunYuan, @grhkm21, etc. (even strongly/aggressively) defend their POV is useful, nor do I think badly of you for it. (I also agree with @YijunYuan’s sentiment that Sage’s docs should be improved.)

[kedlaya]

Setting aside the question of what should be the default behavior for ideals, the fix for this particular issue is clear: one needs to implement a class of ideals in polynomial rings over Z by exposing functionality in Singular. A roughly comparable situation is #29512 where we implemented ideals in Laurent polynomial rings.

[tscrim]

Big +1 on having a specialized subclass for ideals of poly rings over $\mathbb{Z}$.

[kedlaya]

In fact we already have such a subclass, it's just that it's defined for multivariate polynomials:

sage: R.<x,y> = ZZ[]
sage: I = R.ideal(1-2*x,2)
sage: I.is_trivial()
True

It even works with a single variable if you force the issue:

sage: R.<x> = PolynomialRing(ZZ, 1)
sage: I = R.ideal(1-2*x,2)
sage: I.is_trivial()
True

So maybe it is enough to patch the univariate polynomial code so that ideals get created correctly.

[tscrim]

Indeed (I think I noted this somewhere), but I would expect there to be a fairly easy way to implement this directly using the fact that we are working over a PID. I am not sure right now exactly how to use this (or if it could be weaker, such as just being a domain).

[Thrashophil]

In fact we already have such a subclass, it's just that it's defined for multivariate polynomials:

sage: R.<x,y> = ZZ[]
sage: I = R.ideal(1-2*x,2)
sage: I.is_trivial()
True

It even works with a single variable if you force the issue:

sage: R.<x> = PolynomialRing(ZZ, 1)
sage: I = R.ideal(1-2*x,2)
sage: I.is_trivial()
True

So maybe it is enough to patch the univariate polynomial code so that ideals get created correctly.

Thank you for pointing this out because it reminds me of the following issue I once had:
https://ask.sagemath.org/question/56734/quotient-of-polynomial-ring-over-integers-not-working/?answer=56735#post-id-56735

[user202729]

Seems to be related to #23621 .