search

thofma / Hecke.jl

Computational algebraic number theory
Other
209 stars 59 forks source link

Random test failures in `NfOrd/PicardGroup.jl` #1526

Open lgoettgens opened 1 month ago

lgoettgens commented 1 month ago

observed in the downstream tests in AA in https://github.com/Nemocas/AbstractAlgebra.jl/actions/runs/9224253991/job/25379194623?pr=1715#step:7:169

Error During Test at /home/runner/.julia/packages/Hecke/SZzwT/test/NfOrd/PicardGroup.jl:61
  Got exception outside of a @test
  AssertionError: $(Expr(:escape, :(nbits(pp) < 10000)))
  Stacktrace:
    [1] macro expansion
      @ ~/.julia/packages/Hecke/SZzwT/src/Assertions.jl:507 [inlined]
    [2] evaluate_mod(a::FacElem{AbsSimpleNumFieldElem, AbsSimpleNumField}, B::AbsSimpleNumFieldOrderFractionalIdeal)
      @ Hecke ~/.julia/packages/Hecke/SZzwT/src/NumField/NfAbs/CompactRepresentation.jl:361
    [3] macro expansion
      @ ~/.julia/packages/Hecke/SZzwT/src/Hecke.jl:476 [inlined]
    [4] compact_presentation(a::FacElem{AbsSimpleNumFieldElem, AbsSimpleNumField}, nn::Int64; decom::Dict{AbsSimpleNumFieldOrderIdeal, ZZRingElem}, arb_prec::Int64, short_prec::Int64)
      @ Hecke ~/.julia/packages/Hecke/SZzwT/src/NumField/NfAbs/CompactRepresentation.jl:217
    [5] compact_presentation
      @ ~/.julia/packages/Hecke/SZzwT/src/NumField/NfAbs/CompactRepresentation.jl:10 [inlined]
    [6] macro expansion
      @ ~/.julia/packages/Hecke/SZzwT/src/Hecke.jl:476 [inlined]
    [7] _ispower(a::FacElem{AbsSimpleNumFieldElem, AbsSimpleNumField}, n::Int64; with_roots_unity::Bool, decom::Dict{AbsSimpleNumFieldOrderIdeal, ZZRingElem}, trager::Bool)
      @ Hecke ~/.julia/packages/Hecke/SZzwT/src/NumField/NfAbs/CompactRepresentation.jl:435
    [8] is_power(a::FacElem{AbsSimpleNumFieldElem, AbsSimpleNumField}, n::Int64; with_roots_unity::Bool, decom::Dict{AbsSimpleNumFieldOrderIdeal, ZZRingElem}, trager::Bool, easy::Bool)
      @ Hecke ~/.julia/packages/Hecke/SZzwT/src/NumField/NfAbs/CompactRepresentation.jl:427
    [9] macro expansion
      @ ~/.julia/packages/Hecke/SZzwT/src/Hecke.jl:476 [inlined]
   [10] saturate!(d::Hecke.ClassGrpCtx{SMat{ZZRingElem, Hecke.ZZRingElem_Array_Mod.ZZRingElem_Array}}, U::Hecke.UnitGrpCtx{FacElem{AbsSimpleNumFieldElem, AbsSimpleNumField}}, n::Int64, stable::Float64; use_orbit::Bool, easy_root::Bool, use_LLL::Bool)
      @ Hecke.RelSaturate ~/.julia/packages/Hecke/SZzwT/src/NumFieldOrd/NfOrd/Clgp/Saturate.jl:449
   [11] saturate!(d::Hecke.ClassGrpCtx{SMat{ZZRingElem, Hecke.ZZRingElem_Array_Mod.ZZRingElem_Array}}, U::Hecke.UnitGrpCtx{FacElem{AbsSimpleNumFieldElem, AbsSimpleNumField}}, n::Int64, stable::Float64)
      @ Hecke.RelSaturate ~/.julia/packages/Hecke/SZzwT/src/NumFieldOrd/NfOrd/Clgp/Saturate.jl:411
   [12] _class_unit_group(O::AbsSimpleNumFieldOrder; saturate_at_2::Bool, bound::Int64, method::Int64, large::Int64, redo::Bool, unit_method::Int64, use_aut::Bool, GRH::Bool)
      @ Hecke ~/.julia/packages/Hecke/SZzwT/src/NumFieldOrd/NfOrd/Clgp.jl:305
   [13] class_group(O::AbsSimpleNumFieldOrder; bound::Int64, method::Int64, redo::Bool, unit_method::Int64, large::Int64, use_aut::Bool, GRH::Bool, do_lll::Bool, saturate_at_2::Bool)
      @ Hecke ~/.julia/packages/Hecke/SZzwT/src/NumFieldOrd/NfOrd/Clgp.jl:432
   [14] class_group
      @ ~/.julia/packages/Hecke/SZzwT/src/NumFieldOrd/NfOrd/Clgp.jl:420 [inlined]
   [15] _picard_group(O::AbsSimpleNumFieldOrder)
      @ Hecke ~/.julia/packages/Hecke/SZzwT/src/NumFieldOrd/NfOrd/PicardGroup.jl:206
   [16] (::Hecke.var"#2714#2715"{AbsSimpleNumFieldOrder})()
      @ Hecke ~/.julia/packages/Hecke/SZzwT/src/NumFieldOrd/NfOrd/PicardGroup.jl:19
   [17] get!(default::Hecke.var"#2714#2715"{AbsSimpleNumFieldOrder}, h::Dict{Symbol, Any}, key::Symbol)
      @ Base ./dict.jl:479
   [18] get_attribute!
      @ ~/work/AbstractAlgebra.jl/AbstractAlgebra.jl/src/Attributes.jl:230 [inlined]
   [19] picard_group(O::AbsSimpleNumFieldOrder)
      @ Hecke ~/.julia/packages/Hecke/SZzwT/src/NumFieldOrd/NfOrd/PicardGroup.jl:14
   [20] macro expansion
      @ ~/.julia/packages/Hecke/SZzwT/test/NfOrd/PicardGroup.jl:110 [inlined]
   [21] macro expansion
      @ /opt/hostedtoolcache/julia/1.10.3/x64/share/julia/stdlib/v1.10/Test/src/Test.jl:1577 [inlined]
   [22] top-level scope
      @ ~/.julia/packages/Hecke/SZzwT/test/NfOrd/PicardGroup.jl:62
   [23] include
      @ ./Base.jl:495 [inlined]
   [24] macro expansion
      @ ~/.julia/packages/Hecke/SZzwT/test/testdefs.jl:23 [inlined]
   [25] macro expansion
      @ /opt/hostedtoolcache/julia/1.10.3/x64/share/julia/stdlib/v1.10/Test/src/Test.jl:1577 [inlined]
   [26] macro expansion
      @ ~/.julia/packages/Hecke/SZzwT/test/testdefs.jl:22 [inlined]
   [27] macro expansion
      @ ./timing.jl:503 [inlined]
   [28] runtests(name::String, path::String; isolate::Bool, seed::UInt128)
      @ Main ~/.julia/packages/Hecke/SZzwT/test/testdefs.jl:20
   [29] invokelatest(::Any, ::Any, ::Vararg{Any}; kwargs::@Kwargs{seed::UInt128, isolate::Bool})
      @ Base ./essentials.jl:894
   [30] (::Distributed.var"#110#112"{Distributed.CallMsg{:call_fetch}})()
      @ Distributed /opt/hostedtoolcache/julia/1.10.3/x64/share/julia/stdlib/v1.10/Distributed/src/process_messages.jl:287
   [31] run_work_thunk(thunk::Distributed.var"#110#112"{Distributed.CallMsg{:call_fetch}}, print_error::Bool)
      @ Distributed /opt/hostedtoolcache/julia/1.10.3/x64/share/julia/stdlib/v1.10/Distributed/src/process_messages.jl:70
   [32] (::Distributed.var"#109#111"{Distributed.CallMsg{:call_fetch}, Distributed.MsgHeader, Sockets.TCPSocket})()
      @ Distributed /opt/hostedtoolcache/julia/1.10.3/x64/share/julia/stdlib/v1.10/Distributed/src/process_messages.jl:287
thofma commented 1 month ago

@fieker Just a breadcrumb: It seems that we are often running into saturation and are trying to compute roots of large elements:

for i in 1:100
  begin
    Qx, x = QQ["x"]
    f = x^4-3072*x^3+7926*x^2-3920*x-9063
    K, a = number_field(f, "a", cached = false)
    unit_group(maximal_order(f))
  end
end

Tracking the nbits(pp) (aka how many primes used in evaluate_mod), for current master we get:

[ Info: nbits(pp) when done: 26281
[ Info: nbits(pp) when done: 13141
[ Info: nbits(pp) when done: 6601
[ Info: nbits(pp) when done: 3121
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 6601
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 8581
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 3241
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 15181
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 9721
[ Info: nbits(pp) when done: 3181

With version 0.30.12 (which uses flint 2.9):

[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61
[ Info: nbits(pp) when done: 61

Seems that our relations are worse?

fieker commented 1 month ago

that would indicate LLL changes? Shouldn't all be reduced? I.e evalmod should be used on units that are small

fingolfin commented 4 weeks ago

Just run into this when it caused CI tests in AbstractALgebra to fail :-(

thofma commented 5 days ago

Probably the same problem as the following. On master:

julia> Qx, x = QQ["x"];

julia> f = x^6 - 7*x^4 + 14*x^2 - 7;

julia> K, _a = number_field(f; cached = false);

julia> _x = -2*_a^5 + 2*_a^4 + 12*_a^3 - 12*_a^2 - 17*_a + 18
-2*_a^5 + 2*_a^4 + 12*_a^3 - 12*_a^2 - 17*_a + 18

julia> evaluate(Hecke.reduce_mod_powers(_x, 2))
-638*_a^5 - 1014*_a^4 + 2904*_a^3 + 4628*_a^2 - 1825*_a - 2910

With flint 2.9 (aka Hecke 0.31.4):

julia> Qx, x = QQ["x"];

julia> f = x^6 - 7*x^4 + 14*x^2 - 7;

julia> K, _a = number_field(f; cached = false);

julia> _x = -2*_a^5 + 2*_a^4 + 12*_a^3 - 12*_a^2 - 17*_a + 18
-2*_a^5 + 2*_a^4 + 12*_a^3 - 12*_a^2 - 17*_a + 18

julia> evaluate(Hecke.reduce_mod_powers(_x, 2))
_a + 2