From: greil@guug.de (Anton Greil)
Subject: Gauss Numbers: how to generate them ?
Keywords: modular group, Picard group, Moebius transformation, hyperbolic space
Organization: Technical University of Munich, Germany
Date: Fri, 4 Sep 1992 21:20:06 GMT



I suppose, that the following problem is already solved, perhaps in another
context. I'm not a professional researcher, but only fascinated by the question.

Background:
----------
The Modular Group acts discontinously on the hyperbolic plane, thus
creating a tesselation of this space. In the boundary of the hyperbolic
plane - for the half space model this is the completed real axis - all 
the rational numbers are created by the tessalation.

On this ground a process can be organized, which generates each positive
rational number exactly once. 
This beautiful procedure is named "Stern-Brocot tree" in
     R.L. Graham, D.E. Knuth, O. Patashnik: "Concrete Mathematics",
     Reading Mass. 1989, p.116-123, p.291-292.
and it is demonstrated there by elementary means.

The homogeneous binary tree of Stern-Brocot corresponds to the free semigroup
of rank two, where the free generators are two Moebius transformations t1, t2,
represented by the matrices

  m1:  (1  1)       m2:  (1  0)
       (0  1)            (1  1) .

Then each Moebius transformation from the generated semigroup maps the
number 1 to a different positive rational number; and each positive rational
number is obtained in this way (bijection).


Foreground:
----------
The Picard Group acts discontinously on the hyperbolic three-space, it is a
natural generalization of the Modular Group and it contains the Mod. Group.
Most works in a strong analogy: on the boundary of hyperbolic three-space
the Gauss numbers (as quotients of integer Gauss numbers) are created now
by the tessalation of the Picard Group. This analogy is discussed intensively
already in
    R. Fricke, F. Klein: "Vorlesungen ueber die Theorie der automorphen
    Funktionen", Leipzig 1897, Vol.1, p. 76-93.

Another reference is
    W. Magnus, "Noneuclidean Tesselations and Their Groups", New York 1974
    (there, on page 177, figure 18 visualizes the Stern-Brocot tree).


Problem:
-------
Is there a process, which generates each Gauss Number exactly once, in an
analogy to the Stern-Brocot tree ?  (that is: "as free as possible")

This seems to be equivalent to the question:

  Which semigroup is generated by the four Moebius transformations t1,t2,t3,t4
  (without their inverses and) represented by the matrices m1, m2, m3, m4 
  (where: "i" = imaginary unit)

    m1:  (1  1)       m2:  (1  0)      m3:  (1  i)       m4:  (1  0)
         (0  1)            (1  1)           (0  1)            (i  1)

How can this semigroup be composed, e.g. as a direct product, a free product 
with amalgamations or something else ?

There can be easily found some relations  ("13" stands for "t1*t3", etc.):
   13 = 31,  24 = 42,  143 = 432,  234 = 341,  343 = 434
   (34)**3 = (43)**3 = identity

Any hints for a solution would be welcome!

-------------

A further natural extension of the problem is:

  - how to generate all rational quaternions ?
  - how to generate all rational octaves (CAYLEY algebra) ?

as limit points of the hyperbolic spaces H^5 resp. H^9, created by the
reflections of the resp. regular polytope with all angles zero, corresponding
to the zero-angle tetrahedron in H^3.

-------------

Toni Greil, Muenchen (Germany)
greil@guug.de
Xref: sparky sci.math:11397 sci.math.num-analysis:2717