// degree-21.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	: The base field (a quadratic imaginary field)
//	alpha_21: A generator of k over QQ
//	sigma	: An automorphism of k corresponding to complex conjugation
//     	f_21	: A univariate polynomial over k 
//	g_21	: A univariate polynomial over k
//	A_21	: A bivariate polynomial over k
//	B_21	: A bivariate polynomial over k
//	M_20	: A 20x20 matrix over k
//
// The file concludes with an assertion: 
//	f_21(x_1) - g_21(x_2) = A_21(x_1,x_2)B_21(x_1,x_2).
// 
// Briefly, the correspondence V(y_1 - y_2, A_21(x_1,x_2))
// induces an isogeny between the Jacobians of the curves
//     X: P_d(y_1) = f_21(x_1)   and   Y: P_d(y_2) = g_21(x_2) 
// where P_d is the generic monic polynomial of degree d.
// 
// The isogeny splits multiplication-by-4 .
//
// 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 + 11y <= 11d }.
//
// 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_20.
//
// We note that f_21(x) = 2^(21)g(x/2), where g is the polynomial in \S5.5 
// 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_21
//	FACTORS		: Section defining A_21 and B_21
//	MATRIX		: Section defining M_20
//	ASSERTIONS	: Section containing assertions

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

k := ext< RationalField( ) | Polynomial([2,-1,1]) >;
alpha_21 := k.1;

sigma := hom< k -> k | Norm(alpha_21)/alpha_21 >;



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

a := alpha_21;
abar := Norm(a)/a;

f_21 := Polynomial([
  4696767684*alpha_21,
  8637088971*alpha_21 + 9205492695,
  1708403396*alpha_21 + 16523766868,
  -2459323342*alpha_21 + 18242100282,
  -4332603072*alpha_21 + 10737937392,
  -4341402044*alpha_21 + 5721876405,
  -2279293856*alpha_21 + 2006258800,
  -1090995696*alpha_21 + 266146344,
  -414193752*alpha_21 - 32069128,
  -99408078*alpha_21 - 104516426,
  -25341624*alpha_21 - 54772872,
  -1650124*alpha_21 - 18355540,
  1249248*alpha_21 - 6783504,
  417060*alpha_21 - 1450470,
  227136*alpha_21 - 306320,
  46816*alpha_21 - 64568,
  8820*alpha_21 - 2604,
  2331*alpha_21 - 861,
  84*alpha_21 + 84,
  42*alpha_21 + 42,
  0,
  1
]);

g_21 := Polynomial([sigma(c): c in Coefficients(f_21)]);

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

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

A_21 := x_1^5 + (alpha_21 + 1)*x_1^4*x_2 + 2*alpha_21*x_1^3*x_2^2 
	+ (10*alpha_21 + 18)*x_1^3 + (2*alpha_21 - 2)*x_1^2*x_2^3 
	+ (32*alpha_21 - 8)*x_1^2*x_2 + (20*alpha_21 + 4)*x_1^2 
	+ (alpha_21 - 2)*x_1*x_2^4 + (32*alpha_21 - 24)*x_1*x_2^2 
	+ (32*alpha_21 - 16)*x_1*x_2 + (107*alpha_21 + 55)*x_1 - x_2^5 
	+ (10*alpha_21 - 28)*x_2^3 + (20*alpha_21 - 24)*x_2^2 
	+ (107*alpha_21 - 162)*x_2 + 136*alpha_21 - 68
;

B_21 := x_1^16 + (-alpha_21 - 1)*x_1^15*x_2 + (alpha_21 - 1)*x_1^14*x_2^2 
	+ (32*alpha_21 + 24)*x_1^14 + (alpha_21 + 1)*x_1^13*x_2^3 
	+ (-82*alpha_21 + 46)*x_1^13*x_2 + (64*alpha_21 + 80)*x_1^13 
	+ (-2*alpha_21 + 1)*x_1^12*x_2^4 + (12*alpha_21 - 92)*x_1^12*x_2^2 
	+ (-196*alpha_21 + 28)*x_1^12*x_2 + (1088*alpha_21 - 708)*x_1^12 
	+ (alpha_21 - 2)*x_1^11*x_2^5 + (92*alpha_21 - 38)*x_1^11*x_2^3 
	+ (100*alpha_21 - 176)*x_1^11*x_2^2 
	+ (-1006*alpha_21 + 2659)*x_1^11*x_2 + (4844*alpha_21 - 1512)*x_1^11 
	+ (alpha_21 + 1)*x_1^10*x_2^6 + (-64*alpha_21 + 152)*x_1^10*x_2^4 
	+ (140*alpha_21 + 28)*x_1^10*x_2^3 
	+ (-1354*alpha_21 - 786)*x_1^10*x_2^2 
	+ (-7092*alpha_21 + 10140)*x_1^10*x_2 + (12544*alpha_21 - 22296)*x_1^10 
	+ (-2*alpha_21 + 2)*x_1^9*x_2^7 + (-48*alpha_21 - 80)*x_1^9*x_2^5 
	+ (-224*alpha_21 + 224)*x_1^9*x_2^4 
	+ (1477*alpha_21 - 3075)*x_1^9*x_2^3 
	+ (-1816*alpha_21 - 7688)*x_1^9*x_2^2 
	+ (3444*alpha_21 + 31452)*x_1^9*x_2 
	+ (70304*alpha_21 - 116240)*x_1^9 - 3*x_1^8*x_2^8 
	+ (92*alpha_21 - 100)*x_1^8*x_2^6 + (80*alpha_21 - 320)*x_1^8*x_2^5 
	+ (1236*alpha_21 + 2336)*x_1^8*x_2^4 
	+ (8156*alpha_21 - 7732)*x_1^8*x_2^3 
	+ (-19572*alpha_21 + 16828)*x_1^8*x_2^2 
	+ (4184*alpha_21 + 201832)*x_1^8*x_2 + (87040*alpha_21 - 303834)*x_1^8 
	+ 2*alpha_21*x_1^7*x_2^9 + 156*x_1^7*x_2^7 
	+ (160*alpha_21 + 88)*x_1^7*x_2^6 + (-2350*alpha_21 + 1952)*x_1^7*x_2^5 
	+ (-2568*alpha_21 + 14976)*x_1^7*x_2^4 
	+ (-7784*alpha_21 - 31952)*x_1^7*x_2^3 
	+ (-136952*alpha_21 + 35128)*x_1^7*x_2^2 
	+ (93081*alpha_21 + 271889)*x_1^7*x_2 
	+ (-12640*alpha_21 - 1326592)*x_1^7 + (-alpha_21 + 2)*x_1^6*x_2^10 
	+ (-92*alpha_21 - 8)*x_1^6*x_2^8 + (-160*alpha_21 + 248)*x_1^6*x_2^7 
	- 3266*x_1^6*x_2^6 + (-6744*alpha_21 - 4384)*x_1^6*x_2^5 
	+ (26124*alpha_21 - 12512)*x_1^6*x_2^4 
	+ (45576*alpha_21 - 235504)*x_1^6*x_2^3 
	+ (-104032*alpha_21 + 115949)*x_1^6*x_2^2 
	+ (1248768*alpha_21 + 403048)*x_1^6*x_2 
	+ (-181616*alpha_21 - 2743160)*x_1^6 + (-alpha_21 - 1)*x_1^5*x_2^11 
	+ (48*alpha_21 - 128)*x_1^5*x_2^9 + (-80*alpha_21 - 240)*x_1^5*x_2^8 
	+ (2350*alpha_21 - 398)*x_1^5*x_2^7 
	+ (6744*alpha_21 - 11128)*x_1^5*x_2^6 + 28840*x_1^5*x_2^5 
	+ (145584*alpha_21 + 67488)*x_1^5*x_2^4 
	+ (-57862*alpha_21 - 122154)*x_1^5*x_2^3 
	+ (-732104*alpha_21 + 1842296)*x_1^5*x_2^2 
	+ (2128238*alpha_21 + 1327198)*x_1^5*x_2 
	+ (-4506368*alpha_21 - 3115984)*x_1^5 + (2*alpha_21 - 1)*x_1^4*x_2^12 
	+ (64*alpha_21 + 88)*x_1^4*x_2^10 + 224*alpha_21*x_1^4*x_2^9 
	+ (-1236*alpha_21 + 3572)*x_1^4*x_2^8 
	+ (2568*alpha_21 + 12408)*x_1^4*x_2^7 
	+ (-26124*alpha_21 + 13612)*x_1^4*x_2^6 
	+ (-145584*alpha_21 + 213072)*x_1^4*x_2^5 + 54272*x_1^4*x_2^4 
	+ (-1319296*alpha_21 - 630480)*x_1^4*x_2^3 
	+ (-1860824*alpha_21 + 2048384)*x_1^4*x_2^2 
	+ (6064268*alpha_21 - 7168756)*x_1^4*x_2 
	+ (-10618304*alpha_21 - 7415300)*x_1^4 + (-alpha_21 + 2)*x_1^3*x_2^13 
	+ (-92*alpha_21 + 54)*x_1^3*x_2^11 + (-140*alpha_21 + 168)*x_1^3*x_2^10 
	+ (-1477*alpha_21 - 1598)*x_1^3*x_2^9 
	+ (-8156*alpha_21 + 424)*x_1^3*x_2^8 
	+ (7784*alpha_21 - 39736)*x_1^3*x_2^7 
	+ (-45576*alpha_21 - 189928)*x_1^3*x_2^6 
	+ (57862*alpha_21 - 180016)*x_1^3*x_2^5 
	+ (1319296*alpha_21 - 1949776)*x_1^3*x_2^4 - 2547348*x_1^3*x_2^3 
	+ (4561768*alpha_21 + 4011808)*x_1^3*x_2^2 
	+ (17943489*alpha_21 - 13177205)*x_1^3*x_2 
	+ (-18237896*alpha_21 + 10870992)*x_1^3 - alpha_21*x_1^2*x_2^14 
	+ (-12*alpha_21 - 80)*x_1^2*x_2^12 + (-100*alpha_21 - 76)*x_1^2*x_2^11 
	+ (1354*alpha_21 - 2140)*x_1^2*x_2^10 
	+ (1816*alpha_21 - 9504)*x_1^2*x_2^9 
	+ (19572*alpha_21 - 2744)*x_1^2*x_2^8 
	+ (136952*alpha_21 - 101824)*x_1^2*x_2^7 
	+ (104032*alpha_21 + 11917)*x_1^2*x_2^6 
	+ (732104*alpha_21 + 1110192)*x_1^2*x_2^5 
	+ (1860824*alpha_21 + 187560)*x_1^2*x_2^4 
	+ (-4561768*alpha_21 + 8573576)*x_1^2*x_2^3 + 19704964*x_1^2*x_2^2 
	+ (939660*alpha_21 - 14790164)*x_1^2*x_2 
	+ (-44841728*alpha_21 + 37826520)*x_1^2 + (alpha_21 - 2)*x_1*x_2^15 
	+ (82*alpha_21 - 36)*x_1*x_2^13 + (196*alpha_21 - 168)*x_1*x_2^12 
	+ (1006*alpha_21 + 1653)*x_1*x_2^11 + (7092*alpha_21 + 3048)*x_1*x_2^10 
	+ (-3444*alpha_21 + 34896)*x_1*x_2^9 
	+ (-4184*alpha_21 + 206016)*x_1*x_2^8 
	+ (-93081*alpha_21 + 364970)*x_1*x_2^7 
	+ (-1248768*alpha_21 + 1651816)*x_1*x_2^6 
	+ (-2128238*alpha_21 + 3455436)*x_1*x_2^5 
	+ (-6064268*alpha_21 - 1104488)*x_1*x_2^4 
	+ (-17943489*alpha_21 + 4766284)*x_1*x_2^3 
	+ (-939660*alpha_21 - 13850504)*x_1*x_2^2 - 71100456*x_1*x_2 
	+ (-25335840*alpha_21 + 21834000)*x_1 + x_2^16 
	+ (-32*alpha_21 + 56)*x_2^14 + (-64*alpha_21 + 144)*x_2^13 
	+ (-1088*alpha_21 + 380)*x_2^12 + (-4844*alpha_21 + 3332)*x_2^11 
	+ (-12544*alpha_21 - 9752)*x_2^10 + (-70304*alpha_21 - 45936)*x_2^9 
	+ (-87040*alpha_21 - 216794)*x_2^8 + (12640*alpha_21 - 1339232)*x_2^7 
	+ (181616*alpha_21 - 2924776)*x_2^6 + (4506368*alpha_21 - 7622352)*x_2^5
	+ (10618304*alpha_21 - 18033604)*x_2^4 
	+ (18237896*alpha_21 - 7366904)*x_2^3 
	+ (44841728*alpha_21 - 7015208)*x_2^2 
	+ (25335840*alpha_21 - 3501840)*x_2 + 69070113
;

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

M_20 := Matrix(
[
  [
    -alpha_21 - 1,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0
  ],
  [
    0,
    -alpha_21 - 1,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0
  ],
  [
    18*alpha_21 + 18,
    0,
    alpha_21 + 1,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0
  ],
  [
    48*alpha_21 - 80,
    24*alpha_21 - 40,
    0,
    -alpha_21 - 1,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0
  ],
  [
    -330*alpha_21 + 75,
    120*alpha_21 - 60,
    -10,
    0,
    alpha_21 - 2,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0
  ],
  [
    -1176*alpha_21 + 2856,
    -102*alpha_21 + 1050,
    -72*alpha_21 + 120,
    36*alpha_21 + 36,
    0,
    alpha_21 + 1,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0
  ],
  [
    1372*alpha_21 - 532,
    -2828*alpha_21 + 6412,
    -525*alpha_21 + 805,
    28*alpha_21 + 84,
    -28*alpha_21 + 112,
    0,
    2,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0
  ],
  [
    7872*alpha_21 - 75840,
    -8400*alpha_21 - 8912,
    160*alpha_21 - 4448,
    -936*alpha_21 - 744,
    0,
    -48*alpha_21 - 48,
    0,
    -alpha_21 - 1,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0
  ],
  [
    13023*alpha_21 - 157509,
    -21708*alpha_21 - 181548,
    6768*alpha_21 - 43416,
    -6408*alpha_21 - 2340,
    -1053*alpha_21 - 2934,
    -216*alpha_21 + 108,
    -90*alpha_21,
    0,
    -alpha_21 + 2,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0
  ],
  [
    473320*alpha_21 + 1134080,
    134470*alpha_21 - 204685,
    72680*alpha_21 + 44720,
    24640*alpha_21 + 13820,
    2440*alpha_21 - 3600,
    2880*alpha_21 + 510,
    40*alpha_21 - 160,
    120*alpha_21 - 60,
    0,
    alpha_21 - 2,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0
  ],
  [
    2479950*alpha_21 + 4910598,
    2927716*alpha_21 + 1707156,
    563904*alpha_21 + 848716,
    321684*alpha_21 - 160380,
    80696*alpha_21 + 968,
    12452*alpha_21 - 15004,
    3630*alpha_21 - 4950,
    132*alpha_21 - 220,
    -176,
    0,
    -alpha_21 - 1,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0
  ],
  [
    -15505488*alpha_21 - 2240400,
    5387376*alpha_21 + 4314672,
    -1998912*alpha_21 + 2067712,
    -436374*alpha_21 - 272022,
    -11904*alpha_21 + 204864,
    -102504*alpha_21 + 54488,
    2592*alpha_21 + 5088,
    -4188*alpha_21 + 7332,
    0,
    192,
    0,
    alpha_21 + 1,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0
  ],
  [
    -147164511*alpha_21 - 15491515,
    -82419896*alpha_21 + 44128136,
    -30193384*alpha_21 + 8673600,
    -8708076*alpha_21 + 11646596,
    -2342704*alpha_21 + 2925988,
    -318084*alpha_21 + 889772,
    -24024*alpha_21 + 232856,
    -208*alpha_21 + 23036,
    4745*alpha_21 + 4238,
    156*alpha_21 + 104,
    156*alpha_21 - 78,
    0,
    alpha_21 - 2,
    0,
    0,
    0,
    0,
    0,
    0,
    0
  ],
  [
    86612568*alpha_21 - 170161992,
    -306427044*alpha_21 + 195198668,
    -11901568*alpha_21 - 57843296,
    4103148*alpha_21 + 16112460,
    -4489072*alpha_21 - 2112544,
    1938587*alpha_21 - 2551619,
    -253680*alpha_21 + 168000,
    -2156*alpha_21 - 252532,
    -1680*alpha_21 + 9856,
    -5964*alpha_21 - 3024,
    56*alpha_21 + 168,
    -140*alpha_21 + 140,
    0,
    2,
    0,
    0,
    0,
    0,
    0,
    0
  ],
  [
    3910493280*alpha_21 - 3174239280,
    1086398460*alpha_21 - 1882319040,
    665580285*alpha_21 - 999997890,
    119296800*alpha_21 - 386051820,
    18892122*alpha_21 - 117095484,
    -356700*alpha_21 - 30784260,
    -3145905*alpha_21 - 4940310,
    -571140*alpha_21 - 910380,
    -258540*alpha_21 + 51200,
    -25860*alpha_21 - 1560,
    -7020*alpha_21 + 8145,
    -360*alpha_21 + 180,
    -90*alpha_21 + 180,
    0,
    -alpha_21 + 2,
    0,
    0,
    0,
    0,
    0
  ],
  [
    6353569792*alpha_21 - 4481640448,
    6447188416*alpha_21 - 12475550528,
    1778720768*alpha_21 - 1165158144,
    -165651472*alpha_21 - 793998352,
    168487680*alpha_21 - 208084480,
    -22955008*alpha_21 + 41053568,
    3658496*alpha_21 - 15988736,
    3569944*alpha_21 + 2513368,
    -241664*alpha_21 - 407808,
    292096*alpha_21 - 220928,
    -9536*alpha_21 - 832,
    4176*alpha_21 - 13744,
    0,
    -64*alpha_21 - 192,
    0,
    -alpha_21 - 1,
    0,
    0,
    0,
    0
  ],
  [
    -51240705261*alpha_21 + 112165894719,
    86613368*alpha_21 + 26188255064,
    -2531787016*alpha_21 + 27992854296,
    653890788*alpha_21 + 7823937948,
    1270938326*alpha_21 + 2058497224,
    397099192*alpha_21 + 613137504,
    169988508*alpha_21 - 10377480,
    43432484*alpha_21 + 3956580,
    7909046*alpha_21 - 7587168,
    1789488*alpha_21 - 1280304,
    181832*alpha_21 - 354552,
    27880*alpha_21 - 43452,
    4437*alpha_21 - 9282,
    68*alpha_21 - 272,
    102*alpha_21 - 204,
    0,
    alpha_21 - 2,
    0,
    0,
    0
  ],
  [
    -164016913248*alpha_21 + 415629273888,
    -14767205265*alpha_21 + 333436195467,
    -26914429920*alpha_21 + 99290145696,
    15574875228*alpha_21 + 20726632476,
    297633600*alpha_21 + 9508016736,
    930911376*alpha_21 - 171471480,
    326329344*alpha_21 + 346068864,
    -61049700*alpha_21 + 55617804,
    24422760*alpha_21 - 7722672,
    -3460725*alpha_21 + 10651194,
    593496*alpha_21 - 929520,
    110304*alpha_21 + 367380,
    -2664*alpha_21 - 20592,
    5454*alpha_21 + 2304,
    -216*alpha_21 - 144,
    36,
    0,
    -alpha_21 + 2,
    0,
    0
  ],
  [
    -73527994398*alpha_21 - 1781400057174,
    -169740277960*alpha_21 + 118980723992,
    -278207600985*alpha_21 - 297718172253,
    -71160240276*alpha_21 - 85308364404,
    -60155202776*alpha_21 + 11611570016,
    -18130125356*alpha_21 - 1266799464,
    -4652754903*alpha_21 + 4777762914,
    -1689389560*alpha_21 + 1306179244,
    -152843942*alpha_21 + 338412572,
    -60008232*alpha_21 + 114549024,
    -3497235*alpha_21 + 13580972,
    -259692*alpha_21 + 3485436,
    -116508*alpha_21 + 544920,
    27436*alpha_21 + 28576,
    475*alpha_21 + 14554,
    456*alpha_21 - 228,
    114*alpha_21 + 76,
    0,
    alpha_21 - 2,
    0
  ],
  [
    -1173890244240*alpha_21 - 11758472014800,
    -3235257982200*alpha_21 - 4427028700920,
    -1074361546000*alpha_21 - 2250808723040,
    -769792358490*alpha_21 - 96929671005,
    -228144977968*alpha_21 - 86352207712,
    -61595136520*alpha_21 + 28276558800,
    -21254788560*alpha_21 + 11169260640,
    -2410865440*alpha_21 + 992916940,
    -924407280*alpha_21 + 1395064800,
    -144982104*alpha_21 - 7401456,
    -9236400*alpha_21 + 65643360,
    -8252480*alpha_21 + 4293230,
    720240*alpha_21 + 1436640,
    -84840*alpha_21 + 177920,
    26320*alpha_21 + 14560,
    5400*alpha_21 - 4860,
    240*alpha_21 + 160,
    120*alpha_21 - 240,
    0,
    alpha_21 - 2
  ]
]
);

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

assert A_21*B_21 eq (Evaluate(f_21,x_1) - Evaluate(g_21,x_2));
sigmaM_20 := Matrix(20,20,[sigma(M_20[i][j]): i, j in [1..20]]);
assert M_20*sigmaM_20 eq 4*IdentityMatrix(k,20);

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