Time complexity of Magma's `NormEquation` for quadratic extensions of $2$-adic fields

Question

Note: This is similar to, but easier than, a previous question I asked here. It is a different question! I'm hoping this one might get an answer because it concerns a standard algorithm, whereas the previous one is about a modified version of the algorithm. It turns out I only need the running time of the standard one.

Let $E/F$ be a quadratic extension of $2$-adic fields, and let $\alpha \in F^\times$. As the MWE below demonstrates, Magma has an algorithm, called NormEquation, that determines whether $\alpha \in N_{E/F}E^\times$ and, if so, computes an approximate preimage under the norm map. I would like to know the running time of this algorithm.

I suspect that the equation is being solved by some sort of Hensel lifting. The number of lifting steps is probably on the order of $e_F$, where $e_F$ is the absolute ramification index of $F$, since squares are determined modulo $\mathfrak{p}_F^{2e_F + 1}$. Each step probably has complexity at most $q = \lvert\mathbb{F}_F\rvert$, since that is the number of possible lifts (although I'm not sure lifting in this way is actually well-defined). So I suspect the time complexity is at most $O(qe_F)$, but I'd like to know if it can be done faster than that.

// define basefield F
k0 := ChangePrecision(pAdicField(2), 100);
R<X> := PolynomialRing(k0);
totram_part<pi_F> := TotallyRamifiedExtension(k0, X^3 - 2);
F<theta> := UnramifiedExtension(totram_part, 2);

// define quadratic extension E/F
S<Y> := PolynomialRing(F);
pi_F := UniformizingElement(F);
E := TotallyRamifiedExtension(F, Y^2 - pi_F);
G, m := UnitGroup(F);

// use NormEquation in one case for each possible answer
alpha := 1 + pi_F + pi_F^2;
beta := 5 + theta;

print(NormEquation(E, m, alpha));
print(NormEquation(E, m, beta));

Answer 1

Here's what I found. The relevant functions are in package/Ring/RngLoc/class_field.m.

At line 1407 we have

intrinsic NormEquation(R::FldPad,m::Map,b::RngElt) -> BoolElt, RngElt
{Given R/B and the map m : UnitGroup(B) -> B and an element b in B,
 this solves Norm(a) = b for a in R}

which calls a delightful function solve_it, which is line 1394:

function solve_it(R,m,b) // MW, avoid duplicated code
  val:=Valuation(b); prec:=AbsolutePrecision(b)*Degree(R,Codomain(m)); // MW
  b:=ChangePrecision(b,Valuation(b)+Precision(R)); // MW
  gens := UnitGroupGenerators(R:Raw:=true);
  B := Codomain(m); U := Domain(m);
  F := FreeAbelianGroup(#gens); mF := hom<F -> U|[ Norm(g,B)@@m : g in gens]>;
  if not b@@m in Image(mF) then return false, _;
  else 
    aFseq := Eltseq(b@@m@@mF);
    a := &*[gens[i]^aFseq[i]: i in [1..#gens]];
    a:=ChangePrecision(a,val+prec); // MW
    return true, a; end if;   end function;

This function thinks of the norm map as a homomorphism on unit groups, and it just computes the image using an approximation and checks if the element is in the image or not. Apparently there is implicitly an assertion that this precision is correct (Hensel-like). In this example, for the codomain:

> G;      
Abelian Group isomorphic to Z/2 + Z/316912650057057350374175801344 + 
Z/633825300114114700748351602688 + Z/633825300114114700748351602688 + 
Z/633825300114114700748351602688 + Z/2535301200456458802993406410752 + 
Z/7605903601369376408980219232256 + Z
Defined on 8 generators
Relations:
    2*G.1 = 0
    316912650057057350374175801344*G.2 = 0
    633825300114114700748351602688*G.3 = 0
    633825300114114700748351602688*G.4 = 0
    633825300114114700748351602688*G.5 = 0
    2535301200456458802993406410752*G.6 = 0
    7605903601369376408980219232256*G.7 = 0

Those huge integers are mostly just huge powers of $2$, and we think of this as the unit group of some finite approximation of the units of the ring of integers. Same with the codomain. The claim is that if the element is not in the image under some finite approximation, it never will be; and if it is, and the precision is sufficient, then we can Hensel lift.

Accordingly, the running time should be polynomial in the extension degree and $\log p$, where $p$ is the characteristic of the residue field. (Not polynomial in $p$.) I bet you're right that we could improve this to the ramification degree instead of the degree, but that isn't what is coded.

I expect we could do better! But I guess this has been fast enough so far.