subfields of absolute number fields

[martinra]

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

[thofma]

Thanks and good catch. Did you enconter an actual error? Just curious.

We will have a look soonish.

[martinra]

After discovering the Hecke implementation, I didn't dare using it given that "Claus says its wrong".

[thofma]

@martinra We would love to take your version either by PR or just as a snippet here. But we would need to fit it into the generator/basis setting, i.e., it would have to replace the _subfield_basis(K, elt) function.

[martinra]

Just to make sure, _subfield_basis is meant to compute a vector space basis of the subfield over the base field. Correct? Then I'll prepare a pull request soonish.

You seem to have a number of tests for subfields, but none for subfield. Should I add one or two cases?

[thofma]

Just to make sure, _subfield_basis is meant to compute a vector space basis of the subfield over the base field. Correct? Then I'll prepare a pull request soonish.

Yes, correct, thanks!

You seem to have a number of tests for subfields, but none for subfield. Should I add one or two cases?

More tests are of course always welcome :)