# --------------------------------------------------------------------------------------
# Program to count the number of covers of degree d, genus g, covers of a fixed
# elliptic curve E with simple branching. (The branch points also being fixed).
# This is an "orbifold count" -- each cover is counted with weight 1/|Aut|,
# where "Aut" is the automorphism group of the cover. I.e., covers are potentially
# counted with weight <1.
# The command C(g,d) computes this number.
# The mathematics of the computation is fairly straightforward.
# Define:
# infty infty
# ----- -----
# \ \ RC(g,d) (g-1) d
# F := ) ) ------- x t
# / / (2g-2)!
# ----- -----
# g = 1 d = 1
#
# Where RC(g,d) is the number of (possibly) REDUCIBLE covers of degree d
# with (2g-2) points of simple branching over E (fixed, of course). This
# number is again counted in the weighted, orbifold, sense.
# By standard combinatorial arguments (inclusion/exclusion counting using generating
# functions), if we define G as the formal logarithm of 1 + F,
# infty
# ----- k
# \ k+1 F
# G := log(1 + F) = ) (-1) -----
# / k
# -----
# k = 1
#
# (g-1) d # (deg d, genus d IRREDUCIBLE covers)
# then the coefficient in G of x t is -------------------------------------
# (2g - 2)!
# The routine C(g,d) at the end of this file just evaluates the series G, then reads
# off the appropriate coefficient.
# In order to be able to compute F, we need to be able to compute RC(g,d).
# By the standard Hurwitz-type monodromy argument, and elementary facts about the
# symmetric group S_d, this is the same as solving the following problem in S_d:
# { | each h_i is a transposition }
# ----- { | in S_d, and (fixing a repres-}
# \ { | entative c' in c) the product}
# RC(g,d) = ) # { (h , h , ...., h ) | h h .... h c' is in the}
# / { 1 2 (2g-2) | 1 2 (2g-2) }
# ----- { | same conjugacy class as c. }
# c a conjugacy {
# class in S_d
# To compute, RC(g,d) we use another standard combinatorial method:
# Let A_d be the square matrix whose rows and columns are indexed by the conjugacy
# classes in S_d (i.e., by the partitions of d). For any conjugacy classes c_1, c_2,
# let A_d[c_2,c_1] be the number of simple transpositions which take a fixed
# representative c' of the class c_1 into any member of the class c_2.
# (2g-2)
# Then RC(g,d) = Tr( A ), or, in other words, with this notation we have:
# d
# infty
# -----
# \ ( ) d
# F = ) Tr ( Exp( A sqrt(x) ) ) t
# / ( d )
# -----
# d = 1
#
# k
#(note that Tr(A ) = 0 if k is odd, so F above is really a series in x, and not sqrt(x))
# d
# It's clear that the only information we really need about the A_d's is its list
# of eigenvalues. This is stored globally (when known to the program) in the
# table "Cover_Seed_Data". This table is read in from the external file named
# "cover_data.m", or computed as necessary. (For instance, the program will start
# to build this file if it is missing).
# It's easy to compute the matrix A_d, but somewhat difficult (i.e., time consuming)
# to compute the eigenvalues. Fortunately there is faster way: by a pretty argument,
# the eigenvalues are given by the characters of the irreducible representations of the
# symmetric group, evaluated on the class of transpositions.
# More precisely, if X is a character of an irreducible representation of S_d, and `tau'
# is any transposition, then
# [ d ] X(tau)
# e_X : = [ ] -------- is an eigenvalue of A_d.
# [ 2 ] dim X
# (Here dim X = X(1) = the dimension of the irreducible rep. corresponding to X.)
# The eigenvalues of A_d are precisely the values e_X as X runs through the characters
# of the irreducible representations of S_d.
# Given a partition of d associated to an irreducible representation of S_d
# (and its corresponding character X) there is a very fast formula/method
# due to Frobenius for evaluating e_X. We use this method to compute the
# eigenvalues, and this solves the problem.
# The program works like this:
# If the user asks to compute C(g,d), and the seed data (the eigenvalues of the A_k's)
# are known for k <= d, then the routine uses this to work out the appropriate parts
# of the series F, then the appropriate parts of the series G, and then returns
# the answer. This only involves simple power series manipulation, and should be
# fairly rapid.
# If some of the eigenvalue data is missing, then the program first computes these
# numbers, updates the table "Cover_Seed_Data", and saves the updated table in
# the file "cover_data.m", so that it can be used the next time the program is run.
# The program then uses this data to compute F and G, and finally C(g,d) as above.
# The program is relatively quick, at least for `small' (below 40-50) values of g and d.
# Of course, as you ask for larger and larger numbers, everything creaks to a halt.
# The degree up to which we know the seed data is contained in the
# global variable "max_seed_known".
# --------------------------------------------------------------------------------------
# Acknowledgements:
# This program was motivated by the beautiful paper of Robbert Dijkgraaf:
# "Mirror Symmetry and Elliptic Curves"
# In "The Moduli Space of Curves", proceedings of Texel island conference,
# Progress in Mathematics series, published by Birkhauser.
# In particular, the plan for counting the curves, the amazing statement that the counting
# functions F_g(d) := C(g,d) (for fixed g) are given by quasi-modular forms,
# and the speedy method of Frobenius for evaluating e_X are all contained in that paper.
# --------------------------------------------------------------------------------------
# We'll need these external routines
with(combinat,numbpart,partition):
with(numtheory,sigma): # actually, this isn't really needed, it's just
# around for convenience when thinking about g=1
# covers.
# The next routine reads in the data from the file "cover_data.m", or
# if it doesn't exist, initializes the table and sets "max_seed_known" to 1.
init_seed_table:=proc() global Cover_Seed_Data,max_seed_known;
# The following construction, "try", is a maple language procedure that
# allows you to trap errors. The problem is that we're trying to open a file
# which may not exist. If it exists, the only thing this routine does is
# read in the data. If it doesn't, then we ignore the "file not found" error,
# and initialize the table ourselves. If the user asks for any computation
# above degree 1, the updated table will be saved in "cover_data.m", ready for
# use the next time.
try fopen("cover_data.m",READ);
read "cover_data.m";
max_seed_known:=max(op(map(op,[indices(Cover_Seed_Data)])));
fclose("cover_data.m");
catch "file or directory does not exist":
Cover_Seed_Data:=table():
Cover_Seed_Data[1]:=[0];
max_seed_known:=1:
end try;
end:
# Now we need the routines to compute the new seed data when necessary.
# The next routine is the method/formula of Frobenius
# for evaluating e_X, given a partition `alpha` representing
# an irreducible representation of S_d.
e_X:=proc(alpha) local i,s,l,P,Q;
l:=nops(alpha);
P:=0;
Q:=0;
i:=1;
s:=1;
while (i<=l) and (alpha[l-i+1]>=i) do
P:=P+(alpha[l-i+1]-i+1/2)^2;
Q:=Q+(l-i-s+3/2)^2;
while (s<=l) and (alpha[s]*`); # I like the eigenvalues to be sorted this
# way, don't ask me why.
RETURN(L);
end:
# The routine "update_seed_data" is called (by F below) whenever we're
# required to make a computation in some degree for which we don't know
# enough eigenvalues of the A_k's.
# This procedure goes through the list of missing degrees, computes the
# new seed data for each degree, and updates the global variables
# "max_seed_known" and "Cover_Seed_Data". The program F will then be able
# continue with its computation.
# Note that the data is saved to the file "cover_data.m" every time the
# entry for a new degree is known. In case this procedure crashes while computing
# a later degree, this will allow us to recover without losing too much data.
update_seed_data:=proc(d) global Cover_Seed_Data,max_seed_known; local i,s;
s:=max_seed_known;
printf("\nUpdating seed data in degrees %d through %d.\n",s+1,d);
for i from (s+1) to d do
Cover_Seed_Data[i]:= new_seed_data(i);
max_seed_known:=i;
printf("\nSaving degree %d data.\n",i);
save Cover_Seed_Data,"cover_data.m"; # note that I did not include error trapping
# here, out of laziness.
printf("Finished saving. Continuing with computation.\n\n");
od;
end:
# Well, that's it for generating the new data and the file handling
# what's left is to handle the power series F and G, and return the results.
# The following computes the trace of the b-th power of a matrix (A_d in application),
# divided by b!. The arguments are L, the list of eigenvalues of the matrix (which
# we'll get from "Cover_Seed_Data"), and b.
# I.e, this returns the coeff of z^b in Tr(exp(A_d z)).
Tr_exp:=proc(L,b) local i,S;
S:=0;
for i from 1 to nops(L) do
S:=S+L[i]^b;
od;
RETURN(S/b!);
end:
# The function F(s,d) returns the coefficient of x^s t^d in the power series
# F described above.
F:=proc(s,d) option remember; global Cover_Seed_Data, max_seed_known;
if (s=0) then RETURN(numbpart(d)) fi; # The genus 1 case should be handled
# separately, since it's much easier.
if (d=0) then RETURN(0) fi; # also, obviously no degree 0 covers.
if (d=1) then RETURN(0) fi; # no degree 1 covers either if g>1.
# now we'll have to compute something.
# check that we have all the seed data necessary, if not
# go and update it.
if (d>max_seed_known) then update_seed_data(d) fi;
# now that we know the data, go ahead and compute with it.
RETURN(Tr_exp(Cover_Seed_Data[d],2*s));
end:
# The function Fn(s,d,n) returns the coefficient of x^s t^d in F^n. Expansion
# of the multiplication is by recursion.
Fn:=proc(s,d,n) option remember; local i,j,S;
if (n=1) then RETURN(F(s,d)) fi;
S:=0;
for i from 1 to (d-1) do # i goes over all of the possible d values
for j from 0 to s do # j goes over all of the possible s values
S:=S+Fn(j,i,n-1)*F(s-j,d-i);
od;
od;
RETURN(S);
end:
# Now we want the function G, which is the logarithm of F, i.e.,
# G = log(1 + F). G(s,d) should produce the coefficient of x^s t^d in G.
G:=proc(s,d) local i,S;
S:=0;
for i from 1 to d do
S:=S-(-1)^i*Fn(s,d,i)/i;
od;
RETURN(S);
end:
# The final command, C(g,d) counts the irreducible curves of genus g, degree d
# mapping to E (with 2g-2 simple branch points, of course).
C:=proc(g,d) option remember;
RETURN((2*g-2)! * G(g-1,d));
end:
# Finally, the good ol' instructions.
commands:=proc();
printf("\n\n");
printf("-----------------------------------------------------------------\n");
printf("covers -- a routine to the number of genus g, degree d, simply \n");
printf(" branched covers of a fixed elliptic curve E.\n");
printf("-----------------------------------------------------------------\n\n");
printf(" Seed combinatorial data computed up to degree %d.\n\n",max_seed_known);
printf("C(g,d); Count the number of genus g, degree d covers.\n");
printf("commands(); Print this list of commands again.\n\n");
printf("\n");
end:
init_seed_table(): # load in the precomputed data (if it exists).
commands(); # and print the commands.
# We're ready to go!
*