Ideal dimension wrong, depends on term order.

vbraun commented 13 years ago

The dimension of an ideal, that is the Krull dimension of the quotient R/I, does not depend on the monomial order. But

sage: P.<x,y> = PolynomialRing(QQ,order='neglex')
sage: P.ideal(x).dimension()
1
sage: P.ideal(x-1).dimension()
-1

I think this uses Singular "ls" ordering which is related to the localization at <x,y> though I have never used (or properly understood) that functionality in Singular.

Maybe we need to change the term order to a global one internally?

CC: @sagetrac-Bouillaguet @malb @mstreng @sagetrac-jakobkroeker

Component: commutative algebra

Keywords: Singular ideal dimension

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

89f39f15-88e8-4e79-9bc0-0739a7fc497c commented 11 years ago

comment:1

More fundamentally, a (Krull) dimension should not be negative, should it?

vbraun commented 11 years ago

comment:2

Well I don't mind denoting the dimension of the emtpy set at -1. Or, in this case, the supremum of the lengths of the elements of the empty set. Its of course more a matter of definition...

89f39f15-88e8-4e79-9bc0-0739a7fc497c commented 11 years ago

comment:3

Apparently some other things go wrong :

sage: P.<x,y> = PolynomialRing(QQ,order='neglex')
sage: 1 in P.ideal(x-1)
True
sage: P.ideal(x-1).groebner_basis()
[1]

This is obviously crazy. And membership inside an ideal should not depend on the term order:

sage: P.<x,y> = PolynomialRing(QQ)
sage: sage: 1 in P.ideal(x-1)
False
sage: sage: P.ideal(x-1).groebner_basis()
[x - 1]

89f39f15-88e8-4e79-9bc0-0739a7fc497c commented 11 years ago

comment:5

The problem could be caused by the fact that neglex is not a "monomial order" in the usual sense, as it is not Well-founded:

sage: R.<x,y> = PolynomialRing(QQ, order='neglex')
sage: 1 > x > x^2 > x^3 > x^4
True

This clearly is an infinite descending chain.

vbraun commented 11 years ago

comment:6

Thats definitely the problem, but how to fix it?

89f39f15-88e8-4e79-9bc0-0739a7fc497c commented 11 years ago

comment:7

More generally, it seems that the problem occurs with all the "negated" term orders.

sage: P.<x,y> = PolynomialRing(QQ,order='neglex')
sage: P.ideal(x-1).groebner_basis()
[1]

With "negdegrevlex":

sage: P.<x,y> = PolynomialRing(QQ,order='negdegrevlex')
sage: P.ideal(x-1).groebner_basis()
[1]

With "negdeglex":

sage: P.<x,y> = PolynomialRing(QQ,order='negdeglex')
sage: P.ideal(x-1).groebner_basis()
[1]

With "negwdegrevlex"

sage: P.<x,y> = PolynomialRing(QQ, order=TermOrder('negwdegrevlex',(1,2)))
sage: P.ideal(x-1).groebner_basis()
[1]

Digging deeper into this, it seems that we imported from singular the concepts of global and local orderings. The global ones match my own understanding of what a "monomial order" is. In singular they also allow a generalization thereof, by dropping the well-foundedness requirement (the "local" orderings are those such that 1 > x).

Pretty much everything will eventually rely on the groebner basis computation routine, which apparently only works properly on "global" orderings. So a cheap fix would consist in raising an exception in I.groebner_basis if the underlying term-order is not "global"...

Opinions?

In fact, the page of the reference manual on term orderings specifies which orders are "global", but it does not specify what this means (this notion is not present in the textbooks I used to work with, and I suspect that some users won't know about it). It does not say that most routines are broken on the non-global orders. This could possibly be confusing to some users. We should at least mimic the singular documentation on term orderings, which is much more explicit and less confusing about all this.

mstreng commented 11 years ago

comment:8

I assume "local" here means "locally around (0,0)" (which is the only interpretation of the word "local" that makes sense to me in this context). Then these algorithms are not for the ring QQ[x,y], but for the localization (or maybe the completion) of that ring at (x,y), i.e., these algorithms assume that all polynomials f with f(0,0)!=0 are invertible. So the Groebner basis [1] with dimension -1 makes complete sense, as the ideal is the unit ideal locally at (0,0).

I don't know about the design of these PolynomialRing objects with "order=", and I don't know how Singular works, so I don't know whether what happens here is "wrong". Maybe the functionality of the local orderings is in the wrong place? Or maybe even though it only makes sense mathematically for localizations, it is a function of polynomials for efficiency reasons?

89f39f15-88e8-4e79-9bc0-0739a7fc497c commented 11 years ago

comment:9

While this "functionality" may have some use, it is very confusing. The content of an ideal should not depend on the term order. Either a given polynomial belongs to I, or it doesn't --- the order plays no role here. However, currently we allow the counter-intuitive example in comment 3, where the term order influences the content of an ideal.

This (indirectly) surprised vbraun, the original author of the ticket, and I don't like it either. It looks like a computational hack is exposed to the user, and messes with the usual mathematical definitions.

If the functionality is useful, we should probably not remove it, but we should at least be very explicit that contrarily to what one would expect following the usual textbooks, some orders will change the contents of your ideals.

89f39f15-88e8-4e79-9bc0-0739a7fc497c commented 11 years ago

comment:10

In fact, we have two options :

either we close this ticket as invalid, acknowledging that the use of "local" orders is fine, and that users should know what they are doing (i.e. the singular approach).
or we prevent users from using "local" orders in the same way they would use normal orders (for instance by requesting them to explicitly pass a Localization=True flag to the PolynomialRing constructor). This way, our intuitive understanding of most properties (e.g., the ideal dimension, or content) would not depend on the term order, unless the user explicitly says so.

I vote for the second one...

Charles

nbruin commented 9 years ago

comment:11

I concur that "neglex" should not be allowed as a term order on a polynomial ring. Instead, we can have LocalPolynomialRing or something similar that interfaces somehow with this functionality in singular.

This looks like an abuse of terminology on the side of Singular. Probably one that is algorithmically very advantageous for them, but you clearly need to work very carefully with these rings, because there are now "units" in the ring for which the inverse is not expressible in the representation used:

sage: R.<x,y>=PolynomialRing(QQ,order='neglex')
sage: (1+x).is_unit()
True
sage: 1/(1+x)
1
sage: (1+x) * (1/(1+x))
1 + x

I am sure the functionality in singular is very useful, but we can't expose it in the way we're doing here.

soehms commented 4 years ago

comment:13

See new discussion about this on sage-devel.

sagemath / sage

Ideal dimension wrong, depends on term order. #10708