oscar-system / Oscar.jl

A comprehensive open source computer algebra system for computations in algebra, geometry, and number theory.
https://www.oscar-system.org
Other
364 stars 129 forks source link

Gröbner basis for modules #4303

Open Syz-MS opened 1 week ago

Syz-MS commented 1 week ago

Describe the bug While computing some Gröbner bases for modules I encountered some differences between documentation and behaviour in Oscar. It seems like the Gröbner basis is not computed with respect to the requested module ordering. In the example below it looks like during the computation of groebner_basis and leading_module the ordering invlex(M)*deglex(R) is replaced by lex(M)*deglex(R) and therefore does not return a correct result.

To Reproduce

julia> R,_ = polynomial_ring(QQ, 1, :t);

julia> M = free_module(R, 3);

julia> ord = invlex(M)*deglex(R);

julia> g1 = 2M[1] + M[3];

julia> leading_term(g1, ordering=ord)
e[3]

julia> g2 = M[1] + M[2] + M[3];

julia> leading_term(g2, ordering=ord)
e[3]

julia> U,_ = sub(M, [g1, g2])
(Submodule with 2 generators
  1: 2*e[1] + e[3]
  2: e[1] + e[2] + e[3]
represented as subquotient with no relations, Hom: U -> M)

julia> G = groebner_basis(U, ordering=ord)
Gröbner basis with elements
e[3] + 2*e[2]
e[3] + e[2] + e[1]
 with respect to the ordering
invlex([gen(1), gen(2), gen(3)])*deglex([t1])

julia> LG,_ = sub(M, [leading_term(G[i], ordering=ord) for i=1:length(G)])
(Submodule with 2 generators
  1: e[3]
  2: e[3]
represented as subquotient with no relations, Hom: LG -> M)

julia> LU = leading_module(U, ord)
Submodule with 2 generators
  1: 2*e[2]
  2: e[1]
represented as subquotient with no relations

julia> LG == LU
false

Expected behavior The expected result can currently be computed by the following, mathmatically wrong code by replacing invlex(M)*deglex(R) with lex(M)*deglex(R).

julia> G1 = groebner_basis(U, ordering=lex(M)*deglex(R))
Gröbner basis with elements
-e[1] + e[2]
e[1] + e[2] + e[3]
 with respect to the ordering
lex([gen(1), gen(2), gen(3)])*deglex([t1])

julia> LG1,_ = sub(M, [leading_term(G1[i], ordering=ord) for i=1:length(G)])
(Submodule with 2 generators
  1: e[2]
  2: e[3]
represented as subquotient with no relations, Hom: LG1 -> M)

julia> LU1 = leading_module(U, lex(M)*deglex(R))
Submodule with 2 generators
  1: e[2]
  2: e[3]
represented as subquotient with no relations

julia> LG1==LU1
true

Version Information

julia> Oscar.versioninfo(full=true)
OSCAR version 1.3.0-DEV - #master, b3ab222d48 -- 2024-11-12 10:38:02 +0100
  combining:
    AbstractAlgebra.jl   v0.43.10
    GAP.jl               v0.12.0
    Hecke.jl             v0.34.6
    Nemo.jl              v0.47.3
    Polymake.jl          v0.11.22
    Singular.jl          v0.23.10
  building on:
    FLINT_jll               v300.100.300+0
    GAP_jll                 v400.1300.102+2
    Singular_jll            v404.0.606+0
    libpolymake_julia_jll   v0.13.0+0
    libsingular_julia_jll   v0.46.0+0
    polymake_jll            v400.1300.2+0
See `]st -m` for a full list of dependencies.

Julia Version 1.7.3
Commit 742b9abb4d (2022-05-06 12:58 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, skylake)
Official https://julialang.org/ release

Additional context The same problem also occurs with the orderings deglex(R)*lex(M) and deglex(R)*invlex(M).

jankoboehm commented 1 week ago

Conversion from Oscar to Singular orderings for modules is missing.

afkafkafk13 commented 1 week ago

@jankoboehm If it were missing in total, i.e. would throw an error, it were significantly less dangerous than the current state.

Right now, it appears to be working at first glance and you only see at a closer look that there is even an inconsistency between taking the leading_term of a groebner basis (works correctly) and groebner_basis/leading_module (with the two module orderings swapped). This has the potential to pass undetected and lead to wrong conclusions, if people do casual computations while thinking about some problem, or cause work-arounds all over the place, if people are actually writing their own code.

jankoboehm commented 1 week ago

@afkafkafk13 that is not so easy. We have mathematical data structures, e.g. modules, which we can ask mathematical questions (perhaps the underlying question can be handled this way as an short term fix) and get as far as we know correct answers. For modules these homological questions are over various rings internally translated directly or indirectly to Gröbner basis questions to answer these questions. So throwing an error might make this machine inoperable. So I think, as we have observed multiple times, someone has to pick up on the module orderings since the original author (Daniel) is not here any more. There is to some extent a conversion function singular(ord::ModuleOrdering), so this is probably not so difficult, one has to understand what is there.

Some things to take into account that come to my mind: Oscar orderings can be used in a two-fold way: Do comparisons on the Oscar side, translate the ordering to Singular to do computations there. Some questions can in principle be addressed in both ways and have to give consistent answers. Some orderings created on the Oscar side might not have a direct Singular counterpart and would have to use a matrix ordering.

afkafkafk13 commented 1 week ago

@Jankoboehm I am fully aware of this situation. I do not suggest to throw an error, but I wanted to point out that the current state is even more dangerous (but currently without alternative).
On the other hand, the longer we wait, the more 'creative solutions by people bypassing this inconsistency' we will see and need to clean up later on.