Bug in primary decomposition & does not terminate on a principal ideal

[simonbrandhorst]

Describe the bug
Let K be a number field (e.g. a cyclotomic field)

1. Primary decomposition does not terminate after 12 hours for a principal ideal (f) < K[x,y,t]
   (but factor(f) terminates immediately)

2. Primary decomposition throws an error for K a number field and J an ideal over K(t)[x,y]

To Reproduce

using Oscar
F, a = cyclotomic_field(7,:a)
P, (x,y,t) = polynomial_ring(F, [:x,:y,:t])
f = -x^3 + (127961567541885//2*a^5 + 230578777287775//2*a^4 + 230578777287775//2*a^3 + 127961567541885//2*a^2 - 455586040332045//16)*x + y^2 + (3242437110294043228*a^5 + 5842669785012830924*a^4 + 5842669785012830924*a^3 + 3242437110294043228*a^2 - 1443020268154487519)*t^7 + 9351999235365594180359//8*a^5 + 16851720327423257592547//8*a^4 + 16851720327423257592547//8*a^3 + 9351999235365594180359//8*a^2 - 16648124833698322506703//32
I = ideal(f)
factor(f) # works in seconds and confirms that f is irreducible
primary_decomposition(I) # keeps running for hours

The second case:

using Oscar
# Julia code
F, a = cyclotomic_field(7,:a)
P,x = polynomial_ring(F,:x)
f = x^3 - x^2 - 2*x + 1
w = roots(f)[1]
#F,w = number_field(f,:w)
Ft, t = polynomial_ring(F,:t)
FFt = fraction_field(Ft)
E1 = elliptic_curve(FFt,[0,0,0, (-230578777287775//2*w^2+127961567541885//2*w+4144846476936445//16), ((-5842669785012830924*w^2+3242437110294043228*w+13128359838180149367)*t^7-16851720327423257592547//8*w^2+9351999235365594180359//8*w+151461887453084383247079//32)])

then

julia> J = ideal(equation(E1))
Ideal generated by
  -x^3 + (127961567541885//2*a^5 + 230578777287775//2*a^4 + 230578777287775//2*a^3 + 127
  961567541885//2*a^2 - 455586040332045//16)*x + y^2 + (3242437110294043228*a^5 + 584266
  9785012830924*a^4 + 5842669785012830924*a^3 + 3242437110294043228*a^2 - 14430202681544
  87519)*t^7 + 9351999235365594180359//8*a^5 + 16851720327423257592547//8*a^4 + 16851720
  327423257592547//8*a^3 + 9351999235365594180359//8*a^2 - 16648124833698322506703//32

julia> primary_decomposition(J)
ERROR: Unexpected case in prepareQuotientring. Please inform the authors
leaving primdec.lib::prepareQuotientring (0)
leaving primdec.lib::decomp_i (3361)
leaving primdec.lib::primdecGTZ_i (5677)

Stacktrace:
  [1] call_singular_library_procedure
    @ ~/.julia/packages/CxxWrap/5IZvn/src/CxxWrap.jl:624 [inlined]
  [2] low_level_caller_rng(lib::String, name::String, ring::Singular.PolyRing{…}, args::Singular.sideal{…})
    @ Singular ~/.julia/packages/Singular/YQAWd/src/caller.jl:379
  [3] primdecGTZ(ring::Singular.PolyRing{Singular.n_FieldElem{…}}, args::Singular.sideal{Singular.spoly{…}})

Expected behavior
The function should work and terminate as described in the docu :-).

System (please complete the following information):

OSCAR version 1.2.0-DEV - #sb/EnriquesAut, d92758d3a2 -- 2024-07-03 09:53:15 +0000
  combining:
    AbstractAlgebra.jl   v0.41.9
    GAP.jl               v0.10.4
    Hecke.jl             v0.32.3 - #master, 0cf400dfaa -- 2024-06-13 08:05:41 +0200
    Nemo.jl              v0.45.5
    Polymake.jl          v0.11.18
    Singular.jl          v0.23.2
  building on:
    FLINT_jll               v300.100.300+0
    GAP_jll                 v400.1200.200+9
    Singular_jll            v404.0.100+0
    libpolymake_julia_jll   v0.12.0+0
    libsingular_julia_jll   v0.45.1+0
    polymake_jll            v400.1200.1+0
See `]st -m` for a full list of dependencies.

Julia Version 1.10.2
Commit bd47eca2c8a (2024-03-01 10:14 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 20 × 13th Gen Intel(R) Core(TM) i7-1370P
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-15.0.7 (ORCJIT, goldmont)
Threads: 15 default, 0 interactive, 1 GC (on 20 virtual cores)
Environment:
  JULIA_NUM_GC_THREADS = 1
  JULIA_NUM_THREADS = 15
Official https://julialang.org/ release

Additional context
Add any other context about the problem here.

[simonbrandhorst]

cc: @wdecker @hannes14

[thofma]

Can you complete the code for the second case?

[simonbrandhorst]

oops got distracted with computing ray class groups. Will do.

[fieker]

On Wed, Jul 03, 2024 at 10:28:35AM -0700, Simon Brandhorst wrote: oops got distracted with computing ray class groups. Will do.

What kind of ray class groups?

…

-- Reply to this email directly or view it on GitHub: #3905 (comment) You are receiving this because you are subscribed to this thread. Message ID: ***@***.***>

[simonbrandhorst]

See section 2.0.3. K3 class fields
in
https://doi.org/10.1016/j.jnt.2022.04.013

[fingolfin]

I tried to look into this, but in the first example, the definition of f uses variables a and t which are not defined (while w is unused), so I could not try it.

But I can still reproduce the second example, which looks like a problem in the primary decomposition code, so perhaps @wdecker or @hannes14 can have a look?

[simonbrandhorst]

@fingolfin sorry. I cleaned up the first example.

[simonbrandhorst]

Note that in the first example the computation is transferred to a primary decomposition over QQ of the following ideal.

Ideal generated by
  127961567541885//2*θ_1^5*x + 3242437110294043228*θ_1^5*t^7 + 9351999235365594180359//8*θ_1^5 + 230578777287775//2*θ_1^4*x + 5842669785012830924*θ_1^4*t^7 + 
  16851720327423257592547//8*θ_1^4 + 230578777287775//2*θ_1^3*x + 5842669785012830924*θ_1^3*t^7 + 16851720327423257592547//8*θ_1^3 + 127961567541885//2*θ_1^2*
  x + 3242437110294043228*θ_1^2*t^7 + 9351999235365594180359//8*θ_1^2 - x^3 - 455586040332045//16*x + y^2 - 1443020268154487519*t^7 - 16648124833698322506703/
  /32
  θ_1^6 + θ_1^5 + θ_1^4 + θ_1^3 + θ_1^2 + θ_1 + 1

[fingolfin]

Maybe @hannes14 can have a look at the two issues here (@wdecker as well but he is currently unavailable)

[fingolfin]

Triage says that to make this efficient we'll need to use modular GB computations. Apparently @ederc is working on that (integrating the modular GBs, I mean; I am not sure if what he does directly affects this computation).

[fingolfin]

Actually I think I may have confused issues, this may not be about modstd (?).

In any case I hope @hannes14 (and perhaps @wdecker with him) look into what the first (slow) example does, i.e. is it lowered to "efficient" Singular computations?

For the second example, this is an error message in primdec and so not modstd related...

[hannes14]

To the second issue: the coefficients passed to Singular are opaque for Singular, i.e. it can do arithmetic (including GB) with it,
but not factorize (which it needs for primary decomposition).

[fieker]

This is the tip of the iceberg. The ring could be a singular ring, but the conversion is too weak. Poly over rational over number field...

…

On Thu, 31 Oct 2024, 15:19 Hans Schoenemann, ***@***.***> wrote: To the second issue: the coefficients passed to Singular are opaque for Singular, i.e. it can do arithmetic (including GB) with it, but not factorize (which it needs for primary decomposition). — Reply to this email directly, view it on GitHub <#3905 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AA36CVYFUMFZIUGPYOTWT23Z6I36PAVCNFSM6AAAAABKJDKOZCVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDINBZHE4DOOBVGE> . You are receiving this because you commented.Message ID: ***@***.***>

[fieker]

Primary decomp should check if factoring is available before calling singular. Then there is also the oscar version of primary decomp where that problem won't be there

…

On Thu, 31 Oct 2024, 15:41 Claus Fieker, ***@***.***> wrote: This is the tip of the iceberg. The ring could be a singular ring, but the conversion is too weak. Poly over rational over number field... On Thu, 31 Oct 2024, 15:19 Hans Schoenemann, ***@***.***> wrote: > To the second issue: the coefficients passed to Singular are opaque for > Singular, i.e. it can do arithmetic (including GB) with it, > but not factorize (which it needs for primary decomposition). > > — > Reply to this email directly, view it on GitHub > <#3905 (comment)>, > or unsubscribe > <https://github.com/notifications/unsubscribe-auth/AA36CVYFUMFZIUGPYOTWT23Z6I36PAVCNFSM6AAAAABKJDKOZCVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDINBZHE4DOOBVGE> > . > You are receiving this because you commented.Message ID: > ***@***.***> >