attachment:quartmin_ff.sage of daysff/pms

   1 r"""
   2 reduction of quartics over rational function fields 
   3 used for descent
   4 
   5 """
   6 
   7 def quartic_level(A,P,debug = True):
   8     r"""
   9     calculates the I and J invariant and its valuation at P
  10 
  11     INPUT:
  12 
  13     -``A`` -- the coefficients (integral) of the quartic 
  14     -``P`` -- a prime polynomial
  15     
  16     EXAMPLES::
  17 
  18 	sage: K.<T> = FunctionField(GF(5))
  19 	sage: A = [T,1,T**2,T+1,1]
  20 	sage: R = K._ring
  21 	sage: P = R(T.element())
  22 	sage: quartic_level(A,P)
  23 	(T**4 + 4*T + 2, 3*T**6 + 4*T**3 + 3*T + 3, 0)
  24 
  25     """
  26 
  27     a,b,c,d,e = A
  28     K = A[0].parent()
  29     R = K._ring
  30     a = R(K(a).element())
  31     b = R(K(b).element())
  32     c = R(K(c).element())
  33     d = R(K(d).element())
  34     e = R(K(e).element())
  35     if debug:
  36        print a
  37        print b
  38        print c
  39        print d
  40        print e
  41     I = R(12*a*e-3*b*d+c**2)
  42     J = R(72*a*c*e+9*b*c*d-27*a*d**2-27*b**2*e-2*c**3)
  43     if debug:
  44        print I
  45        print J
  46     assert (I != 0 or J != 0)
  47     if (I == 0):
  48        return I,J,(J.valuation(P)/6).floor()
  49     if (J == 0):
  50        return I,J,(I.valuation(P)/4).floor()
  51     return I,J,min((I.valuation(P)/4).floor() , (J.valuation(P)/6).floor() )
  52 
  53 
  54 
  55 def quartic_coefficients(f):
  56     r"""
  57     returns the coefficients of f where y^2 = f is the defining polynomial of a quartic
  58 
  59     INPUT:
  60     -``f`` -- homogeneous polynomial of degree 4 in 2 variables
  61 
  62     EXAMPLES::
  63 
  64 	sage: K.<T> = FunctionField(GF(5))
  65 	sage: KUV.<U,V> = K[]
  66 	sage: f = U**4 + T*U**3*V + T**2*U**2*V**2 + T**3*U*V**3 + T**4*V**4
  67 	sage: quartic_coefficients(f)
  68 	[1, T, T**2, T**3, T**4]
  69 
  70 
  71     """
  72     K = f.parent()
  73     A  = [ [4-x,x] for x in range(5) ]
  74     out = [f.monomial_coefficient(K.gens()[0]**a[0]*K.gens()[1]**a[1])  for a in A]
  75     return out
  76 
  77 def root(f):
  78     r"""
  79    
  80    INPUT:
  81     -``f`` -- homogeneous polynomial of degree 4 in 2 variables
  82 
  83     EXAMPLES::
  84 
  85 	sage: K.<T> = FunctionField(GF(5))
  86 	sage: KUV.<U,V> = K[]
  87 	sage: f = U**4 + T*U**3*V + T**2*U**2*V**2 + T**3*U*V**3 + T**4*V**4 
  88  
  89 
  90 
  91     """
  92     g = f[0]
  93     a = g.MonomialCoefficient({g.parent().gens()[0]:1,g.parent().gens()[1]:0})
  94     b = g.MonomialCoefficient({g.parent().gens()[0]:0,g.parent().gens()[1]:0})
  95     return (-b/a)
  96 
  97 
  98 
  99 def QMOP(f,P,debug = True):
 100 
 101     r"""
 102     reduces the quartic y^2 = f with respect to one prime polynomial
 103     this function needs reside fields.otherwise it wont work.
 104     the seccond example for example wont work until it is changed
 105 
 106     INPUT:
 107     -``f`` -- homogeneous polynomial of degree 4 in 2 variables with integral coefficients over a rational function field
 108     -``P`` -- a polynom in the ring of integers of the coefficients of f
 109   
 110     OUTPUT:
 111     - a minimal quartic equivalent to f
 112     - the transformation matrix
 113 
 114     EXAMPLES::
 115 
 116 	sage: K.<T> = FunctionField(GF(5))
 117 	sage: KUV.<U,V> = K[]
 118 	sage: f = T*U**4 + T*U**3*V + T**2*U**2*V**2 + T**3*U*V**3 + T**4*V**4 
 119  	sage: P = R(T.element())
 120 	sage: QMOP(f,P)
 121 	(False, [T 0]
 122 	[0 1], T**5*U**4 + T**4*U**3*V + T**4*U**2*V**2 + T**4*U*V**3 + T**4*V**4)
 123 
 124 	sage: K.<T> = FunctionField(GF(5))
 125 	sage: KUV.<U,V> = K[]
 126 	sage: f = (T**11 + T + 1)*U**4 + T*U**3*V + T**2*U**2*V**2 + T**3*U*V**3 + T**4*V**4 
 127  	sage: P = R(T.element())
 128 	sage: QMOP(f,P)
 129 	
 130 
 131 
 132     """
 133     KUV = f.parent()
 134     U,V = KUV.gens()
 135     K = KUV.base_ring()
 136     R = K._ring
 137     M = diagonal_matrix(R,[1,1])
 138     cf = quartic_coefficients(f)
 139     cff = [R(aa.element()) for aa in cf] ##coerce to polynomial ring
 140     	  		       	     	 ##because valuation wants
 141 					 ##polynomials
 142     vals = [c.valuation(P) for c in cff]
 143     if debug:
 144        print "valuations: ",vals
 145     minval = min(vals)
 146     I,J,lev = quartic_level(cf,P)
 147     if debug:
 148        print "I: ",I
 149        print "J: ",J
 150        print "level ",lev
 151     if lev == 0:
 152        return True,diagonal_matrix(R,[1,1]),f
 153     
 154     if minval >= 2:
 155        if debug:
 156        	  print "case 1: nothing to do.."
 157        return False,diagonal_matrix(R,[1,1]),f
 158 
 159     if not False in [vals[i] >= i for i in range(1,5)]:
 160        if debug:
 161        	  print "case 2: reducing..."
 162        return False, diagonal_matrix(R,[P,1]),f([P*U,V])
 163 
 164     if not False in [vals[i] >= (4-i) for i in range(0,4) ]:
 165        if debug:
 166        	  print "case 3: reducing..."
 167        return False, matrix(R,2,2,[0,1,P,0]),f(V,P*U)
 168 
 169     if not False in [vals[i] >= (2*i - 2) for i in range(2,5) ]:
 170        if debug:
 171        	  print "case 4: reducing"
 172        return False,diagonal_matrix(R,[P^2,1]),f(P^2*U,V)
 173 
 174     if not False in [vals[i] >= (6 - 2*i) for i in range(0,3) ]:
 175        if debug:
 176        	  print "case 5: reducing.."
 177        return False,matrix(R,2,2,[0,1,P^2,0]),f(V,P^2*U)
 178     if debug:
 179        print "case 6: reducing.."
 180     ##KP has to be the residue field, so as soon as there is a way of
 181     ##constructing residue fields - change it!!!
 182     ##because later a multivariate polynomial over this ring 
 183     ##has to be factored
 184     KP = R.quotient_by_principal_ideal(P)
 185     mapKP = KP.coerce_map_from(R)
 186     KPuv.<u,v> = KP[]
 187     cfP = [mapKP(R(c.element())) for c in cf]
 188     if debug:
 189        print "reduced coefficients: ",cfP
 190        print "KUV",KUV
 191        print "KPuv",KPuv
 192     RXY.<X,Y> = R[]
 193     print RXY
 194     red = RXY.hom([u,v])
 195     coefs = [a.quo_rem(P^minval)[0] for a in f.coefficients()]
 196     if debug:
 197        print "new coefficients: ",coefs
 198        print "coefs[0].parent ->",coefs[0].parent()
 199     mons = f.monomials()
 200     mons2 = []
 201     for mo in mons:
 202     	modegs = mo.degrees()
 203 	mons2 = mons2 + [X**modegs[0]*Y**modegs[1]]
 204     ###f1 = sum([coefs[i]*mons[i] for i in range(len(mons))])
 205     ###dont think that i ll need f1
 206     f2 = sum([coefs[i].numerator()*mons2[i] for i in range(len(mons2))])
 207     if debug:
 208        #print "f1: ",f1
 209        #print red
 210        print "f2: ",f2
 211        print f2.parent() 
 212     pf = red(f2)
 213     QUAD = True
 214     cfP = [mapKP(c) for c in quartic_coefficients(f2)]
 215     if debug:
 216        print "cfP: ",cfP
 217     ###this does not work. need to go for residue fields
 218     fac = factor(pf)
 219     if debug:
 220        print fac
 221     if (v,4) in fac:
 222        f = f(V,U)    
 223        M = matrix(R,2,2,[0,1,1,0])
 224 
 225     if (v,3) in fac:
 226        g = [x for x in fac if x[1] == 1 ]
 227        assert len(g) == 1
 228        assert g[0][0].total_degree() == 1
 229        s = root(g[0])
 230        QUAD = False
 231        f = f(U + s*V,V)
 232        M = matrix(R,2,2,[1,s,0,1])
 233 
 234     if cfP[0] != 0:
 235        if len(fac) == 1:
 236        	  assert fac[0][1] == 4
 237 	  s = root(fac[0])
 238 	  f = f(U + s*V,V)
 239 	  M = matrix(R,2,2,[1,s,0,1])
 240        rts = [x for x in fac if x[0].total_degree() == 1 ]
 241        if len(rts) == 2:
 242        	  r1 = rts[0]
 243 	  r2 = rts[1]
 244 	  QUAD = False
 245 	  if r2[1] == 3:
 246 	     s1 = root(r2)
 247 	     s2 = root(r1)	
 248 	  else:
 249 	     s1 = root(r1)
 250 	     s2 = root(r2)
 251 	  s1 = 1/(s1 - s2)
 252 	  f = f(U + s2*V,V)
 253 	  f = f(V,U + s1*V)
 254 	  M = matrix(R,2,2,[s2,s1*s2 + 1,1,s1])
 255     if QUAD:
 256        return False,M*matrix(R,2,2,[P,0,0,1]),f(P*U,V)
 257     assert not QUAD
 258     KP2 = R.quotient_by_principal_ideal(P^2)
 259     s = KP2.coerce(-cf[2]/(3*cf[1])).lift()
 260     f = f(U + s*V,V)
 261     M = M*matrix(R,2,2,[1,s,0,1])
 262     if minval == 0:
 263        return False,M*matrix(R,2,2,[P,0,0,1]),f(P*U,V)
 264     else:
 265 	return False,M*matrix(R,2,2,[P^2,0,0,1]),f(P^2*U,V)
 266 
 267  
 268 def my_quartic_minimize(f,debug=True):
 269 
 270     r"""
 271     reduces the quartic y^2 = f with respect to all prime polynomials
 272 
 273     INPUT:
 274     -``f`` -- homogeneous polynomial of degree 4 in 2 variables with integral coefficients over a rational function field
 275     EXAMPLES::
 276 
 277 	sage: K.<T> = FunctionField(GF(5))
 278 	sage: KUV.<U,V> = K[]
 279 	sage: f = (T**11 + T + 1)*U**4 + T*U**3*V + T**2*U**2*V**2 + T**3*U*V**3 + T**4*V**4 
 280  	sage: P = R(T.element())
 281 	sage: my_quartic_minimize(f)
 282     """
 283     K = f.parent().base_ring()
 284     R = K._ring
 285     sl2 = diagonal_matrix(R,[1,1])
 286     cf = quartic_coefficients(f)
 287     I,J,_ = QuarticLevel(cf,R.gens()[0])
 288     df = 4*I^3 - J^2
 289     if df.is_zero():
 290        return f,sl2
 291     fac = factor(df)
 292     if debug:
 293        print "fac: ",fac
 294     bp = [x[0] for x in fac]
 295     bp = [(p,df.valuation(p)) for p in bp ]
 296     bp = [x for x in bp if x[1] >= 12 ]
 297 
 298     for p in bp:
 299     	if debug:
 300 	   print "reducing ",p
 301     	flag = False
 302 	while not flag:
 303 	      flag,mat,f = QMOP(f,p[0])
 304 	      print f
 305 	      e = (min([x.valuation(p[0]) for x in QuarticCoefficients(f)])/2).floor()
 306 	      coefs = [a.quo_rem(p[0]^(2*e))[0] for a in f.coefficients()]
 307     	      mons = f.monomials()
 308     	      f = sum([coefs[i]*mons[i] for i in range(len(mons))])
 309 	      sl2 = sl2*mat
 310 	if debug:
 311 	   print "finished reduction for ",p
 312     return f,sl2