// degree-13.m /////////////////////////////////////////////////////////////////
// 
// Benjamin Smith
// INRIA Saclay--Île-de-France 2009
// 
// Contact: smith@lix.polytechnique.fr
//
// File last updated 15 June 2010
//
// This file is distributed with the article
// "Families of explicitly isogenous Jacobians of variable-separated curves"
//
// This file is an executable Magma program: see
//	http://magma.maths.usyd.edu.au/
// It contains a series of definitions, followed by a series of assertions
// to verify the correctness of the definitions.
// If the assertions are correct, then no output is produced.
// If the assertions no not hold, then executing this file will produce a
// runtime error.
// 
// We define:
//	k_0	: A real quadratic field
//     	k	: The base field (a quadratic imaginary extension of k_0)
//      alpha_13: A generator of k over k_0
//	K	: A rational function field over k
//	t	: A generator of K over k
//	sigma	: An automorphism of K extending complex conjugation on k
//     	f_13	: A univariate polynomial over K 
//	g_13	: A univariate polynomial over K
//	A_13	: A bivariate polynomial over K
//	B_13	: A bivariate polynomial over K
//      M_12	: A 12x12 matrix over K
//
// The file concludes with an assertion: 
//	f_13(x_1) - g_13(x_2) = A_13(x_1,x_2)B_13(x_1,x_2).
// 
//
// Briefly, the correspondence V(y_1 - y_2, A_13(x_1,x_2))
// induces an isogeny between the Jacobians of the curves
//     X: P_d(y_1) = f_13(x_1)   and   Y: P_d(y_2) = g_13(x_2) 
// where P_d is the generic monic polynomial of degree d.
//
// The isogeny splits multiplication-by-3 .
//
// The regular differentials on X (resp. Y) 
// have bases of the form 
//      w_{i,j} = y_1^{i-1}d(x_1^j)/P_d'(y_1)   (on X)
// and
//      w_{i,j}' = y_2^{i-1}d(x_2^j)/P_d'(y_2)  (on Y),
// where (i,j) ranges over the interior integer points of the Newton polygon
// of X and Y, which is { (x,y) in RR^2 : x >= 0, y >= 0, dx + 13y <= 13d }.
//
// The homomorphism of regular differentials induced by the isogeny
// is given by the diagonal block matrix \oplus_i M_j ,
// where M_j is the upper-left jxj submatrix of M_12.
//
// We note that f_13 = 13g, where g is the polynomial defined in \S5.3 
// of Cassou-Nogues and Couveignes, "Factorisations explicites de g(y)-h(z)".

// To navigate through this file, use the following tags:
//	BASEFIELD	: Section defining base field and sigma
//	POLYNOMIALS	: Section defining f_13 and g_13
//	FACTORS		: Section defining A_13 and B_13
//	MATRIX		: Section defining M_12
//	ASSERTIONS	: Section containing assertions

// Section BASEFIELD ///////////////////////////////////////////////////////////

k_0 := ext< RationalField( ) | Polynomial([3,-5,1]) >;
beta_13 := k_0.1;
k := ext< k_0 | Polynomial([ beta_13, (beta_13 - 2), 1 ]) >;
alpha_13 := k.1;
K := FunctionField(k);
t := K.1;

sigma := hom< K -> K | hom<k -> K | Norm(alpha_13)/alpha_13>, t> ;
// sigma essentially acts as complex conjugation on coefficients


// Section POLYNOMIALS /////////////////////////////////////////////////////////

f_13 := Polynomial([
  ((-628678908*beta_13 + 2705064336)*alpha_13 - 628678908*beta_13)*t^6 + ((-172388736*beta_13 + 741750048)*alpha_13 - 172388736*beta_13)*t^5, // trailing coefficient
  ((-353229552*beta_13 + 1519867908)*alpha_13 + (144804348*beta_13 - 623060100))*t^6 + ((957009573*beta_13 - 4117797567)*alpha_13 - 1259079471*beta_13 + 5417536527)*t^5 + ((10016136*beta_13 - 43097184)*alpha_13 - 3950856*beta_13 + 16999632)*t^4,
  ((652044978*beta_13 - 2805603723)*alpha_13 - 411068034*beta_13 + 1768733577)*t^5 + ((-43465734*beta_13 + 187023330)*alpha_13 + (48682296*beta_13 - 209469078))*t^4,
  ((23756733*beta_13 - 102221028)*alpha_13 + (34038225*beta_13 - 146460717))*t^5 + ((-104073255*beta_13 + 447804045)*alpha_13 + (44891496*beta_13 - 193158108))*t^4,
  ((-14701986*beta_13 + 63260028)*alpha_13 - 21742344*beta_13 + 93552732)*t^4 + ((930852*beta_13 - 4005261)*alpha_13 - 490347*beta_13 + 2109861)*t^3,
  ((6547203*beta_13 - 28170207)*alpha_13 - 7610031*beta_13 + 32746194)*t^4 + ((-234468*beta_13 + 1008774)*alpha_13 + (1559142*beta_13 - 6708663))*t^3,
  ((-1923129*beta_13 + 8274474)*alpha_13 + (1767987*beta_13 - 7607574))*t^3,
  ((-387153*beta_13 + 1665495)*alpha_13 + (155844*beta_13 - 671463))*t^3 + ((21294*beta_13 - 91611)*alpha_13 - 16965*beta_13 + 73008)*t^2,
  ((21060*beta_13 - 90558)*alpha_13 - 468*beta_13 + 2106)*t^2,
  ((-2262*beta_13 + 9789)*alpha_13 + (6747*beta_13 - 28821))*t^2,
  ((117*beta_13 - 507)*alpha_13 - 156*beta_13 + 663)*t,
  ((117*beta_13 - 507)*alpha_13 - 78*beta_13 + 312)*t,
  0,
  1 // leading coefficient
] );

g_13 := Polynomial([sigma(c): c in Coefficients(f_13)]);


// Section FACTORS /////////////////////////////////////////////////////////////

R := PolynomialRing(K,2);
x_1 := R.1;
x_2 := R.2;

A_13 := x_1^4 + ((-beta_13 + 4)*alpha_13 - 2)*x_1^3*x_2 + (beta_13 - 3)*x_1^2*x_2^2 + 3*((17*beta_13 - 73)*alpha_13 - 12*beta_13 + 50)*t*x_1^2 + ((beta_13 - 4)*alpha_13 - beta_13 + 3)*x_1*x_2^3 + (-27*beta_13 + 126)*t*x_1*x_2 + ((15*beta_13 - 66)*alpha_13 - 27*beta_13 + 114)*t*x_1 + x_2^4 + ((-51*beta_13 + 219)*alpha_13 + (30*beta_13 - 135))*t*x_2^2 + ((-15*beta_13 + 66)*alpha_13 - 6*beta_13 + 27)*t*x_2 + (564*beta_13 - 2424)*t^2;

B_13 := x_1^9 + ((beta_13 - 4)*alpha_13 + 2)*x_1^8*x_2 + (alpha_13 + (beta_13 - 2))*x_1^7*x_2^2 + ((66*beta_13 - 288)*alpha_13 - 42*beta_13 + 162)*t*x_1^7 + ((beta_13 - 3)*alpha_13 + 2)*x_1^6*x_2^3 + ((-33*beta_13 + 132)*alpha_13 + (54*beta_13 - 264))*t*x_1^6*x_2 + ((102*beta_13 - 441)*alpha_13 - 129*beta_13 + 549)*t*x_1^6 + (alpha_13 + (beta_13 - 3))*x_1^5*x_2^4 + (-15*alpha_13 - 18*beta_13 + 51)*t*x_1^5*x_2^2 + ((147*beta_13 - 636)*alpha_13 + (3*beta_13 - 21))*t*x_1^5*x_2 + ((-1362*beta_13 + 5901)*alpha_13 + (2169*beta_13 - 9225))*t^2*x_1^5 + (alpha_13 + 1)*x_1^4*x_2^5 + ((-48*beta_13 + 189)*alpha_13 + (60*beta_13 - 279))*t*x_1^4*x_2^3 + ((-153*beta_13 + 654)*alpha_13 + (81*beta_13 - 354))*t*x_1^4*x_2^2 + ((-1146*beta_13 + 5010)*alpha_13 + (6*beta_13 + 141))*t^2*x_1^4*x_2 + ((5823*beta_13 - 25029)*alpha_13 + (3204*beta_13 - 13743))*t^2*x_1^4 + ((beta_13 - 3)*alpha_13 + 1)*x_1^3*x_2^6 + ((-48*beta_13 + 189)*alpha_13 - 15*beta_13 + 45)*t*x_1^3*x_2^4 + ((162*beta_13 - 702)*alpha_13 - 108*beta_13 + 459)*t*x_1^3*x_2^3 + ((-750*beta_13 + 3318)*alpha_13 + (1383*beta_13 - 5817))*t^2*x_1^3*x_2^2 + ((-17244*beta_13 + 74232)*alpha_13 + (12492*beta_13 - 53694))*t^2*x_1^3*x_2 + (((-15066*beta_13 + 64692)*alpha_13 - 10260*beta_13 + 43902)*t^3 + ((11880*beta_13 - 51111)*alpha_13 - 8820*beta_13 + 37962)*t^2)*x_1^3 + alpha_13*x_1^2*x_2^7 + (-15*alpha_13 + (3*beta_13 - 21))*t*x_1^2*x_2^5 + ((-153*beta_13 + 654)*alpha_13 + (114*beta_13 - 495))*t*x_1^2*x_2^4 + ((-750*beta_13 + 3318)*alpha_13 - 315*beta_13 + 1431)*t^2*x_1^2*x_2^3 + ((3132*beta_13 - 13446)*alpha_13 - 2025*beta_13 + 8748)*t^2*x_1^2*x_2^2 + (((13374*beta_13 - 57771)*alpha_13 - 2448*beta_13 + 10215)*t^3 + ((-3987*beta_13 + 17163)*alpha_13 + (10359*beta_13 - 44559))*t^2)*x_1^2*x_2 + ((-315549*beta_13 + 1357668)*alpha_13 + (216567*beta_13 - 931905))*t^3*x_1^2 + ((beta_13 - 4)*alpha_13 - beta_13 + 3)*x_1*x_2^8 + ((-33*beta_13 + 132)*alpha_13 - 21*beta_13 + 99)*t*x_1*x_2^6 + ((147*beta_13 - 636)*alpha_13 - 198*beta_13 + 852)*t*x_1*x_2^5 + ((-1146*beta_13 + 5010)*alpha_13 + (1566*beta_13 - 6723))*t^2*x_1*x_2^4 + ((-17244*beta_13 + 74232)*alpha_13 + (10008*beta_13 - 43038))*t^2*x_1*x_2^3 + (((13374*beta_13 - 57771)*alpha_13 - 15201*beta_13 + 65205)*t^3 + ((-3987*beta_13 + 17163)*alpha_13 - 5157*beta_13 + 22194)*t^2)*x_1*x_2^2 + ((45054*beta_13 - 193950)*alpha_13 - 29394*beta_13 + 126369)*t^3*x_1*x_2 + (((173979*beta_13 - 748449)*alpha_13 - 71253*beta_13 + 306774)*t^4 + ((-453276*beta_13 + 1950318)*alpha_13 + (612900*beta_13 - 2637198))*t^3)*x_1 + -1*x_2^9 + ((66*beta_13 - 288)*alpha_13 - 48*beta_13 + 216)*t*x_2^7 + ((102*beta_13 - 441)*alpha_13 - 6*beta_13 + 27)*t*x_2^6 + ((-1362*beta_13 + 5901)*alpha_13 - 354*beta_13 + 1509)*t^2*x_2^5 + ((5823*beta_13 - 25029)*alpha_13 - 10764*beta_13 + 46332)*t^2*x_2^4 + (((-15066*beta_13 + 64692)*alpha_13 + (29754*beta_13 - 128088))*t^3 + ((11880*beta_13 - 51111)*alpha_13 - 6651*beta_13 + 28620)*t^2)*x_2^3 + ((-315549*beta_13 + 1357668)*alpha_13 + (194454*beta_13 - 836784))*t^3*x_2^2 + (((173979*beta_13 - 748449)*alpha_13 - 155259*beta_13 + 668187)*t^4 + ((-453276*beta_13 + 1950318)*alpha_13 - 22410*beta_13 + 96390)*t^3)*x_2 + ((619164*beta_13 - 2664090)*alpha_13 - 403299*beta_13 + 1735344)*t^4 + ((169776*beta_13 - 730512)*alpha_13 - 110592*beta_13 + 475848)*t^3
;

// Section MATRIX //////////////////////////////////////////////////////////////

M_12 := Matrix(
[
  [
    (beta_13 - 4)*alpha_13 + 2,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0
  ],
  [
    0,
    alpha_13 + 1,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0
  ],
  [
    ((9*beta_13 - 36)*alpha_13 - 54*beta_13 + 234)*t,
    0,
    (beta_13 - 4)*alpha_13 + 2,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0
  ],
  [
    ((-144*beta_13 + 624)*alpha_13 + (96*beta_13 - 408))*t,
    ((-48*beta_13 + 216)*alpha_13 + (72*beta_13 - 312))*t,
    0,
    (-beta_13 + 4)*alpha_13 + beta_13 - 3,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0
  ],
  [
    ((-5775*beta_13 + 24870)*alpha_13 + (3945*beta_13 - 16980))*t^2,
    ((-150*beta_13 + 645)*alpha_13 + (120*beta_13 - 525))*t,
    ((-60*beta_13 + 255)*alpha_13 + (15*beta_13 - 60))*t,
    0,
    alpha_13 + 1,
    0,
    0,
    0,
    0,
    0,
    0,
    0
  ],
  [
    ((-5238*beta_13 + 22572)*alpha_13 + (19872*beta_13 - 85482))*t^2,
    ((8928*beta_13 - 38349)*alpha_13 - 3006*beta_13 + 12897)*t^2,
    ((-234*beta_13 + 1008)*alpha_13 + (54*beta_13 - 234))*t,
    ((-90*beta_13 + 378)*alpha_13 + (126*beta_13 - 540))*t,
    0,
    alpha_13 + 1,
    0,
    0,
    0,
    0,
    0,
    0
  ],
  [
    ((129339*beta_13 - 556353)*alpha_13 + (87003*beta_13 - 374346))*t^3 + ((14994*beta_13 - 64512)*alpha_13 - 5922*beta_13 + 25452)*t^2,
    ((1575*beta_13 - 6804)*alpha_13 + (5796*beta_13 - 25137))*t^2,
    ((-2772*beta_13 + 11844)*alpha_13 + (7980*beta_13 - 34419))*t^2,
    ((84*beta_13 - 357)*alpha_13 - 84*beta_13 + 378)*t,
    ((-210*beta_13 + 924)*alpha_13 + (147*beta_13 - 609))*t,
    0,
    -alpha_13 - beta_13 + 3,
    0,
    0,
    0,
    0,
    0
  ],
  [
    ((4032720*beta_13 - 17351712)*alpha_13 - 2272032*beta_13 + 9776016)*t^3,
    ((578376*beta_13 - 2488176)*alpha_13 - 794448*beta_13 + 3418200)*t^3 + ((16344*beta_13 - 70344)*alpha_13 - 4176*beta_13 + 17928)*t^2,
    ((-23112*beta_13 + 99432)*alpha_13 + (40464*beta_13 - 174168))*t^2,
    ((11256*beta_13 - 48576)*alpha_13 + (2016*beta_13 - 8784))*t^2,
    ((-144*beta_13 + 624)*alpha_13 + (96*beta_13 - 408))*t,
    ((-240*beta_13 + 1056)*alpha_13 + (168*beta_13 - 696))*t,
    0,
    -alpha_13 - beta_13 + 3,
    0,
    0,
    0,
    0
  ],
  [
    ((18352737*beta_13 - 78966576)*alpha_13 - 20806227*beta_13 + 89525007)*t^4 + ((2638980*beta_13 - 11354904)*alpha_13 - 4047165*beta_13 + 17413623)*t^3,
    ((226719*beta_13 - 975888)*alpha_13 - 54675*beta_13 + 233037)*t^3,
    ((1408671*beta_13 - 6062040)*alpha_13 - 742689*beta_13 + 3194559)*t^3 + ((18387*beta_13 - 79137)*alpha_13 + (11664*beta_13 - 50220))*t^2,
    ((-8748*beta_13 + 37665)*alpha_13 - 7452*beta_13 + 32319)*t^2,
    ((-10503*beta_13 + 45387)*alpha_13 + (21087*beta_13 - 90450))*t^2,
    ((108*beta_13 - 459)*alpha_13 - 27*beta_13 + 108)*t,
    ((-135*beta_13 + 567)*alpha_13 - 27*beta_13 + 81)*t,
    0,
    (beta_13 - 4)*alpha_13 + 2,
    0,
    0,
    0
  ],
  [
    ((39024180*beta_13 - 167911380)*alpha_13 - 241747740*beta_13 + 1040184990)*t^4 + ((-957960*beta_13 + 4121820)*alpha_13 - 25380*beta_13 + 109080)*t^3,
    ((-64741950*beta_13 + 278572905)*alpha_13 + (15140385*beta_13 - 65145600))*t^4 + ((4187700*beta_13 - 18019260)*alpha_13 - 4061880*beta_13 + 17476560)*t^3,
    ((6953760*beta_13 - 29920950)*alpha_13 - 4502340*beta_13 + 19372140)*t^3,
    ((1996920*beta_13 - 8593560)*alpha_13 - 1810350*beta_13 + 7788420)*t^3 + ((-25785*beta_13 + 110970)*alpha_13 + (35865*beta_13 - 154305))*t^2,
    ((44820*beta_13 - 192780)*alpha_13 + (2250*beta_13 - 9720))*t^2,
    ((4815*beta_13 - 20520)*alpha_13 + (12360*beta_13 - 52935))*t^2,
    ((-390*beta_13 + 1680)*alpha_13 + (420*beta_13 - 1800))*t,
    ((-120*beta_13 + 510)*alpha_13 + (120*beta_13 - 540))*t,
    0,
    (-beta_13 + 4)*alpha_13 + beta_13 - 3,
    0,
    0
  ],
  [
    ((-1693341936*beta_13 + 7286077656)*alpha_13 + (584953083*beta_13 - 2516916402))*t^5 + ((-791593803*beta_13 + 3406050648)*alpha_13 + (269003592*beta_13 - 1157466024))*t^4,
    ((24857118*beta_13 - 106957422)*alpha_13 + (17918901*beta_13 - 77119614))*t^4 + ((-434808*beta_13 + 1870803)*alpha_13 - 1004454*beta_13 + 4321944)*t^3,
    ((37477440*beta_13 - 161263674)*alpha_13 - 96114447*beta_13 + 413549136)*t^4 + ((11722293*beta_13 - 50438916)*alpha_13 - 10421730*beta_13 + 44841951)*t^3,
    ((-1932678*beta_13 + 8315604)*alpha_13 + (1547073*beta_13 - 6653394))*t^3,
    ((2903373*beta_13 - 12490731)*alpha_13 - 964953*beta_13 + 4155624)*t^3 + ((-7128*beta_13 + 30690)*alpha_13 + (18909*beta_13 - 81378))*t^2,
    ((11484*beta_13 - 49302)*alpha_13 + (6930*beta_13 - 30195))*t^2,
    ((-33825*beta_13 + 145266)*alpha_13 + (33858*beta_13 - 146421))*t^2,
    ((-330*beta_13 + 1419)*alpha_13 + (165*beta_13 - 693))*t,
    ((-132*beta_13 + 594)*alpha_13 + 66)*t,
    0,
    -alpha_13 - beta_13 + 3,
    0
  ],
  [
    ((-37688478984*beta_13 + 162165074760)*alpha_13 + (25015489200*beta_13 - 107636051016))*t^5 + ((-516711312*beta_13 + 2223291564)*alpha_13 + (528134256*beta_13 - 2272445604))*t^4,
    ((-4007119896*beta_13 + 17241754608)*alpha_13 + (5245380504*beta_13 - 22569690312))*t^5 + ((-153973872*beta_13 + 662507586)*alpha_13 - 307193796*beta_13 + 1321776144)*t^4,
    ((-332027748*beta_13 + 1428634584)*alpha_13 - 228732660*beta_13 + 984184344)*t^4 + ((1238652*beta_13 - 5329692)*alpha_13 - 3915324*beta_13 + 16846920)*t^3,
    ((-97501131*beta_13 + 419516604)*alpha_13 - 25814295*beta_13 + 111065175)*t^4 + ((10253628*beta_13 - 44118432)*alpha_13 - 1592784*beta_13 + 6854544)*t^3,
    ((13448160*beta_13 - 57863268)*alpha_13 - 14402772*beta_13 + 61971804)*t^3,
    ((2535516*beta_13 - 10908108)*alpha_13 - 2546532*beta_13 + 10959516)*t^3 + ((-41688*beta_13 + 179334)*alpha_13 + (29322*beta_13 - 126306))*t^2,
    ((72360*beta_13 - 311472)*alpha_13 + (28728*beta_13 - 123768))*t^2,
    ((38790*beta_13 - 167058)*alpha_13 - 20844*beta_13 + 89316)*t^2,
    ((-432*beta_13 + 1872)*alpha_13 + (288*beta_13 - 1224))*t,
    ((36*beta_13 - 144)*alpha_13 + (180*beta_13 - 756))*t,
    0,
    (-beta_13 + 4)*alpha_13 + beta_13 - 3
  ]
]
);


// Section ASSERTIONS //////////////////////////////////////////////////////////

assert (Evaluate(f_13,x_1) - Evaluate(g_13,x_2)) eq A_13*B_13;
sigmaM_12 := Matrix(12,12,[sigma(M_12[i][j]): i, j in [1..12]]);
assert M_12*sigmaM_12 eq 3*IdentityMatrix(K,12);

// End of File degree-13.m /////////////////////////////////////////////////////
