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.
Text file Source (historic): geocities.com/assafwool/Quat
geocities.com/assafwool(to report bad content: archivehelp @ gmail)
|
|
|
|
|