Description of the QuatGap file =================================== QuatGap is a GAP file for computations of analogues of the modular group arising from quaternion algebras over the Rational numbers. This is a first version, which may be incomplete and may contain bugs and errors. It may certainly be improved. Any suggestions and comments are welcome. The program can be used and changed freely. I cannot promise full support, and I will certainly not be able to support other peoples changes. Author: Assaf Wool email: assafwool@yahoo.com date: July 2004 1. GAP version -------------- The program was written using version 4.2 of GAP and known to work for version 4.3 as well. 2. General description ---------------------- The main data container is a global record variable called QuatGlob. The various functions read from and write to this variable, assuming the existence of certain data members when they are needed. It would be better to use the GAP built-in object oriented structures, and perhaps this will be done in a later stage when the need arises. The object of the program is to build a model for a Rational quaternion algebra with discriminant D and to find the group of units in a maximal order in terms of specific generators and a fundamental region for its action on the unit circle. I will give a description of the computation stages. The function createQuatObj is a "runner" function which runs all stages in the appropriate order. Its input is a discriminant D, which must be a positive square free number with an even number of prime divisors. At the end QuatGlob is filled with as much information as I can provide. 3. Algebra and maximal order ---------------------------- The function findOrderType(D) starts from a discriminant D and initializes QuatGlob with data about the model used for the algebra and the maximal order. The model used is of type B(-u,v), where u,v are positive integers. This is a quaternion algebra with basis <1,i,j,k> over the Rationals, satisfying i^2=-u, j^2=v, ij=-ji=k. QuatGlob.disc is the discriminant D, QuatGlob.u and QuatGlob.v are u and v defining the model. The function returns 0 if D is not a valid discriminant. The maximal order is described by QuatGlob.type. There are three types of orders used: type=1: <1,i,j,1/2(1+i+j+k)> type=2: <1,i,1/2(1+j),1/2(i+k)> type=3: <1,1/2(1+j),1/2(i+k),1/v(aj+k)> Type 3 occurs only when u=D, and the auxillary number a can be found in QuatGlob.aux (a satisfies a^2+D=0 mod v). QuatGlob.den is the maximal denominator of elements in the maximal order. It is 2 for types 1 and 2, and 2*v for type 3. QuatGlob.alg is the GAP quaternion algebra object for B(-u,v). QuatGlob.basis is the standard <1,i,j,k> basis for this algebra. A few geometric invariants of the Shimura curve defined by the algebra are calculated as well. QuatGlob.n2 is the number of 2-torsion points, QuatGlob.n3 the number of 3-torsion points. QuatGlob.twog is twice the genus, QuatGlob.vol is the hyperbolic volume. QuatGlob.numgen is the minimal number of generators needed for the group of units. 4. Group elements ----------------- The function findComplexNorms(U, max, min) finds all ways to represent integers n in the range min-max as n=x^2+Uy^2. The results are found in the lists QuatGlob.x, QuatGlob.y and QuatGlob.norm. These lists have equal length, and x[i] combines with y[i] to give the complex norm norm[i]. The norm list is sorted in ascending order. If min is zero the function starts the lists from scratch, otherwise it is assumed that the lists contain all values in the norm range of 0-(min-1) and the lists are extended. The function findQuatElem(V,type) finds elements of the unit group in the maximal order. It looks for pairs of norms in the norm list satisfying n1-V*n2=den^2. Using the associated values of x,y the element 1/den(x1+y1*i+x2*j+y2*k) may be in the unit group, if it satisfies the filter of being in the maximal order specified by the type. The elements found are stored in QuatGlob.elem as lists of 4 elements [a,b,c,d], ascending in the complex norm n2=c^2+ud^2. 5. Group generators ------------------- The function findQuatGenerators() finds a subset of the elements in QuatGlob.elem which is a potential generating set. The result is put in QuatGlob.gen. The function removes from the list of elements any g such that g=h1*h2 with h1 and h2 appearing earlier in the list - having a smaller "complex norm". Such elements are trivially redundant as generators. The remaining elements are some of the gluing transformations of the Ford region for the group, a fact that is handy later. When there are no torsion elements in the group, the list of generators is completed so that each element is paired with its geometric opposite, negating the coordinates of j and k. Note that all order types are invariant under this operation. Note also that the Ford region is also invariant, so this is still a list of gluing transformations. This is used later for finding a torsion element in the normalizer. The function arrangeGenerators() performs some "tidying up" operations on the generator list. The generators are sorted with respect to the argument of g(0). Generators are discarded from the list if their inverse is not on it (this can happen). Special care is taken for the case of u=1, this is the only case where an element of the group stabilizes 0 (the element is i of order 2). In this case generators g may be replaced by g*i so that both g(0) and g^{-1}(0) are in the same semicircle. The remaining list of (potential) generators is put in QuatGlob.gen replacing the previous list. Now the generators are in their GAP form as elements of QuatGlob.alg. The list QuatGlob.imap is the mapping of inverses, QuatGlob.imap[i] is the index of the inverse of the i-th generator. If u=1 the first generator is always i. 6. Relations ------------ The function findRelations() finds the relations that are satisfied by the generators in QuatGlob.gen. The method uses the fact that the generators are gluing transformations of the Ford region. Relations are then loops in the Cayley graph associated with this region, with the images of 0 as vertices and only using the generator subset for edges. A potential minimal loop can be described as a simple word in the generators (repeating in the case of a torsion relation). If such a word is the identity then it stands for a real relation. Otherwise the path is not closed in the graph. QuatGlob.rel holds the words in the generators that are potential relations or torsion elements, as lists of generator indices. QuatGlob.grel holds the quaternion element value of the words in QuatGlob.rel. If some value in QuatGlob.grel is not torsion or the identity the function returns 0. QuatGlob.tor2, QuatGlob.tor3 and QuatGlob.ng are the actual number of 2-torsion points, 3-torsion points and minimal generators found. If these values don't match the calculated numbers (n2,n3 and numgen) then the function returns 0. Otherwise it returns 1. In the runner function createQuatObj, if a value 0 is returned at this stage then there are not enough generators for the group. The maximal "complex norm" is doubled and the process starts again. 7. Minimal generators --------------------- The function reduceGens() uses the relations to reduce redundant generators. It locates generators that appear in identity (not torsion) relations, while their inverse appears in a different relations. Such a generator can be eliminated and then the process is repeated until there are no more redundancies left. At each stage the redundant generator with the highest "complex norm" is eliminated. QuatGlob.gen, QuatGlob.imap, QuatGlob.rel and QuatGlog.grel are updated. At the end there should be one identity surface relation if there is no torsion, or several torsion relations with no identity relation. 8. Fundamental region --------------------- The function findVertices() finds the vertices of a fundamental region whose gluing transformations are in QuatGlob.gen. For torsion relations the obvious choice of the invariant points of the relation and its cyclic conjugates are the only choice possible. For the case of one identity surface relation an initial point has to be chosen. We use the fact that in this case i is of positive norm, it normalizes the group and it it a 2-torsion element. By adding i to the group we get an overgroup of index 2 with torsion, and we use a torsion point other than 0 as a starting point. This point is found in the function findTorsionW(), which is used before reduction of elements. At this stage the relations and generators are symmetric with respect to the action of i. The function essentially adds i to the group and finds a torsion relation other than i itself. This procedure is not guaranteed to work. Even in the case of torsion relations, where there is only one choice possible for the vertices, it is possible that the resulting region is not a real polygon (intersecting edges) or not convex. There is a check at the end of the function to see if the vertices are oriented around the center in the same way as the generators. Since GAP does not allow easy treatment of algebraic numbers the vertices are just printed as strings. The notation S() is for square root. No attempt is made to write the value in reduced form. All vertices have the form r(a+bS(-u)), where r is some Real algebraic number, a and b are Rationals and u is QuatGlob.u. The index at the beginning points to the generator in QuatGlob.gen that glues the region to a neighbour, with a connecting edge to the right of the vertex (looking from 0). 9. Performance and implementation --------------------------------- The program was not written with maximal efficiency. For all discriminants below 100 this is not really a problem but for some discriminants above and close to 100 there is a real problem. I have some ideas that could greatly improve the situation, especially concerning the function findQuatElem. I leave this for later versions.