<\body> >]]>>>>(N)>>>>>>>>>>>>>>>>>>>>>>>.> >>> > >>>>>>>>>>>>>>>>>>>|^>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>(w)>>(w)|^>>>>(w)|^>>>--->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\>>>>>>>>>>>>>>>>>>|>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> >|>>|>|>>>>>>> >|>|>>|>|>|>>|>|>| >>>>>>> >|>>|>| >>>>>>> >>| >>>>>>> >|>>|>| >>>>>>>i>>>>>>>>>>>>>>>|^>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>(/)>>>>>>>>>>>>>>>()>>>>()>>()>>()>>>>>>()>>>>>>>>>>>>|~>>>>>>>>> \>>>>|>||>>>>>>|>||>>>>>>>>>>>>>>>>>>.>>> >>>>>>> ||<\make-title> > > <\center> Copyright (c) 2004 William Stein The author grants permission to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the Appendix. <\table-of-contents|toc> \; Preface> This is a book about algorithms for computing with modular forms. I am writing it for a Fall 2004 graduate course at Harvard University. This book is meant to answer the question ``How do compute spaces (N,)> of modular forms'', which theoretical mathematicians often ask me, and to provide a rigorous foundation for the specific algorithms I use, some of which have until now never been formally stated or proven to be correct, except in my head while I typed them into a computer language. I have spent several years trying to find the best ways to compute with classical modular forms for congruence subgroups of ()>, and have implemented most of these algorithms several times, first in C++ , then in MAGMA , and most recently in Python/C++ (see Chapter ). Much of this work has involved turning formulas and constructions burried in books and papers into precise computable recipes, then testing these in many cases and eliminating subtle inaccuracies (published theorems often contain very small mistakes that are greatly magnified when implemented and run on a computer). The goal of this book is to explain what I have learned along the way, and also describe unsolved problems whose solution would move the theory forward. The author is aware of no other books on computing with modular forms, the closest work being Cremona's book , which is about computing with elliptic curves, and Cohen's book about algebraic number theory. This field is not mature, and there are some missing details and potential improvements to many of the algorithms, which you the reader might fill in, and which would be greatly appreciated by other mathematicians. Also, it seems that nobody has tried to analyze the formal complexity of any of the algorithms in this book (the author intends to do this as he writes the book) again this is somewhere you might contribute. This book focuses on how best to compute the spaces (N,)> of modular forms, where 2> is an integer and > is a Dirichlet character modulo . I will spend the most effort explaining the algorithms that appear so far to be the best for such computations. I will not discuss computing half-integral weight forms, weight one forms, forms for non-congruence subgroups or groups other than >, Hilbert and Siegel modular forms, trace formulas, or -adic modular forms. I will also write very little about computing with modular abelian varieties. These are topics for another book or two. The reader is not assumed to have prior exposure to modular forms, but should have a firm grasp of abstract algebra, and be familiar with algebraic number theory, geometry of curves, algebraic topology of Riemann surfaces, and complex analysis. For Chapter , the reader should be familiar with the Python programming language. The text of this book is licensed under the GNU Free Documentation License, Version 1.2, November 2002. This means that you may freely copy this book. For the precise details, see the Appendix. Kevin Buzzard made many helpful remarks which were helpful in finding the algorithms in Chapter . Remarks throughout chapters 1 and 2. The students in Math 257. <\itemize> Abhinav Kumar (abhinav@math.harvard.edu): Discussions about computing width of cusp. Thomas James Barnet-Lamb (tbl@math.harvard.edu): About how to represent Dirichlet characters in the computer. Tseno V. Tselkov (tselkov@fas.harvard.edu) Jennifer Balakrishnan (jbalakr@fas.harvard.edu) Jesse Kass (kass@math.harvard.edu) This chapter follows parts of (Ch. VII) closely, though we adjust the notation, definitions, and order of presentation to be more in line with what we will do in the rest of the book. Note that Serre writes everywhere instead of , which may seem like a good idea if one is only interested in modular forms of level , since there are no nonzero level forms of odd weight. The complex upper half plane > is equipped with an action of <\equation*> ()=:a*d-b*c=1,a,b,c,d\ via linear fractional transformations. The is the subgroup ()> of ()> of matrices with integer entries. It acts on the upper half plane and has as fundamental domain the set of elements of > that satisfy 1> and (z)\1/2> (see (S)). Using this fundamental domain, one sees that ()> is generated as a group by the matrices > and >. <\definition> [Weakly Modular Function] A of weight is a meromorphic function on > that satisfies <\equation> f(z)=(c*z+d)f(\(z)) for all =\()>. Note that there are no modular forms of odd weight, since () implies f(z)>. When is even () is the same as <\equation*> f(\(z))d(\(z))=f(z)d*z, so the weight differential form > is fixed by ()>. Note also that the product of two weakly modular functions of weights > and > is a weakly modular function of weight +k>. Since ()> is generated by and , we can show that a meromorphic function is a weakly modular function by checking that <\equation> f(z+1)=f(z)f(-1/z)=zf(z). Let i*z>>. Since , there is a set-theoretic function (q)> such that (q)=f(z)>. If, moreover, <\equation*> (q)=>aq for some > and all in a neighborhood of , we say that is >>. If also 0>, then we say that is >>. <\definition> [Modular Function] A of weight is a weakly modular function of weight that is meromorphic at >. <\definition> [Modular Form] A of weight is a modular function of weight that is holomorphic on > and at >. If is a modular form, then there are complex numbers > such that <\equation*> f=>aq, and the above series converges for all > (since is holomorphic on the punctured open unit disk, its Laurent series converges absolutely in the punctured open unit; see also (S) for a bound on \|>). Also we set )=a>, since i*z>\0> as \>. <\definition> [Modular Form] A (of level 1) of weight is a modular function of weight that is holomorphic on > and at >. <\definition> [Cusp Form] A (of level 1) of weight is a modular form of weight such that )=0>, i.e., =0>. If is a nonzero meromorphic function on > and >, let (f)> be the largest integer such that > is holomorphic at . If >aq> with \0>, let >(f)=m>. We will use the following theorem to give a presentation for the vector space of modular forms of weight , which will make it possible to computable a basis for that space. <\theorem> [Valence Formula]Suppose is a modular form. Then <\equation*> >(f)+(f)+>(f)+D>>(f)=, where >> is the sum over elements of the fundamental domain other than or >. Serre proves this theorem in (S) using the residue theorem from complex analysis. We will not prove it in this book. For an even integer 4>, define the (not-normalized) Eisenstein series> to be <\equation*> G(z)=>>>, where the sum is over all > such that 0>. <\proposition> The function (z)> is a modular form of weight . See (S), where he proves that (z)> defines a holomorphic function on {\}>. To see that > is modular, note that <\equation*> G(z+1)=>>=>>=>>, and <\equation*> G(-1/z)=>>=>|(-m+n*z)>=z>>=zG(z). <\proposition> (\)=2\(k)>, where > is the Riemann zeta function. <\proof> Taking the limit as i\> in the definition of (z)>, we obtain >>>>, since the terms involving all go to as i\>. This sum is twice (k)=1>>>. For example, one can show that <\equation*> G(\)=2\(4)=\5>\ and <\equation*> G(\)=2\(6)=\5\7>\. Suppose /\> is an elliptic curve over >, viewed as a quotient of > by a lattice =\+\>, with /\\>. Then <\equation*> \>(u)=>+>>(k-1)G(\/\)u, and <\equation*> (\)=4\-60G(\/\)\-140G(\/\). The discriminant of the cubic -60G(\/\)x-140G(\/\)> is (\/\)>, where <\equation*> \=(60G)-27(140G) is a cusp form of weight . Since is an elliptic curve, (\/\)\0>. <\proposition> For every even integer 2>, we have <\equation*> G(z)=2\(k)+2\i)|(k-1)!>\>\(n)q, where (n)> is the sum of the th powers of the divisors of . For the proof, see (S), which uses clever manipulations of various series, starting with the identity <\equation*> \cot(\z)=+>+. From a computational point of view, the -expansion for > from Proposition is unsatisfactory, because it involves transcendental numbers. To understand more clearly what is going on, we introduce the > for 0> by the following equality of formal power series: <\equation> -1>=>B|n!>. Expanding the power series on the left we have <\equation*> -1>=1-+|12>-|720>+|30240>-|1209600>+\ As this expansion suggests, the Bernoulli numbers > with 1> odd are (see ernoulli>). Expanding the series further, we obtain the following table: B=1,B=-,B=,B=-,B=,B=-,> B=,B=-,B=,B=-,B=,> B=-,B=,B=-,B=.> For us the significance of the Bernoulli numbers is their connection with values of > at positive even integers. <\proposition> If 2> is an integer, then <\equation*> \(k)=-i)|2\k!>\B. The proof involves manipulating a power series expansion for (see (S)). <\definition> [Normalized Eisenstein Series] The of even weight 4> is <\equation*> E=(2\i)>\G Combining Propositions and we see that <\equation> E=-|2k>+q+>\(n)q. <\remark> Our series > is normalized so that the coefficient of is , but most books normalize > so that the constant coefficient is . We use the normalization with the coefficient of equal to , because then the eigenvalue of the th Hecke operator (see Section ) is the coefficient of >. Our normalization will also be convenient when we consider congruences between cusp forms and Eisenstein series. Let > denote the complex vector space of modular forms of weight , and let > denote the subspace of cusp forms. We have an exact sequence <\equation*> 0\S\M\ that sends M> to )>. When 4> is even, the space > contains > and (\)=2\(k)\0>, so the map \> is surjective, and )=dim(M)-1>, so <\equation*> M=S\G. <\proposition> For 0> and , we have =0>. <\proof> Suppose M> is nonzero yet or 0>. By Theorem , <\equation*> >(f)+(f)+>(f)+D>>(f)=\1/6. This is impossible because each quantity on the left-hand side is nonnegative so whatever the sum is, it is too big (or , in which ). <\theorem> Multiplication by > defines an isomorphism \S>. <\proof> (We follow (S) closely.) We apply Theorem to > and >. If >, then <\equation*> >(f)+(f)+>(f)+D>>(f)==, with the >s all nonnegative, so >(G)=1> and (G)=0> for all \>. Likewise (G)=1> and (G)=0> for all i>. Thus (i)\0>, so > is not identically (we also saw this above using the Weierstrass > function). Since > has weight and >(\)\1>, Theorem implies that > has a simple zero at > and does not vanish on >. Thus if S> and we let >, then is holomorphic and satisfies the appropriate transformation formula, so is a modular form of weight . <\corollary> For , the vector space > has dimension , with basis , >, >, >, >, and >, respectively, and =0>. <\proof> Combining Proposition with Theorem we see that the spaces > for 10> can not have dimension bigger than , since then >\0> for some \0>. Also > has dimension at most , since > has dimension . Each of the indicated spaces of weight 4> contains the indicated Eisenstein series, so has dimension , as claimed. <\corollary> =|k,>>|k/12\>|k2,>>|k/12\+1>|k>2,>>>>>> where x\> is the biggest integer x>. <\proof> As we have seen above, the formula is true when 12>. By Theorem , the dimension increases by when is replaced by . <\theorem> The space > has as basis the modular forms G>, where are all pairs of nonnegative integers such that . <\proof> We first prove by induction that the modular forms G> generate >, the cases 12> being clear (e.g., when we have and basis ). Choose some pair of integers such that (it is an elementary exercise to show these exist). The form G> is not a cusp form, since it is nonzero at >. Now suppose M> is arbitrary. Since =S\G>, there is \> such that g\S>. Then by Theorem , there is M> such that g=\h>. By induction, is a polynomial in > and > of the required type, and so is >, so is as well. Suppose there is a nontrivial linear relation between the G> for a given . By multiplying the linear relation by a suitable power of > and >, we may assume that that we have such a nontrivial relation with 0>. Now divide the linear relation by > to see that /G> satisfies a polynomial with coefficients in >. Hence /G> is a root of a polynomial, hence a constant, which is a contradiction since the -expansion of /G> is not constant. Given integers and , this algorithm computes a basis of -expansions for the complex vector space > mod >. The -expansions output by this algorithm have coefficients in >. <\steps> [Simple Case] If output the basis with just in it, and terminate; otherwise if 4> or is odd, output the empty basis and terminate. [Power Series] Compute > and > mod > using the formula from () and the definition () of Bernoulli numbers. [Initialize] Set 0>. [Enumerate Basis] For each integer between and k/6\>, compute . If is an integer, compute and output the basis element E>>. When we compute, e.g., >, do the computation by finding >> for each a>, and save these intermediate powers, so they can be reused later, and likewise for powers of >.\ > <\proof> This is simply a translation of Theorem into an algorithm, since > is a nonzero scalar multiple of >. That the -expansions have coefficients in > is Equation . <\example> We compute a basis for >, which is the space with smallest weight whose dimension is bigger than . It has as basis >, E>, and >, whose explicit expansions are <\align*> >|+q+q+\>>|E>|-q-q+\>>|>|-q+q+\>>>> In Section , we will discuss properties of the reduced row echelon form of any basis for >, which have better properties than the above basis. Let be an integer. Define the weight right action of ()> on functions on > as follows. If =\()>, let <\equation*> f\|[\]=det(\)(c*z+d)f(\(z)). One checks as an exercise that <\equation*> f\|[\\]=(f\|[\])\|[\], i.e., that this is a right group action. Also is a weakly modular function if is meromorphic and ]=f> for all \()>. For any positive integer , let <\equation*> S=\M():a\1,a*d=n,0\b\d. Note that the set > is in bijection with the set of sublattices of > of index , where > corresponds to \(a,b)+\(0,d)>, as one can see, e.g., by using Hermite normal form (the analogue of reduced row echelon form over >). <\definition> [Hecke Operator >] The th Hecke operator > of weight is the operator on functions on > defined by <\equation*> T(f)=\S>f\|[\]. <\remark> It would make more sense to write > on the right, e.g., >, since > is defined using a right group action. However, if are integers, then > and > commute, so it doesn't matter whether we consider the Hecke operators as acting on the right or left. <\proposition> If is a weakly modular function of weight , so is (f)>, and if is also a modular function, then so is (f)>. <\proof> Suppose \()>. Since > induces an automorphism of >, the set <\equation*> S\\={\\:\\S} is also in bijection with the sublattices of > of index . Then for each element \\S\\>, there is \()> such that \\\S> (the element > is the transformation of \> to Hermite normal form), and the set of elements \\> is equal to >. Thus <\equation*> T(f)=\\\S>f\|[\\\]=\S>f\|[\\]=T(f)\|[\]. That being holomorphic on > implies (f)> is holomorphic on > follows because each ]> is holomorphic on >, and a finite sum of holomorphic functions is holomorphic. We will frequently drop from the notation in >, since the weight is implicit in the modular function to which we apply the Hecke operator. Thus we henceforth make the convention that if we write (f)> and is modular, then we mean (f)>, where is the weight of . <\proposition> On weight modular functions we have <\equation> T=TT(n,m)=1, and <\equation> T>=T>T-pT>, is prime>. <\proof> Let be a lattice of index . The quotient /L> is an abelian group of order , and , so /L> decomposes uniquely as a direct sum of a subgroup order with a subgroup of order . Thus there exists a unique lattice > such that L\>, and > has index in >. Thus > corresponds to an element of >, and the index subgroup L> corresponds to multiplying that element on the right by some uniquely determined element of >. We thus have <\equation*> ()\S\S=()\S i.e., the set products of elements in > with elements of > equal the elements of >, up to ()>-equivalence. It then follows from the definitions that for any , we have (f)=T(T(f))>. We will show that >+pT>=TT>>. Suppose is a weight weakly modular function. Using that =(p)pf=pf>, we have <\equation*> S>>f\|[x]+pS>>f\|[x]=S>>f\|[x]+pp*S>>f\|[x]. Also <\equation*> TT>(f)=S>S>>f\|[x]\|[y]=S>\S>f\|[x]. Thus it suffices to show that >> union copies of >> is equal to >\S>, where we consider elements up to ()>-equivalence. Suppose is a sublattice of > of index >, so corresponds to an element of >>. First suppose is not contained in >. Then the image of in /p=(/p)> is of order , so if =p+L>, then :L]=p> and ]=p>, and > is the only lattice with this property. Second suppose that p> if of index >, and that S>> corresponds to . Then every one of the lattices \> of index contains . Thus there are chains L\> with :L]=p>. The chains L\> with :L]=p> and :L]=p> are in bijection with the elements of >\S>. On the other hand the union of >> with copies of >> corresponds to the lattices of index >, but with those that contain > counted times. The structure of the set of chains L\> that we derived in the previous paragraph gives the result. <\corollary> The Hecke operator >>, for prime , is a polynomial in >. If are any integers then T=TT>. <\proof> The first statement is clear from (), and this gives commutativity when and are both powers of . Combining this with () gives the second statement in general. <\remark> (X)> such that >=f(T)>. ||<\quote-env> \ If you normalize the Hecke operators by considering <\equation*> S=nT then the recursion on the polynomials (X)> such that ,k>=P(S)> becomes <\equation*> X*P=P+P, which is the recursion satisfied by the Chebychev polynomials > such that <\equation*> U(2cos t)=. Alternatively, those give the characters of the symmetric powers of the standard representation of ()>, evaluated on a rotation matrix <\equation*> cos(t)>. For references, see for instance (p. 97) or (p. 78, p. 81), and there are certainly many others.\ > <\proposition> Suppose >aq> is a modular function of weight . Then <\equation*> T(f)=>c\(n,m)>ca>q. In particular, if is prime, then <\equation*> T(f)=>a+paq, where =0> if >>. The proposition is not that difficult to prove (or at least the proof is easy to follow), and is proved in (S) by writing out (f)> explicitly and using that b\d>ei*b*m/d>> is if m> and otherwise. A corollary of Proposition is that > preserves > and >. <\corollary> The Hecke operators preserve > and >. <\remark> (Elkies) We knew this already---for > it's Proposition , and for > it's easy to show directly that if )=0> then f> also vanishes at >. <\example> Recall that <\equation*> E=+q+9q+28q+73q+126q+252q+344q+\. Using the formula of Proposition , we see that <\equation*> T(E)=(1/240+2\(1/240))+9q+(73+2\1)q+\=9E. Since > has dimension , and we have proved that > preserves >, we know that > acts as a scalar. Thus we know just from the constant coefficient of (E)> that (E)=9E>. More generally, (E)=(1+p)E>, and even more generally <\equation*> T(E)=\(n)E, for any integer 1> and even weight 4>. <\example> The Hecke operators > also preserve the subspace > of >. Since > has dimension , this means that > is an eigenvector for all >. Since the coefficient of in the -expansion of > is , the eigenvalue of > on > is the th coefficient of >. Moreover the function (n)> that gives the th coefficient of > is a multiplicative function. Likewise, one can show that the series > are eigenvectors for all >, and because in this book we normalize > so that the coefficient of is , the eigenvalue of > on > is the coefficient (n)> of >. <\lemma> [Victor Miller]The space > has a basis ,\,f> such that if (f)> is the th coefficient of >, then (f)=\> for ,d>. Moreover the > all lie in [[q]]>. This is a straightforward construction involving >, > and >. The following proof is copied almost verbatim from (Ch. X, Thm. 4.4), which is in turn presumably copied from the first lemma of Victor Miller's thesis. <\proof> Let >. Since =-1/30> and =1/42>, we note that <\equation*> F=-8/B\E=1+240q+2160q+6720q+17520q+\ and <\equation*> F=-12/B\E=1-504q-16632q-122976q-532728q+\ have -expansions in [[q]]> with leading coefficient . Choose integers 0> such that <\equation*> 4a+6b\144a+6bk, with when 0>, and let <\equation*> g=\FF,j=1,\,d. Then <\equation*> a(g)=1,a(g)=0i\j. Hence the > are linearly independent over >, and thus form a basis for >. Since ,F>, and > are all in [[q]]>, so are the >. The > may then be constructed from the > by Gauss elimination. The coefficients of the resulting power series lie in > because each time we clear a column we use the power series > whose leading coefficient is (so no denominators are introduced). <\remark> The basis coming from Victor Miller's lemma is canonical, since it is just the reduced row echelon form of any basis. Also the linear combinations are precisely the modular forms of level with integral -expansion. <\remark> (Elkies) <\enumerate> If you have just a single form in > to write as a polynomial in > and >, then it is wasteful to compute the Victor Miller basis. Instead, use the upper triangular basis FF>, and match coefficients from > to >. (Or use ``my'' recursion if happens to be the Eisenstein series.) When k>, the zeroth form > in the Miller basis is also the theta function of an extremal self-dual even lattice of dimension (if one exists). More generally, if a lattice is with of extremality then its theta function differs from > by a linear combination of ,f,...,f>. We extend the Victor Miller basis to all > by taking a multiple of > with constant term , and subtracting off the > from the Victor Miller basis so that the coefficients of ,\q> of the resulting expansion are . We call the extra basis element >. <\example> If , then . Choose , since 0>. Then <\equation*> g=\F=q-1032q+245196q+10965568q+60177390q-\ and <\equation*> g=\=q-48q+1080q-15040q+\ We let =g> and <\equation*> f=g+1032g=q+195660q+12080128q+44656110q-\. <\examplesession> \ n4 := Newforms(MF(1,4))[1][1]; \ F4 := n4*240; \ F4; 1 + 240*q + 2160*q + 6720*q + 17520*q + 30240*q + 60480*q + 82560*q + O(q) \ n6 := Newforms(MF(1,6))[1][1]; \ n6 \ '; \\ '; ser error: Unexpected newline in literal identifier \ n6; -1/504 + q + 33*q + 244*q + 1057*q + 3126*q + 8052*q + 16808*q + O(q) \ F6 := n6*(-504); \ F4; 1 + 240*q + 2160*q + 6720*q + 17520*q + 30240*q + 60480*q + 82560*q + O(q) \ F6; 1 - 504*q - 16632*q - 122976*q - 532728*q - 1575504*q - 4058208*q - 8471232*q + O(q) \ Delta := Newforms(CS(MF(1,12)))[1][1]; \ Delta; q - 24*q + 252*q - 1472*q + 4830*q - 6048*q - 16744*q + O(q) \ Delta*F6; q - 1032*q + 245196*q + 10965568*q + 60177390*q - 1130921568*q + 870123128*q + O(q) \ Delta; q - 48*q + 1080*q - 15040*q + 143820*q - 985824*q + O(q) \ 1032*Delta + Delta*F6; q + 195660*q + 12080128*q + 44656110*q - 982499328*q - 147247240*q + O(q) \ S := CS(MF(1,36)); \ Basis(S); [ q + 57093088*q + 37927345230*q + 5681332472832*q + 288978305864000*q + O(q), q + 194184*q + 7442432*q - 197264484*q + 722386944*q + O(q), q - 72*q + 2484*q - 54528*q + 852426*q + O(q) ]\ <\example> When , the Victor Miller basis, including >, is <\align*> >|6218175600q+15281788354560q+\>>|>|q+57093088q+37927345230q+\>>|>|q+194184q+7442432q+\>>|>|q-72q+2484q+\>>>> > on the Victor Miller basis for >. <\steps> [Compute dimension] Set dim(S)>, which we compute using Corollary . [Compute basis] Using the algorithm implicit in Lemma , compute a basis ,\,f> for > modulo >. [Compute Hecke operator] Using the formula from Proposition , compute (f)>> for each . [Write in terms of basis]The elements (f)>> uniquely determine linear combinations of ,f,\,f>>. These linear combinations are trivial to find, since the basis of > are in reduced row echelon form. I.e., the combinations are just the first few coefficients of the power series (f)>. [Write down matrix] The matrix of > acting from the left is the matrix whose rows are the linear combinations found in the previous step, i.e., whose rows are the coefficients of (f)>.\ > <\proof> First note that we only have to compute a modular form modulo > in order to compute (f)> modulo >. This follows from Proposition , since in the formula the th coefficient of (f)> involves only >, and smaller-indexed coefficients of . The uniqueness assertion of Step follows from Lemma above. <\example> This is the Hecke operator > on >: <\equation*> 34359738369>|0>|6218175600>|9026867482214400>>||0>|34416831456>|5681332472832>>||1>|194184>|-197264484>>||0>|-72>|-54528>>>>> It has characteristic polynomial <\equation*> (x-34359738369)\(x-139656x-59208339456x-1467625047588864), where the cubic factor is irreducible. <\conjecture> [Maeda] The characteristic polynomial of > on > is irreducible for any .\ Kevin Buzzard even observed that in many specific cases the Galois group of the characteristic polynomial of > is the full symmetric group (see ). See also for more evidence for Maeda's conjecture. > in Polynomial Time?> Let <\align*> >|>\(n)q>>||+252q-1472q+4830q-6048q-16744q>>||+84480q-113643q-115920q+534612q->>||370944q-577738q+401856q+1217160q+>>||987136q-6905934q+2727432q+10661420q+\>>>> >-function. | Bas Edixhoven and his students have been working intensely for years to apply sophisticated techniques from arithmetic geometry (e.g., étale cohomology, motives, Arakelov theory) in order to prove that such an algorithm exists (among other things), and he believes they are almost there. There is evidently a significant gap between proving of an algorithm that shold be polynomial time, and actually writing down such an algorithm with explicitly bounded running times. The ideas Edixhoven uses are very similar to the ones used for counting points on elliptic curves in polynomial time (the algorithm of Schoof, with refinements by Atkins and Elkies).|(p)>, for prime , that is polynomial-time in the number of digits of . >> Fix an integral domain and a root > of unity in . <\definition> [Dirichlet Character] A modulo over with given choice of \R> is a map :\R> such that there is a homomorphism /N)>\\\\> for which <\equation*> (a)=|(a,N)\1,>>|(a)>|(a,N)=1.>>>>> We denote the group of such Dirichlet characters by )>, or by just , when the choice of > is clear. It follows immediately from the definition that elements of are in bijection with homomorphisms /N)>\\\\>. In this chapter we develop a systematic theory for computing with Dirichlet characters. These will be extremely important everywhere in the rest of this book, when we compute with spaces (\(N))> of modular forms for <\equation*> \(N)=\():|0|1>. For example, Eisenstein series in (\(N))> are associated to pairs of Dirichlet characters. Also the complex vector space (\(N))> with its structure as a module over the Hecke algebra decomposes as a direct sum <\equation*> M(\(N))=\D(N,)>M(\(N))(). Each space (\(N))()> is frequently much easier to compute with than the full (\(N))>. For example, (\(100))> has dimension , whereas (\(100))(1)> has dimension only , and (\(389))> has dimension , whereas (\(389))(1)> has dimension only . <\remark> If <\equation*> \(N)=\():|\|0|\>, then (\(N))(1)=M(\(N))>. <\lemma> The groups /N)>> and ((/N)>,>)D(N,>)> are non-canonically isomorphic. <\proof> This follows from the more general fact that for any abelian group , we have that (G,>)>. To prove that this latter non-canonical isomorphism exists, first reduce to the case when is cyclic of order , in which case the statement follows because \>>, so (G,>)(G,\\\)> is also cyclic of order . <\corollary> We have (N)>, with equality if and only if the order of our choice of \R> is a multiple of the exponent of the group /N)>>. <\example> The group )> has elements , so is cyclic of order (5)=4>. In contrast, the group )> has only the two elements and and order . Fix a positive integer , and write p>> where \p\\\p> are the prime divisors of . By , each factor /p>)>> is a cyclic group =\g\>, except if =2> and \3>, in which case /p>)>> is a product of the cyclic subgroup =\-1\> of order with the cyclic subgroup =\5\>. In all cases we have <\equation*> (/N)>i\n>C=i\n>\g\. For such that \2>, choose the generator > of > to be the element of ,p>-1}> that is smallest and generates. Finally, use the Chinese Remainder Theorem (see (S))) to lift each > to an element in /N)>>, also denoted >, that is modulo each >> for i>. /p)>>|Given an odd prime power >, this algorithm computes a minimal generator for /p)>>. <\steps> [Factor Group Order] Factor (p)=p\2\((p-1)/2)> as a product p>> of primes. This is equivalent in difficulty to factoring . (See chapters 8 and 10 of for integer factorization algorithms.) [Initialize]Set 2>. [Generator?] Using the binary powering algorithm (see (S)), compute >>>, for each prime divisor > of . If any of these powers are , set g+1> and go to Step . If no powers are , output and terminate.\ > For the proof, see . <\example> A minimal generator for /49)>> is . We have (49)=42=2\3\7>, and <\equation*> 21,218,215. so is not a generator for /49)>>. (We see this just from 1>.) However <\equation*> 348,330,343. <\example> In this example we compute minimal generators for , , and : <\enumerate> The minimal generator for /25)>> is . Minimal generators for /100)>>, lifted to numbers modulo , are =51>, =1> and =77>. Notice that -1> and 1>, that =1> since N>, but N>, and 2> is the minimal generator modulo . Minimal generators for /200)>>, lifted to numbers modulo , are =151>, =101>, and =177>. Note that -1>, that 5>, and 2>. Fix an element > of finite multiplicative order in a ring , and let denote the group of Dirichlet characters modulo over , with image in \\{0}>. We specify an element \D(N,R)> by giving the list <\equation> [(g),(g),\,(g)] of images of the generators of /N)>>. (Note if is even, the number of elements of the list () does depend on whether or not N>---there are always two factors corresponding to .) This representation completely determines > and is convenient for arithmetic operations with Dirichlet characters. It is analogous to representing a linear transformation by a matrix. See Section for a discussion of alternative ways to represent Dirichlet characters. <\example> If , then =151>, =101> and =177>, as we saw in Example . The exponent of /200)>> is , since that is the least common multiple of the exponents of /8)>> and /25)>>. The orders of >, > and > are , , and . Let =\> be a primitive th root of unity in >. Then the following are generators for )>: <\equation*> =[-1,1,1],=[1,-1,1],=[1,1,\], and =[1,-1,\]> is an example element of order . To evaluate (3)>, we write in terms of >, >, and >. First, reducing modulo , we see that g\g>. Next reducing modulo , and trying powers of =2>, we find that g>. Thus <\align*> (3)>|(g\g\g)>>||(g)(g)(g)>>||(-1)\(\)>>||=-\.>>>> Example illustrates that if > is represented using a list as described above, evaluation of > on an arbitrary integer is inefficient without extra information; it requires solving the discrete log problem in /N)>>. In fact, for a general character > calculation of > will probably be at least as hard as finding discrete logarithms no matter what representation we use (quadratic characters are easier---see Algorithm ). >|Given a Dirichlet character > modulo , represented by a list (g),(g),\,(g)]>, and an integer , this algorithm computes (a)>. <\steps> [GCD] Compute . If 1>, output and terminate. [Discrete Log]For each , write >>> as a power > of > using some algorithm for solving the discrete log problem (see below). (If =2>, write >>> as >\5>>.) This step is analogous to writing a vector in terms of a basis. [Multiply] Compute and output (g)>> as an element of , and terminate. This is analogous to multiplying a matrix times a vector.\ > By we have an isomorphism of groups <\equation*> (1+p(/p),\)(/p,+), so one sees by induction that Step is ``about as difficult'' as finding a discrete log in /p)>>. There is an algorithm called ``baby-step giant-step'', which solves the discrete log problem in /p)>> in time >)>, where > is the largest prime factor of /p)>> (note that the discrete log problem in /p)>> reduces to a series of discrete log problems in each prime order cyclic factor). This is unfortunately still exponential in the number of digits of >. Given a prime , a generator of /p)>>, and an element (/p)>>, this algorithm finds an such that =a>. (Note that this algorithm works in any cyclic group, not just /p)>>.) <\steps> [Make Lists] Let \> be the ceiling of >, and construct two lists <\equation*> g,g,\,g,g> and <\equation*> a*g,a*g,\,a*g,a*g. [Find Match]Sort the two lists and find a match =a*g>. Then >.\ > <\proof> We prove that there will always be a match. Since we know that > for some with k\p-1> and any such can be written in the form for i,j\m-1>, we will find such a match. Algorithm uses nothing special about /p)>>, so it works in a generic group. It is a theorem that there is no faster algorithm to find discrete logs in a ``generic group'' (see ). Fortunately there are much better subexponential algorithms for solving the discrete log problem in /p)>>, which use the special structure of this group. They use the number field sieve (see e.g., ), which is also the best known algorithm for factoring integers. This class of algorithms has been very well studied by cryptographers; though sub-exponential, solving discrete log problems when is large is still extremely difficult. For a more in-depth survey see . <\example> MAGMA contains an algorithm to compute discrete logarithms in /p)>> for small . Using a Pentium-M 1.8Ghz, I used MAGMA to compute a few discrete logs. The commands below create /p> in MAGMA, then let be the unit group /p)>>, and finally find the power of the minimal generator that equals . The resulting timings below are horrible. After a few seconds of discussion with Allan Steel of MAGMA, it emerged that the MAGMA code below causes MAGMA V2.11-8 to use an check through all possibilities. Presumably, this will be fixed soon.\ <\verbatim> \ G := Integers(NextPrime(10^5)); U,f := UnitGroup(G); \ time 100@@f; 54580*U.1 Time: 0.000 \ G := Integers(NextPrime(10^6)); U,f := UnitGroup(G); \ time 100@@f; 584760*U.1 Time: 0.020 \ G := Integers(NextPrime(10^7)); U,f := UnitGroup(G); \ time 100@@f; 9305132*U.1 Time: 0.320 \ G := Integers(NextPrime(10^8)); U,f := UnitGroup(G); \ time 100@@f; 83605942*U.1 Time: 2.940 \ G := Integers(NextPrime(10^9)); U,f := UnitGroup(G);\ \ time 100@@f; 763676566*U.1 Time: 27.780 \ G := Integers(NextPrime(10^10)); U,f := UnitGroup(G); \ time 100@@f; 8121975284*U.1 Time: 3150.470 Currently the way to request computation of a discrete logarithm in MAGMA is to use the command. Using this command we obtain the above logarithms much more quickly:\ <\verbatim> \ p := NextPrime(10^5); k := GF(p); a := k!PrimitiveRoot(p); \ time Log(k!a, k!100); 54580 Time: 0.000 \ p := NextPrime(10^8); k := GF(p); a := k!PrimitiveRoot(p); \ time Log(k!a, k!100); 83605942 Time: 0.000 \ p := NextPrime(10^12); k := GF(p); a := k!PrimitiveRoot(p); \ time Log(k!a, k!100); 837165108486 Time: 0.000 \ p := NextPrime(10^15); k := GF(p); a := k!PrimitiveRoot(p); \ time Log(k!a, k!100); 543584576740840 Time: 0.060 \ p := NextPrime(10^20); k := GF(p); a := k!PrimitiveRoot(p); \ time Log(k!a, k!100); 55635183831704631320 Time: 0.210 \ p := NextPrime(10^25); k := GF(p); a := k!PrimitiveRoot(p); \ time Log(k!a, k!100); 8669816947492932609764592 Time: 0.480 \ p := NextPrime(10^35); k := GF(p); a := k!PrimitiveRoot(p); \ time Log(k!a, k!100); 28138566543929117345335749648530454 Time: 5.610 \ Factorization(p-1); [ \2, 2\, \3, 1\, \31, 1\, \59, 1\, \36289857533, 1\,\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \125550886981850531627, 1\ ] \ p := NextPrime(p); \ Factorization(p-1); [ \2, 1\, \72229, 1\, \692242727990142463553420371319, 1\ ] \ k := GF(p); a := k!PrimitiveRoot(p); \ time Log(k!a, k!100); 23346611965343882546546326674895020 Time: 4.940 Thus one can deal with primes having around digits in a few seconds. Moral: Having an understanding of the theoretical complexity of an algorithm, is much better than just some timing with an implementation, becuause you might unwittingly misuse the implementation. The specific applications of Dirichlet characters in this book involve computing modular forms, and for these applications will be fairly small, e.g., 10>. Also we will evaluate > on a number of random elements, inside inner loops of algorithms. Thus for our purposes it will often be better to make a table of all values of >, so that evaluation of > is extremely fast. The following algorithm computes a table of all values of >, and it does not require computing any discrete logs since we are computing values. <\algorithm|Values of >> \ Given a Dirichlet character > represented by the list of values of > on the minimal generators > of /N)>>, this algorithm creates a list of all the values of >. <\steps> [Initialize] For each minimal generator >, set 0>. Let g>>, and set 1>. Create a list of values, all initially set equal to . When this algorithm terminates the list will have the property that <\equation*> v[x]=(x). Notice that we index starting at . [Add Value to Table]Set z>. [Finished?] If each > is one less than the order of >, output and terminate. [Increment] Set a+1>, n\g>, and z\(g)>. If \(g)>, set \0>, then set a+1>, n\g>, and z\(g)>. If \(g)>, do what you just did with >, but with all subscripts replaced by . Etc. (Imagine a car odometer.) Go to Step .\ \ Frequently people describe quadratic characters in terms of the Kronecker symbol. The following algorithm gives a way to go between the two representations. Given an integer , this algorithm computes a representation of the Kronecker symbol > as a Dirichlet character. <\steps> Compute the minimal generators > of /N)>> using Algorithm . Compute |N>> for each > using one of the algorithms of (S).\ > <\remark> The algorithms in (S) for computing the Kronecker symbol run in time quadratic in the number of digits of the input, so they do not require computing discrete logarithms. (They use, e.g., that a>, when is an odd prime.) If is very large and we are only interested in evaluating (a)=> for a few , then viewing > as a Dirichlet character in the sense of this chapter leads to a less efficient way to compute with >. The algorithmic discussion of characters in this chapter is most useful for working with the full group of characters, and characters that cannot be expressed in terms of Kronecker characters. <\example> We compute the Dirichlet character associated to the Kronecker symbol >. Using PARI, we find that |200>>, for , where the > are as in Example :\ <\verbatim> ? kronecker(151,200) 1 ? kronecker(101,200) -1 ? kronecker(177,200) 1 Thus the corresponding character is defined by . <\remark> [Elkies] Jacobi reciprocity must be used to efficiently compute the Jacobi symbol >. It's faster than computing > when is prime, but more significantly it makes it possible to compute Jacobi symbols > for all without knowing the factorization of ---which of course would be a computation much longer than quadratic. <\example> We compute the character associated to >. We have 3\5\7>, and minimal generators are <\equation*> g=211,g=1,g=281,g=337,g=241. We have -1>, 2>, 2> and 3>. Using PARI again we find |420>=|420>=1> and |420>=|420>=|420>=-1>, so the corresponding character is . The following algorithm for computing the order of > reduces the problem to computing the orders of powers of > in . This algorithm computes the order of a Dirichlet character \D(N,R)>. <\steps> Compute the order > of each (g)>, for each minimal generator > of /N)>>. Since the order of (g)> is divisor of /p>)>>, we can compute its order by factoring and considering the divisors of . Compute and output the least commmon multiple of the integers >.\ > <\remark> Computing the order of (g)\R> is potentially difficult and tedious. Using a different (simultaneous) representation of Dirichlet characters avoids having to compute the order of elements of . See Section . The next algorithm factors > as a product of ``local'' characters, one for each prime divisor of . It is useful for other algorithms, and also for explicit computations with the Hijikita trace formula (see ). This factorization is easy to compute because of how we represent >. Given a Dirichlet character \D(N,R)>, with p>>, this algorithm finds Dirichlet characters > modulo >>, such that for all (/N)>>, we have (a)=(a>>)>. If N>, the steps are as follows: <\steps> Let > be the minimal generators of /N)>>, so > is given by a list <\equation*> [(g),\,(g)]. For ,n>, let > be the element of >,R)> defined by the singleton list (g)]>. Let > be the element of >,R)> defined by the list (g),(g)]> of length . Output the > and terminate.\ If N>, then omit Step , and include all in Step . > The factorization of Algorithm is unique since each > is determined by the image of the canonical map /p>)>> in /N)>>, which sends >>> to the element of /N)>> that is >>> and >>> for i>. <\example> If =[1,-1,\]\D(200,)>, then =[1,-1]\D(8,)> and =[\]\D(25,)>. <\definition> [Conductor] The of a Dirichlet character \D(N,R)> is the smallest positive divisor N> such that there is a character \D(c,R)> for which (a)=(a)> for all > with . A Dirichlet character is if its modulus equals its conductor. The character > associated to > with modulus equal to the conductor of > is called the >. We will be interested in conductors later, when computing new subspaces of spaces of modular forms with character. Also certain formulas for special values of functions are only valid for primitive characters. This algorithm computes the conductor of a Dirichlet character \D(N,R)>. <\steps> [Factor Character]Using Algorithm , find characters > whose product is >. [Compute Orders] Using Algorithm , compute the orders > of each >. [Conductors of Factors]For each , either set \1> if > is the trivial character (i.e., of order ), or set p>(r)+1>>, where (n)> is the largest power of that divides . [Adjust at ?] If =2> and (5)\1>, set 2c>. [Finished] Output c> and terminate.\ > <\proof> Let > be the local factors of >, as in Step . We first show that the product of the conductors > of the > is the conductor of >. Since > factors through /f)>>, the product > of the > factors through /f)>>, so the conductor of > divides f>. Conversely, if >(f)\>(f)> for some , then we could factor > as a product of local (prime power) characters differently, which contradicts that this factorization is unique. It remains to prove that if > is a nontrivial character modulo >, where is a prime, and is the order of >, then the conductor of > is (r)+1>>, except possibly if p>. Since the order and conductor of > and of the associated primitive character > are the same, we may assume > is primitive, i.e., that > is the conductor of >; note that that 0>, since > is nontrivial. First suppose is odd. Then the abelian group ,R)> splits as a direct sum D(p,R)>, where ,R)> is the -power torsion subgroup of ,R)>. Also > has order p>, where , which is coprime to , is the order of the image of > in and > is the order of the image in ,R)>. If , then the order of > is coprime to , so > is in , which means that , so , as required. If 0>, then \R> must have order divisible by , so has characteristic not equal to . The conductor of > does not change if we adjoin roots of unity to , so in light of Lemma we may assume that (/N)>>. It follows that for each \n>, the -power subgroup >,R)> of >,R)> is the -1>>-torsion subgroup of ,R)>. Thus , since ,R)> is by assumption the smallest such group that contains the projection of >. This proves the formula of Step . We leave the argument when as an exercise (see ). <\example> If =[1,-1,\]\D(200,)>, then as we saw in Example , > is the product of =[1,-1]> and =[\]>. Because (5)=-1>, the conductor of > is . The order of > is (since > is a th root of unity), so the conductor of > is . Thus the conductor of > is 5>. The following two algorithms restrict and extend characters to a compatible modulus. Using them it is easy to define multiplication of two characters \D(N,R)> and \D(N,R)>, as long as and > are subrings of a common ring. To carry out the multiplication, just extend bother characters to characters modulo (N,N)>, then multiply. Given a Dirichlet character \D(N,R)> and a divisor > of that is a multiple of the conductor of >, this algorithm finds a characters \D(N,R)>, such that (a)=(a)>, for all > with . <\steps> [Conductor] Compute the conductor of > using Algorithm , and verify that indeed > is divisible by the conductor and divides . [Minimal Generators] Compute the minimal generators > for /N)>>. [Values of Restriction]For each , compute (g)> as follows. Find a multiple > of > such that +a*N,N)=1>; then (g)=(g+a*N)>. [Output Character] Output the Dirichlet character modulo > defined by (g),\,(g)]>. > <\proof> The only part that is not clear is that in Step there is an such that +a*N,N)=1>. If we write \N>, with ,N)=1>, and > divisible by all primes that divide >, then ,N)=1> since ,N)=1>. By the Chinese Remainder Theorem, there is an > such that g>> and 1>>. Then +b*N=g+(b*N/N)\N> and , which completes the proof. <\algorithm|Extension of Character> Given a Dirichlet character \D(N,R)> and a multiple > of , this algorithm finds a characters \D(N,R)>, such that (a)=(a)>, for all > with )=1>. <\steps> [Minimal Generators] Compute the minimal generators > for /N)>>. [Evaluate] Compute (g)> for each . Since ,N)=1>, we also have ,N)=1>. [Output Character] Output the character defined by (g),\,(g)]>.\ \ We finish with an algorithm that computes the Galois orbit of an element in . This can be used to divide up into Galois orbits, which is useful for modular forms computations, because, e.g., the spaces (\(N))()> and (\(N))()> are canonically isomorphic if > and > are conjugate. \D(N,R)>, this algorithm computes the orbit of > under the action of (/F)>, where is the prime subfield of (R)>, so > or >. <\steps> [Order of >] Let be the order of the chosen root \R>. [Nontrivial Automorphisms]If (R)=0>, let <\equation*> A={a:2\a\n(a,n)=1}. If (R)=p\0>, compute the multiplicative order of modulo , and let <\equation*> A={p:1\m\r}. [Compute Orbit] Compute and output the of unique elements > for each A> (there could be repeats, so we output unique elements only).\ > <\proof> We prove that the nontrivial automorphisms of \\> in characteristic are as in Step . It is well-known that every automorphism in characteristic on \> is of the form x>>, for some . The images of > under such automorphisms are <\equation*> \,\,\>,\. Suppose 0> is minimal such that =\>>. Then the orbit of > is ,\,\>>. Also 1>, where is the multiplicative order of >, so is the multiplicative order of modulo , which completes the proof. <\example> The Galois orbits of characters in >)> are as follows: <\align*> >|>|>|>|>|],[1,1,-\]}>>|>|],[-1,1,-\]}>>|>|>|>|>>> The conductors of the characters in orbit > are , in order > are , in orbit > they are , in > they are , in > the conductor is , and in > the conductor is . (You should verify this.) Let be a positive integer and an integral domain, with fixed root of unity > order , and let )>. As in the rest of this chapter, write p>>, and let =\g\> be the corresponding cyclic factors of /N)>>. In this section we discuss other ways to represent elements \D(N,R)>. Each representation has advantages and disadvantages, and no single representation is best. It emerged while writing this chapter that simultaneously using more than one representation of elements of would be best. It is easy to convert between them, and some algorithms are much easier using one representation, than when using another. In this section we present two other representations, each which has advantages and disadvantages. But, we emphasize that there is frequently no reason to restrict to only one representation! We could represent > by giving a list ,\,b]>, where each \/n> and (g)=\>>. Then arithmetic in is arithmetic in /n)>, which is very efficient. A drawback to this approach is that it is easy to accidently consider sequences that do not actually correspond to elements of , though it is not really any easier to do this than with the representation we use elsewhere in this chapter. Also the choice of > is less clear, which can cause confusion. Finally, the orders of the local factors is more opaque, e.g., compare ]> with . Overall this representation is not too bad, and is more like representing a linear transformation by a matrix. It has the over the representation discussed earlier in this chapter that arithmetic in is very efficient, and doesn't require any operations in the ring ; such operations could be quite slow, e.g., if were a large cyclotomic field. Another way to represent > would be to give a list ,\,b]> of integers, but this time with \/gcd(s,n)>, where > is the order of >. Then <\equation*> (g)=\\n/(gcd(s,n))>, which is already complicated enough to ring warning bells. With this representation we set up an identification <\equation*> D(N,R)/gcd(s,n), and arithmetic is efficient. This approach is seductive because every sequence of integers determines a character, and the sizes of the integers in the sequence nicely indicate the local orders of the character. However, giving analogues of many of the algorithms discussed in this chapter that operate on characters represented this way is tricky. For example, the representation depends very much on the order of >, so it is difficult to correctly compute natural maps D(N,S)>, for S> rings, whereas for the representation elsewhere in this chapter such maps are trivial to compute. This was the representation the author (Stein) implemented in MAGMA. > of order >. This definition says that, e.g., the value of the character on > is| on the Abelian group (/N)g> is given by a row vector =[a,\,a]> such that (g>)=e*x*p(2i\an/N)>.'' >> <\equation*> \(g)=(ei/N>)>. Thus the integers > are integers modulo >, and this representation is basically the same as the one we described in the previous paragraph (and which the author does not like). <\exercises> This exercise is about the structure of the units of /p>. <\enumerate> If is odd and is a positive integer, prove that /p)>> is cyclic. If 3> prove that /2)>> is a direct sum of the cylclic subgroups -1\> and 5\>, of orders 2 and >, respectively. Prove that Algorithm works, i.e., that if (/p)>> and >\1> for all \n=(n)>, then is a generator of /p)>>. Let be an odd prime and 2> an integer, and prove that <\equation*> (1+p(/p),\)(/p,+). Use this to show that solving the discrete log problem in /p)>> is ``not much harder'' than solving the discrete log problem in /p)>>. Suppose > is a nontrivial Dirichlet character modulo > of order over the complex numbers >. Prove that the conductor of > is <\equation*> c=(r)+1>>|(5)=1>>>>|(r)+2>>|(5)\1>.>>>>>> <\enumerate> Find an irreducible quadratic polynomial over >. Then =[x]/(f)>. Find an element with multiplicative order in >. Make a list of all Dirichlet characters in ,\)>. Divide these characters up into orbits for the action of (/)>. Higher Level>In this chapter, we define the space (N,)> modular forms of arbitrary level and character and discuss generalized Bernoulli numbers attached to Dirichlet characters. Then we give an algorithm to enumerate the Eisenstein series in (N,)>. We will have to wait until Chapter for an algorithm to compute all cusp forms in (N,)>. In this section, we define the space (N,)> of modular forms for (N)> with character >. We begin with the definition of (\(N))>. <\definition> [Modular Forms] Let (\(N))> be the complex vector space of holomorphic functions >\> such that ]=f> for all \\(N)>. What it means for to be holomorphic at the elements of {i\}> is somewhat subtle. We say is at > if its -expansion aq> has no nonzero coefficient > for 0>. To make sense of holomorphicity of at \>, let \()> be such that (\)=\>. Then we say is holomorphic at > if ]> is holomorphic at infinity. Note that formally <\equation*> f\|[\](\)=(c*z+d)f(\), where is the bottom row of > and the factor > does not affect holomorphicity at >. Another subtlety hidden in this definition is that ]> is a modular form for the conjugate group \(N)\>, which need not equal (N)>. In particular, the matrix > need not be in , so ]> need not even have a power series expansion >bq> at infinity! Fortunately (see idth>) there is some positive integer such that \G>, so ]> has a power series expansion >bq> in powers of >, and we again say ]> is holomorphic at infinity if =0> for all 0>. (The reason we obtain a power series in > is that ](h*z)> is invariant under z+1>, so ](h*z)> has an expansion in powers of .) A is a subgroup > of ()> that contains the kernel (N)=ker(()\(/N))> for some . The smallest such is the of >. <\definition> [Width of Cusp] The minimal such that \\\\> is called the (\)> for the group >. <\algorithm|Width of Cusp> \ Given a congruence subgroup > of level and a cusp > for >, this algorithm computes the width of >. We assume that > is given by congruence conditions, e.g., =\(N)> or (N)>. <\steps> [Find >] Using the extended Euclidean algorithm, find \()> such that (\)=\>. If =\> set 1>; otherwise, write =a/b>, find such that , and set >. [Generic Conjugate Matrix] Compute the following matrix in ([x])>: <\equation*> \(x)\\. Note that (x)> matrix whose entries are constant or linear in . [Solve] The congruence conditions that define > give rise to four linear congruence conditions on . Use techniques from elementary number theory to find the smallest simultaneous positive solution to these four equations.\ \ <\example> <\enumerate> Suppose =0> and =\(N)> or (N)>. Then => has the property that (\)=\>. Next, the congruence condition is <\equation*> \(x)=\\=|0|1>. Thus the smallest positive solution is , so the width of is . Suppose where are distinct primes, and let =1/p>. Then => sends > to >. The congruence condition for (p*q)> is <\equation*> \(x)=\\=x|p*x+1>|\|0|\>. Since x0>, we see that is the smallest solution. Thus has width , and likewise has width . <\remark> For (N)>, once we enforce that the bottom left entry is >, and use that the determinant is 1, the coprimeness that one gets from the other two congruences is automatic. So there is one congruence to solve for (N)>. There are 2 congruences in the (N)> case (the bottom left entry and top left entry). The group /N)>> acts on (\(N))> through the d\>. For (/N)>>, define <\equation*> f\|=f\|[>], where >\()> is congruent to |0|0|d>>. Note that the map ()\(/N)> is surjective (see ), so it makes sense to consider the matrix >>. To prove that > preserves (\(N))>, we prove the more general fact that (N)> is normal in <\equation*> \(N)=\():|\|0|\>. This will imply that > preserves (\(N))> since >\\(N)>. <\lemma> The group (N)> is a normal subgroup of (N)>, and the quotient (N)/\(N)> is isomorphic to /N)>>. <\proof> Consider the surjective homomorphism ()\(/N)>. Then (N)> is the exact inverse image of the subgroup of matrices of the form |0|1>> and (N)> is the inverse image of the subroup of upper triangular matrices. It thus suffices to observe that is normal in , which is clear. Finally, the quotient is isomorphic to the group of diagonal matrices in (/N)>>, which is isomorphic to /N)>>. The diamond bracket action is simply the action of (N)/\(N)(/N)>> on (\(N))>. Since (\(N))> is a vector space over >, the > action breaks (\(N))> up as a direct sum of factors corresponding to the Dirichlet characters of modulus . <\proposition> We have <\equation*> M(\(N))=\D(N,)>M(N,), where <\equation*> M(N,)=f\(\(N)):f\|=(d)fd\(/N)>. <\proof> The linear transformations >, for the (/N)>>, all commute, since > acts through the abelian group (N)/\(N)>. Also, if is the exponent of /N)>>, then =>==1>, so the matrix of > is diagonalizable. It is a standard fact from linear algebra that any commuting family of diagonalizable linear transformations is simultaneously diagonalizable (see ), so there is a basis ,\,f> for (\(N))> so that all > act by diagonal matrices. The eigenvalues of the action of /N)>> on a fixed > defines a Dirichlet character, i.e., each > has the property that \|=(d)>, for all (/N)>> and some Dirichlet character >. The > for a given > then span (N,)>, and taken together the (N,)> must span (\(N))>. <\definition> [Character of Modular Form] If M(N,)>, we say that >. <\remark> People also often write that has ``nebentypus character'' >. I rarely hear anyone actually nebentypus, and it's somewhat redundant, so I will simply omit it in this book. The spaces (N,)> are a direct sum of subspaces (N,)> and (N,)>, where (N,)> is the subspace of cusp forms, i.e., forms that vanish at cusps (elements of {\}>), and (N,)> is the subspace of Eisenstein series, which is the unique subspace of (N,)> that is invariant under all Hecke operators and is such that (N,)=S(N,)\E(N,)>. The space (N,)> can also be defined as the space spanned by all Eisenstein series of weight and level , as defined below. It can also be defined using the Petersson inner product. <\remark> The notation (N)> will not be used anywhere in this book (except in this sentence). Suppose > is a Dirichlet character modulo over >. <\definition> [Generalized Bernoulli Number] Define the >> attached to > by the following identity of infinite series: <\equation*> (a)\x\e|e-1>=>B>\|k!>. If > is the trivial character of modulus and > are as in Section , then >=B>, except when , in which case >=-B=1/2> (see riv>). Let ()> denote the field generated by the values of the character >, so ()> is the cyclotomic extension (\)>, where is the order of >. Given an integer 0> and any Dirichlet character > with modulus , this algorithm computes the generalized Bernoulli numbers >>, for k>. <\steps> Compute x/(e-1)\[[x]]> to precision )> by computing -1=1>Nx/n!> to precision )>, and computing the inverse -1)>. For completeness, note that if +ax+ax+\>, then we have the following recursive formula for the coefficients > of the expansion of : <\equation*> b-|a>\(ba+ba+\+ba). For each ,N>, compute g\e\[[x]]>, to precision )>. This requires computing =0>ax/n!> to precision )>. (One can omit computation of > if 1>.) Then for k>, we have <\equation*> B>j!\(a)\c(f), where (f)> is the coefficient of > in >.\ > Note that in Steps and we compute the power series doing arithmetic only in [[x]]>, not in ()[[x]]>, which could be much less efficient if > has large order. One could also write down a recurrence formula for >>, but this would simply encode arithmetic in power series rings and the definitions in a formula. <\example> Let > be the nontrivial character with modulus . Thus > has order and takes values in >. Then the Bernoulli numbers >> for even are all and for odd they are <\align*> >>|>|>>|>|>>|>|>>|>|>>|>|>>|>|>>|>|>>|>|>>|>|>>|>>> These Bernoulli numbers can be divisible by large primes. For example, >=5\17\228135437/2>. <\example> This examples illustrates that the generalized Bernoulli numbers need not be rational numbers. Suppose > is the mod character such that (2)=i=>. Then >=0> for even and <\align*> >>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>||>>> <\proposition> If (-1)\(-1)>, then >=0>. Suppose > and > are primitive Dirichlet characters with conductors and , respectively. Let <\equation> E,\>(q)=c+1>\(n)\\(m/n)\nq\(\,\)[[q]], where <\equation*> c=|L\1,>>|->|2k>>|L=1.>>>>> Note that when =\=1> and 4>, then ,\>=E>, where > is from Chapter . Miyake proves statements that imply the following theorems in (Ch. 7). We will not prove them in this book since developing the theory needed to prove them would take us far afield from our goal, which is to compute (N,)>. <\theorem> Suppose is a positive integer and >, > are as above, and that is a positive integer such that (-1)\(-1)=(-1)>. Except when and =\=1>, the power series ,\>(q)> defines an element of (M*L*t,\/\)>. If =\=1>, , 1>, and =E,\>>, then (q)-t*E(q)> is a modular form in (\(t))>. <\theorem> The Eisenstein series in (N,)> coming from Theorem form a basis for the Eisenstein subspace (N,)>. <\theorem> The Eisenstein series ,\>(q)\M(M*L)> defined above is an eigenvector for all Hecke operators >. Also (q)-t*E(q)>, for 1>, is an eigenform. Since ,\>(q)> is normalizes so the coefficient of is , the eigenvalue of > is <\equation*> \(n)\\(m/n)\n. Also for (q)-t*E(q)> with 1> prime, the coefficient of is , and (f)=\(m)\f> for , and (f)=((t+1)-t)f=f>. <\algorithm|Enumerating Eisenstein Series> Given a weight and a Dirichlet character > of modulus , this algorithm computes a basis for the Eisenstein subspace (N,)> of (N,)> to precision )>. <\steps> [Weight 2 Trivial Character?] If and =1>, output the Eisenstein series (q)-t*E(q)>, for each divisor N> with 1>, then terminate. [Compute Dirichlet Group] Let D(N,(\))> be the group of Dirichlet characters with values in (\)>, where is the exponent fo /N)>>. [Compute Conductors]Compute the conductor of every element of (which just involves computing the orders of the local components of each character). [List Characters >]Form a list all Dirichlet characters \G> such that (\)\(\/)> divides . [Compute Eisenstein Series] For each character > in , let =\/>, and compute ,\>(q)>> for each divisor of (\)\(\))>. We compute ,\>(q)>> using () and Algorithm . \ <\remark> Algorithm is what I currently use in my programs. It might be better to first reduce to the prime power case by writing all characters as product of local characters and combine Steps and into a single step that involves orders. However, this might make things more complicated and obscure. <\example> The following is a basis of Eisenstein series ,\>> for (\(13))>.\ <\verbatim> f1 = 1/2 + q + 3*q^2 + 4*q^3 + O(q^4) \; f2 = (-7/13*zeta_12^2 - 11/13) + q + (2*zeta_12^2 + 1)*q^2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + (-3*zeta_12^2 + 1)*q^3 + O(q^4) \; f3 = q + (zeta_12^2 + 2)*q^2 + (-1*zeta_12^2 + 3)*q^3 + O(q^4) \; f4 = (-1*zeta_12^2) + q + (2*zeta_12^2 - 1)*q^2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + (3*zeta_12^2 - 2)*q^3 + O(q^4) \; f5 = q + (zeta_12^2 + 1)*q^2 + (zeta_12^2 + 2)*q^3 + O(q^4) \; f6 = (-1) + q + (-1)*q^2 + 4*q^3 + O(q^4) \; f7 = q + q^2 + 4*q^3 + O(q^4) \; f8 = (zeta_12^2 - 1) + q + (-2*zeta_12^2 + 1)*q^2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + (-3*zeta_12^2 + 1)*q^3 + O(q^4) \; f9 = q + (-1*zeta_12^2 + 2)*q^2 + (-1*zeta_12^2 + 3)*q^3 + O(q^4) \; f10 = (7/13*zeta_12^2 - 18/13) + q + (-2*zeta_12^2 + 3)*q^2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + (3*zeta_12^2 - 2)*q^3 + O(q^4) \; f11 = q + (-1*zeta_12^2 + 3)*q^2 + (zeta_12^2 + 2)*q^3 + O(q^4) <\exercises> Suppose \()> and is a positive integer. Prove that there is a positive integer such that \\\(N)\>. Prove that the map ()\(/N)> is surjective. (Hint: There is a proof of a more general result near the beginning of Shimura's book .) Prove that (N,1)=M(\(N))>. Suppose and are diagonalizable linear transformations of a finite-dimensional vector space and that both and are diagonalizable. Prove there is a basis for so that the matrices of and with respect to that both are simultaneously diagonal. If > is the trivial character of modulus and > are as in Section , then >=B>, except when , in which case >=-B=1/2>. Prove that if 1> is odd, then the Bernoulli number > is . When computing with spaces of modular forms, it is helpful to have easy-to-compute formulas for dimensions of these spaces, and certain of their subspaces. For example, they provide a double-check on the output of the algorithms from Chapter that compute explicit bases for spaces of modular forms. Alternatively, dimension formulas can be used to improve the efficiency of some of the algorithms in Chapter , since we can use them to determine the ranks of certain matrices without having to explicitly compute them. If we know the dimension of (N,)>, and we have a process for computing -expansions of elements of (N,)>, e.g., multiplying together -expansions of certain forms of smaller weight or searching for >-series attached to quadratic forms, then we can tell when we are done generating (N,)>. This chapter contains formulas the author knows for computing dimensions of spaces of modular forms, along with some hints about how to compute them, when this isn't obvious. In several cases we give dimension formulas for spaces that haven't yet been defined in this book, so we define them in this chapter (e.g., we will discuss newforms and oldforms further). We also give many examples, which were computed using the modular symbols algorithms from Chapter . Many of the dimension formulas and algorithms we give below grew out of a program that Bruce Caskel wrote (around 1996) in PARI, which Kevin Buzzard extended. Their program codified dimension formulas that Buzzard and Caskel found or extracted from the literature (mainly (S)). The algorithm for dimensions of spaces with nontrivial character are from , with some slight refinements from Kevin Buzzard. For the rest of this chapter, denotes a positive integer and 2> is an integer. We give for dimensions of spaces of weight modular forms, because it is an to give such formulas; the geometric methods used to derive the formulas below do not apply in the case . If , the only modular forms are the constants, and for 0> the dimension of (N,)> is . For a nonzero integer and a prime , let (N)> be the largest such that \N>. In the formulas below, always denotes a prime number. Let (N,)> be the space of modular forms of level weight and character >, and (N,)> and (N,)> the cuspidal and Eisenstein subspaces. The dimension formulas below for (\(N))>, (\(N))>, (\(N))> and (\(N))> below are almost straight from (S) (see also (S)), and they are derived using the Riemann-Roch Theorem applied to the covering (N)\X(1)> or (N)\X(1)> and appropriately chosen divisors. It would be natural to give a sample argument along these lines at this point, but I will not since it easy to find such arguments in other books and survey papers (see, e.g., ). So you will not learn much about how to derive dimension formulas from this chapter. What you will learn is what is known about dimension formulas and what some of the obscure references are. (N)>>Define functions of a positive integer by the following formulas: <\align*> (N)>|N>p(N)>+p(N)-1>>>|(N)>||N>,>>>|N>1+>|>>>>>>>|(N)>||N> or N>,>>>|N>1+>|>>>>>>>|(N)>|N>(gcd(d,N/d))>>|(N)>|(N)|12>-(N)|4>-<\n>(N)|3>-(N)|2>>>||>>> Note that (N)> is the index of (N)> in ()>. Also (N)> is the genus of the modular curve (N)>, and (N)> is the number of cusps of (N)>. <\proposition> We have (\(N))=g(N)>, and for 4> even, <\align*> (\(N))>|(g(N)-1)+-1\c(N)+>>||\(N)\+\(N)\.>>>> The dimension of the Eisenstein subspace is as follows: <\equation*> dim E(\(N))=(N)>|2>,>>>|(N)-1>|.>>>>>> The following table contains the dimension of (\(N))> for some sample values of and : <\center> ||||||||||| >|(\(N))> >|(\(N))> >|(\(N))> >|(\(N))>>>|||||>|||||>|||||>|||||>|||||>|||||>|||||>|||||>>>> For each divisor > of , there are natural maps <\equation*> \:M(\(N))\M(\(N)), corresponding to the divisors of >, and maps <\equation*> \:M(\(N))\M(\(N)). such that \\> is multiplication by a nonzero scalar. On -expansions, (f(q))=f(q)>, and the definition of > is a more complicated ``trace map'' (see, e.g., ). The space (\(N))> decomposes as a direct sum <\equation*> M(\(N))=M(\(N))>\M(\(N))>, where (\(N))>> is the subspace generated by all images (M(\(N))> where > runs through proper divisors of and runs through all divisors of >. The new subspace (\(N))>> can be defined as either the intersection of the kernels of all maps > to lower level, or the largest Hecke-stable complement of (\(N))>>. Atkin and Lehner proved that the space (\(N))> is built out of new subspaces, in the following sense. <\theorem> [Atkin-Lehner]We have an isomorphism <\equation*> S(\(N))=N>N/M>\(S(\(M))>). This is an isomorphism of > modules, where > is the anemic Hecke algebra, i.e., the subring generated by Hecke operators > with . This theorem reduces the problem of computing (\(N))> to that of computing (\(M))>> for divisors of , a fact that will be central later in this book. Atkin and Lehner also prove that one can completely determine (\(M))>> just from the information of how the Hecke operators act on it (their ``multiplicity one'' theory). Atkin and Lehner's work was generalized to fairly arbitrary congruence subgroups of ()> by Winnie Li in her Berkeley Ph.D. thesis under A. Ogg (see ). If \N\N>, then the maps > from (\(N))> to (\(N))> factor through (\(N))>. Thus in the definition of (\(N))>> and (\(N))>>, it would suffice to consider only proper divisors > of such that > is prime. For a fixed =N/p>, the images of > and > need always be linearly independent (see Example below). However, the images of the new subspace (\(N))>> are linearly independent, as asserted by Theorem . <\proposition> The dimension of the new subspace is <\equation*> dim S(\(N))>=N>>(N/M)\dim S(\(M)), where the sum is over the positive divisors of , and for an integer , <\equation*> >(R)=|\R> for some >>>|\R>-2>|,>>>>> where the product is over primes that exactly divide . (Note that >> is the Moebius function, but is similar to it.) Let (\(n))> and (\(n))>>. Theorem implies that <\equation> f(N)=N>\(N/M)g(M), where (N/M)> is the number of divisors of . Presumably there is an analogue of Moebius inversion, but for functions with the property in (), which involves the function >>. <\example> The space (\(45))> has dimension and basis\ <\verbatim> 1 + 12*q^15 + O(q^20), q + q^7 + 3*q^16 + 6*q^19 + O(q^20), q^2 + 4*q^11 + 3*q^14 + q^17 + O(q^20), q^3 + q^12 + q^15 + 3*q^18 + O(q^20), q^4 + q^7 + 2*q^13 + 4*q^16 + 2*q^19 + O(q^20), q^5 + O(q^20), q^6 + 2*q^12 + 2*q^15 - q^18 + O(q^20), q^8 + q^14 + q^17 + O(q^20), q^9 - 2*q^15 + 3*q^18 + O(q^20), q^10 + O(q^20) The new subspace is spanned by the single cusp form\ <\verbatim> q + q^2 - q^4 - q^5 - 3*q^8 - q^10 + 4*q^11 - 2*q^13 + O(q^14) First consider =45/3=15>. The space (\(15))> has basis\ <\verbatim> 1 + 12*q^5 + O(q^8), q + q^4 + q^5 + 3*q^6 + 2*q^7 + O(q^8), q^2 + 2*q^4 + 2*q^5 - q^6 + 2*q^7 + O(q^8), q^3 - 2*q^5 + 3*q^6 + O(q^8) There are two maps > and > from (\(15))> to (\(45))>. The one dimension space (\(5))> embeds in (\(15))> via f(q)> and f(q)>. We have a commutative diagram <\equation*> |(\(15))[r*d]>>|>|(\(5))[u*r]>[d*r]>>||(\(45)).>>||(\(15))[u*r]>>|>>>> This diagram illustrates that the intersection of the two images of (\(15))> has dimension at least . In fact, the sum of the images of the two maps from (\(15))> is a -dimensional subspace of (\(45))>. Next consider =45/5=9>, where the space (\(9))=E(\(9))> has as basis the three forms\ <\verbatim> 1 + 12*q^3 + 36*q^6 + O(q^8), q + 7*q^4 + 8*q^7 + O(q^8), q^2 + 2*q^5 + O(q^8) There are two maps > and > from (\(9))> to (\(45))>. The images of these two maps span a space of dimension , and this space intersects the span of the images of (\(15))> in a space of dimension . Thus the old subspace (\(45))>> has dimension , and the new subspace has dimension . The new subspace is spanned by the single cusp form\ <\verbatim> q + q^2 - q^4 - q^5 - 3*q^8 - q^10 + 4*q^11 + O(q^12) <\remark> Csirik, Wetherell, and Zieve prove in that a random positive integer has probability of being a value of (N)=dim S(\(N))>, and give bounds on the size of the set of values of (N)> below some given . For example, they show that > are the first few integers that are not of the form (N)> for some . (N)>> This section follows Section closely, but with suitable modifications with (N)> replaced by (N)>. The notion of new and old subspaces for (N)> is exactly the same as for (N)>; simply replace (N)> by (N)> in the discussion of new and old forms in Section . Define functions of a positive integer by the following formulas: <\align*> (N)>|(N)>|,>>>|(N)\\(N)|2>>|>>>>>>>|(N)>||4>,>>>|(N)>|>>>>>>>|(N)>||4>,>>>|(N)>|>>>>>>>|(N)>|(N)>|,>>>||,>>>|N>(d)\(N/d)|2>>|.>>>>>>>|(N)>|(N)|12>-(N)|4>-(N)|3>-(N)|2>>>>> Note that (N)> is the genus of the modular curve (N)>, and (N)> is the number of cusps of (N)>. 5>.> <\proposition> We have (\(N))=g(N)>. If 2>, then <\equation*> dim S(\(N))=dim S(\(N)), where (\(N))> is given by the formula of Proposition . If 3>, let <\equation*> a=(k-1)(g(N)-1)+-1\c(N). Then for 3>, <\equation*> dim S(\(N))=| and k>,>>>|k/3\>|,>>>||>>>>> The dimension of the Eisenstein subspace is as follows: <\equation*> dim E(\(N))=(N)>|2>,>>>|(N)-1>|.>>>>>> The dimension of the new subspace of (\(N))> is <\equation*> dim S(\(N))>=N>>(N/M)\dim S(\(M)), where >> is as in the statement of Proposition . <\remark> Since =S\E>, the formulas above also give a formula for the dimension of >. The following table contains the dimension of (\(N))> for some sample values of and : <\center> ||||||||||| >|(\(N))> >|(\(N))> >|(\(N))> >|(\(N))>>>|||||>|||||>|||||>|||||>|||||>|||||>|||||>|||||>>>> Fix a Dirichlet character > modulo , and let be the conductor of > (we do assume that > is primitive). Assume that \1>, since otherwise (N,)=M(\(N))> and the formulas of Section apply. Also, assume that (-1)=(-1)>, since otherwise (\(N))=0>. In this section we discuss formulas for certain subspaces of (N,)>. In , Cohen and Oesterle assert (without proof, see Remark below) that for any > and , > as above, that <\align*> (N,)>|(N,)>>||\\(N)-\N>\(p,N,v(c))>>||+\(k)\A(N)>(x)+\(k)\A(N)>(x)>>>> where (N)> is as in Section , (N)={x\/N:x+1=0}> and (N)={x\/N:x+x+1=0}>, and ,\> are: <\align*> (k)>||2>>>>||0>>>>|| is odd>>>>>>>>|(k)>||2>>>>||0>>>>||1>>>>>>>>>>> It remains to define >. Fix a prime divisor N> and let (N)>. Then <\equation*> \(p,N,v(c))=>+p-1>>|v(c)\r> and r>,>>>|p>>|v(c)\r> and r>,>>>|p(c)>>|v(c)\r>>>>>>> The formula can be used to compute (N,)>, (N,)>, and (N,)> for any , >, 1>, by using that <\align*> (N,)>|0>>>>|(N,)>|0>>>>|(N,)>|>>>>> One thing that is not straightforward when implementing an algorithm to compute the above dimension formulas is how to efficiently compute the sets (N)> and (N)>. Kevin Buzzard suggested the following two algorithms to the author. Note that if is odd, then (k)=0>, so the sum over (N)> is only needed when is even. (N)>|INPUT: A positive integer and an even Dirichlet character > modulo .OUTPUT: The sum A(N)>(x)>. <\steps> [Factor ] Compute the prime factorization >\p>> of . [Initialize] Set 1> and 0>. [Loop over prime divisors]Set i+1>. If n>, return . Otherwise set p> and e>. <\steps> If 3>, return . If and 1>, return . If and , go to Step . Compute a generator (/p)>> using Algorithm . Compute =a>. Using the Chinese Remainder Theorem to find /N> such that a> and 1>>. Set x>>. Set (x)>. If , set 2t> and go to Step . If , set -2t> and go to Step .\ \ > <\proof> Note that (-x)=(x)>, since > is even. By the chinese remainder theorem, the set (N)> is empty if and only if there is no square root of modulo some prime power divisor of . If (N)> is empty, the algorithm correctly detects this fact in steps --. Thus assume (N)> is non-empty. For each prime power >> that exactly divides , let \Z/N> be such that =-1> and 1>>> for j>. This is the value of computed in steps -- (as one can see using elementary number theory). The next key observation is that <\equation> ((x)+(-x))=A(N)>(x), since by the chinese remainder theorem the elements of (N)> are in bijection with the choices for a square root of modulo each prime power divisors of . The observation () is a huge gain from an efficiency point of view---if had prime factors, then (N)> would have size >, which could be prohibitive, where the product involves only factors. To finish the proof, just note that Steps -- compute the local factors (x)+(-x)=2(x)>, where again we use that > is even. (Note, e.g., that a solution of +10> lifts uniquely to a solution mod > for any , because the kernel of the natural homomorphism /p)>\(/p)>> is a group of -power order. The algorithm for computing the sum over (N)> is similar, but we omit it. The following table contains the dimension of (N,)> for some sample values of and . In each case, > is the product of characters > of maximal order corresponding to the prime power factors of (i.e., the product of the generators of >)>). <\center> ||||||||||| >|(N,)> >|(N,)> >|(N,)> >|(N,)>>>|||||>|||||>|||||>|||||>|||||>|||||>|||||>>>> <\remark> Cohen and Oesterle also give dimension formulas for spaces of half-integral weight modular forms, which we do not give in this chapter. Also does not contain any that their claimed formulas are correct, but instead say only that ``Les formules qui les donnent sont connues de beaucoup de gens et il existe plusieurs méthodes permettant de les obtenir (théorčme de Riemann-Roch, application des formules de trace données par Shimura).'' (The formulas that we give here are well known and there exist many methods to prove them, e.g., the Riemann-Roch theorem and applications of the trace formula of Shimura.) <\exercises> Fill in the elementary number theory details of the proof of Algorithm . Track this down the analogue of Moebius inversion for >> and give a quick presentation on it. Implement in your favorite computer language an algorithm to compute (\(N))>. This chapter is about exact matrix algebra with over the rational numbers and cyclotomic fields. Algorithms for linear algebra over exact fields are necessary in order to implement the modular symbols algorithms that we will describe in Chapter . This chapter partly overlaps with (S). <\definition> [Reduced Row Echelon Form] A matrix is in if each row in the matrix starts with more zeros than the row above it. A matrix is in if it is in row echelon form, the first nonzero entry of any row is , and the first nonzero entry of any row is the only nonzero value in its column. Given a matrix , there is another matrix such that is obtained from by left multiplication by an invertible matrix and is in reduced row echelon form. This matrix is called the reduced row echelon form of . It is unique. A of is one such that the reduced row echelon form of contains a leading . <\example> The following matrix is in row echelon form, but not reduced row echelon form:\ <\verbatim> \ [ 14, \ 2, \ 7, \ 228, -224; \ \ \ \ 0, \ 0, \ 3, \ \ 78, \ -70; \ \ \ \ 0, \ 0, \ 0, -405, \ 381] The reduced row echelon form of the above matrix is\ <\verbatim> \ \ [1, 1/7, 0, 0, -1174/945; \ \ \ 0, \ \ 0, 1, 0, \ \ 152/135; \ \ \ 0, \ \ 0, 0, 1, \ -127/135] Notice that the entries of the reduced row echelon form can easily be messy. Another example is the simple looking matrix\ <\verbatim> \ \ [ -9, \ 6, \ 7, 3, 1, 0, 0, 0; \ \ \ -10, \ 3, \ 8, 2, 0, 1, 0, 0; \ \ \ \ \ 3, -6, \ 2, 8, 0, 0, 1, 0; \ \ \ \ -8, -6, -8, 6, 0, 0, 0, 1] whose echelon form is\ <\verbatim> \ \ [1, 0, 0, 0, \ 42/1025, \ -92/1025, \ 1/25, \ -9/205; \ \ \ 0, 1, 0, 0, 716/3075, -641/3075, -2/75, \ -7/615; \ \ \ 0, 0, 1, 0, -83/1025, \ 133/1025, \ 1/25, -23/410; \ \ \ 0, 0, 0, 1, 184/1025, -159/1025, \ 2/25, \ \ 9/410] One learns in a basic linear algebra course that two matrices and have the same reduced row echelon form if and only if there is an invertible matrix such that . Also, many standard operations in linear algebra, e.g., computation of the kernel of a linear map, intersection of subspaces, membership checking, etc., can be encoded as a question about computing the echelon form of a matrix. The following is a naive algorithm for computing the echelon form of a matrix. <\algorithm|Gauss Elimination> INPUT: An n> matrix over a field.OUTPUT: The reduced row echelon form of .We write for the entry of , where i\m-1> and j\n-1>.\ <\verbatim> def echelon(A): \ \ \ \ start_row = 0 \ \ \ \ nr = A.nrows \ \ \ \ \ \ \ # The number of rows of A \ \ \ \ nc = A.ncols \ \ \ \ \ \ \ # The number of columns of A \ \ \ \ for c in range(nc): # for c = 0, 1, 2, ..., nc-1 \ \ \ \ \ \ \ \ for r in range(nr): \ \ \ \ \ \ \ \ \ \ \ \ a = A[r,c] \ \ \ \ \ \ \ \ \ \ \ \ # if a is nonzero \ \ \ \ \ \ \ \ \ \ \ \ if a != 0: \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ # Rescale row r of A by 1/a. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ A.scale_row(r, 1/a) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ # Swap row r with the start_row row. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ A.swap_rows(r, start_row) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ # Clear the c-th column \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ for i in range(nr): \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ if i != start_row: \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ if A[i,c] != 0: \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ # Add -A[i,c] times start_row to the i-th row \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ # in order to clear the leading entry of\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ # the i-th row. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ A.add_multiple_of_row(start_row, -A[i,c], i) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ # Increment the start_row \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ start_row = start_row + 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ # The following break means that we skip the rest \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ # of the for loop over r in range(nr), and \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ # increase c and start a new for loop over r. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ break This algorithm takes )> arithmetic operation in the base field, where is an n> matrix. If the base field is >, the entries can become huge and arithmetic operations can be increasingly expensive. See Section for ways to mitigate this problem. To conclude this section we mention how to convert a few standard problems into questions about reduced row echelon forms of matrices. Note that one can also phrase some of these answers in terms of the echelon form, which might be easier to compute, or an LUP decomposition (lower triangular times upper triangular times permutation matrix), which the numerical analysts use. <\enumerate> :> Since passing to the reduced row echelon form of is the same as multiplying on the left by an invertible matrix, the kernel of the reduce row echelon form is the same as the kernel of . Thus we may assume is in reduced row echelon form. There is a basis vector of that corresponds to each non-pivot column of . That vector has a at the non-pivot column, 's at all other non-pivot columns, and for each pivot column, the negative of the entry of at the non-pivot column in the row with that pivot element. Suppose > and > are subspace of a finite-dimensional vector space . Let > and > be matrices whose columns form a basis for > and >, respectively. Let \|A]> be the augmented matrix formed from > and >. Let be the kernel of the linear transformation defined by . Then K is isomorphic to the desired intersection. To write down the intersection explicitly, suppose that dim(W)> and do the following: For each in a basis for , write down the linear combination of a basis for got by taking the first entries of the vector . The fact that is in (A)> implies that the vector we just wrote down is also in . We took to have smaller dimension just so that the linear combinations in the intersection could be written down slightly more quickly. >>A major difficulty with computation of the echelon form of a dense matrix over the rational numbers is that arithmetic with large rational numbers is very time consuming, since each addition potentially requires a and numerous additions and multiplications of integers. Moreover, the entries of during intermediate steps of Algorithm can be huge even though the entries of and the answer are small. For example, suppose is an invertible square matrix. Then the echelon form of is the identity matrix, but during intermediate steps the entries of could be quite large. One technique for mitigating this problem is to compute the echelon form using a multi-modular method. The following is a sketch of such a multi-modular method (we will give a more precise version later): <\enumerate> By clearing denominators, we may assume that the entries of are integers. Compute the echelon forms > of the reduction > of modulo several primes }>, using some variant of Algorithm . (Note that arithmetic modulo for a ``machine size'' prime is fast.) Use the Chinese Remainder Theorem to find a matrix with integer entries such that B> for all P>. Use rational reconstruction (see below) to find a matrix whose coefficients are rational numbers such that >, where is the product of the primes in , and B> for each prime . Use height bounds to verify that is the reduced row echelon form of . Rational reconstruction is a process that allows one to sometimes lift an integer modulo uniquely to a bounded rational number. <\algorithm|Rational Reconstruction> INPUT: An integer 0> and an integer 1>.OUTPUT: The numerator and denominator , of the unique rational number , if it exists, with <\equation*> \|n\|,d\>na*d, or returns , if no such rational number exists.\ <\verbatim> def rational_reconstruction(a, m): \ \ \ \ # Reduce a modulo m \ \ \ \ a = a % m \ \ \ \ \ \ \ \ \ \ \ \ \ \ # Trivial special cases \ \ \ \ if a == 0: return (0,1) \ \ \ \ if a == 1: return (1,1) \ \ \ \ # Let bnd be the integer part of the square root of m/2. \ \ \ \ bnd = sqrt(m/2.0) \ \ \ \ \ \ \ # Initialize Euclidean algorithm. \ \ \ \ u = m \ \ \ \ v = a \ \ \ \ # Perform the extended Euclidean algorithm, but terminate \ \ \ \ # when V[2] is \= bnd. \ \ \ \ U = (1,0,u) \ \ \ \ V = (0,1,v) \ \ \ \ while abs(V[2]) \ bnd: \ \ \ \ \ \ \ \ q = U[2]//V[2] \ \ \ \ \ # // means divide and take the integer part \ \ \ \ \ \ \ \ tmp = (U[0]-q*V[0], U[1]-q*V[1], U[2]-q*V[2]) \ \ \ \ \ \ \ \ U = V \ \ \ \ \ \ \ \ V = tmp \ \ \ \ d = abs(V[1]) \ \ \ \ n = V[2] \ \ \ \ if V[1] \ 0: \ n = n * (-1) \ \ \ \ if d \= bnd and gcd(n,d) == 1: \ \ \ \ \ \ \ \ return (n,d) \ \ \ \ return (0,0) <\remark> [Technical Python Remarks] In Python, use the function from the GMP library, not the one from . With Python integers, also means divide and take the floor, i.e., what we denote by above. Finally, is not included with Python. Use, e.g., the function. Algorithm for rational reconstruction is described (with a complete nontrivial proof) in (pg.656--657) as the solution to exercise 51 on page 379. See in particular the paragraph right in the middle of page 657, which describes the algorithm. Knuth says this rational reconstruction algorithm is due to Wang, Kornerup, and Gregory from around 1983. We now give an indication of why Algorithm computes the rational reconstruction of >, leaving the precise details and uniqueness to (pg.656--657). At each step in Algorithm , the -tuple ,v,v)> satisfies <\equation> m\v+a\v=v, and similarly for . When computing the usual extended , at the end =gcd(a,m)> and >, > give a representation of the > as a >-linear combination of and . In Algorithm , we are instead interested in finding a rational number such that a\d>. If we set > and > in () and rearrange, we obtain <\equation*> n=a\d+m\v. Thus at step of the algorithm we find a rational number such that a*d>. The problem at intermediate steps is that, e.g., > could be , or or could be too large. If is a matrix with rational entries, let be the of , which is the maximum of the absolute values of the numerators and denominators of all entries of . INPUT: An n> matrix with entries in >.OUTPUT: The reduced row echelon form of . <\steps> Rescale the input matrix to have integer entries. This does not change the echelon form and makes reduction modulo many primes easier. Henceforth we assume has integer entries. Let be a guess for the height of the echelon form. List successive primes ,p,\> such that the product of the > is bigger than c\H(A)+1>, where is the number of columns of . Compute the echelon forms > of the reduction >> using, e.g., Algorithm or something similar. Discard any > whose pivot column list is not maximal among pivot lists of all > found so far. (The pivot list associated to > is the ordered list of integers such that the th column of > is a pivot column. We mean maximal with respect to the following ordering on integer sequences: shorter integer sequences are smaller, and if two sequences have the same length, then order in reverse lexicographic order. Thus is smaller than , and is smaller than . Think of maximal as ``optimal'', i.e., best possible pivot columns.) Use the Chinese Remainder Theorem to find a matrix with integer entries such that B>> for all >. Use rational reconstruction (Algorithm ) to try to find a matrix whose coefficients are rational numbers such that >, where p>, and B>> for each prime . If rational reconstruction fails, compute a few more echelon forms mod the next few primes (using the above steps), and attempt rational reconstruction again. Let be the matrix over > so obtained. Compute the denominator of , i.e., the smallest positive integer such that has integer entries. If <\equation> H(d*E)\H(A)\n\p, then is the reduced row echelon form of . If not, repeat the above steps with a few more primes.\ > <\proof> We prove that if the bound () is satisfied, then the matrix computed by the algorithm really is the reduced row echelon form of . The set of pivot columns of all matrices > used to construct are the same, so the pivot columns of are the same as those of any >. Thus is in reduced row echelon form. Recall from the end of Section that a matrix whose columns are a basis for the kernel of can be obtained from the reduced row echelon form of . Let be the matrix whose columns are the vectors in the kernel algorithm applied to , so . Since the reduced row echelon form is got by left multiplying by an invertible matrix, for each , there is an invertible matrices > mod > such that B> so <\equation*> A\d*Kd*CBKC\d*E\K0>. Since and are integer matrices, <\equation*> A\d*K0p>. The integer entries of d*K> are all at most H(d*K)\n>, where is the number of columns of . Since H(E)>, the bound () implies that d*K=0>. Thus , so (E)\(A)>. On the other hand, the rank of equals the rank of each > (since the pivot columns are the same), so <\equation*> (E)=(B)=(A>)\(A). Thus (A))\dim((E))>, and combining this with the bound obtained above we see that (E)=(A)>. This implies that is the reduced row echelon form of , since two matrices have the same kernel if and only if they have the same reduced row echelon form (the echelon form is an invariant of the row space, and the kernel is the orthogonal complement of the row space). The reason for Step is that the matrices > need be the reduction of modulo >, and indeed this reduction might not even be defined, e.g., if > divides the denominator of some element of , then this reduction makes no sense. For example, set > and suppose >. Then >, which has no reduction modulo ; also, the reduction of modulo > is =>, which is already in reduced row echelon form. However if we were to combine > with the echelon form of modulo another prime, the result could never be lifted using rational reconstruction. Thus the reason we exclude all > with non-maximal pivot column sequence is so that a rational reconstruction will exist. There are only finitely many primes that divide denominators of entries of , so eventually all > will have maximal pivot column sequences, i.e., are the reduction of the true reduced row echelon form , so the algorithm terminates. <\remark> <\enumerate> I learned about rational reconstruction in the context of computing echelon forms from Allan Steel, who is one of the developers of . I learned from Allan that does not use the above algorithm; instead it uses a Strassen ``divide and conquer'' echelon procedure that involves random permuting of rows, etc., and takes advantage of asymptotically fast matrix multiplication algorithms. The matrix multiplies are done using a modular CRT technique. This is probably better in many cases, especially for dense matrices. I have tested an implementation of Algorithm against MAGMA V2.11-8. For large square matrices over >, e.g., over a hundred rows, (a case of importance when cutting out eigenspaces for Hecke operators), Algorithm is much more efficient (both in time and memory usage) than MAGMA. In contrast, for matrices with more columns than rows (an important case, e.g., when intersecting subspaces), MAGMA is often an order of magnitude faster. Thus an optimal package should probably implement both Algorithm for square matrices and a divide and conquer echelon strategy for non-square matrices. I have never seen Algorithm anywhere else, and found the details and proof myself. I have seen the idea of using a multi-modular method for linear algebra problems hinted out or explicitly suggested ; I've just never seen a discussion of computing reduced row echelon forms this way. There is also an iterative -adic method for lifting solutions modulo to an equation to characteristic . This is supposed to be faster for a single solution, but slower for lifting many solutions. See\ <\verbatim> http://magma.maths.usyd.edu.au/users/allan/gb/faugere_f4.ps.gz for a discussion. Algorithm , with all matrices , seems to work very well in practice. A simple but helpful modification to Algorithm in the sparse case is to clear each column using a row with a minimal number of nonzero entries, so as to reduce the amount of ``fill in'' (denseness) of the matrix. There are more sophisticated methods along these lines called ``intelligent Gauss elimination''. (Cryptographers are interested in linear algebra with huge sparse linear, since they come up in factor basis attacks on the discrete log problem or integer factorization.) One can likely adapt Algorithm to computation of reduced row echelon forms of matrices over cyclotomic fields (\)>. Assume has denominator . Let be a prime that splits completely in (\)>. Compute the homomorphisms :[\]\> by finding the elements of order in >>. Then compute the mod matrix (A)> for each , and find its reduced row echelon form. Taken together, the maps > together induce an isomorphism :[X]/\(X)>, where (X)> is the th cyclotomic polynomial and is its degree. It's easy to compute (f(x))> by evaluating at each element of order in >. To compute > simply use linear algebra over > to invert a matrix that represents >. Use > to compute the the reduced row echelon form of >, where is the non-prime ideal in [\]> generated by . Do this for several primes , and use rational reconstruction on each coefficient of each power of >, to recover the echelon form of . Problems: What is the analogue of ()? There are several linear algebra algorithms that involve polynomials and are important to modular forms algorithms. Computation of characteristic polynomials of matrices is crucial to modular forms computations. There are many approaches to this problems: compute symbolically (bad), compute the traces of the powers of (bad), or compute the Hessenberg form modulo many primes and use CRT (not so bad, see (S)). Another more sophisticated method is to compute the rational canonical form of using Giesbrecht's algorithms, which involve computing Krylov subspaces (i.e., cyclic spaces spanned by a single vector), and building up the whole space on which acts. This latter method may be viewed as a generalization of Weiedemann's algorithm for computing characteristic polynomials, but with more structure. The algorithm used in is similar to Giesbrecht's (probably independently discovered). PARI uses only Lagrange interpolation (?) and Hessenberg form. Factorization of polynomials in [X]> is an important step in computing an explicit basis of newforms for a space of modular forms. The best algorithm is the van Hoeij method, which uses LLL in a novel way to solve the sort of optimization problems that come up in trying to lift factorizations mod to >. It has aparently been generalized to number fields and is included in new versions of PARI, , and NTL. For more details, see van Hoeij's web page: . Modular symbols are a formalism that make it fairly easy and elementary to compute with homology or cohomology related to certain Kuga-Sato varieties (these are \\\>, where is a modular curve and > is the univeral elliptic curve over it). It is not necessary to know anything about these Kuga-Sato varieties in order to compute with modular symbols. This chapter is about spaces of modular symbols and how to compute with them. It is by far the most important chapter in this book. The algorithms that build on the theory in this chapter are central to all the computations we will do later in the book. We will start with the basics, in that the intended reader of this chapter is not assumed to have ever seen a modular symbol before. Much of this chapter follows Loic Merel's paper very closely. First we define modular symbols of weight 2>. Then we define the corresponding Manin symbols, and state a theorem of Merel-Shokurov, which gives all relations between Manin symbols. (The proof of the Merel-Shokurov theorem is beyond the scope of this book.) Next we describe how the Hecke operators act on both modular and Manin symbols, and how to compute trace and inclusion maps between spaces of modular symbols of different levels. We close the chapter with a discussion of computations with modular symbols over finite fields. In this book we will view modular symbols primarily as a formalism that generates algorithms for computing with modular forms. I.e., . However, modular symbols have also been used to prove theoretical results about modular forms. For example, certain technical calculations with modular symbols are used in Loic Merel's proof of the uniform boundedness conjecture for torsion points on elliptic curves over number fields; modular symbols arise, e.g., in order to understand linear independence of Hecke operators. Another example is Grigor Grigorov's in-progress Ph.D. thesis, which distills hypotheses about Kato's Euler system in > of modular curves to a simple formula involving modular symbols (when the hypotheses are satisfied, one obtains a lower bound on the Shafarevich-Tate group of an elliptic curve). We begin by defining a free abelian group > of modular symbols, which you should think of as the homology of the extended upper half plane >=

()> relative to the cusps. This is the free abelian group on symbols ,\}> with <\equation*> \,\\

()={\} subject to the relations <\equation*> {\,\}+{\,\}+{\,\}=0, for all ,\,\\

()>. More precisely, =(F/R)/(F/R)>>, where is the free abelian group on all pairs ,\)> and is the subgroup generated by all elements of the form ,\)+(\,\)+(\,\)>. Note that > is a huge free abelian group of countable rank. <\remark> [Warning!] The ,\}> satisfy the relations ,\}=-{\,\}>, since ,\}+{\,\}+{\,\}=0.> Thus the order matters. The notation ,\}> looks like the set containing two elements, which strongly (and incorrectly) suggests that the order does not matter. This is annoying, but it is the standard notation, and we will stick with it. Now fix an integer 2>. Let [X,Y]> be the abelian group of homogeneous polynomials of degree in two variables (so [X,Y]> is isomorphic to ()> as a group, but certain natural actions are different). Set <\equation*> =[X,Y]>, which is a torsion-free abelian group whose elements are sums of expressions of the form Y{\,\}>. For example, <\equation*> X{0,1/2}-17X*Y{\,1/7}\. Fix a finite index subgroup of ()>. Define a > on [X,Y]> as follows. If \G> and [X,Y]>, let <\equation*> (g.P)(X,Y)=P(d*X-b*Y,-c*X+a*Y). Note that if we think of as a column vector, then <\equation*> (g.P)(z)=P(gz), since =d|-b|-c|a>>, since . The reason for the inverse is so that this is a left action instead of a right action, which is what function pre-composition always is. As further explanation, observe that if G>, then <\equation*> ((g*h).P)(z)=P((g*h)z)=P(hgz)=(h.P)(gz)=(g.(h.P))(z). Let act on the left on > by <\equation*> g.{\,\}={g(\),g(\)}. Here is acting via linear fractional transformations, so if >, then <\equation*> g(\)=+b|c\+d>. For example, useful special cases to remember are that if > then <\equation*> g(0)=g(\)=. We now combine these two actions to obtain a left action of on >, which is given by <\equation*> g.(P{\,\})=(g.P){g(\),g(\)}. For example, <\align*> 1|2|-2|-3>.(X{0,1/2})>|-,->>||=(-27X-54XY-36X*Y-8Y)-,-.>>>> We will often write ,\}> for {\,\}>. <\definition> [Modular Symbols] Let 2> be an integer and let be a finite index subgroup of ()>. The space (G)> of weight modular symbols for is the quotient of > by all relations for > and by any torsion. Note that > is a torsion free abelian group, and it is a nontrivial fact that > has finite rank. We denote modular symbols for in exactly the same way we denote elements of >, but with surrounding text that hopefully makes the group clear. Thus {0,1/2}> is an example element of (\(8))>, because I say so. In practice this does not cause confusion. The space of > is <\equation*> (G,R)=(G)>R. In Section we will discuss computing (G,R)> when is a finite field. At this point you are probably wondering how one could possibly ever program a computer to (G)> for any specific and . As defined above, (G)> is the quotient of one infinitely generated abelian group by another one. This section is about Manin symbols, which are simply a distinguished subset of the elements of (G)> that lead to a finite presentation for (G)>. Also, it has emerged that formulas written in terms of Manin symbols are frequently much easier to compute using a computer than formulas in terms of modular symbols. The associated to ()> and [X,Y]> is <\equation*> [P,g]=g.(P{0,\})\(G). Notice that if , then , since the symbol })> is invariant by the action of on the left (by definition, since it is a modular symbols for ). Thus we can also write , and since has finite index in ()>, the abelian group generated by Manin symbols is of finite rank, generated by <\equation*> [XY,G*g]:i=0,\,k-2,j=0,\,r, where ,\,g> run through representatives for the right cosets ()>. The great thing about Manin symbols is that every modular symbols can be written as a >-linear combination of them, so they generate all (G)>. The proof of this fact is known as ``Manin's trick''. <\proposition> The Manin symbols generate (G)>. <\proof> Suppose that we are given a modular symbol ,\}> and wish to represent it as a sum of Manin symbols. Because <\equation*> P{a/b,c/d}=P{a/b,0}+P{0,c/d}, it suffices to write in terms of Manin symbols. Let <\equation*> 0=|q>=,|q>=,|1>=|q>,|q>,|q>,\,|q>= denote the continued fraction convergents of the rational number . Then <\equation*> pq-pq=(-1)-1\j\r. If we let =p|p|(-1)q|q>>, then \> and <\align*> ||q>,|q>>>||g((gP){0,\})>>||[gP,g].>>>> Since \> and has integer coefficients, the polynomial P> also has integer coefficients, so we introduce no denominators. As is well known, the continued fraction expansion ,c,\,c]> of the rational number can be computed using the Euclidean algorithm. The first term > is the ``quotient'': +r>, with r\b>. Let =b>, =r> and compute > as =bc+r>, etc., terminating when the remainder is . For example, the expansion of is . The numbers <\equation*> d=c+c+c+\>> will then be the (finite) convergents. For example if , then the convergents are <\equation*> 0/1,1/0,d=0,d=,d=,d=,d=. <\remark> One can prove Proposition inductively without introducing continued fractions, but that proof is essentially the same one used to prove the existence of continued fractions of integers. (I think I saw this in , but I can't seem to find the exact location in that paper right now.) Now that we know the Manin symbols generate (G)>, the next question is what are the relations between Manin symbols. Fortunately the answer is fairly simple (though the proof is not). Let <\equation*> \=0>,\=,J=0|0|-1>. Define a of ()> on Manin symbols as follows. If ()>, let <\equation*> [P,g].h=[h.P,g*h]. This is a right action because P> is a right action, and right multiplication g*h> is also a right action. <\theorem> If is a Manin symbol, then <\align> >|>|+x.\>|>||>>> Moreover, these are all the relations between Manin symbols, in the sense that the space (G)> of modular symbols is isomorphic to the quotient of the free abelian group on the finitely many symbols Y,G*g]> (for ,k-2>, and G\()>) by the above relations and any torsion. <\proof> We will only prove the easy ``half'' of the theorem here. The proof of the difficult half, i.e., that the above relations are all the relations is more complicated. Merel remarks in (S) that the quotient of Manin symbols by the above relations and torsion is isomorphic to a space of ’okurov symbols, which is in turn isomorphic to (G)>. He cites for most of the proof. See also for an exposition of Manin's proof from when , which involves triangulating the Riemann surface >. For the proof of the easy half, i.e., that the expressions above are in fact relations, we follow Merel's proof from (S). Note that <\equation*> \(0)=\(\)=\\(1)=\(0)=\. Write , we have <\align*> >|.P,g\]>>||})+g\.(\.P{0,\})>>||)}+(g\).(\.P){g\(0),g\(\)}>>||)}+(g.P){g(\),g(0)}>>||)}+{g(\),g(0)})>>||>>> Also, <\align*> |+[P,g].\=[P,g]+[\.P,g\]+[\.P,g\]>>||})+g\.(\.P{0,\})+g\.(\.P{0,\})>>||)}+(g.P){g\(0),g\(\)})+(g.P){g\(0),\(\)})>>||)}+(g.P){g(1),g(0)})+(g.P){g(\),g(1)})>>||)}+{g(\),g(1)}+{g(1),g(0)})>>||>>> Finally, <\align*> |})-g*J.(JP{g*J(0),g*J(\)}>>||)}-(g.P){g(0),g(\)}>>||>>> where we use that acts trivially via linear fractional transformations. If is a finite-index subgroup and we have an algorithm to enumerate the right cosets ()>, and to decide which coset an arbitrary element of ()> belongs to, then Theorem and the algorithms of Chapter yield an algorithm to compute (G,)>. We will defer further discussion about precise details of algorithms to compute modular symbols until Chapter ). Note that if G>, then the relation is automatic. Also note the matrices > and > , so one can first quotient out by the two-term > relations, then quotient out only the remaining free generators by the > relations, and get the right answer in general. <\proposition> The right cosets (N)\()> are in bijection with pairs where /N> and . The coset containing a matrix > corresponds . <\proof> This proof is copied from (pg. 203), except in that paper Cremona works with the analogue of (N)> in ()>, so his result is slightly different. Suppose =|b|c|d>\()>, for . We have <\equation*> \\=|b|c|d>d|-b|-c|a>=d-bc|\|cd-dc|ad-bc>, which is in (N)> if and only if <\equation> cd-dc0 and <\equation> ad-bcad-bc1. Since the > have determinant , if ,d)=(c,d)>, then the congruences (--) hold. Conversely, if (--) hold, then <\align*> >|adc-bcc>>||adc-bccdcdc>>||cad-bc=1,>>>> and likewise <\equation*> dadd-bcdadd-bdcd. Thus we may view weight Manin symbols for (N)> as triples of integers , where i\k-2> and /N> with . Here corresponds to the Manin symbol Y,|d>]>, where > and > lift . The relations of Theorem become <\align*> c,d)+(-1)(k-2-i,d,-c)>|>|c,d)+(-1)(-1)(j,d,-c-d)>|>|+(-1)(-1)(k-2-i+j,-c-d,c)>|>|c,d)-(-1)(i,-c,-d)>|>>> There is a similar description of cosets for (N)>: <\proposition> The right cosets (N)\()> are in bijection with the elements of (/N)>. The coset containing a matrix > corresponds to the point

(/N)>. For a proof, see (S). Suppose now that (N)\()>. Merel defines an action of diamond bracket operators >, with , on modular and Manin symbols. On Manin symbols the action is given by <\equation*> \n\([P,(c,d)])=P,(n*c,n*d). Let <\equation*> :(/N)>\(\)> be a Dirichlet character, where > is an th root of unity and is the order of >. Let (\(N),)> be the quotient of (\(N),[\])> by the relations (given in terms of Manin symbols) <\equation*> x-(d)x=0, for all (\(N),[\])>, and by any torsion. Thus (\(N),)> is a torsion free []>-module. <\remark> I do not know whether or not (\(N),)> is necessarily free as a []>-module. Just as for modular forms, there is a =[T,T,\]> of Hecke operators that act on (\(N))>. Let <\equation*> R=:r=0,1,\,p-1, where we omit > if N>. Then the > on (\(N))> is given by <\equation*> T(x)=R>g.x. Notice when N>, that > is defined by summing over matrices that correspond to the sublattices of \> if index . This is exactly how we defined > on modular forms. You might think at this point that we've just formally defined a computable abelian group, and defined operators formally on it that look something like the usual Hecke operators, but perhaps there's no real connection. As it turns out, the ring generated by all the Hecke operators on modular symbols is commutative, and (\(N),)> is non-canonically isomorphic as a >-module to (\(N))>. Note that (\(N),)> is a real vector space and (\(N))> is a complex vector space, so this should be viewed also as an isomorphism of >-vector spaces. In fact there is an extra conjugation structure on (\(N),)>, which we will discuss later. Let > be a finite index subgroup of ()> and suppose <\equation*> \\() is a set such that \=\\=\> and \\> is finite. For example, =\> trivially satisfies this condition. Also, if =\(N)>, then for any positive integer , the set <\equation*> \=\M():a*d-b*c=n,|0|n> also satisfies this condition, as we will now prove. <\lemma> We have <\equation*> \(N)\\=\\\(N)=\ and <\equation*> \=\(N)\\, where 1/a|0|0|a>>, the union is disjoint and a\n> with n>, , and b\n/a>. In particular, the set of cosets (N)\\> is finite. <\proof> If \\(N)> and \\>, then <\equation*> |0|1>\|0|n>|0|n>\|0|1>|0|n>. Thus (N)\\\>, and since (N)> is a group (N)\=\>; likewise \(N)=\>. For the coset decomposition, we first prove the statement for , i.e., for (N)=()>. If is an arbitrary element of ()> with determinant , then using row operators on the left with determinant , i.e., left multiplication by elements of ()>, we can transform into the form >, with a\n> and b\n>. (Just imagine applying the Euclidean algorithm to the two entries in the first column of . Then is the of the two entries in the first column, and the lower left entry is . Next subtract from until b\n/a>.) Next suppose is arbitrary. Let ,\,g> be such that <\equation*> g\(N)\g\(N)=() is a disjoint union. If \> is arbitrary, then as we showed above, there is some \()>, so that \A=>, with a\n> and b\n/a>, and n>. Write =g\\>, with \\(N)>. Then <\equation*> \\A=g\|0|n>. It follows that <\equation*> g|0|n>\|0|a>. Since \\(N)> and , there is \\(N)> such that <\equation*> \g. We may then choose =\g>. Thus every \> is of the form \>, with \\(N)> and suitably bounded. This proves the second claim. Let any element =\()> act on the left on modular symbols > by <\equation*> \(P{\,\})=P(d*X-b*Y,-c*X+a*Y){\(\),\(\)}. (Until now we had only defined an action of ()> on modular symbols.) For \()>, let <\equation> =d|-b|-c|a>=det(g)\g. Note that |~>=g>. Also, .P(X,Y)=(P\)(X,Y)>, where we set <\equation*> (X,Y)=(d*X-b*Y,-c*X+a*Y). Suppose > and > are as above. Fix a finite set of representatives for \\>. Let <\equation*> T>:(\)\(\) be the linear map <\equation*> T>(x)=\R>\\x, This map is well defined because if \\> and (\)>, then <\equation*> \R>\\\x=>>>\\\x=>>>\\x=\R>\\x, where we have used that \=\\>, and > acts trivially on (\)>. Let =\(N)> and =\>. Then the th Hecke operator > is >>, and by Lemma , <\equation*> T(x)=\\x, where are as in Lemma . Given this definition, we can compute the Hecke operators on (\(N))> as follows. Write as a modular symbol ,\}>, compute (x)> as a modular symbol, then convert back to Manin symbols using (many!) continued fractions expansions. This is extremely inefficient, and fortunately Lo<"|i>c Merel found a much better way, which we now describe (see also and also ). If is a subset of ()>, let <\equation*> ={:g\S}. Also, for any ring and any subset M()>, let denote the free -module with basis the elements of , so the elements of are the finite -linear combinations of the elements of . One of the main theorems of is that for any ,\> as above, if one can find uM\[M()]> and a map <\equation*> \:|~>()\() that satisfies a complicated list of conditions, then for any Manin symbol (\)>, we have <\equation*> T>([P,g])=|~>()M\()>u[\P,\(g*M)]. Merel devotes substantial work to giving examples of > and uM\[M()]> that satisfy all his conditions. When =\(N)>, the complicated list of conditions becomes simpler. Let ()> be the set of 2> matrices with determinant . An element <\equation*> h=u[M]\[M()] >> if for every M()/()>, we have that <\equation> K>u([M\]-[M0])=[\]-[0]\[P()]. If satisfies condition >, then for any Manin symbol M(\(N))>, Merel proves that <\equation> T([P,(u,v)])=u[P(a*X+b*Y,c*X+d*Y),(u,v)M]. Here (/N)> corresponds to a coset of (N)> in ()>, as in Proposition , and if ,v)=(u,v)M\(/N)>, and ,v,N)\1>, then we omit the corresponding summand. For example, we will now check directly that the element <\equation*> h=+++ satisfies condition >. We have, as in the proof of Lemma , but using elementary column operations, that <\align*> ()/()>|():a=1,20\b\2/a>>||(),(),().>>>> To verify condition >, we consider each of the three elements of ()/()> and check that () holds. We have that <\equation*> \(), <\equation*> ,\(), and <\equation*> \(). Thus if ()>, the left sum of () is (\)]-[(0)]=[\]-[0]>, as required. If ()>, then the left side of () is <\equation*> [(\)]-[(0)]+[(\)]-[(0)]=[\]-[1]+[1]-[0]=[\]-[0]. Finally, for ()> we also have (\)]-[(0)]=[\]-[0]>, as required. Thus by () we can compute > on Manin symbol, by summing over the action of the four matrices ,,,>. <\proposition> [Merel]The element <\equation*> b\0d\c\0a*d-b*c=n>>\[M()] satisfies condition >. Merel's proof isn't too difficult, but takes two pages. <\remark> In (S), Cremona discusses the work of Merel and Mazur on Heilbronn matrices in the special cases =\(N)> and weight . He gives a fairly simple proof that the action of > on Manin symbols can be computed by summing the action of some set > of matrices of determinant . He then describes the set >, and gives an efficient continued fractions algorithm for computing it (but he does not seem to prove that his description of > is correct). (Note: My experience is that Cremona's set > is significantly smaller than the sets appearing in Merel's paper, but when I've tried to use > to do certain more general higher-weight computations that are correct using Merel's sets, they do not work.) Merel also gives another family > of matrices that satisfy condition >, and he proves that as \>, <\equation*> #\>\\(n)log(n), where (n)> is the sum of the divisors of . Thus for a fixed space (\)> of modular symbols, one can compute the Hecke operator > using (n)log(n))> arithmetic operations in the base field. Note that we've fixed (\)>, so we ignore the linear algebra involved in computation of a presentation; also, adding elements takes a bounded number of field operations when the space is fixed. Thus using Manin symbols the complexity of computing >, for prime, is field operations, which is in the number of digits of . There is a trick of Basmaji (see ) for computing a matrix of > on (\)>, when is very large, and it is more efficient than one might naively expect. Basmaji's trick doesn't improve the big-oh complexity for a fixed space, but does improve the complexity by a constant factor of the dimension of (\,)>. Suppose we are interested in computing the matrix for > for some massive integer , and that (\,)> as has fairly large dimension. The trick is as follows. Choose, a list <\equation*> x=[P,g],\,x=[P,g]\V=(\,) of Manin symbols such that the map :\V> given by <\equation*> t\(t*x,\,t*x) is injective. In practice, it is often possible to do this with ``very small''. Also, we emphasize that > is a >-vector space of dimension dim(V)>. Next find Hecke operators >, with small, whose images form a basis for the image of >. Now with the above data precomputed, which only required working with Hecke operators > for small , we are ready to compute > with huge. Compute =T(x)>, for each ,r>, which we can compute using Heilbronn matrices since each =[P,g]> is a Manin symbol. We thus obtain (T)\V.> Since we have precomputed Hecke operators > such that (T)> generate >, we can find > such that a\(T)=\(T)>. Then since > is injective, we have =aT>, which gives the full matrix of > on (\,)>. Let > be the free abelian group on symbols }>, for \

()>, and set <\equation*> =[X,Y]. Define a left action of ()> on > by <\equation*> g.(P{\})=(g.P){g(\)}, for ()>. For any finite index subgroup \()>, let (\)> be the quotient of > by the relations for all \> and by any torsion. Thus (\)> is a torsion free abelian group. The is the map <\equation*> b:(\)\(\) given by extending the map <\equation*> b(P{\,\})=P{\}-P{\} linearly. The space (\)> of is the kernel <\equation*> (\)=ker((\)\(\)), so we have an exact sequence <\equation*> 0\(\)\(\)\(\). One can prove that when 2> then this sequence is exact on the right. Also, there is a presentation of (\)> in terms of ``boundary Manin symbols''. [[TODO: Add this later to the book, but discussing this is not necessary for Math 257.]] In this section we define a pairing between modular symbols and modular forms, and prove that the Hecke operators respect this pairing. We also define an involution on modular symbols, and study its relationship with the pairing. This pairing is crucial in much that follows, because it gives rise to period maps from modular symbols to certain complex vector spaces. Fix an integer weight 2> and a finite-index subgroup > of ()>. Let (\)> denote the space of holomorphic modular forms of weight for >, and (\)> its cuspidal subspace. Following (S), let <\equation*> (\)={:f\S(\)} denote the space of cuspforms. Here > is the function on >> given by (z)=>. Define a pairing <\equation> (S(\)\(\))\(\)\ by <\equation*> \(f,f),P{\,\}\=>>f(z)P(z,1)+>>f(z)P(,1), and extending linearly. Here the integral is a complex path integral along a great circle (or vertical line) from > to > (so, e.g., write , where traces out the path, and consider two real integrals; see any introductory book on complex analysis for more details). The integration pairing is well defined, which means that if we replace ,\}> by an equivalent modular symbols (equivalent modulo the left action of >), then the integral is the same. This follows from the change of variables formulas for integration and the fact that \S(\)> and \(\)>. For example, if , \> and S(\)>, then <\align*> f,g{\,\}\>|f,{g(\),g(\)}\>>||)>)>f(z)>>||>>f(g(z))d*g(z)>>||>>f(z)=\f,{\,\}\,>>>> where in the last step we use that is a weight modular form. <\remark> The integration pairing is related to special values of -functions. The -function attached to a cusp form aq\S(\(N))> is <\equation> L(f,s)=(2\)\(s)>f(i*t)t Note that one can show that >|n>> by switching the order of summation and integration, which is justified using standard estimates on \|> (see, e.g., (S)). For each integer with j\k-1>, we have setting and making the change of variables -i*t> in (), that <\equation*> L(f,j)=i)|(j-1)!>\f,XY{0,\}. The integers as above are called , and when is an eigenform, they have deep conjectural significance. We will discuss tricks to efficiently compute later in this book. <\theorem> [Shokoruv] The pairing \,\\> is nondegenerate when restricted to cuspidal modular symbols: <\equation*> \\,\\:(S(\)\(\))\(\)\. The pairing is also compatible with Hecke operators. Before proving this, we define an action of on (\(N))> and on (\(N))>. The definition is very similar to the one we gave in Section for modular forms of level . For a positive integer , let > be a set of coset representatives for (N)\\> from Lemma . For any =\()> and M(\(N))> set <\equation*> f\|[\]=det(\)(c*z+d)f(\(z)). Also, for (\(N))>, set <\equation*> f\|[\]=det(\)(c+d)f(\(z)). Then for M(\(N))>, <\equation*> T(f)=\R>f\|[\] and for (\(N))>, <\equation*> T(f)=\R>f\|[\]. This agrees with the definition from when . <\remark> If > is an arbitrary finite index subgroup of ()>, then we can define operators >> on (\)> for any > with \=\\=\> and \\> finite. For concreteness we do not do the general case here or in the theorem below, but the proof is exactly the same (see (S)). Finally we prove the promised Hecke compatibility of the pairing. This proof should convince you that the definition of modular symbols is sensible, in that they are ``natural'' expressions to integrate against modular forms. <\theorem> If ,f)\S(\(N))\(\(N))> and (\(N))>, then for any , <\equation*> \T(f),x\=\f,T(x)\. <\proof> We exactly follow (S), and will only prove the theorem when \S(\(N))>, the proof in the general case being the same. Let ,\\

()>, [X,Y]>, and for \()>, set . Let be any positive integer, and let > be a set of coset representatives for (N)\\> from Lemma . We have <\align*> T(f),P{\,\}\>|>>T(f)P(z,1)>>||\R>>>det(\)f(\(z))j(\,z)P(z,1).>>>> Now for each summand corresponding to the \R>, make the change of variables z>. Thus we make change of variables. Also, recall the notation from (), which we will use below. <\align*> T(f),P{\,\}\>|\R>(\)>(\)>det(\)f(u)j(\,\(u))P(\(u),1)d(\(u))>>||\R>(\)>(\)>det(\)f(u)j(|~>,u)det(\)P(|~>(u),1))d*u|j(|~>,u)>>>||\R>(\)>(\)>f(u)j(|~>,u)P(|~>(u),1)d*u>>||\R>(\)>(\)>f(u)\((\.P)(u,1))d*u>>||f,T(P{\,\})\.>>>> The second equality is the trickiest. First, note that (u)=|~>(u)>, since a linear fractional transformation is unchanged by a nonzero rescaling of a matrix that induces it. Thus by the quotient rule, using that |~>> has determinant )>, we see that <\equation*> d(\(u))=)d*u|j(|~>,u)>. The other part of the second equality asserts that <\equation> j(\,\(u))P(\(u),1)=j(|~>,u)det(\)P(|~>(u),1). From the definitions, and again using that (u)=|~>(u)>, we see that <\equation*> j(\,\(u))=)|j(|~>,u)>, which proves that () holds. In the third equality, we use that <\equation*> (\.P)(u,1)=j(|~>,u)P(|~>(u),1). To see this, note that Y>. Using this we see that <\align*> .P)(X,Y)>||~>)(X,Y)>>|||~>,1\-c\+a\Y.>>>> Now substituting for , we see that <\equation*> (\.P)(u,1)=P(|~>(u),1)\(-c*u+a), as required. <\remark> The theorem is true more generally for any > and any operator >>, via the same proof. Suppose that > is finite index subgroup of ()> such that if =0|1>>, then <\equation*> \\\=\. For example, =\(N)> satisfies this condition. There is an involution >> on (\)> given by <\equation> \>(P(X,Y){\,\})=-P(X,-Y){-\,-\}, which we call the . On Manin symbols, >> it is <\equation*> \>[P,(u,v)]=-[P(-X,Y),(-u,v)]. Let (\)> be the eigenspace for >> and (\)> the eigenspace. There is also a map > on modular forms, which is adjoint to >>. <\remark> [WARNING] Notice the sign in front of ,-\}> in (). This sign is missing in , which confused me. Thus the quotient in MAGMA is the quotient where > acts as . (This is a mistake.) We now state the final result about the pairing, which explains how modular symbols and modular forms are related. <\theorem> The pairing \,\\> restricts to give nondegenerate Hecke compatible bilinear pairings <\equation*> (\)\S(\)\(\)\(\)\. In light of the Peterson inner product, the above theorem implies that there is a canonical isomorphism of >-modules <\equation*> (\,)S(\), where > is the anemic Hecke algebra, i.e., the subring of > generated by Hecke operators > with . In fact, one can prove, e.g., using Eichler-Shimura cohomology, that there is a non-canonical isomorphism over the full Hecke algebra <\equation*> (\,)M(\)\(\). In this section we explicitly compute (\(N))> for various and . We represent Manin symbols for (N)> as triples , where

(/N)>, and corresponds to Y,(u,v)]> in the usual notation. <\example> We compute (\(1))>. Because the (\(1))=0>, and (\(1))=E>, we expect to have dimension , and for the Hecke operator > to have eigenvalues (n)>. The Manin symbols are <\equation*> x=(0,0,0),x=(1,0,0),x=(2,0,0). The relation matrix is\ <\verbatim> [ 1, 0, 1, \ \ \ \ \ \ \ \ \ \ \-- S relation 0, 0, 0, \ \ \ \ \ \ \ \ \ \ \-- S relation 2, -2, 2, \ \ \ \ \ \ \ \ \ \-- T relation 1, -1, 1, \ \ \ \ \ \ \ \ \ \-- T relation 2, -2, 2] \ \ \ \ \ \ \ \ \ \-- T relation Note that we don't include all relations, since it is obvious that some are redundant, e.g., and are the same since has order . It's not so clear to me what is going on with relations when 2>, though in this example two of the three relations are redundant. The echelon form of the relation matrix is\ <\verbatim> [1, 0, 1, 0, 1, 0, three zero rows...] This means that we can replace the above complicated list of relations with this simpler list of relations, from which we immediately read off that the second generator > is and =-x>. Thus (\(1))> has dimension , with basis the equivalence class of >. Next we compute the Hecke operator > on (\(1))>. The Heilbronn matrices of determinant from Proposition are\ <\verbatim> [h0=[1, 0, 0, 2], h1=[1, 0, 1, 2], h2=[2, 0, 0, 1], h3=[2, 1, 0, 1]] To compute >, we apply each of these matrices to >, then reduce modulo the relations. We have <\align*> .>|,(0,0)].x>>|.>|,(0,0)]=x>>|.>|,(0,0)]=4x>>|.>|,(0,0)]=x+4x+4x\3x>>>> Summing we see that (x)\9x> in (\(1))>. Notice that +2=\(2)>. Next we compute (\(11))> explicitly. The Manin symbol generators are <\equation*> x=(0,1),x=(1,0),x=(1,1),x=(1,2),x=(1,3),x=(1,4),x=(1,5), <\equation*> x=(1,6),x=(1,7),x=(1,8),x=(1,9),x=(1,10) The relation matrix is\ <\verbatim> 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, \ \ \ \ \ \-- S relation\ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, \ \ \ \ \ \-- S relation 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, \ \ \ \ \ \-- S relation 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, \ \ \ \ \ \-- S relation 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, \ \ \ \ \ \-- S relation 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, \ \ \ \ \ \-- S relation 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, \ \ \ \ \ \-- T relation 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, \ \ \ \ \ \-- T relation 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, \ \ \ \ \ \-- T relation 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0 \ \ \ \ \ \ \-- T relation Many of the -relations are obviously redundant, so we do not include them. The reduced row echelon form of the relation matrix is\ <\verbatim> 1, 1, 0, 0, 0, 0, 0, 0, 0, \ 0, \ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, \ 0, \ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, \ 0, -1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, \ 1, -1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, \ 1, \ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, \ 0, \ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, \ 0, \ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, \ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, \ 0, \ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, \ 0, \ 0, 0 From this we see that every symbol is equivalent to a combination of =(1,0)>, =(1,8)>, and =(1,9)>. For example, T*o*c*o*m*p*u*t*e>T2t*o>xxx [h0=[1, 0, 0, 2], h1=[1, 0, 1, 2], h2=[2, 0, 0, 1], h3=[2, 1, 0, 1]] A*p*p*l*y*i*n*gTx=(1,0)\(1,0)+(1,0)+(2,0)+(2,1)=3x+x\=3x-x.>Tx=(1,8)\x+x+x+x\-2x>Tx=(1,9)\x+x+x+x\-2x.>T \ \ [ 3, \ 0, \ 0; \ \ \ \ 0, -2, \ 0; \ \ \ -1, \ 0, -2] T*h*i*s*h*a*s*c*h*a*r*a*c*t*e*r*i*s*t*i*c*p*o*l*y*n*o*m*i*a*l.>(x-3)2x+2E=X(11)a = -2 = 2+1 - #E() W*e*n*o*w*s*k*e*t*c*h*s*o*m*e*o*f*t*h*e*w*a*y*s*i*n*w*h*i*c*h*w*e*w*i*l*l*a*p*p*l*y*t*h*e*m*o*d*u*l*a*r*s*y*m*b*o*l*s*a*l*g*o*r*i*t*h*m*s*o*f*t*h*i*s*c*h*a*p*t*e*r*l*a*t*e*r*i*n*t*h*i*s*b*o*o*k. C*u*s*p*i*d*a*l*m*o*d*u*l*a*r*s*y*m*b*o*l*s*a*r*e*i*n*H*e*c*k*e-e*q*u*i*v*a*r*i*a*n*t*d*u*a*l*i*t*y*w*i*t*h*c*u*s*p*i*d*a*l*m*o*d*u*l*a*r*f*o*r*m*s,a*n*d*a*s*s*u*c*h*w*e*c*a*n*c*o*m*p*u*t*e*m*o*d*u*l*a*r*f*o*r*m*s*b*y*c*o*m*p*u*t*i*n*g*s*y*s*t*e*m*s*o*f*e*i*g*e*n*v*a*l*u*e*s*f*o*r*t*h*e*H*e*c*k*e*o*p*e*r*a*t*o*r*s*a*c*t*i*n*g*o*n*m*o*d*u*l*a*r*s*y*m*b*o*l*s.B*y*t*h*e*A*t*k*i*n-L*e*h*n*e*r-L*i*t*h*e*o*r*y*o*f*n*e*w*f*o*r*m*s(s*e*e,e.g.,),w*e*c*a*n*c*o*n*s*t*r*u*c*tS(N,)Nk\ 2f*o*r*m*o*r*e*d*e*t*a*i*l*s.> O*n*c*e*w*e*c*a*n*c*o*m*p*u*t*e*s*p*a*c*e*s*o*f*m*o*d*u*l*a*r*s*y*m*b*o*l*s,w*e*m*o*v*e*t*o*c*o*m*p*u*t*i*n*g*t*h*e*c*o*r*r*e*s*p*o*n*d*i*n*g*m*o*d*u*l*a*r*f*o*r*m*s.I*n*S*e*c*t*i*o*n,w*e*d*e*f*i*n*e*i*n*c*l*u*s*i*o*n*a*n*d*t*r*a*c*e*m*a*p*s*f*r*o*m*m*o*d*u*l*a*r*s*y*m*b*o*l*s*o*f*o*n*e*l*e*v*e*lNNVa*c*t*s*a*s>+1 a q*n*e*w*f*o*r*m*s(n*o*r*m*a*l*i*z*e*d*e*i*g*e*n*f*o*r*m*s)i*n>S(N,)Nk\ 2 I*n*C*h*a*p*t*e*r,w*e*c*o*m*p*u*t*e*w*i*t*h*t*h*e*p*e*r*i*o*d*m*a*p*p*i*n*g*f*r*o*m*m*o*d*u*l*a*r*s*y*m*b*o*l*s*t*of \ S(N,)k=2,=1f).I*n*g*e*n*e*r*a*l,c*o*m*p*u*t*a*t*i*o*n*o*f*t*h*i*s*m*a*p*i*s*i*m*p*o*r*t*a*n*t*w*h*e*n*f*i*n*d*i*n*g*e*q*u*a*t*i*o*n*s*f*o*r*m*o*d*u*l*a*r>LL(f,s) M*o*d*u*l*a*r*s*y*m*b*o*l*s*w*e*r*e*i*n*t*r*o*d*u*c*e*d*b*y*B*i*r*c*hi*n*c*o*n*n*e*c*t*i*o*n*w*i*t*h*c*o*m*p*u*t*a*t*i*o*n*s*i*n*s*u*p*p*o*r*t*o*f*t*h*e*B*i*r*c*h*a*n*d*S*w*i*n*n*e*r*t*o*n-D*y*e*r*c*o*n*j*e*c*t*u*r*e.M*a*n*i*nt*h*e*n*m*a*d*e*a*s*y*s*t*e*m*a*t*i*c*s*t*u*d*y*o*f*w*e*i*g*h*t2Li*n*t*h*e*t*i*t*l*e*o*f*M*a*n*i*ns*p*a*p*e*r*m*e*a*n*s``c*u*s*p*s).M*e*r*e*ls*p*a*p*e*rb*u*i*l*d*s*o*n*w*o*r*k*o*f’o*k*u*r*o*v(m*a*i*n*l*y),w*h*i*c*h*d*e*v*e*l*o*p*e*d*a*h*i*g*h*e*r-w*e*i*g*h*t*g*e*n*e*r*a*l*i*z*a*t*i*o*n*o*f*M*a*n*i*ns*w*o*r*k*p*a*r*t*l*y*t*o*u*n*d*e*r*s*t*a*n*d*r*a*t*i*o*n*a*l*i*t*y*p*r*o*p*e*r*t*i*e*s*o*f*s*p*e*c*i*a*l*v*a*l*u*e*s*o*f*m*o*d*u*l*a*r>Ls*b*o*o*kd*i*s*c*u*s*s*e*s*i*n*d*e*t*a*i*l*h*o*w*t*o*c*o*m*p*u*t*e*t*h*e*s*p*a*c*e*o*f*w*e*i*g*h*t>2\(N)d*i*s*c*u*s*s*e*s*t*h*e>\(N) T*h*e*r*e*h*a*v*e*b*e*e*n*s*e*v*e*r*a*l*r*e*c*e*n*t*P*h.D.t*h*e*s*i*s*a*b*o*u*t*m*o*d*u*l*a*r*s*y*m*b*o*l*s.B*a*s*m*a*j*is*t*h*e*s*i*s,w*h*i*c*h*i*s*i*n*G*e*r*m*a*n,c*o*n*t*a*i*n*s*a*t*r*i*c*k*s*t*o*e*f*f*i*c*i*e*n*t*l*y*c*o*m*p*u*t*e*H*e*c*k*e*o*p*e*r*a*t*o*r*sTps*P*h.D.t*h*e*s*i*sc*o*n*t*a*i*n*s*t*w*o*c*h*a*p*t*e*r*s*a*b*o*u*t*h*i*g*h*e*r-w*e*i*g*h*t*m*o*d*u*l*a*r*s*y*m*b*o*l*s,a*n*d*a*n*a*p*p*l*i*c*a*t*i*o*n*t*o*v*i*s*i*b*i*l*i*t*y*o*f*S*h*a*f*a*r*e*v*i*c*h-T*a*t*e*g*r*o*u*p*s(s*e*e*a*l*s*o).D*i*d*e*r*o*ts*t*h*e*s*i*si*s*a*b*o*u*t*a*n*a*t*t*e*m*p*t*t*o*s*t*u*d*y*a*n*a*n*a*l*o*g*u*e*o*f*m*o*d*u*l*a*r*s*y*m*b*o*l*s*f*o*r*w*e*i*g*h*t>1s*t*h*e*s*i*sd*i*s*c*u*s*s*e*s*m*o*d*u*l*a*r*s*y*m*b*o*l*s*f*o*r*q*u*a*d*r*a*t*i*c*i*m*a*g*i*n*a*r*y*f*i*e*l*d*s*i*n*t*h*e*c*o*n*t*e*x*t*o*f>p,w*h*i*c*h*d*i*s*c*u*s*s*e*s*c*o*m*p*u*t*a*t*i*o*n*w*i*t*h*o*f*w*e*i*g*h*t>2 T*h*e*r*e*a*r*e*a*n*a*l*o*g*u*e*s*f*o*r*m*o*d*u*l*a*r*s*y*m*b*o*l*s*f*o*r*g*r*o*u*p*s*b*e*s*i*d*e*s*f*i*n*i*t*e-i*n*d*e*x*s*u*b*g*r*o*u*p*s*o*f()(H*i*l*b*e*r*t*m*o*d*u*l*a*r*f*o*r*m*s*a*r*e*l*i*k*e*c*l*a*s*s*i*c*a*l*m*o*d*u*l*a*r*f*o*r*m*s,b*u*t*a*r*e*f*u*n*c*t*i*o*n*s*o*n*a*p*r*o*d*u*c*t*o*f*c*o*p*i*e*s*o*f>()*a*w*a*r*e*o*f*a*n*y*a*n*a*l*o*g*u*e*o*f*m*o*d*u*l*a*r*s*y*m*b*o*l*s*f*o*r*S*i*e*g*e*l*m*o*d*u*l*a*r*f*o*r*m*s(t*h*e*s*e*a*r*e*l*i*k*e*c*l*a*s*s*i*c*a*l*m*o*d*u*l*a*r*f*o*r*m*s,e*x*c*e*p*t*t*h*e*u*p*p*e*r*h*a*l*f*p*l*a*n*e*i*s*r*e*p*l*a*c*e*d*b*y*a*s*p*a*c*e*o*f*m*a*t*r*i*c*e*s).> G*l*e*n*n*S*t*e*v*e*n*s(a*n*d*r*e*c*e*n*t*l*y*R*o*b*e*r*t*P*o*l*l*a*c*k*a*n*d*H*e*n*r*i*D*a*r*m*o*n,s*e*e)h*a*s*b*e*e*n*w*o*r*k*i*n*g*f*o*r*m*a*n*y*y*e*a*r*s*t*o*d*e*v*e*l*o*p*a*n*a*n*a*l*o*g*u*e*o*f*m*o*d*u*l*a*r*s*y*m*b*o*l*s*i*n*a*r*i*g*i*d*a*n*a*l*y*t*i*c*c*o*n*t*e*x*t,w*h*i*c*h*s*h*o*u*l*d*b*e*v*e*r*y*h*e*l*p*f*u*l*f*o*r*q*u*e*s*t*i*o*n*s*a*b*o*u*t*c*o*m*p*u*t*i*n*g*w*i*t*h*o*v*e*r*c*o*n*v*e*r*g*e*n*tppL G*a*b*o*r*W*e*i*s*e*a*n*d*B*a*s*E*d*i*x*h*o*v*e*n*h*a*v*e*b*e*e*n*w*o*r*k*i*n*g*o*n*t*h*e*o*r*y*a*b*o*u*t*m*o*dp12 F*i*n*a*l*l*y*w*e*m*e*n*t*i*o*n*t*h*a*t*M*a*z*u*r*u*s*e*s*t*h*e*t*e*r*m``m*o*d*u*l*a*r*s*y*m*b*o*ls*l*i*g*h*t*l*y*d*i*f*f*e*r*e*n*t*l*y*i*n*m*a*n*y*o*f*h*i*s*p*a*p*e*r*s*t*o*m*e*a*n*e*s*s*e*n*t*i*a*l*l*y*w*h*a*t*w*e*c*a*l*l*t*h*e*i*n*t*e*g*r*a*l*p*e*r*i*o*d*m*a*p*p*i*n*g(s*e*e*S*e*c*t*i*o*n).T*h*i*s*i*s*a*d*u*a*l*n*o*t*i*o*n,w*h*i*c*h*a*t*t*a*c*h*e*s*a``m*o*d*u*l*a*r*s*y*m*b*o*lt*o*a*m*o*d*u*l*a*r*f*o*r*m*o*r*e*l*l*i*p*t*i*c*c*u*r*v*e,a*n*d*i*s*r*e*a*l*l*y*j*u*s*t*a*n*o*v*e*r*l*o*a*d*i*n*g*o*f*t*h*e*t*e*r*m*i*n*o*l*o*g*y.S*e*ef*o*r*a*n*e*x*t*e*n*s*i*v*e*d*i*s*c*u*s*s*i*o*n*o*f*m*o*d*u*l*a*r*s*y*m*b*o*l*s*f*r*o*m*t*h*i*s*p*o*i*n*t*o*f*v*i*e*w,w*h*e*r*e*t*h*e*y*a*r*e*u*s*e*d*t*o*c*o*n*s*t*r*u*c*tpL <\exercises> C*o*m*p*u*t*e(\(3))T(\(3))2T(x-3)(x+3) P*r*o*v*e*t*h*a*t*t*h*e*p*a*i*r*i*n*gi*s*w*e*l*l*d*e*f*i*n*e*d. <\enumerate> S*h*o*w*t*h*a*t*i*f\ = \ \ \ = \\=\(N)\=\(N) (\)G*i*v*e*a*n*e*x*a*m*p*l*e*o*f*a*f*i*n*i*t*e*i*n*d*e*x*s*u*b*g*r*o*u*p\\ \ \ \ \. -expansions of Newforms> i*s*a*c*u*s*p*f*o*r*mfS(N,)Tf = q + \.> NaS(N,).> (f)> in polynomial time when corresponds to an elliptic curve.> Kf\ M(\,)\a(f) 0>n\ ():\>f 0>.> \[():\].>(\) \ (M(\))Tn\ r.> S(N,)M(N,)\ .> -Functions>S(N,)j1\ j \ k-1L(f,j).> --m*o*d*e*l*s*f*o*r*m*o*d*u*l*a*r*c*u*r*v*e*s --B*a*k*e*r-P*o*o*n*e*n-G*o*n*z*a*l*e*z for arbitrary .>S(\)\=\(N)\(N)L(A,1)/\>.> > s*C*o*n*j*e*c*t*u*r*e> S(N,)\\>i*s*i*r*r*e*d*u*c*i*b*l*e.> \\>.> \\>.> >S(N,)>fg\ S(N,).> M*A*N*I*N*i*s*a*p*a*c*k*a*g*e*f*o*r*c*o*m*p*u*t*i*n*g*w*i*t*h*m*o*d*u*l*a*r*f*o*r*m*s*t*h*a*t*t*h*e*a*u*t*h*o*r*i*s*d*e*v*e*l*o*p*i*n*g*u*s*i*n*g*t*h*e*c*o*m*p*u*t*e*r*l*a*n*g*u*a*g*e*s*P*y*t*h*o*n*a*n*d*C++.T*h*i*s*c*h*a*p*t*e*r*i*s*a*b*o*u*t*t*h*e*s*t*r*u*c*t*u*r*e*a*n*d*i*m*p*l*e*m*e*n*t*a*t*i*o*n*o*f*M*A*N*I*N,a*n*d*i*t*s*r*e*l*a*t*i*o*n*w*i*t*h*t*h*e*a*l*g*o*r*i*t*h*m*s*d*e*s*c*r*i*b*e*d*e*l*s*e*w*h*e*r*e*i*n*t*h*i*s*b*o*o*k. M*A*N*I*N*i*s*a*n*d*w*i*l*l*r*e*m*a*i*n*f*r*e*e*l*y*a*v*a*i*l*a*b*l*e,a*n*d*a*l*l*i*t*s*c*o*m*p*o*n*e*n*t*s*a*r*e*o*p*e*n*s*o*u*r*c*e.I*ts*i*n*i*t*i*a*l*p*u*r*p*o*s*e*i*s*t*o*p*r*o*v*i*d*e*a*p*a*c*k*a*g*e*f*o*r*d*o*i*n*g*c*o*m*p*u*t*a*t*i*o*n*s*w*i*t*h*m*o*d*u*l*a*r*f*o*r*m*s*w*h*o*s*e*s*o*u*r*c*e*c*o*d*e*i*s*e*a*s*y*t*o*r*e*a*d,m*o*d*i*f*y,a*n*d*u*n*d*e*r*s*t*a*n*d.I*t*i*s*u*s*a*b*l*e*f*r*o*m*P*y*t*h*o*n,w*h*i*c*h*i*s*a*n*e*x*t*r*e*m*e*l*y*m*a*t*u*r*e*a*n*d*w*e*l*l-d*e*s*i*g*n*e*d*m*o*d*e*r*n*l*a*n*g*u*a*g*e.B*e*i*n*g*c*o*m*p*l*e*t*e*l*y*f*r*e*e*a*n*d*o*p*e*n*s*o*u*r*c*e*m*a*k*e*s*i*t*m*o*r*e*s*u*i*t*a*b*l*e*f*o*r*c*i*t*a*t*i*o*n*i*n*r*e*s*e*a*r*c*h*p*a*p*e*r*s.S*p*e*e*d*i*s*i*m*p*o*r*t*a*n*t*b*u*t*i*s*o*f*s*e*c*o*n*d*a*r*y*i*m*p*o*r*t*a*n*c*e(t*h*e*a*u*t*h*o*rs*M*A*G*M*A*p*a*c*k*a*g*e*s*a*r*e*m*u*c*h*f*a*s*t*e*r*i*n*m*a*n*y*c*a*s*e*s). W*e*b*e*g*i*n*w*i*t*h*a*s*a*m*p*l*e*M*A*N*I*N*s*e*s*s*i*o*n. <\verbatim> \\\ M = ModularSymbols(11) \\\ M.basis() [(1,0), (1,8), (1,9)] \\\ t2 = M.hecke_operator(2);\ \\\ t2 \ \ [ 3, \ 0, \ 0; \ \ \ \ 0, -2, \ 0; \ \ \ -1, \ 0, -2] \\\ charpoly(t2) x^3 + x^2 - 8*x - 12 \\\ t2.charpoly() \ \ \ \ \ \ \ \ \ \ \ \ # call in more ``object-oriented'' way. x^3 + x^2 - 8*x - 12 s*m*w*r*a*n*k> <\with|font-size|0.84> A*p*p*e*n*d*i*x:G*N*U*F*r*e*e*D*o*c*u*m*e*n*t*a*t*i*o*n*L*i*c*e*n*s*e> <\center> V*e*r*s*i*o*n1.2,N*o*v*e*m*b*e*r2002 C*o*p*y*r*i*g*h*t2000,2001,2002F*r*e*e*S*o*f*t*w*a*r*e*F*o*u*n*d*a*t*i*o*n,I*n*c. 59T*e*m*p*l*e*P*l*a*c*e,S*u*i*t*e330,B*o*s*t*o*n,M*A02111-1307U*S*A E*v*e*r*y*o*n*e*i*s*p*e*r*m*i*t*t*e*d*t*o*c*o*p*y*a*n*d*d*i*s*t*r*i*b*u*t*e*v*e*r*b*a*t*i*m*c*o*p*i*e*s*o*f*t*h*i*s*l*i*c*e*n*s*e*d*o*c*u*m*e*n*t,b*u*t*c*h*a*n*g*i*n*g*i*t*i*s*n*o*t*a*l*l*o*w*e*d. <\center> <\with|font-series|bold> T*h*e*p*u*r*p*o*s*e*o*f*t*h*i*s*L*i*c*e*n*s*e*i*s*t*o*m*a*k*e*a*m*a*n*u*a*l,t*e*x*t*b*o*o*k,o*r*o*t*h*e*r*f*u*n*c*t*i*o*n*a*l*a*n*d*u*s*e*f*u*l*d*o*c*u*m*e*n*t``f*r*e*ei*n*t*h*e*s*e*n*s*e*o*f*f*r*e*e*d*o*m:t*o*a*s*s*u*r*e*e*v*e*r*y*o*n*e*t*h*e*e*f*f*e*c*t*i*v*e*f*r*e*e*d*o*m*t*o*c*o*p*y*a*n*d*r*e*d*i*s*t*r*i*b*u*t*e*i*t,w*i*t*h*o*r*w*i*t*h*o*u*t*m*o*d*i*f*y*i*n*g*i*t,e*i*t*h*e*r*c*o*m*m*e*r*c*i*a*l*l*y*o*r*n*o*n*c*o*m*m*e*r*c*i*a*l*l*y.S*e*c*o*n*d*a*r*i*l*y,t*h*i*s*L*i*c*e*n*s*e*p*r*e*s*e*r*v*e*s*f*o*r*t*h*e*a*u*t*h*o*r*a*n*d*p*u*b*l*i*s*h*e*r*a*w*a*y*t*o*g*e*t*c*r*e*d*i*t*f*o*r*t*h*e*i*r*w*o*r*k,w*h*i*l*e*n*o*t*b*e*i*n*g*c*o*n*s*i*d*e*r*e*d*r*e*s*p*o*n*s*i*b*l*e*f*o*r*m*o*d*i*f*i*c*a*t*i*o*n*s*m*a*d*e*b*y*o*t*h*e*r*s. T*h*i*s*L*i*c*e*n*s*e*i*s*a*k*i*n*d*o*f``c*o*p*y*l*e*f*t",w*h*i*c*h*m*e*a*n*s*t*h*a*t*d*e*r*i*v*a*t*i*v*e*w*o*r*k*s*o*f*t*h*e*d*o*c*u*m*e*n*t*m*u*s*t*t*h*e*m*s*e*l*v*e*s*b*e*f*r*e*e*i*n*t*h*e*s*a*m*e*s*e*n*s*e.I*t*c*o*m*p*l*e*m*e*n*t*s*t*h*e*G*N*U*G*e*n*e*r*a*l*P*u*b*l*i*c*L*i*c*e*n*s*e,w*h*i*c*h*i*s*a*c*o*p*y*l*e*f*t*l*i*c*e*n*s*e*d*e*s*i*g*n*e*d*f*o*r*f*r*e*e*s*o*f*t*w*a*r*e. W*e*h*a*v*e*d*e*s*i*g*n*e*d*t*h*i*s*L*i*c*e*n*s*e*i*n*o*r*d*e*r*t*o*u*s*e*i*t*f*o*r*m*a*n*u*a*l*s*f*o*r*f*r*e*e*s*o*f*t*w*a*r*e,b*e*c*a*u*s*e*f*r*e*e*s*o*f*t*w*a*r*e*n*e*e*d*s*f*r*e*e*d*o*c*u*m*e*n*t*a*t*i*o*n:a*f*r*e*e*p*r*o*g*r*a*m*s*h*o*u*l*d*c*o*m*e*w*i*t*h*m*a*n*u*a*l*s*p*r*o*v*i*d*i*n*g*t*h*e*s*a*m*e*f*r*e*e*d*o*m*s*t*h*a*t*t*h*e*s*o*f*t*w*a*r*e*d*o*e*s.B*u*t*t*h*i*s*L*i*c*e*n*s*e*i*s*n*o*t*l*i*m*i*t*e*d*t*o*s*o*f*t*w*a*r*e*m*a*n*u*a*l*s;i*t*c*a*n*b*e*u*s*e*d*f*o*r*a*n*y*t*e*x*t*u*a*l*w*o*r*k,r*e*g*a*r*d*l*e*s*s*o*f*s*u*b*j*e*c*t*m*a*t*t*e*r*o*r*w*h*e*t*h*e*r*i*t*i*s*p*u*b*l*i*s*h*e*d*a*s*a*p*r*i*n*t*e*d*b*o*o*k.W*e*r*e*c*o*m*m*e*n*d*t*h*i*s*L*i*c*e*n*s*e*p*r*i*n*c*i*p*a*l*l*y*f*o*r*w*o*r*k*s*w*h*o*s*e*p*u*r*p*o*s*e*i*s*i*n*s*t*r*u*c*t*i*o*n*o*r*r*e*f*e*r*e*n*c*e. <\center> <\with|font-size|1.41> T*h*i*s*L*i*c*e*n*s*e*a*p*p*l*i*e*s*t*o*a*n*y*m*a*n*u*a*l*o*r*o*t*h*e*r*w*o*r*k,i*n*a*n*y*m*e*d*i*u*m,t*h*a*t*c*o*n*t*a*i*n*s*a*n*o*t*i*c*e*p*l*a*c*e*d*b*y*t*h*e*c*o*p*y*r*i*g*h*t*h*o*l*d*e*r*s*a*y*i*n*g*i*t*c*a*n*b*e*d*i*s*t*r*i*b*u*t*e*d*u*n*d*e*r*t*h*e*t*e*r*m*s*o*f*t*h*i*s*L*i*c*e*n*s*e.S*u*c*h*a*n*o*t*i*c*e*g*r*a*n*t*s*a*w*o*r*l*d-w*i*d*e,r*o*y*a*l*t*y-f*r*e*e*l*i*c*e*n*s*e,u*n*l*i*m*i*t*e*d*i*n*d*u*r*a*t*i*o*n,t*o*u*s*e*t*h*a*t*w*o*r*k*u*n*d*e*r*t*h*e*c*o*n*d*i*t*i*o*n*s*s*t*a*t*e*d*h*e*r*e*i*n.T*h*e>,b*e*l*o*w,r*e*f*e*r*s*t*o*a*n*y*s*u*c*h*m*a*n*u*a*l*o*r*w*o*r*k.A*n*y*m*e*m*b*e*r*o*f*t*h*e*p*u*b*l*i*c*i*s*a*l*i*c*e*n*s*e*e,a*n*d*i*s*a*d*d*r*e*s*s*e*d*a*s>.Y*o*u*a*c*c*e*p*t*t*h*e*l*i*c*e*n*s*e*i*f*y*o*u*c*o*p*y,m*o*d*i*f*y*o*r*d*i*s*t*r*i*b*u*t*e*t*h*e*w*o*r*k*i*n*a*w*a*y*r*e*q*u*i*r*i*n*g*p*e*r*m*i*s*s*i*o*n*u*n*d*e*r*c*o*p*y*r*i*g*h*t*l*a*w. A>o*f*t*h*e*D*o*c*u*m*e*n*t*m*e*a*n*s*a*n*y*w*o*r*k*c*o*n*t*a*i*n*i*n*g*t*h*e*D*o*c*u*m*e*n*t*o*r*a*p*o*r*t*i*o*n*o*f*i*t,e*i*t*h*e*r*c*o*p*i*e*d*v*e*r*b*a*t*i*m,o*r*w*i*t*h*m*o*d*i*f*i*c*a*t*i*o*n*s*a*n*d/o*r*t*r*a*n*s*l*a*t*e*d*i*n*t*o*a*n*o*t*h*e*r*l*a*n*g*u*a*g*e. A>i*s*a*n*a*m*e*d*a*p*p*e*n*d*i*x*o*r*a*f*r*o*n*t-m*a*t*t*e*r*s*e*c*t*i*o*n*o*f*t*h*e*D*o*c*u*m*e*n*t*t*h*a*t*d*e*a*l*s*e*x*c*l*u*s*i*v*e*l*y*w*i*t*h*t*h*e*r*e*l*a*t*i*o*n*s*h*i*p*o*f*t*h*e*p*u*b*l*i*s*h*e*r*s*o*r*a*u*t*h*o*r*s*o*f*t*h*e*D*o*c*u*m*e*n*t*t*o*t*h*e*D*o*c*u*m*e*n*ts*o*v*e*r*a*l*l*s*u*b*j*e*c*t(o*r*t*o*r*e*l*a*t*e*d*m*a*t*t*e*r*s)a*n*d*c*o*n*t*a*i*n*s*n*o*t*h*i*n*g*t*h*a*t*c*o*u*l*d*f*a*l*l*d*i*r*e*c*t*l*y*w*i*t*h*i*n*t*h*a*t*o*v*e*r*a*l*l*s*u*b*j*e*c*t.(T*h*u*s,i*f*t*h*e*D*o*c*u*m*e*n*t*i*s*i*n*p*a*r*t*a*t*e*x*t*b*o*o*k*o*f*m*a*t*h*e*m*a*t*i*c*s,a*S*e*c*o*n*d*a*r*y*S*e*c*t*i*o*n*m*a*y*n*o*t*e*x*p*l*a*i*n*a*n*y*m*a*t*h*e*m*a*t*i*c*s.)T*h*e*r*e*l*a*t*i*o*n*s*h*i*p*c*o*u*l*d*b*e*a*m*a*t*t*e*r*o*f*h*i*s*t*o*r*i*c*a*l*c*o*n*n*e*c*t*i*o*n*w*i*t*h*t*h*e*s*u*b*j*e*c*t*o*r*w*i*t*h*r*e*l*a*t*e*d*m*a*t*t*e*r*s,o*r*o*f*l*e*g*a*l,c*o*m*m*e*r*c*i*a*l,p*h*i*l*o*s*o*p*h*i*c*a*l,e*t*h*i*c*a*l*o*r*p*o*l*i*t*i*c*a*l*p*o*s*i*t*i*o*n*r*e*g*a*r*d*i*n*g*t*h*e*m. T*h*e>a*r*e*c*e*r*t*a*i*n*S*e*c*o*n*d*a*r*y*S*e*c*t*i*o*n*s*w*h*o*s*e*t*i*t*l*e*s*a*r*e*d*e*s*i*g*n*a*t*e*d,a*s*b*e*i*n*g*t*h*o*s*e*o*f*I*n*v*a*r*i*a*n*t*S*e*c*t*i*o*n*s,i*n*t*h*e*n*o*t*i*c*e*t*h*a*t*s*a*y*s*t*h*a*t*t*h*e*D*o*c*u*m*e*n*t*i*s*r*e*l*e*a*s*e*d*u*n*d*e*r*t*h*i*s*L*i*c*e*n*s*e.I*f*a*s*e*c*t*i*o*n*d*o*e*s*n*o*t*f*i*t*t*h*e*a*b*o*v*e*d*e*f*i*n*i*t*i*o*n*o*f*S*e*c*o*n*d*a*r*y*t*h*e*n*i*t*i*s*n*o*t*a*l*l*o*w*e*d*t*o*b*e*d*e*s*i*g*n*a*t*e*d*a*s*I*n*v*a*r*i*a*n*t.T*h*e*D*o*c*u*m*e*n*t*m*a*y*c*o*n*t*a*i*n*z*e*r*o*I*n*v*a*r*i*a*n*t*S*e*c*t*i*o*n*s.I*f*t*h*e*D*o*c*u*m*e*n*t*d*o*e*s*n*o*t*i*d*e*n*t*i*f*y*a*n*y*I*n*v*a*r*i*a*n*t*S*e*c*t*i*o*n*s*t*h*e*n*t*h*e*r*e*a*r*e*n*o*n*e. T*h*e>a*r*e*c*e*r*t*a*i*n*s*h*o*r*t*p*a*s*s*a*g*e*s*o*f*t*e*x*t*t*h*a*t*a*r*e*l*i*s*t*e*d,a*s*F*r*o*n*t-C*o*v*e*r*T*e*x*t*s*o*r*B*a*c*k-C*o*v*e*r*T*e*x*t*s,i*n*t*h*e*n*o*t*i*c*e*t*h*a*t*s*a*y*s*t*h*a*t*t*h*e*D*o*c*u*m*e*n*t*i*s*r*e*l*e*a*s*e*d*u*n*d*e*r*t*h*i*s*L*i*c*e*n*s*e.A*F*r*o*n*t-C*o*v*e*r*T*e*x*t*m*a*y*b*e*a*t*m*o*s*t5w*o*r*d*s,a*n*d*a*B*a*c*k-C*o*v*e*r*T*e*x*t*m*a*y*b*e*a*t*m*o*s*t25w*o*r*d*s. A>c*o*p*y*o*f*t*h*e*D*o*c*u*m*e*n*t*m*e*a*n*s*a*m*a*c*h*i*n*e-r*e*a*d*a*b*l*e*c*o*p*y,r*e*p*r*e*s*e*n*t*e*d*i*n*a*f*o*r*m*a*t*w*h*o*s*e*s*p*e*c*i*f*i*c*a*t*i*o*n*i*s*a*v*a*i*l*a*b*l*e*t*o*t*h*e*g*e*n*e*r*a*l*p*u*b*l*i*c,t*h*a*t*i*s*s*u*i*t*a*b*l*e*f*o*r*r*e*v*i*s*i*n*g*t*h*e*d*o*c*u*m*e*n*t*s*t*r*a*i*g*h*t*f*o*r*w*a*r*d*l*y*w*i*t*h*g*e*n*e*r*i*c*t*e*x*t*e*d*i*t*o*r*s*o*r(f*o*r*i*m*a*g*e*s*c*o*m*p*o*s*e*d*o*f*p*i*x*e*l*s)g*e*n*e*r*i*c*p*a*i*n*t*p*r*o*g*r*a*m*s*o*r(f*o*r*d*r*a*w*i*n*g*s)s*o*m*e*w*i*d*e*l*y*a*v*a*i*l*a*b*l*e*v*d*r*a*w*i*n*g*e*d*i*t*o*r,a*n*d*t*h*a*t*i*s*s*u*i*t*a*b*l*e*f*o*r*i*n*p*u*t*t*o*t*e*x*t*f*o*r*m*a*t*t*e*r*s*o*r*f*o*r*a*u*t*o*m*a*t*i*c*t*r*a*n*s*l*a*t*i*o*n*t*o*a*v*a*r*i*e*t*y*o*f*f*o*r*m*a*t*s*s*u*i*t*a*b*l*e*f*o*r*i*n*p*u*t*t*o*t*e*x*t*f*o*r*m*a*t*t*e*r*s.A*c*o*p*y*m*a*d*e*i*n*a*n*o*t*h*e*r*w*i*s*e*T*r*a*n*s*p*a*r*e*n*t*f*i*l*e*f*o*r*m*a*t*w*h*o*s*e*m*a*r*k*u*p,o*r*a*b*s*e*n*c*e*o*f*m*a*r*k*u*p,h*a*s*b*e*e*n*a*r*r*a*n*g*e*d*t*o*t*h*w*a*r*t*o*r*d*i*s*c*o*u*r*a*g*e*s*u*b*s*e*q*u*e*n*t*m*o*d*i*f*i*c*a*t*i*o*n*b*y*r*e*a*d*e*r*s*i*s*n*o*t*T*r*a*n*s*p*a*r*e*n*t.A*n*i*m*a*g*e*f*o*r*m*a*t*i*s*n*o*t*T*r*a*n*s*p*a*r*e*n*t*i*f*u*s*e*d*f*o*r*a*n*y*s*u*b*s*t*a*n*t*i*a*l*a*m*o*u*n*t*o*f*t*e*x*t.A*c*o*p*y*t*h*a*t*i*s*n*o*t``T*r*a*n*s*p*a*r*e*n*ti*s*c*a*l*l*e*d>. E*x*a*m*p*l*e*s*o*f*s*u*i*t*a*b*l*e*f*o*r*m*a*t*s*f*o*r*T*r*a*n*s*p*a*r*e*n*t*c*o*p*i*e*s*i*n*c*l*u*d*e*p*l*a*i*n*A*S*C*I*I*w*i*t*h*o*u*t*m*a*r*k*u*p,T*e*x*i*n*f*o*i*n*p*u*t*f*o*r*m*a*t,L*a*T*e*X*i*n*p*u*t*f*o*r*m*a*t,S*G*M*L*o*r*X*M*L*u*s*i*n*g*a*p*u*b*l*i*c*l*y*a*v*a*i*l*a*b*l*e*D*T*D,a*n*d*s*t*a*n*d*a*r*d-c*o*n*f*o*r*m*i*n*g*s*i*m*p*l*e*H*T*M*L,P*o*s*t*S*c*r*i*p*t*o*r*P*D*F*d*e*s*i*g*n*e*d*f*o*r*h*u*m*a*n*m*o*d*i*f*i*c*a*t*i*o*n.E*x*a*m*p*l*e*s*o*f*t*r*a*n*s*p*a*r*e*n*t*i*m*a*g*e*f*o*r*m*a*t*s*i*n*c*l*u*d*e*P*N*G,X*C*F*a*n*d*J*P*G.O*p*a*q*u*e*f*o*r*m*a*t*s*i*n*c*l*u*d*e*p*r*o*p*r*i*e*t*a*r*y*f*o*r*m*a*t*s*t*h*a*t*c*a*n*b*e*r*e*a*d*a*n*d*e*d*i*t*e*d*o*n*l*y*b*y*p*r*o*p*r*i*e*t*a*r*y*w*o*r*d*p*r*o*c*e*s*s*o*r*s,S*G*M*L*o*r*X*M*L*f*o*r*w*h*i*c*h*t*h*e*D*T*D*a*n*d/o*r*p*r*o*c*e*s*s*i*n*g*t*o*o*l*s*a*r*e*n*o*t*g*e*n*e*r*a*l*l*y*a*v*a*i*l*a*b*l*e,a*n*d*t*h*e*m*a*c*h*i*n*e-g*e*n*e*r*a*t*e*d*H*T*M*L,P*o*s*t*S*c*r*i*p*t*o*r*P*D*F*p*r*o*d*u*c*e*d*b*y*s*o*m*e*w*o*r*d*p*r*o*c*e*s*s*o*r*s*f*o*r*o*u*t*p*u*t*p*u*r*p*o*s*e*s*o*n*l*y. T*h*e>m*e*a*n*s,f*o*r*a*p*r*i*n*t*e*d*b*o*o*k,t*h*e*t*i*t*l*e*p*a*g*e*i*t*s*e*l*f,p*l*u*s*s*u*c*h*f*o*l*l*o*w*i*n*g*p*a*g*e*s*a*s*a*r*e*n*e*e*d*e*d*t*o*h*o*l*d,l*e*g*i*b*l*y,t*h*e*m*a*t*e*r*i*a*l*t*h*i*s*L*i*c*e*n*s*e*r*e*q*u*i*r*e*s*t*o*a*p*p*e*a*r*i*n*t*h*e*t*i*t*l*e*p*a*g*e.F*o*r*w*o*r*k*s*i*n*f*o*r*m*a*t*s*w*h*i*c*h*d*o*n*o*t*h*a*v*e*a*n*y*t*i*t*l*e*p*a*g*e*a*s*s*u*c*h,``T*i*t*l*e*P*a*g*em*e*a*n*s*t*h*e*t*e*x*t*n*e*a*r*t*h*e*m*o*s*t*p*r*o*m*i*n*e*n*t*a*p*p*e*a*r*a*n*c*e*o*f*t*h*e*w*o*r*ks*t*i*t*l*e,p*r*e*c*e*d*i*n*g*t*h*e*b*e*g*i*n*n*i*n*g*o*f*t*h*e*b*o*d*y*o*f*t*h*e*t*e*x*t. A*s*e*c*t*i*o*n>m*e*a*n*s*a*n*a*m*e*d*s*u*b*u*n*i*t*o*f*t*h*e*D*o*c*u*m*e*n*t*w*h*o*s*e*t*i*t*l*e*e*i*t*h*e*r*i*s*p*r*e*c*i*s*e*l*y*X*Y*Z*o*r*c*o*n*t*a*i*n*s*X*Y*Z*i*n*p*a*r*e*n*t*h*e*s*e*s*f*o*l*l*o*w*i*n*g*t*e*x*t*t*h*a*t*t*r*a*n*s*l*a*t*e*s*X*Y*Z*i*n*a*n*o*t*h*e*r*l*a*n*g*u*a*g*e.(H*e*r*e*X*Y*Z*s*t*a*n*d*s*f*o*r*a*s*p*e*c*i*f*i*c*s*e*c*t*i*o*n*n*a*m*e*m*e*n*t*i*o*n*e*d*b*e*l*o*w,s*u*c*h*a*s>,>,>,o*r>.)T*o>o*f*s*u*c*h*a*s*e*c*t*i*o*n*w*h*e*n*y*o*u*m*o*d*i*f*y*t*h*e*D*o*c*u*m*e*n*t*m*e*a*n*s*t*h*a*t*i*t*r*e*m*a*i*n*s*a*s*e*c*t*i*o*n``E*n*t*i*t*l*e*d*X*Y*Za*c*c*o*r*d*i*n*g*t*o*t*h*i*s*d*e*f*i*n*i*t*i*o*n. T*h*e*D*o*c*u*m*e*n*t*m*a*y*i*n*c*l*u*d*e*W*a*r*r*a*n*t*y*D*i*s*c*l*a*i*m*e*r*s*n*e*x*t*t*o*t*h*e*n*o*t*i*c*e*w*h*i*c*h*s*t*a*t*e*s*t*h*a*t*t*h*i*s*L*i*c*e*n*s*e*a*p*p*l*i*e*s*t*o*t*h*e*D*o*c*u*m*e*n*t.T*h*e*s*e*W*a*r*r*a*n*t*y*D*i*s*c*l*a*i*m*e*r*s*a*r*e*c*o*n*s*i*d*e*r*e*d*t*o*b*e*i*n*c*l*u*d*e*d*b*y*r*e*f*e*r*e*n*c*e*i*n*t*h*i*s*L*i*c*e*n*s*e,b*u*t*o*n*l*y*a*s*r*e*g*a*r*d*s*d*i*s*c*l*a*i*m*i*n*g*w*a*r*r*a*n*t*i*e*s:a*n*y*o*t*h*e*r*i*m*p*l*i*c*a*t*i*o*n*t*h*a*t*t*h*e*s*e*W*a*r*r*a*n*t*y*D*i*s*c*l*a*i*m*e*r*s*m*a*y*h*a*v*e*i*s*v*o*i*d*a*n*d*h*a*s*n*o*e*f*f*e*c*t*o*n*t*h*e*m*e*a*n*i*n*g*o*f*t*h*i*s*L*i*c*e*n*s*e. <\center> <\with|font-size|1.41> Y*o*u*m*a*y*c*o*p*y*a*n*d*d*i*s*t*r*i*b*u*t*e*t*h*e*D*o*c*u*m*e*n*t*i*n*a*n*y*m*e*d*i*u*m,e*i*t*h*e*r*c*o*m*m*e*r*c*i*a*l*l*y*o*r*n*o*n*c*o*m*m*e*r*c*i*a*l*l*y,p*r*o*v*i*d*e*d*t*h*a*t*t*h*i*s*L*i*c*e*n*s*e,t*h*e*c*o*p*y*r*i*g*h*t*n*o*t*i*c*e*s,a*n*d*t*h*e*l*i*c*e*n*s*e*n*o*t*i*c*e*s*a*y*i*n*g*t*h*i*s*L*i*c*e*n*s*e*a*p*p*l*i*e*s*t*o*t*h*e*D*o*c*u*m*e*n*t*a*r*e*r*e*p*r*o*d*u*c*e*d*i*n*a*l*l*c*o*p*i*e*s,a*n*d*t*h*a*t*y*o*u*a*d*d*n*o*o*t*h*e*r*c*o*n*d*i*t*i*o*n*s*w*h*a*t*s*o*e*v*e*r*t*o*t*h*o*s*e*o*f*t*h*i*s*L*i*c*e*n*s*e.Y*o*u*m*a*y*n*o*t*u*s*e*t*e*c*h*n*i*c*a*l*m*e*a*s*u*r*e*s*t*o*o*b*s*t*r*u*c*t*o*r*c*o*n*t*r*o*l*t*h*e*r*e*a*d*i*n*g*o*r*f*u*r*t*h*e*r*c*o*p*y*i*n*g*o*f*t*h*e*c*o*p*i*e*s*y*o*u*m*a*k*e*o*r*d*i*s*t*r*i*b*u*t*e.H*o*w*e*v*e*r,y*o*u*m*a*y*a*c*c*e*p*t*c*o*m*p*e*n*s*a*t*i*o*n*i*n*e*x*c*h*a*n*g*e*f*o*r*c*o*p*i*e*s.I*f*y*o*u*d*i*s*t*r*i*b*u*t*e*a*l*a*r*g*e*e*n*o*u*g*h*n*u*m*b*e*r*o*f*c*o*p*i*e*s*y*o*u*m*u*s*t*a*l*s*o*f*o*l*l*o*w*t*h*e*c*o*n*d*i*t*i*o*n*s*i*n*s*e*c*t*i*o*n3. Y*o*u*m*a*y*a*l*s*o*l*e*n*d*c*o*p*i*e*s,u*n*d*e*r*t*h*e*s*a*m*e*c*o*n*d*i*t*i*o*n*s*s*t*a*t*e*d*a*b*o*v*e,a*n*d*y*o*u*m*a*y*p*u*b*l*i*c*l*y*d*i*s*p*l*a*y*c*o*p*i*e*s. <\center> <\with|font-size|1.41> I*f*y*o*u*p*u*b*l*i*s*h*p*r*i*n*t*e*d*c*o*p*i*e*s(o*r*c*o*p*i*e*s*i*n*m*e*d*i*a*t*h*a*t*c*o*m*m*o*n*l*y*h*a*v*e*p*r*i*n*t*e*d*c*o*v*e*r*s)o*f*t*h*e*D*o*c*u*m*e*n*t,n*u*m*b*e*r*i*n*g*m*o*r*e*t*h*a*n100,a*n*d*t*h*e*D*o*c*u*m*e*n*ts*l*i*c*e*n*s*e*n*o*t*i*c*e*r*e*q*u*i*r*e*s*C*o*v*e*r*T*e*x*t*s,y*o*u*m*u*s*t*e*n*c*l*o*s*e*t*h*e*c*o*p*i*e*s*i*n*c*o*v*e*r*s*t*h*a*t*c*a*r*r*y,c*l*e*a*r*l*y*a*n*d*l*e*g*i*b*l*y,a*l*l*t*h*e*s*e*C*o*v*e*r*T*e*x*t*s:F*r*o*n*t-C*o*v*e*r*T*e*x*t*s*o*n*t*h*e*f*r*o*n*t*c*o*v*e*r,a*n*d*B*a*c*k-C*o*v*e*r*T*e*x*t*s*o*n*t*h*e*b*a*c*k*c*o*v*e*r.B*o*t*h*c*o*v*e*r*s*m*u*s*t*a*l*s*o*c*l*e*a*r*l*y*a*n*d*l*e*g*i*b*l*y*i*d*e*n*t*i*f*y*y*o*u*a*s*t*h*e*p*u*b*l*i*s*h*e*r*o*f*t*h*e*s*e*c*o*p*i*e*s.T*h*e*f*r*o*n*t*c*o*v*e*r*m*u*s*t*p*r*e*s*e*n*t*t*h*e*f*u*l*l*t*i*t*l*e*w*i*t*h*a*l*l*w*o*r*d*s*o*f*t*h*e*t*i*t*l*e*e*q*u*a*l*l*y*p*r*o*m*i*n*e*n*t*a*n*d*v*i*s*i*b*l*e.Y*o*u*m*a*y*a*d*d*o*t*h*e*r*m*a*t*e*r*i*a*l*o*n*t*h*e*c*o*v*e*r*s*i*n*a*d*d*i*t*i*o*n.C*o*p*y*i*n*g*w*i*t*h*c*h*a*n*g*e*s*l*i*m*i*t*e*d*t*o*t*h*e*c*o*v*e*r*s,a*s*l*o*n*g*a*s*t*h*e*y*p*r*e*s*e*r*v*e*v*t*h*e*t*i*t*l*e*o*f*t*h*e*D*o*c*u*m*e*n*t*a*n*d*s*a*t*i*s*f*y*t*h*e*s*e*c*o*n*d*i*t*i*o*n*s,c*a*n*b*e*t*r*e*a*t*e*d*a*s*v*e*r*b*a*t*i*m*c*o*p*y*i*n*g*i*n*o*t*h*e*r*r*e*s*p*e*c*t*s. I*f*t*h*e*r*e*q*u*i*r*e*d*t*e*x*t*s*f*o*r*e*i*t*h*e*r*c*o*v*e*r*a*r*e*t*o*o*v*o*l*u*m*i*n*o*u*s*t*o*f*i*t*l*e*g*i*b*l*y,y*o*u*s*h*o*u*l*d*p*u*t*t*h*e*f*i*r*s*t*o*n*e*s*l*i*s*t*e*d(a*s*m*a*n*y*a*s*f*i*t*r*e*a*s*o*n*a*b*l*y)o*n*t*h*e*a*c*t*u*a*l*c*o*v*e*r,a*n*d*c*o*n*t*i*n*u*e*t*h*e*r*e*s*t*o*n*t*o*a*d*j*a*c*e*n*t*p*a*g*e*s. I*f*y*o*u*p*u*b*l*i*s*h*o*r*d*i*s*t*r*i*b*u*t*e*O*p*a*q*u*e*c*o*p*i*e*s*o*f*t*h*e*D*o*c*u*m*e*n*t*n*u*m*b*e*r*i*n*g*m*o*r*e*t*h*a*n100,y*o*u*m*u*s*t*e*i*t*h*e*r*i*n*c*l*u*d*e*a*m*a*c*h*i*n*e-r*e*a*d*a*b*l*e*T*r*a*n*s*p*a*r*e*n*t*c*o*p*y*a*l*o*n*g*w*i*t*h*e*a*c*h*O*p*a*q*u*e*c*o*p*y,o*r*s*t*a*t*e*i*n*o*r*w*i*t*h*e*a*c*h*O*p*a*q*u*e*c*o*p*y*a*c*o*m*p*u*t*e*r-n*e*t*w*o*r*k*l*o*c*a*t*i*o*n*f*r*o*m*w*h*i*c*h*t*h*e*g*e*n*e*r*a*l*n*e*t*w*o*r*k-u*s*i*n*g*p*u*b*l*i*c*h*a*s*a*c*c*e*s*s*t*o*d*o*w*n*l*o*a*d*u*s*i*n*g*p*u*b*l*i*c-s*t*a*n*d*a*r*d*n*e*t*w*o*r*k*p*r*o*t*o*c*o*l*s*a*c*o*m*p*l*e*t*e*T*r*a*n*s*p*a*r*e*n*t*c*o*p*y*o*f*t*h*e*D*o*c*u*m*e*n*t,f*r*e*e*o*f*a*d*d*e*d*m*a*t*e*r*i*a*l.I*f*y*o*u*u*s*e*t*h*e*l*a*t*t*e*r*o*p*t*i*o*n,y*o*u*m*u*s*t*t*a*k*e*r*e*a*s*o*n*a*b*l*y*p*r*u*d*e*n*t*s*t*e*p*s,w*h*e*n*y*o*u*b*e*g*i*n*d*i*s*t*r*i*b*u*t*i*o*n*o*f*O*p*a*q*u*e*c*o*p*i*e*s*i*n*q*u*a*n*t*i*t*y,t*o*e*n*s*u*r*e*t*h*a*t*t*h*i*s*T*r*a*n*s*p*a*r*e*n*t*c*o*p*y*w*i*l*l*r*e*m*a*i*n*t*h*u*s*a*c*c*e*s*s*i*b*l*e*a*t*t*h*e*s*t*a*t*e*d*l*o*c*a*t*i*o*n*u*n*t*i*l*a*t*l*e*a*s*t*o*n*e*y*e*a*r*a*f*t*e*r*t*h*e*l*a*s*t*t*i*m*e*y*o*u*d*i*s*t*r*i*b*u*t*e*a*n*O*p*a*q*u*e*c*o*p*y(d*i*r*e*c*t*l*y*o*r*t*h*r*o*u*g*h*y*o*u*r*a*g*e*n*t*s*o*r*r*e*t*a*i*l*e*r*s)o*f*t*h*a*t*e*d*i*t*i*o*n*t*o*t*h*e*p*u*b*l*i*c. I*t*i*s*r*e*q*u*e*s*t*e*d,b*u*t*n*o*t*r*e*q*u*i*r*e*d,t*h*a*t*y*o*u*c*o*n*t*a*c*t*t*h*e*a*u*t*h*o*r*s*o*f*t*h*e*D*o*c*u*m*e*n*t*w*e*l*l*b*e*f*o*r*e*r*e*d*i*s*t*r*i*b*u*t*i*n*g*a*n*y*l*a*r*g*e*n*u*m*b*e*r*o*f*c*o*p*i*e*s,t*o*g*i*v*e*t*h*e*m*a*c*h*a*n*c*e*t*o*p*r*o*v*i*d*e*y*o*u*w*i*t*h*a*n*u*p*d*a*t*e*d*v*e*r*s*i*o*n*o*f*t*h*e*D*o*c*u*m*e*n*t. <\center> <\with|font-size|1.41> Y*o*u*m*a*y*c*o*p*y*a*n*d*d*i*s*t*r*i*b*u*t*e*a*M*o*d*i*f*i*e*d*V*e*r*s*i*o*n*o*f*t*h*e*D*o*c*u*m*e*n*t*u*n*d*e*r*t*h*e*c*o*n*d*i*t*i*o*n*s*o*f*s*e*c*t*i*o*n*s2a*n*d3a*b*o*v*e,p*r*o*v*i*d*e*d*t*h*a*t*y*o*u*r*e*l*e*a*s*e*t*h*e*M*o*d*i*f*i*e*d*V*e*r*s*i*o*n*u*n*d*e*r*p*r*e*c*i*s*e*l*y*t*h*i*s*L*i*c*e*n*s*e,w*i*t*h*t*h*e*M*o*d*i*f*i*e*d*V*e*r*s*i*o*n*f*i*l*l*i*n*g*t*h*e*r*o*l*e*o*f*t*h*e*D*o*c*u*m*e*n*t,t*h*u*s*l*i*c*e*n*s*i*n*g*d*i*s*t*r*i*b*u*t*i*o*n*a*n*d*m*o*d*i*f*i*c*a*t*i*o*n*o*f*t*h*e*M*o*d*i*f*i*e*d*V*e*r*s*i*o*n*t*o*w*h*o*e*v*e*r*p*o*s*s*e*s*s*e*s*a*c*o*p*y*o*f*i*t.I*n*a*d*d*i*t*i*o*n,y*o*u*m*u*s*t*d*o*t*h*e*s*e*t*h*i*n*g*s*i*n*t*h*e*M*o*d*i*f*i*e*d*V*e*r*s*i*o*n: <\itemize> U*s*e*i*n*t*h*e*T*i*t*l*e*P*a*g*e(a*n*d*o*n*t*h*e*c*o*v*e*r*s,i*f*a*n*y)a*t*i*t*l*e*d*i*s*t*i*n*c*t*f*r*o*m*t*h*a*t*o*f*t*h*e*D*o*c*u*m*e*n*t,a*n*d*f*r*o*m*t*h*o*s*e*o*f*p*r*e*v*i*o*u*s*v*e*r*s*i*o*n*s(w*h*i*c*h*s*h*o*u*l*d,i*f*t*h*e*r*e*w*e*r*e*a*n*y,b*e*l*i*s*t*e*d*i*n*t*h*e*H*i*s*t*o*r*y*s*e*c*t*i*o*n*o*f*t*h*e*D*o*c*u*m*e*n*t).Y*o*u*m*a*y*u*s*e*t*h*e*s*a*m*e*t*i*t*l*e*a*s*a*p*r*e*v*i*o*u*s*v*e*r*s*i*o*n*i*f*t*h*e*o*r*i*g*i*n*a*l*p*u*b*l*i*s*h*e*r*o*f*t*h*a*t*v*e*r*s*i*o*n*g*i*v*e*s*p*e*r*m*i*s*s*i*o*n. L*i*s*t*o*n*t*h*e*T*i*t*l*e*P*a*g*e,a*s*a*u*t*h*o*r*s,o*n*e*o*r*m*o*r*e*p*e*r*s*o*n*s*o*r*e*n*t*i*t*i*e*s*r*e*s*p*o*n*s*i*b*l*e*f*o*r*a*u*t*h*o*r*s*h*i*p*o*f*t*h*e*m*o*d*i*f*i*c*a*t*i*o*n*s*i*n*t*h*e*M*o*d*i*f*i*e*d*V*e*r*s*i*o*n,t*o*g*e*t*h*e*r*w*i*t*h*a*t*l*e*a*s*t*f*i*v*e*o*f*t*h*e*p*r*i*n*c*i*p*a*l*a*u*t*h*o*r*s*o*f*t*h*e*D*o*c*u*m*e*n*t(a*l*l*o*f*i*t*s*p*r*i*n*c*i*p*a*l*a*u*t*h*o*r*s,i*f*i*t*h*a*s*f*e*w*e*r*t*h*a*n*f*i*v*e),u*n*l*e*s*s*t*h*e*y*r*e*l*e*a*s*e*y*o*u*f*r*o*m*t*h*i*s*r*e*q*u*i*r*e*m*e*n*t. S*t*a*t*e*o*n*t*h*e*T*i*t*l*e*p*a*g*e*t*h*e*n*a*m*e*o*f*t*h*e*p*u*b*l*i*s*h*e*r*o*f*t*h*e*M*o*d*i*f*i*e*d*V*e*r*s*i*o*n,a*s*t*h*e*p*u*b*l*i*s*h*e*r. P*r*e*s*e*r*v*e*a*l*l*t*h*e*c*o*p*y*r*i*g*h*t*n*o*t*i*c*e*s*o*f*t*h*e*D*o*c*u*m*e*n*t. A*d*d*a*n*a*p*p*r*o*p*r*i*a*t*e*c*o*p*y*r*i*g*h*t*n*o*t*i*c*e*f*o*r*y*o*u*r*m*o*d*i*f*i*c*a*t*i*o*n*s*a*d*j*a*c*e*n*t*t*o*t*h*e*o*t*h*e*r*c*o*p*y*r*i*g*h*t*n*o*t*i*c*e*s. I*n*c*l*u*d*e,i*m*m*e*d*i*a*t*e*l*y*a*f*t*e*r*t*h*e*c*o*p*y*r*i*g*h*t*n*o*t*i*c*e*s,a*l*i*c*e*n*s*e*n*o*t*i*c*e*g*i*v*i*n*g*t*h*e*p*u*b*l*i*c*p*e*r*m*i*s*s*i*o*n*t*o*u*s*e*t*h*e*M*o*d*i*f*i*e*d*V*e*r*s*i*o*n*u*n*d*e*r*t*h*e*t*e*r*m*s*o*f*t*h*i*s*L*i*c*e*n*s*e,i*n*t*h*e*f*o*r*m*s*h*o*w*n*i*n*t*h*e*A*d*d*e*n*d*u*m*b*e*l*o*w. P*r*e*s*e*r*v*e*i*n*t*h*a*t*l*i*c*e*n*s*e*n*o*t*i*c*e*t*h*e*f*u*l*l*l*i*s*t*s*o*f*I*n*v*a*r*i*a*n*t*S*e*c*t*i*o*n*s*a*n*d*r*e*q*u*i*r*e*d*C*o*v*e*r*T*e*x*t*s*g*i*v*e*n*i*n*t*h*e*D*o*c*u*m*e*n*ts*l*i*c*e*n*s*e*n*o*t*i*c*e. I*n*c*l*u*d*e*a*n*u*n*a*l*t*e*r*e*d*c*o*p*y*o*f*t*h*i*s*L*i*c*e*n*s*e. P*r*e*s*e*r*v*e*t*h*e*s*e*c*t*i*o*n*E*n*t*i*t*l*e*d``H*i*s*t*o*r*y",P*r*e*s*e*r*v*e*i*t*s*T*i*t*l*e,a*n*d*a*d*d*t*o*i*t*a*n*i*t*e*m*s*t*a*t*i*n*g*a*t*l*e*a*s*t*t*h*e*t*i*t*l*e,y*e*a*r,n*e*w*a*u*t*h*o*r*s,a*n*d*p*u*b*l*i*s*h*e*r*o*f*t*h*e*M*o*d*i*f*i*e*d*V*e*r*s*i*o*n*a*s*g*i*v*e*n*o*n*t*h*e*T*i*t*l*e*P*a*g*e.I*f*v*t*h*e*r*e*i*s*n*o*s*e*c*t*i*o*n*E*n*t*i*t*l*e*d``H*i*s*t*o*r*yi*n*t*h*e*D*o*c*u*m*e*n*t,c*r*e*a*t*e*o*n*e*s*t*a*t*i*n*g*t*h*e*t*i*t*l*e,y*e*a*r,a*u*t*h*o*r*s,a*n*d*p*u*b*l*i*s*h*e*r*o*f*t*h*e*D*o*c*u*m*e*n*t*a*s*g*i*v*e*n*o*n*i*t*s*T*i*t*l*e*P*a*g*e,t*h*e*n*a*d*d*a*n*i*t*e*m*d*e*s*c*r*i*b*i*n*g*t*h*e*M*o*d*i*f*i*e*d*V*e*r*s*i*o*n*a*s*s*t*a*t*e*d*i*n*t*h*e*p*r*e*v*i*o*u*s*s*e*n*t*e*n*c*e. P*r*e*s*e*r*v*e*t*h*e*n*e*t*w*o*r*k*l*o*c*a*t*i*o*n,i*f*a*n*y,g*i*v*e*n*i*n*t*h*e*D*o*c*u*m*e*n*t*f*o*r*p*u*b*l*i*c*a*c*c*e*s*s*t*o*a*T*r*a*n*s*p*a*r*e*n*t*c*o*p*y*o*f*t*h*e*D*o*c*u*m*e*n*t,a*n*d*l*i*k*e*w*i*s*e*t*h*e*n*e*t*w*o*r*k*l*o*c*a*t*i*o*n*s*g*i*v*e*n*i*n*t*h*e*D*o*c*u*m*e*n*t*f*o*r*p*r*e*v*i*o*u*s*v*e*r*s*i*o*n*s*i*t*w*a*s*b*a*s*e*d*o*n.T*h*e*s*e*m*a*y*b*e*p*l*a*c*e*d*i*n*t*h*e``H*i*s*t*o*r*ys*e*c*t*i*o*n.Y*o*u*m*a*y*o*m*i*t*a*n*e*t*w*o*r*k*l*o*c*a*t*i*o*n*f*o*r*a*w*o*r*k*t*h*a*t*w*a*s*p*u*b*l*i*s*h*e*d*a*t*l*e*a*s*t*f*o*u*r*y*e*a*r*s*b*e*f*o*r*e*t*h*e*D*o*c*u*m*e*n*t*i*t*s*e*l*f,o*r*i*f*t*h*e*o*r*i*g*i*n*a*l*p*u*b*l*i*s*h*e*r*o*f*t*h*e*v*e*r*s*i*o*n*i*t*r*e*f*e*r*s*t*o*g*i*v*e*s*p*e*r*m*i*s*s*i*o*n. F*o*r*a*n*y*s*e*c*t*i*o*n*E*n*t*i*t*l*e*d``A*c*k*n*o*w*l*e*d*g*e*m*e*n*t*so*r``D*e*d*i*c*a*t*i*o*n*s",P*r*e*s*e*r*v*e*t*h*e*T*i*t*l*e*o*f*t*h*e*s*e*c*t*i*o*n,a*n*d*p*r*e*s*e*r*v*e*i*n*t*h*e*s*e*c*t*i*o*n*a*l*l*t*h*e*s*u*b*s*t*a*n*c*e*a*n*d*t*o*n*e*o*f*e*a*c*h*o*f*t*h*e*c*o*n*t*r*i*b*u*t*o*r*a*c*k*n*o*w*l*e*d*g*e*m*e*n*t*s*a*n*d/o*r*d*e*d*i*c*a*t*i*o*n*s*g*i*v*e*n*t*h*e*r*e*i*n. P*r*e*s*e*r*v*e*a*l*l*t*h*e*I*n*v*a*r*i*a*n*t*S*e*c*t*i*o*n*s*o*f*t*h*e*D*o*c*u*m*e*n*t,u*n*a*l*t*e*r*e*d*i*n*t*h*e*i*r*t*e*x*t*a*n*d*i*n*t*h*e*i*r*t*i*t*l*e*s.S*e*c*t*i*o*n*n*u*m*b*e*r*s*o*r*t*h*e*e*q*u*i*v*a*l*e*n*t*a*r*e*n*o*t*c*o*n*s*i*d*e*r*e*d*p*a*r*t*o*f*t*h*e*s*e*c*t*i*o*n*t*i*t*l*e*s. D*e*l*e*t*e*a*n*y*s*e*c*t*i*o*n*E*n*t*i*t*l*e*d``E*n*d*o*r*s*e*m*e*n*t*s".S*u*c*h*a*s*e*c*t*i*o*n*m*a*y*n*o*t*b*e*i*n*c*l*u*d*e*d*i*n*t*h*e*M*o*d*i*f*i*e*d*V*e*r*s*i*o*n. D*o*n*o*t*r*e*t*i*t*l*e*a*n*y*e*x*i*s*t*i*n*g*s*e*c*t*i*o*n*t*o*b*e*E*n*t*i*t*l*e*d``E*n*d*o*r*s*e*m*e*n*t*s"o*r*t*o*c*o*n*f*l*i*c*t*i*n*t*i*t*l*e*w*i*t*h*a*n*y*I*n*v*a*r*i*a*n*t*S*e*c*t*i*o*n. P*r*e*s*e*r*v*e*a*n*y*W*a*r*r*a*n*t*y*D*i*s*c*l*a*i*m*e*r*s. I*f*t*h*e*M*o*d*i*f*i*e*d*V*e*r*s*i*o*n*i*n*c*l*u*d*e*s*n*e*w*f*r*o*n*t-m*a*t*t*e*r*s*e*c*t*i*o*n*s*o*r*a*p*p*e*n*d*i*c*e*s*t*h*a*t*q*u*a*l*i*f*y*a*s*S*e*c*o*n*d*a*r*y*S*e*c*t*i*o*n*s*a*n*d*c*o*n*t*a*i*n*n*o*m*a*t*e*r*i*a*l*c*o*p*i*e*d*f*r*o*m*t*h*e*D*o*c*u*m*e*n*t,y*o*u*m*a*y*a*t*y*o*u*r*o*p*t*i*o*n*d*e*s*i*g*n*a*t*e*s*o*m*e*o*r*a*l*l*o*f*t*h*e*s*e*s*e*c*t*i*o*n*s*a*s*i*n*v*a*r*i*a*n*t.T*o*d*o*t*h*i*s,a*d*d*t*h*e*i*r*t*i*t*l*e*s*t*o*t*h*e*l*i*s*t*o*f*I*n*v*a*r*i*a*n*t*S*e*c*t*i*o*n*s*i*n*t*h*e*M*o*d*i*f*i*e*d*V*e*r*s*i*o*ns*l*i*c*e*n*s*e*n*o*t*i*c*e.T*h*e*s*e*t*i*t*l*e*s*m*u*s*t*b*e*d*i*s*t*i*n*c*t*f*r*o*m*a*n*y*o*t*h*e*r*s*e*c*t*i*o*n*t*i*t*l*e*s. Y*o*u*m*a*y*a*d*d*a*s*e*c*t*i*o*n*E*n*t*i*t*l*e*d``E*n*d*o*r*s*e*m*e*n*t*s",p*r*o*v*i*d*e*d*i*t*c*o*n*t*a*i*n*s*n*o*t*h*i*n*g*b*u*t*e*n*d*o*r*s*e*m*e*n*t*s*o*f*y*o*u*r*M*o*d*i*f*i*e*d*V*e*r*s*i*o*n*b*y*v*a*r*i*o*u*s*p*a*r*t*i*e*s--f*o*r*e*x*a*m*p*l*e,s*t*a*t*e*m*e*n*t*s*o*f*p*e*e*r*r*e*v*i*e*w*o*r*t*h*a*t*t*h*e*t*e*x*t*h*a*s*b*e*e*n*a*p*p*r*o*v*e*d*b*y*a*n*o*r*g*a*n*i*z*a*t*i*o*n*a*s*t*h*e*a*u*t*h*o*r*i*t*a*t*i*v*e*d*e*f*i*n*i*t*i*o*n*o*f*a*s*t*a*n*d*a*r*d. Y*o*u*m*a*y*a*d*d*a*p*a*s*s*a*g*e*o*f*u*p*t*o*f*i*v*e*w*o*r*d*s*a*s*a*F*r*o*n*t-C*o*v*e*r*T*e*x*t,a*n*d*a*p*a*s*s*a*g*e*o*f*u*p*t*o25w*o*r*d*s*a*s*a*B*a*c*k-C*o*v*e*r*T*e*x*t,t*o*t*h*e*e*n*d*o*f*t*h*e*l*i*s*t*o*f*C*o*v*e*r*T*e*x*t*s*i*n*t*h*e*M*o*d*i*f*i*e*d*V*e*r*s*i*o*n.O*n*l*y*o*n*e*p*a*s*s*a*g*e*o*f*F*r*o*n*t-C*o*v*e*r*T*e*x*t*a*n*d*o*n*e*o*f*B*a*c*k-C*o*v*e*r*T*e*x*t*m*a*y*b*e*a*d*d*e*d*b*y(o*r*t*h*r*o*u*g*h*a*r*r*a*n*g*e*m*e*n*t*s*m*a*d*e*b*y)a*n*y*o*n*e*e*n*t*i*t*y.I*f*t*h*e*D*o*c*u*m*e*n*t*a*l*r*e*a*d*y*i*n*c*l*u*d*e*s*a*c*o*v*e*r*t*e*x*t*f*o*r*t*h*e*s*a*m*e*c*o*v*e*r,p*r*e*v*i*o*u*s*l*y*a*d*d*e*d*b*y*y*o*u*o*r*b*y*a*r*r*a*n*g*e*m*e*n*t*m*a*d*e*b*y*t*h*e*s*a*m*e*e*n*t*i*t*y*y*o*u*a*r*e*a*c*t*i*n*g*o*n*b*e*h*a*l*f*o*f,y*o*u*m*a*y*n*o*t*a*d*d*a*n*o*t*h*e*r;b*u*t*y*o*u*m*a*y*r*e*p*l*a*c*e*t*h*e*o*l*d*o*n*e,o*n*e*x*p*l*i*c*i*t*p*e*r*m*i*s*s*i*o*n*f*r*o*m*t*h*e*p*r*e*v*i*o*u*s*p*u*b*l*i*s*h*e*r*t*h*a*t*a*d*d*e*d*t*h*e*o*l*d*o*n*e. T*h*e*a*u*t*h*o*r(s)a*n*d*p*u*b*l*i*s*h*e*r(s)o*f*t*h*e*D*o*c*u*m*e*n*t*d*o*n*o*t*b*y*t*h*i*s*L*i*c*e*n*s*e*g*i*v*e*p*e*r*m*i*s*s*i*o*n*t*o*u*s*e*t*h*e*i*r*n*a*m*e*s*f*o*r*p*u*b*l*i*c*i*t*y*f*o*r*o*r*t*o*a*s*s*e*r*t*o*r*i*m*p*l*y*e*n*d*o*r*s*e*m*e*n*t*o*f*a*n*y*M*o*d*i*f*i*e*d*V*e*r*s*i*o*n. <\center> <\with|font-size|1.41> Y*o*u*m*a*y*c*o*m*b*i*n*e*t*h*e*D*o*c*u*m*e*n*t*w*i*t*h*o*t*h*e*r*d*o*c*u*m*e*n*t*s*r*e*l*e*a*s*e*d*u*n*d*e*r*t*h*i*s*L*i*c*e*n*s*e,u*n*d*e*r*t*h*e*t*e*r*m*s*d*e*f*i*n*e*d*i*n*s*e*c*t*i*o*n4a*b*o*v*e*f*o*r*m*o*d*i*f*i*e*d*v*e*r*s*i*o*n*s,p*r*o*v*i*d*e*d*t*h*a*t*y*o*u*i*n*c*l*u*d*e*i*n*t*h*e*c*o*m*b*i*n*a*t*i*o*n*a*l*l*o*f*t*h*e*I*n*v*a*r*i*a*n*t*S*e*c*t*i*o*n*s*o*f*a*l*l*o*f*t*h*e*o*r*i*g*i*n*a*l*d*o*c*u*m*e*n*t*s,u*n*m*o*d*i*f*i*e*d,a*n*d*l*i*s*t*t*h*e*m*a*l*l*a*s*I*n*v*a*r*i*a*n*t*S*e*c*t*i*o*n*s*o*f*y*o*u*r*c*o*m*b*i*n*e*d*w*o*r*k*i*n*i*t*s*l*i*c*e*n*s*e*n*o*t*i*c*e,a*n*d*t*h*a*t*y*o*u*p*r*e*s*e*r*v*e*a*l*l*t*h*e*i*r*W*a*r*r*a*n*t*y*D*i*s*c*l*a*i*m*e*r*s. T*h*e*c*o*m*b*i*n*e*d*w*o*r*k*n*e*e*d*o*n*l*y*c*o*n*t*a*i*n*o*n*e*c*o*p*y*o*f*t*h*i*s*L*i*c*e*n*s*e,a*n*d*m*u*l*t*i*p*l*e*i*d*e*n*t*i*c*a*l*I*n*v*a*r*i*a*n*t*S*e*c*t*i*o*n*s*m*a*y*b*e*r*e*p*l*a*c*e*d*w*i*t*h*a*s*i*n*g*l*e*c*o*p*y.I*f*t*h*e*r*e*a*r*e*m*u*l*t*i*p*l*e*I*n*v*a*r*i*a*n*t*S*e*c*t*i*o*n*s*w*i*t*h*t*h*e*s*a*m*e*n*a*m*e*b*u*t*d*i*f*f*e*r*e*n*t*c*o*n*t*e*n*t*s,m*a*k*e*t*h*e*t*i*t*l*e*o*f*e*a*c*h*s*u*c*h*s*e*c*t*i*o*n*u*n*i*q*u*e*b*y*a*d*d*i*n*g*a*t*t*h*e*e*n*d*o*f*i*t,i*n*p*a*r*e*n*t*h*e*s*e*s,t*h*e*n*a*m*e*o*f*t*h*e*o*r*i*g*i*n*a*l*a*u*t*h*o*r*o*r*p*u*b*l*i*s*h*e*r*o*f*t*h*a*t*s*e*c*t*i*o*n*i*f*k*n*o*w*n,o*r*e*l*s*e*a*u*n*i*q*u*e*n*u*m*b*e*r.M*a*k*e*t*h*e*s*a*m*e*a*d*j*u*s*t*m*e*n*t*t*o*t*h*e*s*e*c*t*i*o*n*t*i*t*l*e*s*i*n*t*h*e*l*i*s*t*o*f*I*n*v*a*r*i*a*n*t*S*e*c*t*i*o*n*s*i*n*t*h*e*l*i*c*e*n*s*e*n*o*t*i*c*e*o*f*t*h*e*c*o*m*b*i*n*e*d*w*o*r*k. I*n*t*h*e*c*o*m*b*i*n*a*t*i*o*n,y*o*u*m*u*s*t*c*o*m*b*i*n*e*a*n*y*s*e*c*t*i*o*n*s*E*n*t*i*t*l*e*d``H*i*s*t*o*r*y"i*n*t*h*e*v*a*r*i*o*u*s*o*r*i*g*i*n*a*l*d*o*c*u*m*e*n*t*s,f*o*r*m*i*n*g*o*n*e*s*e*c*t*i*o*n*E*n*t*i*t*l*e*d"H*i*s*t*o*r*y";l*i*k*e*w*i*s*e*c*o*m*b*i*n*e*a*n*y*s*e*c*t*i*o*n*s*E*n*t*i*t*l*e*d``A*c*k*n*o*w*l*e*d*g*e*m*e*n*t*s",a*n*d*a*n*y*s*e*c*t*i*o*n*s*E*n*t*i*t*l*e*d``D*e*d*i*c*a*t*i*o*n*s".Y*o*u*m*u*s*t*d*e*l*e*t*e*a*l*l*s*e*c*t*i*o*n*s*E*n*t*i*t*l*e*d``E*n*d*o*r*s*e*m*e*n*t*s". <\center> <\with|font-size|1.41> Y*o*u*m*a*y*m*a*k*e*a*c*o*l*l*e*c*t*i*o*n*c*o*n*s*i*s*t*i*n*g*o*f*t*h*e*D*o*c*u*m*e*n*t*a*n*d*o*t*h*e*r*d*o*c*u*m*e*n*t*s*r*e*l*e*a*s*e*d*u*n*d*e*r*t*h*i*s*L*i*c*e*n*s*e,a*n*d*r*e*p*l*a*c*e*t*h*e*i*n*d*i*v*i*d*u*a*l*c*o*p*i*e*s*o*f*t*h*i*s*L*i*c*e*n*s*e*i*n*t*h*e*v*a*r*i*o*u*s*d*o*c*u*m*e*n*t*s*w*i*t*h*a*s*i*n*g*l*e*c*o*p*y*t*h*a*t*i*s*i*n*c*l*u*d*e*d*i*n*t*h*e*c*o*l*l*e*c*t*i*o*n,p*r*o*v*i*d*e*d*t*h*a*t*y*o*u*f*o*l*l*o*w*t*h*e*r*u*l*e*s*o*f*t*h*i*s*L*i*c*e*n*s*e*f*o*r*v*e*r*b*a*t*i*m*c*o*p*y*i*n*g*o*f*e*a*c*h*o*f*t*h*e*d*o*c*u*m*e*n*t*s*i*n*a*l*l*o*t*h*e*r*r*e*s*p*e*c*t*s. Y*o*u*m*a*y*e*x*t*r*a*c*t*a*s*i*n*g*l*e*d*o*c*u*m*e*n*t*f*r*o*m*s*u*c*h*a*c*o*l*l*e*c*t*i*o*n,a*n*d*d*i*s*t*r*i*b*u*t*e*i*t*i*n*d*i*v*i*d*u*a*l*l*y*u*n*d*e*r*t*h*i*s*L*i*c*e*n*s*e,p*r*o*v*i*d*e*d*y*o*u*i*n*s*e*r*t*a*c*o*p*y*o*f*t*h*i*s*L*i*c*e*n*s*e*i*n*t*o*t*h*e*e*x*t*r*a*c*t*e*d*d*o*c*u*m*e*n*t,a*n*d*f*o*l*l*o*w*t*h*i*s*L*i*c*e*n*s*e*i*n*a*l*l*o*t*h*e*r*r*e*s*p*e*c*t*s*r*e*g*a*r*d*i*n*g*v*e*r*b*a*t*i*m*c*o*p*y*i*n*g*o*f*t*h*a*t*d*o*c*u*m*e*n*t. <\center> <\with|font-size|1.41> A*c*o*m*p*i*l*a*t*i*o*n*o*f*t*h*e*D*o*c*u*m*e*n*t*o*r*i*t*s*d*e*r*i*v*a*t*i*v*e*s*w*i*t*h*o*t*h*e*r*s*e*p*a*r*a*t*e*a*n*d*i*n*d*e*p*e*n*d*e*n*t*d*o*c*u*m*e*n*t*s*o*r*w*o*r*k*s,i*n*o*r*o*n*a*v*o*l*u*m*e*o*f*a*s*t*o*r*a*g*e*o*r*d*i*s*t*r*i*b*u*t*i*o*n*m*e*d*i*u*m,i*s*c*a*l*l*e*d*a*n``a*g*g*r*e*g*a*t*ei*f*t*h*e*c*o*p*y*r*i*g*h*t*r*e*s*u*l*t*i*n*g*f*r*o*m*t*h*e*c*o*m*p*i*l*a*t*i*o*n*i*s*n*o*t*u*s*e*d*t*o*l*i*m*i*t*t*h*e*l*e*g*a*l*r*i*g*h*t*s*o*f*t*h*e*c*o*m*p*i*l*a*t*i*o*ns*u*s*e*r*s*b*e*y*o*n*d*w*h*a*t*t*h*e*i*n*d*i*v*i*d*u*a*l*w*o*r*k*s*p*e*r*m*i*t.W*h*e*n*t*h*e*D*o*c*u*m*e*n*t*i*s*i*n*c*l*u*d*e*d*i*n*a*n*a*g*g*r*e*g*a*t*e,t*h*i*s*L*i*c*e*n*s*e*d*o*e*s*n*o*t*a*p*p*l*y*t*o*t*h*e*o*t*h*e*r*w*o*r*k*s*i*n*t*h*e*a*g*g*r*e*g*a*t*e*w*h*i*c*h*a*r*e*n*o*t*t*h*e*m*s*e*l*v*e*s*d*e*r*i*v*a*t*i*v*e*w*o*r*k*s*o*f*t*h*e*D*o*c*u*m*e*n*t. I*f*t*h*e*C*o*v*e*r*T*e*x*t*r*e*q*u*i*r*e*m*e*n*t*o*f*s*e*c*t*i*o*n3i*s*a*p*p*l*i*c*a*b*l*e*t*o*t*h*e*s*e*c*o*p*i*e*s*o*f*t*h*e*D*o*c*u*m*e*n*t,t*h*e*n*i*f*t*h*e*D*o*c*u*m*e*n*t*i*s*l*e*s*s*t*h*a*n*o*n*e*h*a*l*f*o*f*t*h*e*e*n*t*i*r*e*a*g*g*r*e*g*a*t*e,t*h*e*D*o*c*u*m*e*n*ts*C*o*v*e*r*T*e*x*t*s*m*a*y*b*e*p*l*a*c*e*d*o*n*c*o*v*e*r*s*t*h*a*t*b*r*a*c*k*e*t*t*h*e*D*o*c*u*m*e*n*t*w*i*t*h*i*n*t*h*e*a*g*g*r*e*g*a*t*e,o*r*t*h*e*e*l*e*c*t*r*o*n*i*c*e*q*u*i*v*a*l*e*n*t*o*f*c*o*v*e*r*s*i*f*t*h*e*D*o*c*u*m*e*n*t*i*s*i*n*e*l*e*c*t*r*o*n*i*c*f*o*r*m.O*t*h*e*r*w*i*s*e*t*h*e*y*m*u*s*t*a*p*p*e*a*r*o*n*p*r*i*n*t*e*d*c*o*v*e*r*s*t*h*a*t*b*r*a*c*k*e*t*t*h*e*w*h*o*l*e*a*g*g*r*e*g*a*t*e. <\center> <\with|font-size|1.41> T*r*a*n*s*l*a*t*i*o*n*i*s*c*o*n*s*i*d*e*r*e*d*a*k*i*n*d*o*f*m*o*d*i*f*i*c*a*t*i*o*n,s*o*y*o*u*m*a*y*d*i*s*t*r*i*b*u*t*e*t*r*a*n*s*l*a*t*i*o*n*s*o*f*t*h*e*D*o*c*u*m*e*n*t*u*n*d*e*r*t*h*e*t*e*r*m*s*o*f*s*e*c*t*i*o*n4.R*e*p*l*a*c*i*n*g*I*n*v*a*r*i*a*n*t*S*e*c*t*i*o*n*s*w*i*t*h*t*r*a*n*s*l*a*t*i*o*n*s*r*e*q*u*i*r*e*s*s*p*e*c*i*a*l*p*e*r*m*i*s*s*i*o*n*f*r*o*m*t*h*e*i*r*c*o*p*y*r*i*g*h*t*h*o*l*d*e*r*s,b*u*t*y*o*u*m*a*y*i*n*c*l*u*d*e*t*r*a*n*s*l*a*t*i*o*n*s*o*f*s*o*m*e*o*r*a*l*l*I*n*v*a*r*i*a*n*t*S*e*c*t*i*o*n*s*i*n*a*d*d*i*t*i*o*n*t*o*t*h*e*o*r*i*g*i*n*a*l*v*e*r*s*i*o*n*s*o*f*t*h*e*s*e*I*n*v*a*r*i*a*n*t*S*e*c*t*i*o*n*s.Y*o*u*m*a*y*i*n*c*l*u*d*e*a*t*r*a*n*s*l*a*t*i*o*n*o*f*t*h*i*s*L*i*c*e*n*s*e,a*n*d*a*l*l*t*h*e*l*i*c*e*n*s*e*n*o*t*i*c*e*s*i*n*t*h*e*D*o*c*u*m*e*n*t,a*n*d*a*n*y*W*a*r*r*a*n*t*y*D*i*s*c*l*a*i*m*e*r*s,p*r*o*v*i*d*e*d*t*h*a*t*y*o*u*a*l*s*o*i*n*c*l*u*d*e*t*h*e*o*r*i*g*i*n*a*l*E*n*g*l*i*s*h*v*e*r*s*i*o*n*o*f*t*h*i*s*L*i*c*e*n*s*e*a*n*d*t*h*e*o*r*i*g*i*n*a*l*v*e*r*s*i*o*n*s*o*f*t*h*o*s*e*n*o*t*i*c*e*s*a*n*d*d*i*s*c*l*a*i*m*e*r*s.I*n*c*a*s*e*o*f*a*d*i*s*a*g*r*e*e*m*e*n*t*b*e*t*w*e*e*n*t*h*e*t*r*a*n*s*l*a*t*i*o*n*a*n*d*t*h*e*o*r*i*g*i*n*a*l*v*e*r*s*i*o*n*o*f*t*h*i*s*L*i*c*e*n*s*e*o*r*a*n*o*t*i*c*e*o*r*d*i*s*c*l*a*i*m*e*r,t*h*e*o*r*i*g*i*n*a*l*v*e*r*s*i*o*n*w*i*l*l*p*r*e*v*a*i*l. I*f*a*s*e*c*t*i*o*n*i*n*t*h*e*D*o*c*u*m*e*n*t*i*s*E*n*t*i*t*l*e*d``A*c*k*n*o*w*l*e*d*g*e*m*e*n*t*s","D*e*d*i*c*a*t*i*o*n*s",o*r``H*i*s*t*o*r*y",t*h*e*r*e*q*u*i*r*e*m*e*n*t(s*e*c*t*i*o*n4)t*o*P*r*e*s*e*r*v*e*i*t*s*T*i*t*l*e(s*e*c*t*i*o*n1)w*i*l*l*t*y*p*i*c*a*l*l*y*r*e*q*u*i*r*e*c*h*a*n*g*i*n*g*t*h*e*a*c*t*u*a*l*t*i*t*l*e. <\center> <\with|font-size|1.41> Y*o*u*m*a*y*n*o*t*c*o*p*y,m*o*d*i*f*y,s*u*b*l*i*c*e*n*s*e,o*r*d*i*s*t*r*i*b*u*t*e*t*h*e*D*o*c*u*m*e*n*t*e*x*c*e*p*t*a*s*e*x*p*r*e*s*s*l*y*p*r*o*v*i*d*e*d*f*o*r*u*n*d*e*r*t*h*i*s*L*i*c*e*n*s*e.A*n*y*o*t*h*e*r*a*t*t*e*m*p*t*t*o*c*o*p*y,m*o*d*i*f*y,s*u*b*l*i*c*e*n*s*e*o*r*d*i*s*t*r*i*b*u*t*e*t*h*e*D*o*c*u*m*e*n*t*i*s*v*o*i*d,a*n*d*w*i*l*l*a*u*t*o*m*a*t*i*c*a*l*l*y*t*e*r*m*i*n*a*t*e*y*o*u*r*r*i*g*h*t*s*u*n*d*e*r*t*h*i*s*L*i*c*e*n*s*e.H*o*w*e*v*e*r,p*a*r*t*i*e*s*w*h*o*h*a*v*e*r*e*c*e*i*v*e*d*c*o*p*i*e*s,o*r*r*i*g*h*t*s,f*r*o*m*y*o*u*u*n*d*e*r*t*h*i*s*L*i*c*e*n*s*e*w*i*l*l*n*o*t*h*a*v*e*t*h*e*i*r*l*i*c*e*n*s*e*s*t*e*r*m*i*n*a*t*e*d*s*o*l*o*n*g*a*s*s*u*c*h*p*a*r*t*i*e*s*r*e*m*a*i*n*i*n*f*u*l*l*c*o*m*p*l*i*a*n*c*e. <\center> <\with|font-size|1.41> T*h*e*F*r*e*e*S*o*f*t*w*a*r*e*F*o*u*n*d*a*t*i*o*n*m*a*y*p*u*b*l*i*s*h*n*e*w,r*e*v*i*s*e*d*v*e*r*s*i*o*n*s*o*f*t*h*e*G*N*U*F*r*e*e*D*o*c*u*m*e*n*t*a*t*i*o*n*L*i*c*e*n*s*e*f*r*o*m*t*i*m*e*t*o*t*i*m*e.S*u*c*h*n*e*w*v*e*r*s*i*o*n*s*w*i*l*l*b*e*s*i*m*i*l*a*r*i*n*s*p*i*r*i*t*t*o*t*h*e*p*r*e*s*e*n*t*v*e*r*s*i*o*n,b*u*t*m*a*y*d*i*f*f*e*r*i*n*d*e*t*a*i*l*t*o*a*d*d*r*e*s*s*n*e*w*p*r*o*b*l*e*m*s*o*r*c*o*n*c*e*r*n*s.S*e*e*h*t*t*p://w*w*w.g*n*u.o*r*g/c*o*p*y*l*e*f*t/. E*a*c*h*v*e*r*s*i*o*n*o*f*t*h*e*L*i*c*e*n*s*e*i*s*g*i*v*e*n*a*d*i*s*t*i*n*g*u*i*s*h*i*n*g*v*e*r*s*i*o*n*n*u*m*b*e*r.I*f*t*h*e*D*o*c*u*m*e*n*t*s*p*e*c*i*f*i*e*s*t*h*a*t*a*p*a*r*t*i*c*u*l*a*r*n*u*m*b*e*r*e*d*v*e*r*s*i*o*n*o*f*t*h*i*s*L*i*c*e*n*s*e``o*r*a*n*y*l*a*t*e*r*v*e*r*s*i*o*na*p*p*l*i*e*s*t*o*i*t,y*o*u*h*a*v*e*t*h*e*o*p*t*i*o*n*o*f*f*o*l*l*o*w*i*n*g*t*h*e*t*e*r*m*s*a*n*d*c*o*n*d*i*t*i*o*n*s*e*i*t*h*e*r*o*f*t*h*a*t*s*p*e*c*i*f*i*e*d*v*e*r*s*i*o*n*o*r*o*f*a*n*y*l*a*t*e*r*v*e*r*s*i*o*n*t*h*a*t*h*a*s*b*e*e*n*p*u*b*l*i*s*h*e*d(n*o*t*a*s*a*d*r*a*f*t)b*y*t*h*e*F*r*e*e*S*o*f*t*w*a*r*e*F*o*u*n*d*a*t*i*o*n.I*f*t*h*e*D*o*c*u*m*e*n*t*d*o*e*s*n*o*t*s*p*e*c*i*f*y*a*v*e*r*s*i*o*n*n*u*m*b*e*r*o*f*t*h*i*s*L*i*c*e*n*s*e,y*o*u*m*a*y*c*h*o*o*s*e*a*n*y*v*e*r*s*i*o*n*e*v*e*r*p*u*b*l*i*s*h*e*d(n*o*t*a*s*a*d*r*a*f*t)b*y*t*h*e*F*r*e*e*S*o*f*t*w*a*r*e*F*o*u*n*d*a*t*i*o*n. <\bibliography|bib|plain|b*i*b*l*i*o> \; <\references> <\collection> |||\|||>>>|35>> |||\|||>>>|17>> > > > > > > |||\|||>>>|21>> > > |||\|||>>>|19>> > > > > |||\|||>>>|35>> > |4>> > > > > > > > > > > |5>> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > |||\|||>>>|29>> > |||\|||>>>|23>> |||\|||>>>|23>> |||\|||>>>|29>> |||\|||>>>|23>> |||\|||>>>|29>> |||\|||>>>|29>> > > |||\|||>>>|29>> |||\|||>>>|23>> > |||\|||>>>|29>> > > > > > > > > > > > > > > > > > > > > > > > > > > |||\|||>>>|19>> |||\|||>>>|21>> |||\|||>>>|26>> |||\|||>>>|26>> |||\|||>>>|26>> |||\|||>>>|20>> |||\|||>>>|40>> |||\|||>>>|28>> |||\|||>>>|17>> |||\|||>>>|20>> |||\|||>>>|20>> |||\|||>>>|17>> |||\|||>>>|16>> |||\|||>>>|22>> |||\|||>>>|20>> > > > > > > > > |||\|||>>>|13>> <\auxiliary> <\collection> <\associate|bib> stein:hecke magma cremona:algs cohen:course python serre:arithmetic serre:arithmetic serre:arithmetic serre:arithmetic serre:arithmetic serre:arithmetic serre:arithmetic serre:arithmetic iwaniec:topics serre:asymptotique serre:arithmetic lang:modular buzzard:t2 farmer-james:maeda cohen:course cohen:course cohen:course shoup:lower nechaev:lower gordon:dlog gordon:dlp cohen:course cohen:course hijikata:trace miyake shimura:intro shimura:intro cohen-oesterle:dimensions shimura:intro miyake diamond-im lang:modular atkin-lehner winnie:newforms csirik-wetherell-zieve:g0 cohen-oesterle:dimensions cohen-oesterle:dimensions cohen:course knuth2 knuth2 cohen:course merel:1585 mtt merel:1585 sokurov:shimura math252 manin:parabolic merel:1585 cremona:gammaone cremona:algs merel:1585 mazur:symboles merel:1585 cremona:algs basmaji:thesis merel:1585 knapp:elliptic merel:1585 merel:1585 cremona:algs birch:bsd manin:parabolic merel:1585 sokurov:shimura cremona:algs cremona:gammaone basmaji:thesis stein:phd agashe:phd diderot:thesis lemelin:dominic frey-muller dembele darmon-pollack mtt <\associate|idx> |> |> |> |> <\associate|toc> |math-font-series||Preface> |.>>>>|> |math-font-series||1Modular Forms of Level One> |.>>>>|> 1.1Basic Definitions |.>>>>|> 1.2Eisenstein Series and Delta |.>>>>|> 1.3Structure Theorem |.>>>>|> 1.4Hecke Operators |.>>>>|> 1.5The Victor Miller Basis |.>>>>|> 1.6Can One Compute the Coefficients of |\> in Polynomial Time? |.>>>>|> |math-font-series||2Dirichlet Characters> |.>>>>|> 2.1Representation and Arithmetic |.>>>>|> 2.2Algorithms |.>>>>|> 2.3Alternative Representations of Characters |.>>>>|> |math-font-series||3Modular Forms and Eisenstein Series ofHigher Level> |.>>>>|> 3.1Modular Forms of Higher Level |.>>>>|> 3.2Generalized Bernoulli Numbers |.>>>>|> 3.3Explicit Basis for the Eisenstein Subspace |.>>>>|> |math-font-series||4Computing Dimensions of Spaces of Modular Forms> |.>>>>|> 4.1Modular Forms for |\(N)> |.>>>>|> |4.1.1New and Old Subspaces |.>>>>|> > 4.2Modular Forms for |\(N)> |.>>>>|> 4.3Modular Forms with Character |.>>>>|> |math-font-series||5Linear Algebra> |.>>>>|> 5.1Echelon Form |.>>>>|> 5.2Echelon Forms over ||Q>> |.>>>>|> 5.3Polynomials |.>>>>|> |math-font-series||6Modular Symbols> |.>>>>|> 6.1Modular Symbols |.>>>>|> 6.2Manin Symbols |.>>>>|> |6.2.1Coset Representatives and Manin Symbols |.>>>>|> > |6.2.2Modular Symbols With Character |.>>>>|> > 6.3Hecke Operators |.>>>>|> |6.3.1General Definition of Hecke Operators |.>>>>|> > |6.3.2Hecke Operators on Manin Symbols |.>>>>|> > |6.3.3Remarks on Complexity |.>>>>|> > 6.4Cuspidal Modular Symbols |.>>>>|> 6.5The Pairing Between Modular Symbols and Modular Forms |.>>>>|> 6.6Examples |.>>>>|> 6.7A*p*p*l*i*c*a*t*i*o*n*s |.>>>>|> |6.7.1L*a*t*e*r*i*n*t*h*i*s*B*o*o*k |.>>>>|> > |6.7.2D*i*s*c*u*s*s*i*o*n*o*f*t*h*e*L*i*t*e*r*a*t*u*r*e*a*n*d*R*e*s*e*a*r*c*h |.>>>>|> > |math-font-series||7C*o*m*p*u*t*i*n*g*W*i*t*h*M*o*d*u*l*a*r*S*y*m*b*o*l*s> |.>>>>|> |math-font-series||8U*s*i*n*g*M*o*d*u*l*a*r*S*y*m*b*o*l*s*t*o*C*o*m*p*u*t*e*S*p*a*c*e*s*o*f*M*o*d*u*l*a*r*F*o*r*m*s> |.>>>>|> 8.1|q>-expansions of Newforms |.>>>>|> 8.2C*o*n*g*r*u*e*n*c*e*s |.>>>>|> |math-font-series||9P*e*r*i*o*d*M*a*p*p*i*n*g*s*A*s*s*o*c*i*a*t*e*d*t*o*N*e*w*f*o*r*m*s> |.>>>>|> 9.1C*o*m*p*l*e*x*P*e*r*i*o*d*M*a*p*p*i*n*g |.>>>>|> 9.2R*a*t*i*o*n*a*l*a*n*d*I*n*t*e*g*r*a*l*P*e*r*i*o*d*M*a*p*p*i*n*g |.>>>>|> 9.3S*p*e*c*i*a*l*V*a*l*u*e*s*o*f|L>-Functions |.>>>>|> |math-font-series||10M*o*d*u*l*a*r*C*u*r*v*e*s*a*n*d*A*b*e*l*i*a*n*V*a*r*i*e*t*i*e*s> |.>>>>|> 10.1M*o*d*u*l*a*r*C*u*r*v*e*s |.>>>>|> 10.2M*o*d*u*l*a*r*A*b*e*l*i*a*n*V*a*r*i*e*t*i*e*s |.>>>>|> 10.3T*h*e*B*i*r*c*h*a*n*d*S*w*i*n*n*e*r*t*o*n-D*y*e*r*C*o*n*j*e*c*t*u*r*e |.>>>>|> 10.4H*o*w*C*r*e*m*o*n*a*C*o*m*p*u*t*e*s*a*l*l*E*l*l*i*p*t*i*c*C*u*r*v*e*s*o*f*C*o*n*d*u*c*t*o*r|N> |.>>>>|> |math-font-series||11A*p*p*l*i*c*a*t*i*o*n:S*e*r*r*es*C*o*n*j*e*c*t*u*r*e> |.>>>>|> 11.1S*t*a*t*e*m*e*n*t*o*f*t*h*e*C*o*n*j*e*c*t*u*r*e |.>>>>|> 11.2D*e*t*e*r*m*i*n*i*n*g*I*r*r*e*d*u*c*i*b*i*l*i*t*y |.>>>>|> 11.3C*o*m*p*u*t*i*n*g*t*h*e*S*e*r*r*e*I*n*v*a*r*i*a*n*t*s |.>>>>|> 11.4F*i*n*d*i*n*g*t*h*e*N*e*w*f*o*r*m*s*t*h*a*t*G*i*v*e*R*i*s*e*t*o*a*R*e*p*r*e*s*e*n*t*a*t*i*o*n |.>>>>|> |math-font-series||12S*o*f*t*w*a*r*e*f*o*r*C*o*m*p*u*t*i*n*g*W*i*t*h*M*o*d*u*l*a*r*F*o*r*m*s> |.>>>>|> 12.1M*A*G*M*A |.>>>>|> 12.2P*y*t*h*o*n/M*A*N*I*N |.>>>>|> 12.3C*r*e*m*o*n*as*m*w*r*a*n*k |.>>>>|> 12.4H*E*C*K*E*C++L*i*b*r*a*r*y |.>>>>|> 12.5P*A*R*I/G*P*P*a*c*k*a*g*e |.>>>>|> |math-font-series||A*p*p*e*n*d*i*x:G*N*U*F*r*e*e*D*o*c*u*m*e*n*t*a*t*i*o*n*L*i*c*e*n*s*e> |.>>>>|> |math-font-series||Bibliography> |.>>>>|>