Monomial orderings `revlex` and `degrevlex` unintuitive

[lgoettgens]

@gfourier found this today while trying around with #2936.

Describe the bug We expect that a degree-graded ordering behaves exactly as the non-graded ordering on same-degree monomials. So revlex and degrevlex should behave exactly the same in cmp when both input monomials have the same total degree. The behavior is consistent with the documentation (revlex and degrevlex), but nonetheless, we find it extremely unintuitive.

To Reproduce

using Oscar
julia> R, (x,y,z) = polynomial_ring(QQ, [:x,:y,:z])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])

julia> cmp(revlex(R),y*z,x*y)
1

julia> cmp(degrevlex(R),y*z,x*y)
-1

System (please complete the following information): Please paste the output of Oscar.versioninfo(full=true) below. If this does not work, please paste the output of Julia's versioninfo() and your Oscar version.

julia> Oscar.versioninfo(full=true)
julia> Oscar.versioninfo(full=true)
OSCAR version 0.14.0-DEV - #gf/BasisLieHighestWeight, 1cfdc19312 -- 2023-10-24 12:04:38 +0200
  combining:
    AbstractAlgebra.jl   v0.33.0
    GAP.jl               v0.10.0
    Hecke.jl             v0.22.3
    Nemo.jl              v0.37.2
    Polymake.jl          v0.11.7
    Singular.jl          v0.18.17
  building on:
    Antic_jll               v0.201.500+0
    Arb_jll                 v200.2300.0+0
    Calcium_jll             v0.401.100+0
    FLINT_jll               v200.900.7+0
    GAP_jll                 v400.1200.200+7
    Singular_jll            v403.208.800+0
    libpolymake_julia_jll   v0.10.6+0
    libsingular_julia_jll   v0.40.3+0
    polymake_jll            v400.1000.1+0
See `]st -m` for a full list of dependencies.

Julia Version 1.9.3
Commit bed2cd540a1 (2023-08-24 14:43 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 8 × Intel(R) Core(TM) i7-10510U CPU @ 1.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-14.0.6 (ORCJIT, skylake)
  Threads: 1 on 8 virtual cores
Official https://julialang.org/ release...

[thofma]

I can relate to the confusion, but I am not sure I would consider this a bug, since it is already covered in the documentation. Also I think SageMath, Magma, Macaulay2, Singular all use these definitions. Adding the dozens of textbooks and articles, I don't think it would be a good idea to change it. I guess for people that were in contact with those materials, there would be nothing unintuitive about the current Oscar behaviour.

PS: I was wrong. Everything is inconsistent, even among the systems, see https://github.com/oscar-system/Oscar.jl/issues/2950#issuecomment-1778570799.

[YueRen]

I agree with both of you. It is unintuitive, but that's just how things are. The root problem is that reverse lexicographic order is ambiguous and this isn't just a problem with monomial orderings. I also think that we shouldn't change it, but I wouldn't be opposed to a warning in the documentation of revlex or degrevlex.

[afkafkafk13]

I agree with @thofma and @YueRen : As unintuitive as some standard definitions might be, we should stick to the textbook definitions of the respective field, but a warning remark for the user from outside the field might be helpful in this case.

[wdecker]

The definition of revlex in Singular is in my eyes non-standard. Accordingly, the definition of negrevlex is non-standard. In fact, negrevlex should be called revlex to make things consistent (note that this is a local ordering). And revlex should just be removed. Similarly in OSCAR. @hannes14, @ederc What do you think? Where in Singular are these orderings used? @gfourier, @lgoettgens thx for bringing this up.

[ederc]

@wdecker I think you are right. Renaming negrevlex to revlex would then also be consistent with Macaulay2 if I remember correctly.

[thofma]

Hm, if we were consistent with Macaulay2, I guess it would still be unintuitive? By it I mean the observation of @lgoettgens and @gfourier. Even with the Macaulay2 convention, degree reverse lexicographical ordering is not degree comparison followed by "reverse lexicographical ordering":

i1 : R = QQ[x,y,z,MonomialOrder => RevLex, Global => false];

i2 : x*z^2 > x^2 * z

o2 = true

i3 : R = QQ[x,y,z,MonomialOrder => GRevLex, Global => true];

i4 : x*z^2 > x^2 * z

o4 = false

For whatever reason, "reverse" seems to have different meanings depending on what substantive is following. Using the language of https://oeis.org/wiki/Orderings#Reverse_lexicographic_order, here is a small summary: Singular:

• revlex: Reflected lexicographic order.
• degrevlex: Degree + Reverse reflected lexicographic order.

Macaulay2:

• RevLex: Reverse lexicographic order.
• GRevLex: Degree + Reverse reflected lexicographic order.

Magma:

• Has no "reverse" lexicographical ordering.
• grev-lex: Degree + Reverse reflected lexicographic order.

SageMath:

• I think has the same as Singular, but I did not check the details.

There seems to be no rhyme or reason to the usage of the word "reverse".

[ederc]

If I remember correctly SageMath calls Singular's revlex invlex, I recall that there were a discussion about this years ago at some Sage days.

[afkafkafk13]

@wdecker I think you are right. Renaming negrevlex to revlex would then also be consistent with Macaulay2 if I remember correctly.

Suppressing the inconsistent and ambiguous identifier revlex completely would be fine with me. With the crucial difference between Macaulay and Singular, it will be a constant source of confusion between the communities anyway. But I am opposed to not prepending a local ordering by neg, which would again be a source of confusion for users. Therefore, I would leave negrevlex as it is -- it is reverse reflected lexciographical ordering, which is again clear on all sides.

@ederc : Indeed, Singular's revlex is called invlex in sage and another revlex is not present in the documentation.

[fingolfin]

Regarding how this is defined in books: in e.g. Cox, Little, O'Shea they justify their choices by requiring that "standard" orderings they describe all satisfy that $x_1 > x_2 > \dots$. And this is satisfied by our lex, deglex, degrevlex ordering, but not by revlex.

So all in all, I think we should remove the current revlex. E.g. by renaming it to invlex as in the book by Cox, Little, O'Shea, and apparently also in SageMath.

By the way, I also think that the docstring for deglex, degrevlex etc. should be improved -- saying "this is the XYZ order" is not so helpful, it should also be explained what is meant by that.

[YueRen]

Hm, if we were consistent with Macaulay2, I guess it would still be unintuitive? By it I mean the observation of @lgoettgens and @gfourier. Even with the Macaulay2 convention, degree reverse lexicographical ordering is not degree comparison followed by "reverse lexicographical ordering":

i1 : R = QQ[x,y,z,MonomialOrder => RevLex, Global => false];

i2 : x*z^2 > x^2 * z

o2 = true

i3 : R = QQ[x,y,z,MonomialOrder => GRevLex, Global => true];

i4 : x*z^2 > x^2 * z

o4 = false

For whatever reason, "reverse" seems to have different meanings depending on what substantive is following. Using the language of https://oeis.org/wiki/Orderings#Reverse_lexicographic_order, here is a small summary: Singular:

* `revlex`: Reflected lexicographic order.

* `degrevlex`: Degree + Reverse reflected lexicographic order.

Macaulay2:

* `RevLex`: Reverse lexicographic order.

* `GRevLex`: Degree + Reverse reflected lexicographic order.

Magma:

* Has no "reverse" lexicographical ordering.

* `grev-lex`: Degree + Reverse reflected lexicographic order.

SageMath:

* I think has the same as Singular, but I did not check the details.

There seems to be no rhyme or reason to the usage of the word "reverse".

@thofma I believe "revlex" in Singular and M2 is called "reverse colexicographic" in oeis. See for example how the following monomials are ordered in Singular:

> f;
x1*x2*x3+x1*x2*x4+x1*x3*x4+x2*x3*x4+x1*x2*x5+x1*x3*x5+x2*x3*x5+x1*x4*x5+x2*x4*x5+x3*x4*x5+x1*x2*x6+x1*x3*x6+x2*x3*x6+x1*x4*x6+x2*x4*x6+x3*x4*x6+x1*x5*x6+x2*x5*x6+x3*x5*x6+x4*x5*x6

Anyways, I think we should just add a warning and leave things as they are. At least Singular / M2 / OSCAR are consistent with each other and with the Greuel-Pfister / Cox-Little-OShea book.

[lgoettgens]

I didn't expect this thread to blow up like this 😅 But apart from the confusion, we would like to have the "two missing" orderings available in OSCAR as well (with monomial_ordering(Rx, :name)), under whatever name the people of the topic can agree on.

1. Degree graded revlex (Note that this is not our degrevlex)
2. degrevlex without checking the degree.

Furthermore, I noticed that almost all definitions of graded orderings are wrong in the documentation (https://docs.oscar-system.org/dev/CommutativeAlgebra/GroebnerBases/orderings/), as they are missing the deg(x^α) = deg(x^β) and... on the right side of the or.

[hannes14]

revlex in Singular is used to construct monomial orderings for the opposite algebra (of a PBW algebra)

[wdecker]

@lgoettgens In order to avoid confusion: Please write down explicit definitions for this:

Degree graded revlex (Note that this is not our degrevlex)
degrevlex without checking the degree.

[lgoettgens]

I'll list all 4 combinations here and name them each with their OSCAR name, if they exist.

1. $x^\alpha > x^\beta \iff \exists 1 \leq i \leq n: \alpha_n = \betan, \dots, \alpha{i+1} = \beta_{i+1}, \alpha_i > \beta_i$ (this is OSCAR's revlex)
2. $x^\alpha > x^\beta \iff \deg(x^\alpha) > \deg(x^\beta) \text{ or } \left( \deg(x^\alpha) = \deg(x^\beta) \text{ and } \exists 1 \leq i \leq n: \alpha_n = \betan, \dots, \alpha{i+1} = \beta_{i+1}, \alpha_i > \beta_i \right)$ (this is the previous one, just with a degree check. I called this "degree graded revlex")
3. $x^\alpha > x^\beta \iff \deg(x^\alpha) > \deg(x^\beta) \text{ or } \left( \deg(x^\alpha) = \deg(x^\beta) \text{ and } \exists 1 \leq i \leq n: \alpha_n = \betan, \dots, \alpha{i+1} = \beta_{i+1}, \alpha_i < \beta_i \right)$ (this is OSCAR's degrevlex if I fix the error in the docs definition (the deg = deg part is missing there)
4. $x^\alpha > x^\beta \iff \exists 1 \leq i \leq n: \alpha_n = \betan, \dots, \alpha{i+1} = \beta_{i+1}, \alpha_i < \beta_i$ (this is the previous one, just without the degree check. I called this "degrevlex without checking the degree")

Please note that both 1 and 4, and 2 and 3 just differ by the direction of a single <.

[fingolfin]

Here is a plan people here seem to be OK with:

• we rename the current revlex to invlex
• we introduce a dummy function revlex which just throws an error that explains the situation (and points to invlex and possibly whatever name for "revlex as in M2" or so); its docstring could explain the situation in a bit more details.

[wdecker]

No, I disagree. I will make a more detailed suggestion later on today.

[wdecker]

@thofma I think the definition of revlex in 'Macaulay2' is inconsistent with the behaviour shown in your example:

https://macaulay2.com/doc/Macaulay2/share/doc/Macaulay2/Macaulay2Doc/html/___Rev__Lex.html

[wdecker]

@fingolfin I will move the (corrected) definitions of monomial orderings from the .md files to the .jl files.

[thofma]

@thofma I believe "revlex" in Singular and M2 is called "reverse colexicographic" in oeis.

@YueRen Are you saying that both are equal? According to the documentation, they are not if I understand correctly. https://docs.oscar-system.org/dev/CommutativeAlgebra/GroebnerBases/orderings/#The-Reverse-Lexicographical-Ordering and https://macaulay2.com/doc/Macaulay2/share/doc/Macaulay2/Macaulay2Doc/html/___Rev__Lex.html look different. For example, revlex (Singular) starts at the end, while RevLex (M2) startes at the beginning?

@wdecker: I am not sure I follow. A = [1, 0, 2], B = [2, 0, 1], A - B = [-1, 0, 1] and -1 is negative and the first non-zero entry. So x^A > x^B?

[wdecker]

@wdecker Sorry, I was actually looking at this link of the manual when I started to type:

http://www.math.kobe-u.ac.jp/icms2006/icms2006-video/slides/grayson/share/doc/Macaulay2/Macaulay2/html/___Rev__Lex.html

So they probably changed this at some time.

[wdecker]

I summarize the discussion, using 1-4 as done by @lgoettgens:

1. current revlex --> new invlex
2. new deginvlex
3. current degrevlex stays as it is (the copy and paste error in the docu will be corrected)
4. current negrevlex --> new revlex The suggestion 4 is consistent but does differ from current Maculay2 due to the afore mentioned change. Also, it does not please @afkafkafk13. Any other suggestion?

[hannes14]

Names of non-global orderings should start with neg

[fingolfin]

I could live with the proposal by @wdecker but so far everyone I talked to was concerned that using the name revlex would lead to people making mistakes.

Worse, if we just change its meaning, that means we will potentially break code by people currently using it in their Oscar code outside of this repository. I'd be very wary about tusch a move.

A compromise could be to turn revlex into a helpful error (in the way I described) for some time (say until after OSCAR 1.0), and then when we think nobody is still using it, we could think about reusing it for some order or another.

[wdecker]

O.k., how about the following:

4. current negrevlex --> new neginvlex

[afkafkafk13]

O.k., how about the following: 4. current negrevlex --> new neginvlex

Sounds good to me.

[lgoettgens]

I think that this can be closed now due to the changes in https://github.com/oscar-system/Oscar.jl/pull/3038. @gfourier Can you please have a look there as well if that resolves your confusion about the ordering? The updated docs are available at https://docs.oscar-system.org/dev/CommutativeAlgebra/GroebnerBases/orderings/.

[gfourier]

I think that this can be closed now due to the changes in #3038. @gfourier Can you please have a look there as well if that resolves your confusion about the ordering? The updated docs are available at https://docs.oscar-system.org/dev/CommutativeAlgebra/GroebnerBases/orderings/.

Yes, this resolved the confusion.