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