## Attachment 'quartmin_ff.sage'

```   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)
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])
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]
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])
256        return False,M*matrix(R,2,2,[P,0,0,1]),f(P*U,V)
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
```

## Attached Files

To refer to attachments on a page, use attachment:filename, as shown below in the list of files. Do NOT use the URL of the [get] link, since this is subject to change and can break easily.
• [get | view] (2010-05-29 03:33:20, 8.3 KB) [[attachment:quartmin_ff.sage]]
All files | Selected Files: delete move to page copy to page