From: greil@guug.de (Anton Greil)
Newsgroups: sci.math.research,comp.graphics.algorithms
Subject: a new (?) method of continued fractions for complex numbers
Date: Tue, 1 Feb 1994 20:06:46 +0100
Keywords: approximation of complex numbers by Gaussian numbers,
extended Stern-Brocot tree, smooth surfaces
Summary: I found a natural extension of the "Stern-Brocot number system"
(D.E. Knuth) to the (rational) Gaussian numbers.
I have found a new (?) method of continued fractions for the complex numbers.
Complex numbers are approximated here by Gaussian numbers.
This method is a natural extension of the "Stern-Brocot tree" for the
generation of the usual rational numbers, as shown in the textbook of
Donald E. Knuth et al., "Concrete Mathematics". Now all Gaussian numbers
of a quadrant of the complex plane can be listed in a 3-dim tree, where each
Gaussian number has its unique position and code.
"Natural extension" is meant from the viewpoint of hyperbolic geometry.
The "Stern-Brocot wreath" generates all rational numbers by two infinite
homogeneous binary trees, or equivalently by 2 free semigroups of rank 2:
If a(z),b(z),a'(z) and b'(z) denote the 4 Moebius transformations
a (z) := z+1, b (z) := z / (z+1)
a'(z) := z-1, b'(z) := z / (-z+1)
then a and b generate a free semigroup of rank 2, denoted by (a,b) ,
and a' and b' generate a free semigroup of rank 2, denoted by (a',b') .
Each positive rational number is the image f(1) of the number 1 under a unique
element f(z) from (a,b).
Each negative rational number is the image f(-1) of the number -1 under a
unique element f'(z) from (a',b').
For an extension of this matter to the Gaussian numbers, I regarded the two
semigroups as hyperbolic motions in the hypberbolic 2-space H_2, and their
role for a decomposition of the modular group PSL(2,Z).
This decomosition is the set partition:
PSL(2,Z) = (s) cup (a,b).(s) cup (a',b').(s) .
where "cup" stands for the union of sets, "." for the complex product, (a,b)
is the semigroup generated by a and b, and (s) is the semigroup generated by
s, which leads to a group of order 2. The Moebius transformation s(z) is
defined by: s(z) = -1/z .
In the extension to the Gaussian numbers the Picard group PSL(2,Z[i]) takes
over the role of PSL(2,Z), now as a discrete group of hyperbolic motions in H_3.
The Picard group generates the Gaussian numbers in the boundary of the H_3,
in an analogous way as the modular group generates the usual rational numbers
in the limit set of H_2. Both groups operate transitively on the resp. rational
numbers.
The analogous decomposition of the Picard group is:
PSL(2,Z[i]) = (s,t) cup (u^0)H(u^0)'.(s,t)
cup (u^1)H(u^1)'.(s,t)
cup (u^2)H(u^2)'.(s,t)
cup (u^3)H(u^3)'.(s,t)
Here H is the analogous semigroup, which must be also conjugated by the powers
of the element u(z) = iz, which is not an element of the Picard group but of
the group extension of PSL(2,Z[i]) by u. Thus the conjugations are outer
automorphisms of the Picard group. Here t(z) := 1/z .
The direct analogon for PSL(2,Z) is:
PSL(2,Z) = (s) cup (t^0)H(t^0)'.(s)
cup (t^1)H(t^1)'.(s)
with H = (a,b),
where t(z) = 1/z, is not an element of PSL(2,Z) but of PSL(2,Z[i]), and t(z)
operates by congujation as an outer automorphism on the modular group.
The semigroup H for PSL(2,Z[i]) is generated by 7 elements and is not a free
semigroup - the situation increases in complexity.
The 7 generators of the semigroup H are:
a: (1,1,0,1)
b: (1,0,1,1)
c: (1,i,0,1)
d: (1,0,-i,1)
e: ...
f: ...
g: ...
As already mentioned, this semigroup is not free upon these generators.
There are "relations", e.g. ac = ca, bd = db.
I have found a normalform for this semigroup and can encode now uniquely
(1) all elements of the Picard group,
according to the above decomposition.
(2) all Gaussian numbers.
Hereby each Gaussian number of the first quadrant is the image
under a unique element from H (in normalform) of one of the
numbers {1,i,1+i,(1+i)/2}.
From the last topic results a straight forward algorithm for the approximation
of the complex numbers by Gaussian numbers. This algorithm is a kind of
continued fractions, as the Stern-Brocot tree is a variant of the method
of the regular continued fractions.
Offer / application
-------------------
The above method of generating systematically all Gaussian numbers produces
all triples of (usual) integers (u,v,w), where u,v,w have the greatest
common divisor 1.
Or in other words:
All "rational directions" for lines, running through the vertices of a
3-dim grid of cubes, are generated systematically.
The Stern-Brocot tree solves the analogous problem for a 2-dim grid of
squares. D.E Knuth and J.D. Hobby have used this fact for constructing
optimal smooth fonts in a raster graphic system, published in their books
about the METAFONT system.
Therefore it can be expected, that this approximation technique can be lifted
to 3-dim raster grids, for defining or constructing smooth surfaces.
I'm a German mathematician and software engineer, and offer a further
professional study about the possibility of extending the approximation
to 3-D, based on my investigation and software so far.
I'd prefer to join a research organization for some time, to elaborate this
matter to a working method. Who is interested in such a subject ?
Anton Greil
Postbox 140 206 Phone 0049-89-268562
D-80452 Muenchen
Germany
greil@guug.de
==============================================================================
From: wolfskil@math.niu.edu (John Wolfskill)
Newsgroups: sci.math.numberthy
Subject: Anton Greil's complex continued fractions
Date: 2 Feb 94 14:22:17 GMT
Sender: owner-nmbrthry@VM1.NODAK.EDU
Anton Greil's continued fractions of complex numbers via Mobius maps defined
over Z[i] sounds like something I've seen before. There is a paper by Asmus
Schmidt in Acta Mathematica (Sweden) about 1975. The title of the paper is
"Diophantine approximation of complex numbers," or something pretty close to
that. I'm sorry I don't have the exact reference handy. Schmidt's work
is based on 7 special Mobius maps which transform the upper half-plane and a
companion triangular region in very nice ways. Corresponding to the regular
continued fraction of a real number, Schmidt describes what he calls regular
and dually regular chains of complex numbers. The digits in the chains are
formed from the 7 maps in a specific way. I refer you to Schmidt's paper
for the exact details.
John Wolfskill
DeKalb Illinois