EvenConductorExponent_ExactpAdics.mag

// This file is part of Genus2Conductor
// Copyright (C) 2018 Christopher Doris
//
// Genus2Conductor is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// Genus2Conductor is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Genus2Conductor.  If not, see <http://www.gnu.org/licenses/>.


// TEST CASES:
// - 33237.a.299133.1 (http://www.lmfdb.org/Genus2Curve/Q/33237/a/299133/1): initial factorization seems to take forever

import "EvenConductorExponent_Core.mag": conductor_exponent_data;
Z := Integers();

// This file requires the ExactpAdics package to already be attached.

FACTORS := recformat<success, err, seed, moebius, groebner_basis, K, FtoK, factors, proof>;
FACTOR := recformat<b0, b1, b2, b3, c0, c1, c2, L, M, c2_fac, b3_fac, c2_fac_idx>;

// given f(x) defined over number field F, and prime p of F, finds the 3-torsion of the hyper-elliptic curve C:y^2=f(x) over F_p
function find_3torsion(f, p
  : MinPrec:=100
  , MaxPrec:=6400
  , Randomize:=true
  , Strategy:=[* <"limit", MaxPrec>, MinPrec, <"randomize", Randomize>, <"double"> *]
  , Catch:=false
  , MobiusSkip:=0
  , MobiusRandomize:=0
  , Proof:=true
  , UseOldFactorization:=false
  , UseNP:=true
  , Time:=false
  , UseStrategy:=ExactpAdics_Implementation() eq 1
)
  r := rec<FACTORS | success:=false, seed:=[a,b] where a,b:=GetSeed(), proof:=Proof>;

  // parse Proof parameter
  global_proof := false;
  local_proof := false;
  if Proof cmpeq "Global" then
    global_proof := true;
  elif Proof cmpeq true or Proof cmpeq "Local" then
    local_proof := true;
  elif Proof cmpne false then
    error "bad Proof parameter:", Proof;
  end if;

  // timing
  if Time or GetVerbose("EvenConductorExponent_Genus2") ge 2 then
    function start_timer()
      return Cputime();
    end function;
    procedure log(~t, msg, ...)
      t0 := t;
      t := Cputime();
      print Join([Sprintf("%.2o", t-t0)] cat [Sprintf("%o", m) : m in msg], " ");
    end procedure;
  else
    function start_timer()
      return false;
    end function;
    procedure log(~t, msg, ...)
      ;
    end procedure;
  end if;

  // factorization
  if UseOldFactorization then
    fok, fintr := IsIntrinsic("Builtin_Factorization");
    rok, rintr := IsIntrinsic("Builtin_Roots");
    if not (fok and rok) then
      error "Builtin_Factorization and Builtin_Roots not available";
    end if;
    function factorization(f : Extensions:=false)
      return fintr(f : Strategy:=Strategy, Extensions:=Extensions, UseNP:=UseNP);
    end function;
    function roots(f)
      return rintr(f : Strategy:=Strategy);
    end function;
  elif UseStrategy then
    function factorization(f : Extensions:=false)
      return Factorization(f : Strategy:=Strategy, Extensions:=Extensions);
    end function;
    function roots(f)
      return Roots(f : Strategy:=Strategy);
    end function;
  else
    function factorization(f : Extensions:=false)
      return Factorization(f : Extensions:=Extensions);
    end function;
    function roots(f)
      return Roots(f);
    end function;
  end if;

  // main routine
  procedure go(~r)
    loc_f := f;
    loc_p := p;
    timer := start_timer();

    // check the inputs
    F := NumberField(BaseRing(f));
    OF := Integers(F);
    assert Degree(f) in [5,6];
    assert Order(p) eq OF;
    assert IsPrime(p);
    assert IsPowerOf(AbsoluteNorm(p), 2);

    // find equations
    vprint EvenConductorExponent_Genus2: "finding equations...";
    R<B0, B1, B2, B3, C0, C1, C2> := PolynomialRing(F, 7);
    ntries := 0;
    if MobiusRandomize le 0 then
      mobs := [[1,0,0,1]];
      mobs_lim := 0;
    else
      mobs := [];
      mobs_lim := MobiusRandomize;
    end if;
    while true do
      ntries +:= 1;
      if ntries le MobiusSkip then
        continue;
      end if;
      // ensure there exists a mobius transformation
      while #mobs lt ntries do
        mobs_lim +:= 1;
        mobs cat:= SetToSequence({[a,b,c,d] : a,b,c,d in [-mobs_lim..mobs_lim] | Max([Abs(x) : x in [a,b,c,d]]) eq mobs_lim and a*d-b*c eq 1 and (c eq 0 or Evaluate(f, a/c) ne 0)} diff SequenceToSet(mobs));
      end while;
      // get a defining polynomial
      r`moebius := mobs[ntries];
      vprint EvenConductorExponent_Genus2, 2: "moebius =", r`moebius;
      a,b,c,d := Explode(r`moebius);
      f2 := &+[Coefficient(f, i) * Polynomial([F|b,a])^i * Polynomial([F|d,c])^(6-i) : i in [0..6]];
      assert Degree(f2) in [5,6];
      // use a Groebner basis to get equations
      eqns := Coefficients(Polynomial([B0,B1,B2,B3])^2 - C2*Polynomial([C0,C1,1])^3 - ChangeRing(f2, R));
      G := GroebnerBasis(eqns);
      r`groebner_basis := G;
      if #G ne 7 then
        log(~timer, "groebner basis", ntries);
        continue;
      end if;
      assert forall{i : i in [1..7] | Min([Min([j : j in [1..7] | e[j] ne 0] cat [8]) where e:=Exponents(m) : m in Monomials(G[i])]) eq i};
      if exists{i : i in [1..7] | Degree(G[i], i) ne [1,1,1,2,1,1,40][i]} then
        log(~timer, "groebner basis", ntries);
        continue;
      end if;
      assert G[4] eq B3^2 - C2 - Coefficient(f2, 6);
      assert Evaluate(G[7], [0,0,0,0,0,0,-Coefficient(f2, 6)]) ne 0;
      assert IsSeparable(g) where ok,g := IsUnivariate(G[7]);
      log(~timer, "groebner basis", ntries);
      if global_proof then
        assert forall{eqn : eqn in eqns | NormalForm(eqn, G) eq 0};
        log(~timer, "global proof");
      end if;
      break;
    end while;

    // complete F at p
    vprint EvenConductorExponent_Genus2: "completing...";
    K, FtoK := ExactCompletion(F, p);
    r`K := K;
    r`FtoK := FtoK;
    log(~timer, "completion");

    // evaluates multivariate polynomials at each degree in the ith variable
    function evaluate_coeffs(g, i, xs)
      R := Parent(g);
      n := Rank(R);
      assert n eq 1+#xs;
      K := Universe(xs);
      cs := Coefficients(g, i);
      xs2 := Insert(xs, i, 0);
      return [K| evaluate(c, xs2) : c in cs]
        where evaluate := function (f, xs)
          zis := [i : i in [1..#xs] | IsDefinitelyZero(xs[i])];
          yis := [i : i in [1..#xs] | i notin zis];
          cs, ms := CoefficientsAndMonomials(f);
          K := Universe(xs);
          ts := [K|];
          for i in [1..#cs] do
            c := cs[i];
            if c eq 0 then
              continue;
            end if;
            m := ms[i];
            e := Exponents(m);
            if exists{i : i in zis | e[i] ne 0} then
              continue;
            end if;
            Append(~ts, &*([K| c] cat [K| xs[i]^e[i] : i in yis | e[i] ne 0]));
          end for;
          return &+ts;
        end function;
    end function;

    // evaluates multivariate polynomials into a univariate polynomial in the ith variable
    function evaluate_to_univariate(g, i, xs)
      return Polynomial(evaluate_coeffs(g, i, xs));
    end function;

    // equivalent to finding the linear root of evaluate_to_univariate(g, i, xs)
    function evaluate_to_linear_root(g, i, xs)
      cs := evaluate_coeffs(g, i, xs);
      assert #cs eq 2;
      return UseStrategy select '/'(-cs[1], cs[2] : Strategy:=Strategy) else -cs[1] / cs[2];
    end function;

    // find the fields generated by c2
    vprint EvenConductorExponent_Genus2: "factorizing c2_poly...";
    c2_poly := evaluate_to_univariate(G[7], 7, [K|0,0,0,0,0,0]);
    assert Degree(c2_poly) eq 40;
    c2_facs, _, c2_certs := factorization(c2_poly : Extensions);
    assert forall{fac : fac in c2_facs | fac[2] eq 1};
    assert &+[Degree(fac[1]) : fac in c2_facs] eq 40;
    factors := [];
    c2s := [**];
    log(~timer, "c2 factorization");
    for i in [1..#c2_facs] do
      vprintf EvenConductorExponent_Genus2: "factor %o...\n", i;
      c2_fac := c2_facs[i][1];
      c2_cert := c2_certs[i];
      L := c2_cert`Extension;

      // find c2
      vprint EvenConductorExponent_Genus2: "finding c2...";
      c2 := roots(ChangeRing(c2_fac, L))[1][1];
      log(~timer, "c2");

      // find c1
      vprint EvenConductorExponent_Genus2: "finding c1...";
      c1 := evaluate_to_linear_root(G[6], 6, [L|0,0,0,0,0,c2]);
      log(~timer, "c1");

      // find c0
      vprint EvenConductorExponent_Genus2: "finding c0...";
      c0 := evaluate_to_linear_root(G[5], 5, [L|0,0,0,0,c1,c2]);
      log(~timer, "c0");

      // find the fields generated by b3
      vprint EvenConductorExponent_Genus2: "factorizing b3_poly...";
      b3_poly := evaluate_to_univariate(G[4], 4, [L|0,0,0,c0,c1,c2]);
      assert Degree(b3_poly) eq 2;
      b3_facs, _, b3_certs := factorization(b3_poly : Extensions);
      assert forall{fac : fac in b3_facs | fac[2] eq 1};
      assert &+[Degree(fac[1]) : fac in b3_facs] eq 2;
      log(~timer, "b3 factorization");

      for j in [1..#b3_facs] do
        b3_fac := b3_facs[j][1];
        b3_cert := b3_certs[j];
        M := b3_cert`Extension;
        c0M := M ! c0;
        c1M := M ! c1;
        c2M := M ! c2;

        if local_proof then

          // find b3
          vprint EvenConductorExponent_Genus2: "finding b3...";
          b3 := roots(ChangeRing(b3_fac, M))[1][1];
          log(~timer, "local proof (b3)");

          // find b2
          vprint EvenConductorExponent_Genus2: "finding b2...";
          b2 := evaluate_to_linear_root(G[3], 3, [M|0,0,b3,c0M,c1M,c2M]);
          log(~timer, "local proof (b2)");

          // find b1
          vprint EvenConductorExponent_Genus2: "finding b1...";
          b1 := evaluate_to_linear_root(G[2], 2, [M|0,b2,b3,c0M,c1M,c2M]);
          log(~timer, "local proof (b1)");

          // find b2
          vprint EvenConductorExponent_Genus2: "finding b0...";
          b0 := evaluate_to_linear_root(G[1], 1, [M|b1,b2,b3,c0M,c1M,c2M]);
          log(~timer, "local proof (b0)");

          // hensel lift
          vprint EvenConductorExponent_Genus2: "hensel lifting...";
          soln0 := [M| b0, b1, b2, b3, c0, c1, c2];
          eqnsM := ChangeUniverse(eqns, PolynomialRing(M, 7));
          if UseStrategy then
            ok, soln := IsHenselLiftable(eqnsM, soln0 : Strategy:=Strategy);
          else
            ok, soln := IsHenselLiftable(eqnsM, soln0);
          end if;
          assert ok;
          bb0, bb1, bb2, bb3, cc0, cc1, cc2 := Explode(soln);
          log(~timer, "local proof (hensel)");

          // check primitivity
          vprint EvenConductorExponent_Genus2: "checking primitivity (1)...";
          assert UseStrategy
            select IsHenselLiftable(c2_facM, cc2 : Strategy:=Strategy)
            else   IsHenselLiftable(c2_facM, cc2)
            where c2_facM := ChangeRing(c2_fac, M);
          log(~timer, "local proof (krasner 1)");
          vprint EvenConductorExponent_Genus2: "checking primitivity (2)...";
          assert UseStrategy
            select IsHenselLiftable(b3_facM, bb3 : Strategy:=Strategy)
            else   IsHenselLiftable(b3_facM, bb3)
            where b3_facM := ChangeRing(b3_fac, M);
          log(~timer, "local proof (krasner 2)");

          // save off the factor
          Append(~factors, rec<FACTOR | c0:=cc0, c1:=cc1, c2:=cc2, b0:=bb0, b1:=bb1, b2:=bb2, b3:=bb3, L:=L, M:=M, c2_fac:=c2_fac, b3_fac:=b3_fac, c2_fac_idx:=i>);

        else
          // Proof = false
          Append(~factors, rec<FACTOR | L:=L, M:=M, c2_fac:=c2_fac, b3_fac:=b3_fac, c2_fac_idx:=i>);
        end if;
      end for;
    end for;

    assert &+[Degree(x`M, K) : x in factors] eq 80;

    if local_proof then
      vprint EvenConductorExponent_Genus2: "checking distinctness...";
      for i in [1..#factors] do
        f1 := factors[i];
        L1 := f1`L;
        M1 := f1`M;
        for j in [i+1..#factors] do
          f2 := factors[j];
          L2 := f2`L;
          M2 := f2`M;
          if Degree(L1, K) eq Degree(L2, K)
          and Degree(M1, L1) eq Degree(M2, L2)
          and RamificationDegree(L1, K) eq RamificationDegree(L2, K)
          and RamificationDegree(M1, L1) eq RamificationDegree(M2, L2)
          and Vertices(RamificationPolygon(L1, K)) eq Vertices(RamificationPolygon(L2, K))
          and Vertices(RamificationPolygon(M1, L1)) eq Vertices(RamificationPolygon(M2, L2))
          then
            if f1`c2_fac_idx eq f2`c2_fac_idx then
              // c2 are the same
              assert L1 eq L2;
              // check that val(b3_fac(b3)) > val(b3_fac(b3'))
              assert UseStrategy
                select ValuationGtValuation(x1, x2 : Strategy:=Strategy)
                else   ValuationGtValuation(x1, x2)
                where x1 := Evaluate(f1`b3_fac, f1`b3)
                where x2 := Evaluate(f1`b3_fac, f2`b3);
            else
              // check that val(c2_fac(c2)) > val(c2_fac(c2'))
              assert UseStrategy
                select ValuationGtValuation(x1, x2 : Strategy:=Strategy)
                else   ValuationGtValuation(x1, x2)
                where x1 := Evaluate(f1`c2_fac, f1`c2)
                where x2 := Evaluate(f1`c2_fac, f2`c2);
            end if;
          end if;
        end for;
      end for;
      log(~timer, "local proof (distinctness)");
    end if;

    r`factors := factors;
    r`success := true;
  end procedure;

  // call this procedure, possibly catching the result
  if Catch then
    try
      go(~r);
    catch err
      r`success := false;
      r`err := err;
    end try;
  else
    go(~r);
  end if;

  // done
  return r;
end function;

function crvpol(C)
  f, h := HyperellipticPolynomials(C);
  return 4*f + h^2;
end function;

function prime_ideal(K, p)
  OK := Integers(K);
  pp := ideal<OK | p>;
  error if not IsPrime(pp), "Argument 2 must be a prime over Argument 1";
  return pp;
end function;

function evencondexpdata(C, p : UseRegularModels:=true, MaximumPrecision:=Infinity(), UseOgg:=true, Proof:=true, MobiusRandomize:=0)
  error if Genus(C) ne 2, "Argument 1 must have genus 2";
  error if Type(UseRegularModels) ne BoolElt, "UseRegularModels must be a boolean";
  error if Type(UseOgg) ne BoolElt, "UseOgg must be a boolean";
  K := BaseField(C);
  if UseOgg then
    D := Discriminant(C);
    if Valuation(D, p) lt 12 then
      return rec<recformat<Exponent, WildExponent, TameExponent> | Exponent:=Conductor(C,p)>;
    end if;
  end if;
  OK := Integers(K);
  pp := ideal<OK | p>;
  error if not (IsPrime(pp) and IsDivisibleBy(AbsoluteNorm(pp), 2)), "Arugment 2 must be (coercible to) a prime over Argument 1 above 2";
  f := crvpol(C);
  r := find_3torsion(f, pp : MaxPrec:=MaximumPrecision, Proof:=Proof, MobiusRandomize:=MobiusRandomize);
  dues := [<Degree(L,K), Max(UpperBreaks(TransitionFunction(L,K))), RamificationDegree(L,K)> where L:=x`M : x in r`factors] where K:=r`K;
  s := conductor_exponent_data(f, pp, dues : UseRegularModels:=UseRegularModels, ExtraData:=r);
  return s;
end function;

function evencondexp(C, p : UseRegularModels:=true, MaximumPrecision:=Infinity(), UseOgg:=true, Proof:=true, MobiusRandomize:=0)
  r := evencondexpdata(C, p : UseRegularModels:=UseRegularModels, MaximumPrecision:=MaximumPrecision, UseOgg:=UseOgg, Proof:=Proof, MobiusRandomize:=MobiusRandomize);
  if assigned r`Exponent then
    return r`Exponent;
  else
    error <Sprintf("could not compute exponent (wild exponent is %o, exponent in %o)", r`WildExponent, {r`WildExponent+i : i in [1..3]}), r`Error>;
  end if;
end function;

function is_even(p)
  return IsDivisibleBy(AbsoluteNorm(p), 2);
end function;

intrinsic EvenConductorExponent_Genus2(C :: CrvHyp[FldRat], p : UseRegularModels:=true, MaximumPrecision:=Infinity(), UseOgg:=true, Proof:=true, MobiusRandomize:=0) -> RngIntElt
  {The conductor exponent of C at prime p.}
  return evencondexp(C, p : UseRegularModels:=UseRegularModels, MaximumPrecision:=MaximumPrecision, UseOgg:=UseOgg, Proof:=Proof, MobiusRandomize:=MobiusRandomize);
end intrinsic;

intrinsic EvenConductorExponent_Genus2(C :: CrvHyp[FldNum], p : UseRegularModels:=true, MaximumPrecision:=Infinity(), UseOgg:=true, Proof:=true, MobiusRandomize:=0) -> RngIntElt
  {"}
  return evencondexp(C, p : UseRegularModels:=UseRegularModels, MaximumPrecision:=MaximumPrecision, UseOgg:=UseOgg, Proof:=Proof, MobiusRandomize:=MobiusRandomize);
end intrinsic;

intrinsic EvenConductorExponent_Genus2(C :: CrvHyp[FldRat] : UseRegularModels:=true, MaximumPrecision:=Infinity(), UseOgg:=true, Proof:=true, MobiusRandomize:=0) -> RngIntElt
  {The conductor exponent of C at 2.}
  return evencondexp(C, 2 : UseRegularModels:=UseRegularModels, MaximumPrecision:=MaximumPrecision, UseOgg:=UseOgg, Proof:=Proof, MobiusRandomize:=MobiusRandomize);
end intrinsic;

intrinsic EvenConductorExponentData_Genus2(C :: CrvHyp[FldRat], p : UseRegularModels:=true, MaximumPrecision:=Infinity(), UseOgg:=true, Proof:=true, MobiusRandomize:=0) -> Rec
  {Data relating to the conductor exponent of C at prime p.}
  return evencondexpdata(C, p : UseRegularModels:=UseRegularModels, MaximumPrecision:=MaximumPrecision, UseOgg:=UseOgg, Proof:=Proof, MobiusRandomize:=MobiusRandomize);
end intrinsic;

intrinsic EvenConductorExponentData_Genus2(C :: CrvHyp[FldNum], p : UseRegularModels:=true, MaximumPrecision:=Infinity(), UseOgg:=true, Proof:=true, MobiusRandomize:=0) -> Rec
  {"}
  return evencondexpdata(C, p : UseRegularModels:=UseRegularModels, MaximumPrecision:=MaximumPrecision, UseOgg:=UseOgg, Proof:=Proof, MobiusRandomize:=MobiusRandomize);
end intrinsic;

intrinsic EvenConductorExponentData_Genus2(C :: CrvHyp[FldRat] : UseRegularModels:=true, MaximumPrecision:=Infinity(), UseOgg:=true, Proof:=true, MobiusRandomize:=0) -> Rec
  {Data relating to the conductor exponent of C at 2.}
  return evencondexpdata(C, 2 : UseRegularModels:=UseRegularModels, MaximumPrecision:=MaximumPrecision, UseOgg:=UseOgg, Proof:=Proof, MobiusRandomize:=MobiusRandomize);
end intrinsic;

intrinsic OddConductor(C :: CrvHyp[FldRat]) -> RngIntElt
  {The odd part of the the conductor of C.}
  D := Discriminant(C);
  return &*[Z | p^Conductor(C, p) : p in PrimeDivisors(Numerator(D) * Denominator(D)) | p ne 2];
end intrinsic;

intrinsic OddConductor(C :: CrvHyp[FldNum]) -> .
  {"}
  D := Discriminant(C);
  K := BaseField(C);
  OK := Integers(K);
  return &*[p^Conductor(C, p) : fac in Factorization(ideal<OK | Numerator(D) * Denominator(D)>) | not is_even(p) where p:=fac[1]];
end intrinsic;

intrinsic Conductor_Genus2(C :: CrvHyp[FldRat] : UseRegularModels:=true, MaximumPrecision:=Infinity(), UseOgg:=true, Proof:=true, MobiusRandomize:=0) -> RngIntElt
  {The conductor of C.}
  D := Discriminant(C);
  return &*[Z | p^(p eq 2 select EvenConductorExponent_Genus2(C : UseRegularModels:=UseRegularModels, MaximumPrecision:=MaximumPrecision, UseOgg:=UseOgg, Proof:=Proof, MobiusRandomize:=MobiusRandomize) else Conductor(C, p)) : p in PrimeDivisors(Numerator(D) * Denominator(D))];
end intrinsic;

intrinsic Conductor_Genus2(C :: CrvHyp[FldNum] : UseRegularModels:=true, MaximumPrecision:=Infinity(), UseOgg:=true, Proof:=true, MobiusRandomize:=0) -> RngOrdIdl
  {The conductor of C.}
  D := Discriminant(C);
  F := BaseField(C);
  OF := Integers(F);
  return &*[PowerIdeal(OF) | p^exponent where exponent := is_even(p) select EvenConductorExponent_Genus2(C, p : UseRegularModels:=UseRegularModels, MaximumPrecision:=MaximumPrecision, UseOgg:=UseOgg, Proof:=Proof, MobiusRandomize:=MobiusRandomize) else Conductor(C, p) where p:=fac[1] : fac in Factorization(ideal<OF | Numerator(D)*Denominator(D)>)];
end intrinsic;