/* VERSION: 5 February 2004. ======================================================================== This Magma program is designed to check whether or not there exists a genus-4 curve C over K = F_32 having exactly 75 rational points. In the paper Everett W. Howe and Kristin E. Lauter: Improved upper bounds for the number of points on curves over finite fields, Ann. Inst. Fourier (Grenoble) 53 (2003) 1677--1737 it is shown that such a curve must be a double cover of an elliptic curve E over K having 42 points. Up to Galois conjugacy there is exactly one such elliptic curve, and it is given by the equation y^2 + x*y = x^3 + x + a^7 where a satisfies a^5 + a^2 + 1 = 0. Furthermore, it is shown that the function field of C may be obtained from that of E by adjoining a function z satisfying z^2 + z = f, where f is a function on E having one of a couple of special forms: either f = (c1*x + c2) * y + (c3*x + c4) where c1, c2, c3, and c4 are elements of K with c1 nonzero and with c4^2 = c4, or f = c1*x + c2*(y + y1 + x1)/(x + x1) + c3*(y + y2 + x2)/(x + x2) + c4 where either * P1 = (x1,y1) and P2 = (x2,y2) are K-rational points on E with x1 and x2 nonzero, and c1, c2, c3, c4 are elements of K with c2 and c3 nonzero and with c4^2 = c4 or * P1 = (x1,y1) and P2 = (x2,y2) are Galois conjugate points on E over the quadratic extension L of K, and c1 and c4 are elements of K with c4^2 = c4, and c2 and c3 are nonzero conjugate elements of L. [The first form corresponds to the case where the double cover C --> E is ramified at one point with differential exponent 6, and the second form corresponds to the case where the double cover is ramifed at three points, each with differential exponent 2.] So we can easily enumerate the possible f's. To check whether an f gives us a C having 75 points, we count points in the following manner: 1. We set a variable "count" to the value 84 - n, where n is the number of K-rational poles of f. This would be the number of points on C if all of the rational points on E that don't ramify in C-->E split. 2. We loop through the points on P on E. If P is a pole of f we do nothing. If P is not a pole then we evalute f(P) and see whether there are rational solutions to z^2 + z = f(P). if not, then we subtract 2 from the current value of "count". 3. If the value of "count" ever falls below 75 we move on to the next possible f. ======================================================================== VERSION: 5 February 2004. Updated bibliographic information for Howe/Lauter paper. Changed "GF(32)" to "F_32" where it occurred in comments and print statements. VERSION: 3 October 2002. First published version. */ print "\nIf you do not see a message to further investigate a curve,"; print "then there are no genus-4 curves over F_32 having 75 points."; K:=GF(32); a := Random({a : a in K | a^5 + a^2 + 1 eq 0}); L:=ext; i := Random({i : i in L | i^2 + i + 1 eq 0}); // First we deal with the first kind of functions f: // f = (c1*x + c2) * y + (c3*x + c4), // with c1 nonzero and c4 equal to 0 or 1. pointlist := [[x1,y1] : x1, y1 in K | y1^2 + x1*y1 + x1^3 + x1^2 + a^7 eq 0]; for c1 in K do if c1 ne 0 then for c2, c3 in K do for c4 in [K|0,1] do count := 83; // That's what you would get if every non-ramified // point were to split. for P in pointlist do v := (c1*P[1] + c2)*P[2] + (c3*P[1] + c4); if Trace(v,GF(2)) eq 1 then count-:=2; if count lt 75 then break; end if; end if; end for; if count ge 75 then print "Here is a curve (of the first kind) to check out:"; print c1, c2, c3, c4; end if; end for; end for; end if; end for; // Now we deal with the second kind of f, in the case where // P1 and P2 are both K-rational (and with nonzero x-coordinates). // f = c1*x + c2*(y + y1 + x1)/(x + x1) // + c3*(y + y2 + x2)/(x + x2) + c4 // where c2 and c3 are nonzero, and c4 is either 0 or 1. // Note that the curves we get from a pair (P1, P2) will be // isomorphic to the curves we get from (P1', P2') if we have // any of the following: // P1 = P1' and P2 = P2' // P1 = P2' and P2 = P1' // P1 = -P1' and P2 = -P2' // P1 = -P2' and P2 = -P1' pairpointlistK := [[P,Q] : P, Q in pointlist | (P[1]*Q[1] ne 0) and (P ne Q)]; shortpairlistK := []; for PQ in pairpointlistK do if not ( ([PQ[2],PQ[1]] in shortpairlistK) or ([[PQ[1][1],PQ[1][1]+PQ[1][2]], [PQ[2][1],PQ[2][1]+PQ[2][2]]] in shortpairlistK) or ([[PQ[2][1],PQ[2][1]+PQ[2][2]], [PQ[1][1],PQ[1][1]+PQ[1][2]]] in shortpairlistK) ) then shortpairlistK cat:= [PQ]; end if; end for; // So shortpairlistK is a list of representatives of pairs up to // the equivalence mentioned abive. coeflistK := [[PQ[1][1]+PQ[1][2], PQ[1][1], PQ[2][1]+PQ[2][2], PQ[2][1]] : PQ in shortpairlistK]; // An element [n1,d1,n2,d2] of coeflistK will correspond to // the pair of rational functions // (y + n1)/(x + d1), (y + n2)/(x + d2). cc := #coeflistK; for coefs in coeflistK do n1 := coefs[1]; d1 := coefs[2]; n2 := coefs[3]; d2 := coefs[4]; for c1, c2, c3 in K do if c2*c3 ne 0 then for c4 in [K|0,1] do count := 81; // That's what you would get if every non-ramified // point were to split. for P in pointlist do if (P[1] ne d1) and (P[1] ne d2) then v := c1*P[1] + c2*(P[2]+n1)/(P[1]+d1) + c3*(P[2]+n2)/(P[1]+d2) + c4; if Trace(v,GF(2)) eq 1 then count-:=2; if count lt 75 then break; end if; end if; end if; end for; if count ge 75 then print "Here is a curve (of the second kind, with rational P) to check out:"; print c1, c2, c3, c4, coefs; end if; end for; end if; end for; cc -:=1; print cc; end for; // And finally we deal with the second kind of f, in the case where // P1 and P2 Galois conjugate points of E over L. // f = c1*x + c2*(y + y1 + x1)/(x + x1) // + c3*(y + y2 + x2)/(x + x2) + c4 // where c2 and c3 are nonzero elements of L, and c4 is either 0 or 1. // Note that the curves we get from a pair (P, P-bar) will be // isomorphic to the curves we get from (P', P'-bar) if we have // any of the following: // P = P' // P = P'-bar // P = -P' // P = -P'-bar pointlistL := [[x1,y1] : x1, y1 in L | y1^2 + x1*y1 + x1^3 + x1^2 + a^7 eq 0]; newpointlistL := [P : P in pointlistL | (P[1]^32 - P[1] ne 0) or (P[2]^32 - P[2] ne 0)]; shortpointlistL := []; for P in newpointlistL do if not ( ([P[1]^32, P[2]^32] in shortpointlistL) or ([P[1], P[2] + P[1]] in shortpointlistL) or ([P[1]^32, (P[2] + P[1])^32] in shortpointlistL) ) then shortpointlistL cat:= [P]; end if; end for; coeflistL := [ [Trace(P[1],K), Norm(P[1],K), Trace(P[1]^32,K), Trace(P[1]+P[2] ,K), Trace(P[1]^32*P[2],K), Trace(i*P[1]^32,K), Trace(i*(P[1]+P[2]),K), Trace(i*P[1]^32*P[2],K) + Norm(P[1],K) ] : P in shortpointlistL]; // The idea here is that an element [d1,d2,n1,n2,n3,n4,n5,n6] // corresponds to a pair of functions: // (n1*y + n2*x + n3)/(x^2 + d1*x + d2), // which you get from taking c2 = c3 = 1, and // (x*y + n4*y + n5*x + n6)/(x^2 + d1*x + d2), // which you get from taking c2 = i and c3 = i+1. cc := #coeflistL; for coefs in coeflistL do d1 := coefs[1]; d2 := coefs[2]; n1 := coefs[3]; n2 := coefs[4]; n3 := coefs[5]; n4 := coefs[6]; n5 := coefs[7]; n6 := coefs[8]; valuelist := [ [P[1], ( n1*P[2] + n2*P[1] + n3)/(P[1]^2 + d1*P[1] + d2), (P[1]*P[2] + n4*P[2] + n5*P[1] + n6)/(P[1]^2 + d1*P[1] + d2)] : P in pointlist]; for c1, k1, k2 in K do // We're taking c2 = k1 + i*k2, c3 = c2-bar. if (k1 ne 0) or (k2 ne 0) then for c4 in [K|0,1] do count := 83; // That's what you would get if every non-ramified // point were to split. for V in valuelist do v := c1*V[1] + k1*V[2] + k2*V[3] + c4; if Trace(v,GF(2)) eq 1 then count-:=2; if count lt 75 then break; end if; end if; end for; if count ge 75 then print "Here is a curve (of the second kind, with conjugate P) to check out:"; print c1, k1, k2, c4, coefs; end if; end for; end if; end for; cc -:=1; print cc; end for;