thofma / hecke.jl Goto Github PK

View Code? Open in Web Editor NEW

210.0 12.0 60.0 78.32 MB

Computational algebraic number theory

License: Other

Julia 100.00% Shell 0.01%

julia math computer-algebra algebraic-number-theory number-theory class-field-theory discrete-mathematics

hecke.jl's People

Contributors

Stargazers

Watchers

hecke.jl's Issues

Oscar warnings for Hecke

In Oscar, I am seeing the following warnings when starting Oscar:

WARNING: eval from module Hecke to Oscar:    
Expr(:global, Expr(:call, :signature, Expr(:::, :K, :AnticNumberField)) = Expr(:block, #= Symbol("/home/travis/.julia/packages/Hecke/UZrlo/src/Hecke.jl"):238 =#, Expr(:call, :_signature, :K)))
  ** incremental compilation may be broken for this module **
WARNING: Method definition signature(Nemo.AnticNumberField) in module Nemo at /home/travis/.julia/packages/Nemo/5aSWJ/src/antic/nf_elem.jl:245 overwritten in module Hecke at /home/travis/.julia/packages/Hecke/UZrlo/src/Hecke.jl:238.

Check whether the element in Ideal

Qx, x = QQ["X"]
Qi, a = NumberField(x^2 + 1)
Zi = maximal_order(Qi)
I = (1 + i)^2 * Zi
in(2, I)                   # not working
in(ZZ(2), I)            # not working
in(Zi(2), I)             # not working
in(Qi(2), I)            # only this happen to work

2 // (1 + i)^2         # works
Zi(2) // (1 + i)^2   # not working

Problem during the installation

I have a problem during the installation. When I type

Pkg.add("Hecke")

I get the following error

CC ../build/antic/get_nmod_poly.lo get_nmod_poly.c:37:19: fatal error: flint.h: No such file or directory #include "flint.h" ^ compilation terminated. ../Makefile.subdirs:60: recipe for target '../build/antic/get_nmod_poly.lo' failed make[2]: *** [../build/antic/get_nmod_poly.lo] Error 1 make[2]: Leaving directory '/home/alessandro/.julia/v0.5/Hecke/deps/hecke/antic' Makefile:120: recipe for target 'libhecke.so.0.0.0' failed make[1]: *** [libhecke.so.0.0.0] Error 2 make[1]: Leaving directory '/home/alessandro/.julia/v0.5/Hecke/deps/hecke' Makefile:140: recipe for target 'library' failed make: *** [library] Error 2

I have installed FLINT from http://www.flintlib.org/downloads.html but I still get the same error. I am working on a Dell xps 13 9360 running Ubuntu 17.04.
Any ideas on how to solve it?

Migrating from travis-ci.org to travis-ci.com

In 2018, Travis CI decided to merge travis-ci.org (for open source projects) into travis-ci.com (previously only for commercial projects). This migration has been possible already for some time as a "beta feature". But now there is a deadline: December 31, 2020, they will shutdown travis-ci.org. So projects using travis-ci.org are well advised to migrate before that at a convenient time, to avoid hassle. I've done this several times for multiple projects and can try to provide some assistance.

Details can be found in this email and here you can find migration instructions. In my experience, migration is really easy and smooth, but YMMV.

Oh and of course afterwards, URLs in e.g. the README.md (for status badges) and on external websites etc. need to be adjusted.

CRT for prime power moduli from Hensel lifting

For my application, I need CRT over ℤ[x]/(p^k ⋅ f). Now, this turns out to be decently easy to do with existing functionality in Hecke, but I had to touch a bunch of what seem to be internal functions. I'm wondering if this functionality, could be exposed through some nicer interface (another method of crt_env perhaps?). Please also let me know if this functionality is actually already available through some nice interface that I'm missing.

My code is below. If this doesn't already exist in this form and my implementation seems reasonable, I'm happy to submit a PR, but given my lack of overview of this complete library, I figured I'd check in before attempting that.

using Nemo, Hecke

const p = 2
const k = 8
const pk = 2^8

const ℤ = ZZ
const ℤx, x = PolynomialRing(ℤ, "x")
const ℤp = ResidueRing(ℤ, p)
const ℤxp = PolynomialRing(ℤp, "x")[1]
const ℤpk = ResidueRing(ℤ, pk)
const ℤxpk = PolynomialRing(ℤpk, "x")[1]

cycpoly = cyclotomic(31, x)

using Hecke: HenselCtx, fmpz_poly_raw
ctx = HenselCtx(cycpoly, Hecke.fmpz(p))

# TODO: Why 2k here? The flint docs say that the xgcd factors are 2^l for some l,
# but don't elaborate what l is here. Do we need to use a different method to guarantee that # l>=k?
Hecke.start_lift(ctx, 2*k)

function _crt(p, idx, (v, w, link))
    (l, r) = link[idx], link[idx+1]
    left = l < 0 ? p[-l] : _crt(p, l+1, (v,w,link))
    right = r < 0 ? p[-r] : _crt(p, r+1, (v,w,link))
    left * v[idx+1] * w[idx+1] + right * v[idx] * w[idx]
end

poly_array(ctx, a) = [(f = ℤx(); ccall((:fmpz_poly_set, :libflint), Nothing,
        (Ref{fmpz_poly}, Ref{fmpz_poly_raw}),
        f, a+(i-1)*sizeof(fmpz_poly_raw)); f) for i = 1:(2ctx.r-2)]

function crt(p, h::HenselCtx)
    v = map(parent(p[1]), poly_array(ctx, ctx.v))
    w = map(parent(p[1]), poly_array(ctx, ctx.w))
    link = [unsafe_load(ctx.link, i) for i = 1:(2ctx.r-2)]
    _crt(p, length(link)-1, (v,w,link))
end

function crt_inv(p, h::HenselCtx)
    factors = map(parent(p), poly_array(ctx, ctx.v)[1:ctx.r])
    map(f->rem(p, f), factors)
end

crtpoly = crt(map(ℤxpk, [1:6;]), ctx)
crt_inv(crtpoly, ctx)

Strings vs Symbols

Make sure that all "structure" constructors that want strings (or arrays of strings) also

take symbols
take nothing (and have defaults, different ones for IJulia?)

Possibly also have an interface (at least) to obtain the string(s) back as strings, rather than the Symbols only.

Factoring elements in UFD

Is it possible to factor elements over UFD?
For instance:

using Hecke
R, X = QQ["X"]
K, a = NumberField(X^2 + 1, "a")

What can I do to factor for example 2 over Z_K?

TagBot trigger issue

This issue is used to trigger TagBot; feel free to unsubscribe.

If you haven't already, you should update your TagBot.yml to include issue comment triggers.
Please see this post on Discourse for instructions and more details.

gcd over mpoly gets stuck on big coeffs

The univariate gcd gets the right answer but the multivariate version gets stuck testing bogus gcds.

julia> QA, A = PolynomialRing(Hecke.QQ, "A")
(Univariate Polynomial Ring in A over Rational Field, A)

julia> K, a = number_field(A^3 - 2, "a")
(Number field over Rational Field with defining polynomial A^3 - 2, a)

julia> Kx, x = PolynomialRing(K, "x") # works fine
(Univariate Polynomial Ring in x over K, x)

julia> gcd((2161004576*a^2 + 2086628872*a + 1954799140)*x^3 + (2161555830*a^2 + 2088556612*a + 1956167474)*x^2 + (8054104192483984*a^2 + 9003014017819328*a + 13301830453835520)*x + 8059326812168680*a^2 + 9008895277505808*a + 13307951534515776, (551254*a^2 + 1927740*a + 1368334)*x^2 + 5222619684696*a^2 + 5881259686480*a + 6121080680256)
x^2 + 551140*a^2 + 1926800*a + 1367984

julia> Kx, (x,) = PolynomialRing(K, ["x"]) # gets stuck
(Multivariate Polynomial Ring in x over K, AbstractAlgebra.Generic.MPoly{nf_elem}[x])

julia> gcd((2161004576*a^2 + 2086628872*a + 1954799140)*x^3 + (2161555830*a^2 + 2088556612*a + 1956167474)*x^2 + (8054104192483984*a^2 + 9003014017819328*a + 13301830453835520)*x + 8059326812168680*a^2 + 9008895277505808*a + 13307951534515776, (551254*a^2 + 1927740*a + 1368334)*x^2 + 5222619684696*a^2 + 5881259686480*a + 6121080680256)
testing
gd = -229326538462192059786839084384921803*x^2 + 493829570468992174990110504214611950
testing
gd = (-667955398106330716895329390711086035925399569221078550*a^2 + 646627807884519217282118328519855783726617090352087725*a - 361012669797769879063642259232222836654187190411030770)*x^2 + 34618698910582654978688846278251974433614651632893668*a^2 + 70473776914859013671226897480732586623088701581539890*a - 438160575643914090809132340474709328057834890306833469

subfields of absolute number fields

The computation of subfields of absolute number fields seems to be incorrect according to a TODO note in the source code. Ignorant of the subfield implementation I wrote one myself. If you like, I can split up the code below to fit it into the basis/generators distinction currently used in Hecke. If you prefer to fix the current implementation, just close this issue; it's my way of asking whether you are interested in that code.

@doc Markdown.doc"""
    subfield(K::AnticNumberField, as::Vector{nf_elem}, s::Union{Symbol, AbstractString}; check::Bool = true)

> The number field L[as] generated by the elements of as over the
> base_field L of K.
"""
function subfield(
    K::AnticNumberField,
    as::Vector{nf_elem},
    s::Union{Symbol, AbstractString};
    check::Bool = true
    )
  if check && !all(parent(a) == K for a in as)
    throw(DomainError("elements $as must be contained in $K"))
  end

  k = base_field(K)
  kx = parent(K.pol)
  as = [a for a in as if !iszero(a)]
  if isempty(as)
    F,gF = number_field(gen(kx)-1, s)
    phi = hom(F, K, one(K), check = false)
    return (F, phi)
  end

  d = degree(K)
  Kvs = VectorSpace(k,d)
  # We transition the coefficients of a in reverse order, so that the
  # first vector in the row reduced echelon form yields the highest
  # degree among all elements of Fas.
  (Fvs,phivs) = sub(Kvs, [Kvs([coeff(a,n) for n in d-1:-1:0])
                          for a in as])
  dF = dim(Fvs)
  bs = as
  while !isempty(bs)
    nbs = elem_type(K)[]
    for b in bs
      abs = [a*b for a in as]
      abvs,_ = sub(Kvs, [Kvs([coeff(ab,n) for n in d-1:-1:0])
                         for ab in abs])
      (Fvs,phivs) = sub(Kvs, typeof(Fvs)[Fvs, abvs])
      if dF != dim(Fvs)
        dF = dim(Fvs)
        append!(nbs, abs)
      end
    end
    bs = nbs
  end
  Fas = [let Kv = phivs(v)
           K(kx([Kv[n] for n in d:-1:1]))
         end
         for v in gens(Fvs)]
  
  cs = [zero(k) for n in 1:dF]
  cs[1] = one(k)
  while true
    ca = sum(c*a for (c,a) in zip(cs,Fas))
    pF = minpoly(ca)
    if degree(pF) == dF
      pFden = lcm([denominator(coeff(pF,i)) for i in 0:dF])
      pF = parent(pF)([coeff(pF,i) * pFden^(dF-i) for i in 0:dF])
      F,gF = number_field(pF, s)
      phi = hom(F, K, ca, check = false)
      return (F, phi)
    end
    cs[1] += 1
    let i = 2
      while i <= dF && cs[i-1] > cs[i]+1
        cs[i-1] = zero(k)
        cs[i] += 1
        i += 1
      end
    end
  end
end

resultant for padic polynomials, occasional precision loss

It seems there is quite a rare precision loss in resultant for padic fields, do you think this is avoidable?

julia> using AbstractAlgebra, Nemo

Welcome to Nemo version 0.22.0

Nemo comes with absolutely no warranty whatsoever

julia> R,x= PolynomialRing(PadicField(853,2),"x")
(Univariate Polynomial Ring in x over Field of 853-adic numbers, x)

julia> a = (4*x^5 + x^4 + 256*x^3 + 192*x^2 + 48*x + 4)
(4*853^0 + O(853^2))*x^5 + x^4 + (256*853^0 + O(853^2))*x^3 + (192*853^0 + O(853^2))*x^2 + (48*853^0 + O(853^2))*x +
4*853^0 + O(853^2)

julia> using Hecke
[ Info: Precompiling Hecke [3e1990a7-5d81-5526-99ce-9ba3ff248f21]

Welcome to

    _    _           _
   | |  | |         | |
   | |__| | ___  ___| | _____
   |  __  |/ _ \/ __| |/ / _ \
   | |  | |  __/ (__|   <  __/
   |_|  |_|\___|\___|_|\_\___|

Version 0.10.1 ...
 ... which comes with absolutely no warranty whatsoever
(c) 2015-2021 by Claus Fieker, Tommy Hofmann and Carlo Sircana

WARNING: using Hecke.QQ in module Main conflicts with an existing identifier.


julia> discriminant(a)
O(853^-3)

julia> R,x= PolynomialRing(PadicField(next_prime(853),2),"x")
(Univariate Polynomial Ring in x over Field of 857-adic numbers, x)

julia> a = (4*x^5 + x^4 + 256*x^3 + 192*x^2 + 48*x + 4)
(4*857^0 + O(857^2))*x^5 + x^4 + (256*857^0 + O(857^2))*x^3 + (192*857^0 + O(857^2))*x^2 + (48*857^0 + O(857^2))*x +
4*857^0 + O(857^2)

julia> discriminant(a)
566*857^0 + 385*857^1 + O(857^2)

see also Nemocas/AbstractAlgebra.jl#827 for the generic code having some problems with this too.

Identities, zero matrices, concatenations for sparse matrices

It would be nice to have constructors for

identities
zero matrices

that return sparse matrices.
Moreover, it would also be nice to have basic
concatenation methods for sparse matrices, like

vcat
hcat
cat( (1,2), ...)

Issue with relative norms and factored elements

Let L be a subfield of K, m an injection of L into K, and x a factored element in K. Then x*x^-1 is a factored element with an empty dictionary. The relative norm norm(m, x*x^-1) throws ERROR: Dictionary must not be empty (but norm(x*x^-1) = 1 as expected).

Class group failing because too much precision is required

The class group of the field generated by
f = x^8 + x^7 - 288038x^6 - 288037x^5 + 19521589071x^4 + 34161916765x^3 - 413437974974630x^2 - 909574280147569x + 1400248287952138567

(often) fails because of the call of saturate on the S-units. Some elements are too large and the reduce_mod_units function requires too much precision to reduce them.

Class group is failing for non-monic defining polynomials

julia> Qx,x = Hecke.QQ["x"]
(Univariate Polynomial Ring in x over Rational Field, x)

julia> f = 8x^3+4x^2-4x-1
8*x^3 + 4*x^2 - 4*x - 1

julia> K,a = Hecke.NumberField(f, "a", cached = false)
(Number field over Rational Field with defining polynomial 8*x^3 + 4*x^2 - 4*x - 1, a)

julia> class_group(maximal_order(K))

If run often enough, this will fail.

The problem is that the saturate business (in mod_p) calls _, mF = ResidueFieldSmallDegree1(O, P) and then extend_easy(mF). But extend_easy(mF) expects mF.poly_of_the_field to be set. But ResidueFieldSmallDegree1 for non-nice defining polynomials does not do it.

Make ResidueFieldSmallDegree1 do something clever for non-nice defining polynomials by doing something with the leading coefficient.
Accept only primes not dividing the leading coefficient of the defining polynomial.
Combine the conditions and implement something like issuper_nice_prime_for_saturation(K, p), which we can use as a simple check.

Documentation slow to build

Pretty irrelevant, but

@time include("make.jl")
...
251.851335 seconds (327.10 M allocations: 16.274 GiB, 2.72% gc time)

How can I speed things up?

Implement Witt equivalence of number fields

Reference: https://arxiv.org/pdf/1304.0708.pdf

Would be nice to have

"Level" of a number field (Algorithm 10)
"Pythagoras number" of a number field (Algorithm 11)
Witt equivalence of number fields (Algorithm 13) based on the computation of a set of invariants.

The functions should go into src/NumField/Quad.jl, which has to be created and then be included in src/NumField.jl. Signatures should be:

level(K::AnticNumberField)
pythagoras_number(K::AnticNumberField)
iswitt_equivalent(K::AnticNumberField, L::AnticNumberField).

automorphism group failing for laaarge field (norm change constant)

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

julia> f = x^40 + 1862*x^39 - 1112668826*x^38 - 2991512355894*x^37 + 566993681952202373*x^36 + 2017441405228030707586*x^35 - 175156040975066159587067328*x^34 - 785005126131774557853164582116*x^33 + 36557780851133638195906242592234801*x^32 + 200587082590489185309985631868100635012*x^31 - 5429757747829349016956750367584542284978228*x^30 - 36009847003996154525451877761268398961149527548*x^29 + 587071015371981980470934282455569475736243334592406*x^28 + 4720577122440159274921751893425144676887926994772075508*x^27 - 46180889136357411449592882635819819439915825946455876164672*x^26 - 461839341971493927192034139717310092285999944476104917304279576*x^25 + 2555510467448915039452463274807074340660884849865135550568713989169*x^24 + 34056605646463969801311436797728928914804586902032964105831687030128610*x^23 - 87661907920385711527299103576691660391231601737017407280726180296239164110*x^22 - 1891465196932217852898236407753131526913804157508123118757370189523333822889778*x^21 + 683732008940227049521067389660855055661816296241012390352733859313644550473220787*x^20 + 78068735280216975036640738160865083802110999435759754467376977066564648847359420262910*x^19 + 113778679498782804182002473069010236030689029461107488253929580757039432903686310314816584*x^18 - 2314570810207081789983024763998834178521142294121220202555771365292306040011121404690356419860*x^17 - 7425633812696135863928497328540579634621418874242744461899019503102763977556011588204285646832029*x^16 + 45360958839104937751976352637564911862262579788425871367123506070848343065835304798839966763238814188*x^15 + 249558716653920287241851992798175797844279782828713176105084617666436573549346254187542027024217960335196*x^14 - 437337615653063054814035505110159390235864235626029284997494752883492649947062024660014888910910462526268364*x^13 - 5131386880357026716563915807491962130268349295415833045464279410466699353904204190121732992126111084501222078050*x^12 - 3029393293850928694675392920391397659961396646458990275329136616804251555445078568461814939417797589235068329263876*x^11 + 61024591136968743733681067386602950129365133831090208010213049691275080650169695576710468106059358989416187661109364632*x^10 + 150818901356049810203568377517359017547145720132304060134164296226122670894533050555495249540278005079589521085510144527200*x^9 - 280867793108728886225739567020272658197948159815237732186958415769189099817716680255787793511637347855916561448229255902832493*x^8 - 1739761918427858410184860696267579547757521718466485249769015778645139642009039356056995784299253474956534283272838862557433178914*x^7 - 1713028698120925519537270506073059322775328573486251557685060938064616184071748703372231670104865295385229641668021312021992725775114*x^6 + 5388949446161509546871884250929319541242914992563817315185291005326234199685779776381390261239632464701467822432508674680878580176419930*x^5 + 18334570658995165446575207636442129027514001547007993911000333638121946753743412963404667688799017037983585611422812509219547658673829278845*x^4 + 24411220867980361995510524128840509475031800160188729383943666670907190141187720131373965236021098644275746743177410299231744640956975399225658*x^3 + 17049943832108038517023123509096388521580837288719623844936279514984821192784380632368183202324308212972742112681567236456001651249317285087074440*x^2 + 6132129880898294160271663709906600419410645105514768565916936856541632446845384482893703843539135982686346361169562726353897490737602044166997016420*x + 893439077326279341035471655728440623212462019375269821867473723830962022156998380069397504281330173585050150201296580695995249378607394062499378598947;

julia> K, a = number_field(f);

julia> lll(maximal_order(K));

julia> automorphisms(K);
ERROR: ArgumentError: matrix contains Infs or NaNs
Stacktrace:
  [1] chkuplofinite(A::Matrix{Float64}, uplo::Char)
    @ LinearAlgebra.LAPACK /tmpbig/blub/julia/usr/share/julia/stdlib/v1.7/LinearAlgebra/src/lapack.jl:104
  [2] syevr!(jobz::Char, range::Char, uplo::Char, A::Matrix{Float64}, vl::Float64, vu::Float64, il::Int64, iu::Int64, abstol::Float64)
    @ LinearAlgebra.LAPACK /tmpbig/blub/julia/usr/share/julia/stdlib/v1.7/LinearAlgebra/src/lapack.jl:5079
  [3] eigvals!
    @ /tmpbig/blub/julia/usr/share/julia/stdlib/v1.7/LinearAlgebra/src/symmetric.jl:734 [inlined]
  [4] eigvals(A::LinearAlgebra.Symmetric{Float64, Matrix{Float64}})
    @ LinearAlgebra /tmpbig/blub/julia/usr/share/julia/stdlib/v1.7/LinearAlgebra/src/symmetric.jl:740
  [5] _norm_change_const(v::Vector{nf_elem})
    @ Hecke /tmpbig/blub/packages/Hecke/cGa6u/src/NfOrd/NfOrd.jl:768
  [6] #norm_change_const#1618
    @ /tmpbig/blub/packages/Hecke/cGa6u/src/NfOrd/NfOrd.jl:749 [inlined]
  [7] norm_change_const
    @ /tmpbig/blub/packages/Hecke/cGa6u/src/NfOrd/NfOrd.jl:745 [inlined]
  [8] _lifting_expo(p::Int64, deg_p::Int64, K::AnticNumberField, bnd::Vector{arb})
    @ Hecke /tmpbig/blub/packages/Hecke/cGa6u/src/NfOrd/Hensel.jl:736
  [9] _roots_hensel(f::AbstractAlgebra.Generic.Poly{nf_elem}; max_roots::Int64, ispure::Bool, isnormal::Bool, root_bound::Vector{fmpz})
    @ Hecke /tmpbig/blub/packages/Hecke/cGa6u/src/NfOrd/Hensel.jl:283
 [10] roots(f::AbstractAlgebra.Generic.Poly{nf_elem}; max_roots::Int64, ispure::Bool, isnormal::Bool)
    @ Hecke /tmpbig/blub/packages/Hecke/cGa6u/src/NumField/NfAbs/Elem.jl:703
 [11] _automorphisms(K::AnticNumberField; isabelian::Bool)
    @ Hecke /tmpbig/blub/packages/Hecke/cGa6u/src/Map/automorphisms.jl:60
 [12] automorphisms(K::AnticNumberField; copy::Bool, isabelian::Bool)
    @ Hecke /tmpbig/blub/packages/Hecke/cGa6u/src/Map/automorphisms.jl:148
    @ Hecke /tmpbig/blub/packages/Hecke/cGa6u/src/Map/automorphisms.jl:148
 [13] automorphisms(K::AnticNumberField)
    @ Hecke /tmpbig/blub/packages/Hecke/cGa6u/src/Map/automorphisms.jl:135
 [14] top-level scope
    @ REPL[14]:1

Error loading Hecke when it is only installed "indirectly"

This line (only executed in Julia <= 1.3) is problematic; it results in an exception when Hecke is not installed directly, but only indirectly as a dependency.

Hecke.jl/src/Hecke.jl

Line 414 in f628073

ver = Pkg.installed()["Hecke"]

This leads to CI failures on Travis for Oscar.jl, see https://travis-ci.com/github/oscar-system/Oscar.jl/jobs/352656108

I am working on a workaround for the above issue, but it would be nice if this was also fixed in Hecke (and other packages using similar code).

factor(PolyElem{nf_elem}) slow..

consider:
x^22 + 11264x^21 + 108134400x^20 + 582253281280x^19 + 2643810068725760x^18 + 6274789714415321088x^17 + 10393103790020736581632x^16 - 26964124627218324678246400x^15 - 61113430392878016266187571200x^14 - 213091256467749679196075458560000x^13 + 659795291037497073621484487835648000x^12 - 218715905250259965549160383884820480000x^11 - 4691479368859726215309700317515643617280000x^10 + 18763705130498258945783687744375729600593920000x^9 - 27621622828761193673571225505441090503620689920000x^8 - 2847327150033767189886543281086124743621638881280000x^7 + 96615588727173557503360268281161873703549936525639680000x^6 - 229835907220318672403717140991492550238864203055104000000000x^5 + 308733648987598398195527756629686765531719284130473574400000000x^4 - 259665702138139321625728949251881979040351910093995900928000000000x^3 + 135845160848670688869014474010007121327144581305391801958400000000000x^2 - 40944244103037831174890279502367127526949781124619826437816320000000000*x + 5497408998449834675230023541576565374247802780368536137105408000000000000

then trying to factor over the number field defined by this, the majoritiy of the time is in the norm computation. As Magma does this in <2.5 sec, we should be able to improve on the norm

Factorization failing

From https://github.com/thofma/Hecke.jl/runs/1673293927:

(have, really_used, used) = ([0, 1, 2, 3, 4], Any[3, 2, 1, 0, 4], Any[3, 2, 1, 0, 4])
f = x^5 + 12*x^4 - 1704*x^3 - 56288*x^2 - 628080*x - 2376000
base_ring(f) = Number field over Rational Field with defining polynomial x - 1
Splitting at infinite place: Error During Test at D:\a\Hecke.jl\Hecke.jl\test\AlgAss\AlgAss.jl:202
  Got exception outside of a @test
  too bad
  Stacktrace:

@fieker

Dependency error

I get an error when trying to install Hecke using Julia v1.3 following https://oscar.computeralgebra.de/install/:

julia> using Pkg

julia> Pkg.add("CxxWrap")
   Cloning default registries into `~/.julia`
   Cloning registry from "https://github.com/JuliaRegistries/General.git"
     Added registry `General` to `~/.julia/registries/General`
 Resolving package versions...
 Installed CxxWrap ──────── v0.8.2
 Installed BinaryProvider ─ v0.5.8
  Updating `~/.julia/environments/v1.3/Project.toml`
  [1f15a43c] + CxxWrap v0.8.2
  Updating `~/.julia/environments/v1.3/Manifest.toml`
  [b99e7846] + BinaryProvider v0.5.8
  [1f15a43c] + CxxWrap v0.8.2
  [8f399da3] + Libdl
  [ea8e919c] + SHA
  Building CxxWrap → `~/.julia/packages/CxxWrap/sarOk/deps/build.log`

julia> Pkg.add("AbstractAlgebra")
 Resolving package versions...
 Installed AbstractAlgebra ─ v0.8.0
  Updating `~/.julia/environments/v1.3/Project.toml`
  [c3fe647b] + AbstractAlgebra v0.8.0
  Updating `~/.julia/environments/v1.3/Manifest.toml`
  [c3fe647b] + AbstractAlgebra v0.8.0
  [2a0f44e3] + Base64
  [8ba89e20] + Distributed
  [b77e0a4c] + InteractiveUtils
  [37e2e46d] + LinearAlgebra
  [56ddb016] + Logging
  [d6f4376e] + Markdown
  [9a3f8284] + Random
  [9e88b42a] + Serialization
  [6462fe0b] + Sockets
  [2f01184e] + SparseArrays
  [8dfed614] + Test

julia> Pkg.add("Nemo")
 Resolving package versions...
 Installed Nemo ─ v0.16.0
  Updating `~/.julia/environments/v1.3/Project.toml`
  [2edaba10] + Nemo v0.16.0
  Updating `~/.julia/environments/v1.3/Manifest.toml`
  [2edaba10] + Nemo v0.16.0
  Building Nemo → `~/.julia/packages/Nemo/HQopW/deps/build.log`

julia> Pkg.add("Hecke")
 Resolving package versions...
ERROR: Unsatisfiable requirements detected for package AbstractAlgebra [c3fe647b]:
 AbstractAlgebra [c3fe647b] log:
 ├─possible versions are: [0.1.0-0.1.3, 0.2.0, 0.3.0-0.3.3, 0.4.0-0.4.7, 0.5.0-0.5.4, 0.6.0, 0.7.0-0.7.1, 0.8.0] or uninstalled
 ├─restricted to versions 0.8.0 by an explicit requirement, leaving only versions 0.8.0
 └─restricted by compatibility requirements with Hecke [3e1990a7] to versions: [0.1.1-0.1.3, 0.2.0, 0.3.0-0.3.3, 0.4.0-0.4.7, 0.5.0-0.5.4, 0.7.0-0.7.1] — no versions left
   └─Hecke [3e1990a7] log:
     ├─possible versions are: [0.5.0-0.5.4, 0.6.0-0.6.7] or uninstalled
     └─restricted to versions * by an explicit requirement, leaving only versions [0.5.0-0.5.4, 0.6.0-0.6.7]

Starting from scratch again, a single Pkd.add("Hecke") worked but this didn't install the most recent versions of AbstractAlgebra and Nemo:

julia> Pkg.add("Hecke")
   Cloning default registries into `~/.julia`
   Cloning registry from "https://github.com/JuliaRegistries/General.git"
     Added registry `General` to `~/.julia/registries/General`
 Resolving package versions...
 Installed Requires ──────── v0.5.2
 Installed BinaryProvider ── v0.5.8
 Installed Nemo ──────────── v0.15.1
 Installed AbstractAlgebra ─ v0.7.1
 Installed Hecke ─────────── v0.6.7
  Updating `~/.julia/environments/v1.3/Project.toml`
  [3e1990a7] + Hecke v0.6.7
  Updating `~/.julia/environments/v1.3/Manifest.toml`
  [c3fe647b] + AbstractAlgebra v0.7.1
  [b99e7846] + BinaryProvider v0.5.8
  [3e1990a7] + Hecke v0.6.7
  [2edaba10] + Nemo v0.15.1
...

Block Banner output when using Hecke as dependency

Hi,

Is there a way to disable banner output from Hecke when using it as a dependency for a custom module?
Let me know if more details are required for this issue.

Thanks.

MethodError: AbstractAlgebra.Generic.change_base_ring(::fmpq_poly, ::AnticNumberField) is ambiguous

There is a problem with change_base_ring:

Change of ring: Error During Test at /var/jenkins_home/workspace/oscar/jenv/pkg/packages/Hecke/f614M/test/AlgAss/AlgAss.jl:65
  Test threw exception
  Expression: (isisomorphic(K, base_ring(C)))[1]
  MethodError: AbstractAlgebra.Generic.change_base_ring(::fmpq_poly, ::AnticNumberField) is ambiguous. Candidates:
    change_base_ring(f::PolyElem, R::AbstractAlgebra.Ring) in Hecke at /var/jenkins_home/workspace/oscar/jenv/pkg/packages/Hecke/f614M/src/Misc/Poly.jl:548
    change_base_ring(p::PolyElem{T}, g) where T<:Union{RingElem, AbstractFloat, Integer, Rational} in AbstractAlgebra at /var/jenkins_home/workspace/oscar/jenv/pkg/packages/AbstractAlgebra/Ot2xj/src/Rings.jl:248
  Possible fix, define
    change_base_ring(::PolyElem{T<:Union{RingElem, AbstractFloat, Integer, Rational}}, ::AbstractAlgebra.Ring)
  Stacktrace:
   [1] #roots#923(::Base.Iterators.Pairs{Symbol,Int64,Tuple{Symbol},NamedTuple{(:max_roots,),Tuple{Int64}}}, ::Function, ::fmpq_poly, ::AnticNumberField) at /var/jenkins_home/workspace/oscar/jenv/pkg/packages/Hecke/f614M/src/NfAbs/Elem.jl:579
   [2] (::getfield(Nemo, Symbol("#kw##roots")))(::NamedTuple{(:max_roots,),Tuple{Int64}}, ::typeof(roots), ::fmpq_poly, ::AnticNumberField) at ./none:0
   [3] _issubfield(::AnticNumberField, ::AnticNumberField) at /var/jenkins_home/workspace/oscar/jenv/pkg/packages/Hecke/f614M/src/NfAbs/NfAbs.jl:407
   [4] isisomorphic(::AnticNumberField, ::AnticNumberField) at /var/jenkins_home/workspace/oscar/jenv/pkg/packages/Hecke/f614M/src/NfAbs/NfAbs.jl:536
   [5] top-level scope at /var/jenkins_home/workspace/oscar/jenv/pkg/packages/Hecke/f614M/test/AlgAss/AlgAss.jl:65
   [6] top-level scope at /var/jenkins_home/workspace/oscar/julia/usr/share/julia/stdlib/v1.1/Test/src/Test.jl:1083
   [7] top-level scope at /var/jenkins_home/workspace/oscar/jenv/pkg/packages/Hecke/f614M/test/AlgAss/AlgAss.jl:52
   [8] top-level scope at /var/jenkins_home/workspace/oscar/julia/usr/share/julia/stdlib/v1.1/Test/src/Test.jl:1083
   [9] top-level scope at /var/jenkins_home/workspace/oscar/jenv/pkg/packages/Hecke/f614M/test/AlgAss/AlgAss.jl:49

I think the problem is that the definition of

change_base_ring(p::PolyElem{T}, g) where T<:Union{RingElem, AbstractFloat, Integer, Rational} in AbstractAlgebra at /var/jenkins_home/workspace/oscar/jenv/pkg/packages/AbstractAlgebra/Ot2xj/src/Rings.jl:248

is too general. I am going to provide a pull request to change its signature.

Missing docstring and minor errors in documentation

Scrolling through the documentation for Hecke I saw some minor errors.

For example, at https://www.thofma.com/Hecke.jl/dev/orders/orders/ there is a missing docstring for denominator and a \Z at the first docstring (should probably be \mathbf{Z}).

Elements of bounded T_2 norm in a ring of algebraic integers

Let K be a totally real number field, and O_K its ring of integers.
I need a function that gives me all element of O_K of T_2 norm in some interval.
@thofma told me how to get those, and here is what I think a correct method definition could be:

@doc Markdown.doc"""
    short_t2_elems(O::NfAbsOrd, lb, ub) -> Vector{NfAbsOrdElem}

Return all non-zero elements $x$ in $O$ with $lb \leq T_2(x) \leq ub$, up to sign, 
under the assumption that $nf(O)$ is totally real.
"""
function short_t2_elems(O::NfAbsOrd, lb, ub)
  @assert istotally_real(nf(O))

  trace = trace_matrix(O)
  basis = basis(O)
  return [O(dot(basis,v)) for (v,t) in short_vectors(Zlattice(gram = trace), lb, ub)]
end

I'd be thankful if this (or a suitably corrected version) could be included in Hecke!
I can also turn this into a PR if that's better.

Edit: I'm not sure of the exact semantic of short_vectors regarding bounds (whether they are strict or not) but some simple tests seem to show that both are. I had missed the fact that vectors are only enumerated up to sign, and it seems that 0 does not appear, even when letting lb=0: I don't know if that's expected.

maximial order computation does not work

This is one example that triggers an "n1 not defined" error:
R,x = PolynomialRing(Hecke.ZZ,"x") maximal_order(Hecke.NumberField(x^6+28153176769513638533819953494763742552095011029795886647010626985097770493447390786573312647386923245326294607649641017067997516829897062369182892772219258562789629151345178233470976*x^3+1087544917378569497489782414087715308104486063970662361708698298449681758488800617355980998085309157797376460545454402571140078116543476905649892273803228466894270759398058362231343906313018663670599695143861422721141563129150845697850601640755649472530205143222723244300807912375953120815029721479769822383312924719424335970141907758846596430457135098855468040192)[1])

I tried to naively change n1 to na, but then I get a division error up in the call stack.

minpoly, charpoly with parent

We need to

come up with a consistent scheme to specify the ring for a min/char poly computation
and implement it. Possibly using parent = as a last argument. Natively, Nemo supports specifying it via passing of the gen as first argument as well
similar issues are/ would be at least with
- lift for SeriesElem
- berlekamp_massey

factoring woes

I am attaching basically the full session so you can see if I am doing anything wrong. The issue is with the ERROR: Denominator has to be 1, which I do not think is my fault.

$ julia

(@v1.4) pkg> add Hecke#master
   Updating git-repo `https://github.com/thofma/Hecke.jl.git`
   Updating registry at `~/.julia/registries/General`
   Updating git-repo `https://github.com/JuliaRegistries/General.git`
  Resolving package versions...
   Updating `~/.julia/environments/v1.4/Project.toml`
 [no changes]
   Updating `~/.julia/environments/v1.4/Manifest.toml`
 [no changes]

julia> QA, A = PolynomialRing(QQ, "A")
ERROR: UndefVarError: PolynomialRing not defined
Stacktrace:
 [1] top-level scope at REPL[2]:1

julia> using Hecke

julia> QA, A = PolynomialRing(QQ, "A")
(Univariate Polynomial Ring in A over Rational Field, A)

julia> K, a = number_field(A^3 - 2, "a")
(Number field over Rational Field with defining polynomial A^3-2, a)

julia> Kx, x = PolynomialRing(K, "x")
(Univariate Polynomial Ring in x over K, x)

julia> Hecke.factor(x^4+(1//2*a^2 + 1*a + 2)*x^3+(a^2 + 2*a + 2)*x^2+(1//2*a^2 + 1*a + 2)*x+1)
ERROR: Denominator has to be 1
Stacktrace:
 [1] error(::String) at ./error.jl:33
 [2] (::FmpzPolyRing)(::fmpq_poly) at /home/schultz/.julia/packages/Hecke/MqCAI/src/Misc/Poly.jl:660
 [3] macro expansion at /home/schultz/.julia/packages/Hecke/MqCAI/src/Hecke.jl:535 [inlined]
 [4] factor_trager(::AbstractAlgebra.Generic.Poly{nf_elem}) at /home/schultz/.julia/packages/Hecke/MqCAI/src/NumField/NfAbs/Elem.jl:497
 [5] _factor(::AbstractAlgebra.Generic.Poly{nf_elem}) at /home/schultz/.julia/packages/Hecke/MqCAI/src/NumField/NfAbs/Elem.jl:470
 [6] factor(::AbstractAlgebra.Generic.Poly{nf_elem}) at /home/schultz/.julia/packages/Hecke/MqCAI/src/NumField/NfAbs/Elem.jl:451
 [7] top-level scope at REPL[7]:1

julia> (x+1)^2*(x+a)*(x+a^2//2)
x^4+(1//2*a^2 + 1*a + 2)*x^3+(a^2 + 2*a + 2)*x^2+(1//2*a^2 + 1*a + 2)*x+1

julia> Hecke.factor(ans)
ERROR: Denominator has to be 1
Stacktrace:
 [1] error(::String) at ./error.jl:33
 [2] (::FmpzPolyRing)(::fmpq_poly) at /home/schultz/.julia/packages/Hecke/MqCAI/src/Misc/Poly.jl:660
 [3] macro expansion at /home/schultz/.julia/packages/Hecke/MqCAI/src/Hecke.jl:535 [inlined]
 [4] factor_trager(::AbstractAlgebra.Generic.Poly{nf_elem}) at /home/schultz/.julia/packages/Hecke/MqCAI/src/NumField/NfAbs/Elem.jl:497
 [5] _factor(::AbstractAlgebra.Generic.Poly{nf_elem}) at /home/schultz/.julia/packages/Hecke/MqCAI/src/NumField/NfAbs/Elem.jl:470
 [6] factor(::AbstractAlgebra.Generic.Poly{nf_elem}) at /home/schultz/.julia/packages/Hecke/MqCAI/src/NumField/NfAbs/Elem.jl:451
 [7] top-level scope at REPL[10]:1

Number field interface for the rationals

QQ is a number field, so it could enjoy some of the number field interface
For instance
maximal_order(QQ) could return ZZ
There could also be an ideal type for ZZ
and infinite_places(QQ) could work.

My motivation is to make some generic code for quadratic forms over number fields also work for quadratic forms over QQ.

We need:

ideals (#212)
fractional ideals (#212)
places (#212)

No GB possible over rings created by Hecke

               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.5.1 (2020-08-25)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |

julia> using Hecke

Welcome to

    _    _           _
   | |  | |         | |
   | |__| | ___  ___| | _____
   |  __  |/ _ \/ __| |/ / _ \
   | |  | |  __/ (__|   <  __/
   |_|  |_|\___|\___|_|\_\___|

Version 0.9.0 ...
 ... which comes with absolutely no warranty whatsoever
(c) 2015-2020 by Claus Fieker, Tommy Hofmann and Carlo Sircana


julia> C, a = CyclotomicField(1)
(Cyclotomic field of order 1, 1)

julia> R = maximal_order(C);

julia> using Singular
Singular.jl, based on
                     SINGULAR                                 /
 A Computer Algebra System for Polynomial Computations       /  Singular.jl: 0.4.3
                                                           0<   Singular   : 4.2.0
 by: W. Decker, G.-M. Greuel, G. Pfister, H. Schoenemann     \
FB Mathematik der Universitaet, D-67653 Kaiserslautern        \

julia> S, (x,y,z) = Singular.PolynomialRing( R, [ "x", "y", "z" ] )
(Singular Polynomial Ring (Coeffs(17)),(x,y,z),(dp(3),C), spoly{Singular.n_unknown{NfAbsOrdElem{AnticNumberField,nf_elem}}}[x, y, z])

julia> I = Ideal(S, x,y,z)
Singular Ideal over Singular Polynomial Ring (Coeffs(17)),(x,y,z),(dp(3),C) with generators (x, y, z)

julia> Singular.std(I)
ERROR: MethodError: no method matching gcd(::NfAbsOrdElem{AnticNumberField,nf_elem}, ::NfAbsOrdElem{AnticNumberField,nf_elem})
Stacktrace:
 [1] nemoRingGcd(::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}) at /Users/mo/.julia/dev/Singular/src/libsingular/nemo/Rings.jl:173
 [2] id_Std at /Users/mo/.julia/packages/CxxWrap/68Y7I/src/CxxWrap.jl:596 [inlined]
 [3] std(::sideal{spoly{Singular.n_unknown{NfAbsOrdElem{AnticNumberField,nf_elem}}}}; complete_reduction::Bool) at /Users/mo/.julia/dev/Singular/src/ideal/ideal.jl:381
 [4] std(::sideal{spoly{Singular.n_unknown{NfAbsOrdElem{AnticNumberField,nf_elem}}}}) at /Users/mo/.julia/dev/Singular/src/ideal/ideal.jl:380
 [5] top-level scope at REPL[10]:1

julia>

Unit group computation error

So I won't forget.

julia> using Hecke; Qx, x = Hecke.PolynomialRing(Hecke.QQ, "x");
julia> f = x^5 + 514944*x^2 + 123904;
julia> K, a = Hecke.NumberField(f, "a"); O = Hecke.maximal_order(K);
julia> c, U, b = Hecke._class_unit_group(O);

outputs

ErrorException("Matrix cannot be inverted numerically")

It does not crash. The algorithm runs through and gives a correct result.

coeff is not available for all MPolys

Wolfram is reporting that some of his functions are now broken due to the function

Base.iterate(PC::Hecke.PolyCoeffs{<:AbstractAlgebra.MPolyElem}, st::Int = 0)

in src/Misc/MPoly.jl.

This function uses the coeff function, which is only available for MPoly's with random access, i.e. not for Singular polynomials, which Wolfram is using.

I'm actually not sure why this is suddenly causing a problem right now. Perhaps it is due to another bug somewhere caused by the recent coeffs -> coefficients change.

`issquare` giving wrong results

julia> Qx, x = PolynomialRing(FlintQQ, "x")
(Univariate Polynomial Ring in x over Rational Field, x)

julia> K, a = number_field(f, cached = false)
(Number field over Rational Field with defining polynomial -6//7*x + 1//9, 7//54)

julia> c = 49//4
49//4

julia> issquare(K(c))
(false, 0)

@fieker

factor(::fmpz) failing

@fieker Do you have an idea?

Ns = fmpz[111047079989041803627046695698912153327375381493113760239915162507673600, 72142176878927212049744259199572482693178225347439473391289519352659142618759125824, 2899401998179440452270705905601559298579232559464448, 13872622200253898316527488269647700000000, 885193872574240930783472929433600385242436572409306761364038369029045865888500, 444910789743357033793911759910839943229268887009783520579865804800, 1, 1901232596527208751342097685855786994656290269623085073239405751950576189440, 457528188847657581289433962772922742128417399317541169378794520234416000000000000000000000000, 164785239699254078788367668420665107456464827047101585797950472192, 999394936672234327378142750864533477437635000522800762118426226629541888, 4636173432366288922022336110992039861895613853374733247409168057856772460494848, 1381455288566097085234673258468006738160467660800, 3656731042105264165934774260077480068779389091135394772930158588764319809122861056, 122220438268485672694550192228559361840147682572800000000, 55475371082974431035320965031606463447159743917257335816854058300140072992768, 24037096733707988582996007096219290922410361600758142468096, 672521945843763858299196582031353449809702923185453793280, 25031556340445302243082750656512, 3200677049676990763210750339086223817719953518174400, 9602838377519423999924662605801507301960543230729836907230503182671140272869730980880384, 2820052854473735371110302797646198757836697644765975794941366456785297664, 20546051666149593137728547059920960548960421448573280621458819918307327432146883673088, 470379582707855563693590316396944608651926044672, 147105146190060209854009526121314223348782299749650325643153254327481568902766253568, 23868691083255515557306502314368019707941967000011304652800000000, 120045505066103782700884135141161509027817768635116359082144827515522044793472083072, 88309748749352280898062553402035804449141027457046762425046415997665280, 95058839379147092004458762806405263111972922764573136132812500000000, 2557495996060268839961699474831774245258524116131666894848000, 29838948956958859347889291204939845274743203734968992076715069132960185387883264, 87867545925395728052058525252495756971011787649143668428235328827972041023725000000, 89445483185055977187541186962171108974374371899079791738759121785250000000, 34512018252361256306163184365254934131635258106923304758108674884594752618496, 9407910805595091390087246827706055564918448813980959044409497562906624, 103345807815808292857230600558711872123416240502298142400000000, 61028363962349980320660669697812053944894977280607731197449013777408, 1134985624077666331149794087194813326024870461895827521536, 41785630707168459370272271372662590239998830375701799230698502436794614516175609575585792, 244783733512797647919998220408494782141787482249319249017942016, 10208062639161123318969912105474112789906400435783245716500359309886761548737972749135679488, 421743586366922336969243285272340091018238439937363295875000, 13536648344494001412600355589471611148356576117765502190610484575698256411384807424, 182518820379370729504660503328351449253440136198266316140461384743992781232517120, 9440431396112271964624245294486470076340040665464172318459480110847970094483979264, 2060588712972120401507057729484292620288, 31729619123504375042768459378321513937629010448701053559293326917632, 8845605736466401911667211456376207272401976099743908454134487973888, 55316636612745268738085169580411319803496016748711651357099032576, 1211093859637874117686673494197532543929918816195154676345192786867870160, 40198609674768259043393250160509116777535699018685360131207551306920527052800000000, 29185373240716971993203071956798746780470819378036870832140951764855720736048119352320, 114159963856525122427988026790849979211705149568759454476322094902820864000000, 230557000183619661812411408027095734255075055986923820237252834590720]

julia> for N in Ns[1:54]
         factor(N)
       end
ERROR: AssertionError: !(haskey(r, N))
Stacktrace:
 [1] factor_insert!(r::Dict{fmpz, Int64}, N::fmpz, scale::Int64)
   @ Hecke ~/tmp/lattices/dev/Hecke/src/Misc/Integer.jl:900
 [2] factor_insert!(r::Dict{fmpz, Int64}, N::fmpz, scale::Int64)
   @ Hecke ~/tmp/lattices/dev/Hecke/src/Misc/Integer.jl:897
 [3] factor_insert!(r::Dict{fmpz, Int64}, N::fmpz, scale::Int64)
   @ Hecke ~/tmp/lattices/dev/Hecke/src/Misc/Integer.jl:931
 [4] factor_insert!
   @ ~/tmp/lattices/dev/Hecke/src/Misc/Integer.jl:892 [inlined]
 [5] factor(N::fmpz)
   @ Hecke ~/tmp/lattices/dev/Hecke/src/Misc/Integer.jl:879
 [6] top-level scope
   @ ./REPL[3]:2

You might have to repeat the last command to reproduce the error.

trail(PolyElem) vs trailing_coefficient

the 2nd is the constant term, the 1st the last non-zero. I think they are used wrongly.

Documentation style

The font in the documentation is tiny—too tiny. I checked with Safari, Firefox, Chrome.

Also, the documentation of "Abelian groups" is empty.

Is there a particular reason for not using Documenter (like for AbstractAlgebra and Nemo)? Then everything would be in the same style. (Edit: Of course, you can use whatever you want, just saying. I think Documenter looks nicer and also fits the rest).

Completions

decide on an interface to completions (padic, qadic, Avi, SeriesElem, Hamburger-Noether, ...)

setprecision <-> set_precision (inplace and not) (for elements)
lift, rational_reconstruct
map_coeffs (for series)
ResidueField (with cache parameter)
precision handling for the ring, possibly following BigFloat
induced precision handling for polynomials/ matrices over those rings (for lifting algorithms)
common interface to roots of polynomials, factoring, gcd, resultant, ... (starting with the easy cases)
stable linear algebra
complete Euclidean interface
padic/ qadic:
- prime(ring, expo)
- caching of Frobenius
- Iwasawa log?

BIts and pieces already exists (PolyFactor for qadic, GaloisGrp (Oscar), MPolyFactor for Series, and in other places)

Possible bug in hnf

I have a matrix where hnf seems to hang. Since it is quite large I have uploaded a serialized version here: www.daviddelaat.nl/mat.jls

The following hangs:

using Serialization, Hecke
A = deserialize("mat.jls")
hnf(A)

The following code shows that hnf is very fast (less than a second) for the submatrix consisting of the first 350 rows, but then seems to hang indefinitely for the submatrix consisting of the first 351 rows. Row 351 doesn't seem particularly special to me (sparcity, bitsize).

using Serialization, Hecke
A = deserialize("mat.jls")
B = sparse_matrix(FlintZZ)
for i = 1:nrows(A)
    @show i 
    push!(B, A[i])
    @time hnf(B, truncate=true)
end

Do you know what might be going on here?

BTW, in the code I see @vprint statements, how do I turn on this debugging output?

disc -> discriminant

there are a handful of disc functions around vs many discriminant. I cannot just search and replace as disc is used quite a bit as a variable and member name...

euler_phi broken

The following works fine in Nemo, but is broken in Hecke:

julia> using Hecke
julia> using Test

julia> @test_throws DomainError euler_phi(-1)
Test Failed at REPL[13]:1
  Expression: euler_phi(-1)
    Expected: DomainError
  No exception thrown
ERROR: There was an error during testing

julia> typeof(euler_phi(0))
ERROR: AssertionError: N > 0
Stacktrace:
 [1] factor(::Nemo.fmpz) at /home/wbhart/.julia/packages/Hecke/HqBPo/src/Misc/Integer.jl:815
 [2] factor(::Int64) at /home/wbhart/.julia/packages/Hecke/HqBPo/src/Misc/Integer.jl:719
 [3] euler_phi(::Int64) at /home/wbhart/.julia/packages/Hecke/HqBPo/src/analytic.jl:247
 [4] top-level scope at none:0

julia> typeof(euler_phi(1))
Int64

julia> typeof(euler_phi(2))
Nemo.fmpz

julia> euler_phi(-2)
1

compile times degraded on using Hecke

I started to investigate some of my compile times, and tracked down the following issue to Hecke.

Not using Hecke

using Nemo
fm = FreeModule(QQ, 5);
vs = Vector{fmpq}[];
@time sub(fm, map(fm,vs));
0.410914 seconds (1.64 M allocations: 84.424 MiB, 5.92% gc time)

Using Hecke

using Nemo, Hecke
fm = FreeModule(QQ, 5);
vs = Vector{fmpq}[];
julia> @time sub(fm, map(fm,vs));
178.114302 seconds (488.43 M allocations: 23.518 GiB, 3.03% gc time)

I'm not sufficiently deep into the code base to find the source, but I can provide some experience from a similar phenomenon that I discovered in my own code. The compile time exploded in the same way. I had a function of the shape

function fct(m::MatElem{R}) where R
  rref!(m)
end

which caused Julia type interference to almost break down. My fix was

function fct(m::MatElem{R}) where R
  if R == fmpq
    rref!(m::fmpq_mat)
  else
    rref!(m)
  end
end

I believe I didn't have these problems in Julia 1.4, but I haven't double checked this. In any case, the work around is not great, but 180s is neither.

Simplify failing for non-nice defining polynomial

julia> Qx, x = PolynomialRing(FlintQQ, "x")
(Univariate Polynomial Ring in x over Rational Field, x)

julia> f = -1//3*x^2 - x + 1
-1//3*x^2 - x + 1

julia> K, a = number_field(f, cached = false)
(Number field over Rational Field with defining polynomial -1//3*x^2 - x + 1, _a)

julia> simplify(K)
ERROR: ArgumentError: Not an exact division
Stacktrace:
 [1] divexact(x::fmpz, y::fmpz)
   @ Nemo ~/.julia/packages/Nemo/xNg6C/src/flint/fmpz.jl:366
 [2] simplify(K::AnticNumberField; canonical::Bool, cached::Bool, save_LLL_basis::Bool)
   @ Hecke ~/.julia/dev/Hecke/src/NumField/NfAbs/Simplify.jl:86
 [3] simplify(K::AnticNumberField)
   @ Hecke ~/.julia/dev/Hecke/src/NumField/NfAbs/Simplify.jl:19
 [4] top-level scope
   @ REPL[54]:1

Hecke changes `collect(::fmpz_mat)` to return a Vector instead of a Matrix

If I just load AbstractAlgebra, I see this:

julia> M = MatrixSpace(ZZ, 2, 3); x = M(1:6); collect(x)
2×3 Matrix{BigInt}:
 1  2  3
 4  5  6

If I also load Nemo, I get this:

julia> M = MatrixSpace(ZZ, 2, 3); x = M(1:6); collect(x)
2×3 Matrix{fmpz}:
 1  2  3
 4  5  6

If I also load Hecke, I get this, which arguably is wrong:

julia> M = MatrixSpace(ZZ, 2, 3); x = M(1:6); collect(x)
6-element Vector{fmpz}:
 1
 4
 2
 5
 3
 6

This also happens if I force it to use AA.ZZ:

julia> M = MatrixSpace(AbstractAlgebra.ZZ, 2, 3); x = M(1:6); collect(x)
6-element Vector{BigInt}:
 1
 4
 2
 5
 3
 6

I noticed this because it breaks the doctests in the "new" Oscar.jl manual, which includes the AbstractAlgebra manual, which contains the above example.

`issquare` does not work with non-monic defining polynomials

julia> Qx,x = Hecke.QQ["x"]
(Univariate Polynomial Ring in x over Rational Field, x)
julia> f = 8x^3 + 4x^2 - 4x - 1
8*x^3 + 4*x^2 - 4*x - 1
julia> isirreducible(f)
true
julia> K,a = NumberField(f,"a")
(Number field over Rational Field with defining polynomial 8*x^3 + 4*x^2 - 4*x - 1, a)
julia> issquare(K(1))
ERROR: Primitive element must be integral
Stacktrace:
 [1] error(::String) at ./error.jl:33
 [2] __equation_order(::AnticNumberField) at /home/r/.julia/packages/Hecke/tHGcU/src/NfOrd/NfOrd.jl:1001
 [3] EquationOrder(::AnticNumberField, ::Bool) at /home/r/.julia/packages/Hecke/tHGcU/src/NfOrd/NfOrd.jl:976
 [4] EquationOrder at /home/r/.julia/packages/Hecke/tHGcU/src/NfOrd/NfOrd.jl:970 [inlined]
 [5] _roots_hensel(::AbstractAlgebra.Generic.Poly{nf_elem}; max_roots::Int64, ispure::Bool, isnormal::Bool, root_bound::Array{fmpz,1}) at /home/r/.julia/packages/Hecke/tHGcU/src/NfOrd/Hensel.jl:236
 [6] roots(::AbstractAlgebra.Generic.Poly{nf_elem}; max_roots::Int64, ispure::Bool, isnormal::Bool) at /home/r/.julia/packages/Hecke/tHGcU/src/NumField/NfAbs/Elem.jl:702
 [7] ispower(::nf_elem, ::Int64; with_roots_unity::Bool, isintegral::Bool, trager::Bool) at /home/r/.julia/packages/Hecke/tHGcU/src/NumField/NfAbs/Elem.jl:777
 [8] ispower at /home/r/.julia/packages/Hecke/tHGcU/src/NumField/NfAbs/Elem.jl:751 [inlined]
 [9] issquare(::nf_elem) at /home/r/.julia/packages/Hecke/tHGcU/src/NumField/NfAbs/Elem.jl:841

Is it possible to construct elliptic curves over finite fields?

I tried the next code

F = GF(13)
a = F(3)
b = F(8)

# create elliptic curve over F13
E = EllipticCurve([a,b])

It works just fine, but then it is impossible to do something with this curve:

hasse_interval(E)
ERROR: MethodError: no method matching isqrtrem(::Int64)

rand(E)
ERROR: MethodError: no method matching factor(::AbstractAlgebra.Generic.Poly{AbstractAlgebra.gfelem{Int64}})

Maybe it is possible to use implicit conversions or disallow to create curves over Fp from AbstractAlgebra?

Factoring x fails

julia> QA, A = PolynomialRing(QQ, "A")
(Univariate Polynomial Ring in A over Rational Field, A)

julia> K, a = number_field(A^3 - 2, "a")
(Number field over Rational Field with defining polynomial A^3-2, a)

julia> Kx, x = PolynomialRing(K, "x")
(Univariate Polynomial Ring in x over K, x)

julia> Hecke.factor(2*x^3-1)
2 * (x^2+1//2*a^2*x+1//2*a) * (x-1//2*a^2)

julia> Hecke.factor(x)
ERROR: BoundsError: attempt to access 0-element Array{Nemo.gfp_elem,1} at index [1]
Stacktrace:
 [1] getindex at ./array.jl:788 [inlined]
 [2] power_sums_to_polynomial(::Array{Nemo.gfp_elem,1}) at /home/schultz/.julia/packages/Hecke/vtU7U/src/Misc/Poly.jl:722
 [3] norm_mod(::AbstractAlgebra.Generic.Poly{nf_elem}, ::Int64, ::FmpzPolyRing) at /home/schultz/.julia/packages/Hecke/vtU7U/src/NumField/NfAbs/PolyFact.jl:769
 [4] norm_mod at /home/schultz/.julia/packages/Hecke/vtU7U/src/NumField/NfAbs/PolyFact.jl:765 [inlined]
 [5] macro expansion at /home/schultz/.julia/packages/Hecke/vtU7U/src/Hecke.jl:522 [inlined]
 [6] factor_trager(::AbstractAlgebra.Generic.Poly{nf_elem}) at /home/schultz/.julia/packages/Hecke/vtU7U/src/NumField/NfAbs/Elem.jl:510
 [7] factor(::AbstractAlgebra.Generic.Poly{nf_elem}) at /home/schultz/.julia/packages/Hecke/vtU7U/src/NumField/NfAbs/Elem.jl:465
 [8] top-level scope at REPL[11]:1

Maximal order failing for non-nice polynomials

julia> Qx, x = PolynomialRing(FlintQQ, "x")
(Univariate Polynomial Ring in x over Rational Field, x)

julia> f = 1//6*x^4 - 1//2*x^3 - x^2 + x + 5//2
1//6*x^4 - 1//2*x^3 - x^2 + x + 5//2

julia> K, a = number_field(f, cached = false)
(Number field over Rational Field with defining polynomial 1//6*x^4 - 1//2*x^3 - x^2 + x + 5//2, _a)

julia> Hecke.assertions(true)

julia> maximal_order(K)
ERROR: AssertionError: $(Expr(:escape, :(det(trace_matrix(OK)) == OK.disc)))
Stacktrace:
  [1] macro expansion
    @ ~/.julia/dev/Hecke/src/Assertions.jl:214 [inlined]
  [2] sum_as_Z_modules_fast(O1::NfOrd, O2::NfOrd, z::fmpz_mat)
    @ Hecke ~/.julia/dev/Hecke/src/NfOrd/NfOrd.jl:1270
  [3] sum_as_Z_modules_fast(O1::NfOrd, O2::NfOrd)
    @ Hecke ~/.julia/dev/Hecke/src/NfOrd/NfOrd.jl:1247
  [4] +(a::NfOrd, b::NfOrd; cached::Bool)
    @ Hecke ~/.julia/dev/Hecke/src/NfOrd/NfOrd.jl:1226
  [5] +
    @ ~/.julia/dev/Hecke/src/NfOrd/NfOrd.jl:1223 [inlined]
  [6] pmaximal_overorder_at(O::NfOrd, primes::Vector{fmpz})
    @ Hecke ~/.julia/dev/Hecke/src/NfOrd/MaxOrd/MaxOrd.jl:123
  [7] new_maximal_order(O::NfOrd; index_divisors::Vector{fmpz}, disc::fmpz, ramified_primes::Vector{fmpz})
    @ Hecke ~/.julia/dev/Hecke/src/NfOrd/MaxOrd/MaxOrd.jl:227
  [8] MaximalOrder(K::AnticNumberField; discriminant::fmpz, ramified_primes::Vector{fmpz})
    @ Hecke ~/.julia/dev/Hecke/src/NfOrd/MaxOrd/MaxOrd.jl:73
  [9] MaximalOrder(K::AnticNumberField)
    @ Hecke ~/.julia/dev/Hecke/src/NfOrd/MaxOrd/MaxOrd.jl:67
 [10] top-level scope
    @ REPL[43]:1

conj_quad failing

@fieker Any idea how to adjust the ccall magic? Or just not use it if the defining polynomial is not nice?

julia> Qx, x = PolynomialRing(FlintQQ, "x")
(Univariate Polynomial Ring in x over Rational Field, x)

julia> K, a = number_field(1//2*x^2 + 1, cached = false)
(Number field over Rational Field with defining polynomial 1//2*x^2 + 1, _a)

julia> Hecke.conjugate_quad(a)
ERROR: AssertionError: isone(k.pol_den)
Stacktrace:
 [1] conjugate_quad(a::nf_elem)
   @ Hecke ~/.julia/dev/Hecke/src/NumField/NfAbs/Elem.jl:1092
 [2] top-level scope
   @ REPL[12]:1

Originally posted by @thofma in #252 (comment)

problem with fmpz_mat

(I am not sure whether this is an issue for Nemo or for Hecke.)
Currently the following happens.

julia> using Hecke
[...]

julia> A = fmpz_mat([1 0 ; 0 1]);

julia> b = fmpz_mat(2, 1, [1, 0]);

julia> Hecke.solve(A, b)
ERROR: UndefRefError: access to undefined reference
[...]

The point is that b does not have the field base_ring (which is available in A).
The matrix A gets created by a method from Hecke, whereas the method for creating b belongs to Nemo.
Perhaps the Hecke methods set the field base_ring and rely on it, but the Nemo methods do not know this?
When one creates b as fmpz_mat([1 0])' then one gets an object of the same type as before, but the field is available, and Hecke.solve works.

thofma / hecke.jl Goto Github PK

hecke.jl's People

Contributors

Stargazers

Watchers

Forkers

hecke.jl's Issues

Recommend Projects

Recommend Topics

Recommend Org