COMPLEX CONTINUED FRACTIONS: AN UNDERGRADUATE RESEARCH PROBLEM PROPOSAL

Timothy P. Keller

1. Motivation and Background. Continued fractions are a rich source for undergraduate research projects: appealing problems, easy to motivate by computational example, and amenable to solution by standard techniques. A good reference for the basic terminology and results is [2]. Before getting started, let’s review some of the basic material.

Given a positive real number r, there is a standard algorithm for computing the continued fraction expansion for r. Writing

r = a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2} + \frac{1}{a_{3} + \frac{1}{...}}}}

the integers a_{0}, a_{1}, … are generated by taking a_{0} = ⌊r⌋, z_{0} = r and for i > 0

\begin{aligned}z_{i+1} & = \frac{1}{z_{i} − a_{i}} , \\ a_{i+1} & = ⌊\frac{1}{z_{i+1}} ⌋, if z_{i+1} ≠ 0. \end{aligned}

The nth partial quotient is the rational number p_{n}/q_{n} given by

r = a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2} + \frac{1}{a_{3} + \frac{1}{... + \frac{1}{a_{n−1} + \frac{1}{a_{n}}}}}}} ,

which is compactly denoted by {a_{0}; a_{1}, …, a_{n}}.

One way to think about the continued fraction expansion of a real number r > 0 is to consider it as an extension of the Euclidean algorithm. If r is a rational number p/q, where p and q are positive integers with gcd(p, q) = 1, then the process given above terminates with a_{N+1} = 0 for some N, and p_{N} = p, q_{N} = q. The partial quotients satisfy p_{n+1}q_{n} − q_{n+1}p_{n} = (−1)^{n}, hence s = (−1)^{N}q_{N−1} and t = (−1)^{N}p_{N−1} are integers so that sp + tq = 1. If r > 0 is an irrational real, then no a_{i} is 0, but p_{n}/q_{n} → r as n → ∞.

To what extent can these ideas be generalized? A very general (and ambitious) investigation could start with an integral domain R, associated quotient field K and an algebraic extension L ⊇ K, equipped with a suitable topology. For convenience, the set of non–zero elements of a ring R will be denoted R^{∗}. If R is an integral domain, then an element c of R is a divisor of an element a of R, if there is an element b in R so that a = bc. An element c is a greatest common divisor of two elements a and b in R^{∗} if c is a common divisor of a and b and given any common divisor d of a and b, then d is a divisor of c. (Note gcd(a, b) is only defined up to associates, i.e. if u is a unit of R and d is a greatest common divisor of a and b, then ud is a greatest common divisor of a and b.) An integral domain R is a greatest common divisor domain, GCD domain for short, if gcd(a, b) exists for all a and b in R^{∗}. If R is a GCD domain, then it does not necessarily follow that there exist elements s and t in R so that sa + tb = gcd(a, b); if this latter property holds, one has what is called a Bezout domain [1]. The ring of integers is a Bezout domain and there is an algorithm for actually finding s and t: the well–known Euclidean algorithm. The Euclidean algorithm is a consequence of the property that given two integers with 0 < b ≤ a, there exist integers p and q so that a = bp + q and 0 ≤ q < b. That is, the integers are a Euclidean domain. In many ways the integers are the nicest of all possible domains; on the other hand, it’s hard to see how to generalize an idea starting with just one example.

Fortunately, there is another ‘nice’ example to consider. The set of Gaussian integers, that is the set of complex numbers ℤ[i] = {x + yi|x and y are integers }, is also a Euclidean domain in the sense that, if | · | is the usual complex norm, then given Gaussian integers a and b with 0 < |b| ≤ |a|, then there are Gaussian integers p and q so that a = bp + q and 0 ≤ |q| < |b|. To say that a complex number z has a continued fraction expansion would mean that there exist Gaussian integers a_{0}, a_{1}, … so that the corresponding partial quotients converge to z in the topology on ℂ associated with the complex norm | · |. It would be interesting to investigate whether such an expansion exists; and, given the existence of the expansion, it would be even more interesting to describe an algorithm for actually finding the Gaussian integers a_{0}, a_{1}, . . .. This could be a good undergraduate research project. In what follows, some ideas will be presented and discussed that might help initiate such an undergraduate research project.

2. Extending the Greatest Integer Function. To begin our attempt at finding an algorithm that given z ∈ ℂ^{∗} constructs Gaussian integers a_{0}, a_{1}, … so that p_{n}/q_{n} → z as n → ∞, we proceed by analogy with the real case and look for the appropriate analogy to the greatest integer function. That is, a function G: ℂ → ℤ[i] so that for z in ℤ[i], G(z) = z. After having decided on the function G, the proposed algorithm is the same as the algorithm in the real case, except that G takes the place of ⌊·⌋.

Reviewing the proofs for some of the basic results found in [2], it is found that many of them generalize to the complex case with very little change, and with no restriction on the choice of the function G. In particular,

\underline{Proposition 1}.
p_{n} = a_{n}p_{n−1} + p_{n−2} and q_{n} = a_{n}q_{n−1} + q_{n−2}

for n > 0, where p_{−1} = 1, q_{−1} = 0 and p_{0} = 0, q_{0} = 1 in the case |z| < 1.

(This result greatly simplifies the computation of the partial quotients.)

\underline{Proposition 2}. For n > 0,

p_{n+1}q_{n} − q_{n+1}p_{n} = (−1)^{n}.

\underline{Proposition 3}. If z is irrational, then for all n, one may find a complex number z_{n+1} so that

z = \{a_{0}; a_{1}, …, a_{n}, z_{n+1}\} and z − \frac{p_{n}}{q_{n}} = \frac{(−1)^{n}}{q_{n}(q_{n}z_{n+1} + q_{n−1})}.

One candidate for such a function is G(x + yi) = ⌊x⌋ + ⌊y⌋i. Note that for a real number r, |r − ⌊r⌋| < 1, but |G(z) − z| > 1 is certainly possible for some non–real z. One could consider the function H defined by

H(z) = \{ \begin{matrix}⌊z⌋, & if Im (z) = 0 \\ w ∈ ℤ[i]^{∗} so that |z − w| is smallest, & if Im (z) ≠ 0. \end{matrix}

In the second case, there may be ties for the role of w so that |z − w| is smallest; so in that event, choose among the w’s so that Re (w) is smallest. If that doesn’t break the tie, then take the w so that Im (w) is as small as possible.

Consider some sample computations using G and H.

3. Some Computations.

\underline{Using G}. Let’s try computing a continued fraction expansion for z = \sqrt{2}+\sqrt{3}i. Using the function G, one computes the a_{i}’s and the partial quotients for z − a_{0} to be:

Table 1.

p_{−1} = 1  q_{−1} = 0
a_{0} = 1 + i  p_{0} = 0  q_{0} = 1
a_{1} = i  p_{1} = 1  q_{1} = −2i  |q_{1}|^{2} = 4
a_{2} = −i  p_{2} = −i  q_{2} = −1  |q_{2}|^{2} = 1
a_{3} = 1 − i  p_{3} = −i  q_{3} = −1 − i  |q_{3}|^{2} = 2
a_{4} = 1 − i  p_{4} = −1 − 2i  q_{4} = −3  |q_{4}|^{2} = 9
a_{5} = i  p_{5} = −4 + i  q_{5} = −1 + 5i  |q_{5}|^{2} = 26
a_{6} = −i  p_{6} = 2i  q_{6} = 2 + i  |q_{6}|^{2} = 5
a_{7} = 2 − i  p_{7} = −2 + 5i  q_{7} = 4 + 5i  |q_{7}|^{2} = 41
a_{8} = 19 − 41i p_{8} = 167 + 160i  q_{8} = 283 − 68i  |q_{8}|^{2} = 84713

and so on . . ..

Note that a_{0} + p_{8}/q_{8} ≈ 1.414634 + 1.731707i, which is actually a ray of false hope for convergence: a_{0} + p_{9}/q_{9} ≈ 1.429462 + 1.668563i, which is further from z than a_{0} + p_{8}/q_{8}, and a_{31} + p_{31}/q_{31} ≈ 0.056528 + 0.977573i, — not at all close to \sqrt{2} + \sqrt{3}i.

Consider the proof given on p. 84 in [2] that for a real r > 0, the partial quotients converge to r. The key to the proof is that q_{n} → ∞ as n → ∞; since the q_{i}’s are integers, this follows from the earlier result that for all i, q_{i+1} > q_{i}. From Proposition 3, the proof of convergence then follows easily. Note that using the function G to generate the a_{i}’s does not produce a sequence of partial quotients so that |q_{i+1}| > |q_{i}|. Let’s try using H to generate the a_{i}’s.

\underline{Using H}. Let’s try computing a continued fraction expansion for z = \sqrt{2}+\sqrt{3}i again. Using the function H, one computes the a_{i}’s and the partial quotients for z − a_{0} to be:

Table 2.

p_{−1} = 1  q_{−1} = 0
a_{0} = 1 + 2i  p_{0} = 0  q_{0} = 1
a_{1} = 2 + i  p_{1} = 1  q_{1} = 2 + i  |q_{1}|^{2} = 5
a_{2} = −3 − i p_{2} = −3 − i  q_{2} = −4 − 5i  |q_{2}|^{2} = 41
a_{3} = −20 + 40i p_{3} = 101 − 100i  q_{3} = 282 − 59i  |q_{3}|^{2} = 83005
a_{4} = 4 − i  p_{4} = 300 − 502i  q_{4} = 1065 − 523i |q_{4}|^{2} = 1407754
a_{5} = 1 − 2i  p_{5} = −602 − 1204i q_{5} = 301 − 2712i |q_{5}|^{2} = 7445545
a_{6} = −3 − 2i p_{6} = −301 + 4314i q_{6} = −5262 + 7011i |q_{6}|^{2} = 76842765
a_{7} = 1 − 2i  p_{7} = 7725 + 3712i q_{7} = 9061 + 14823i |q_{7}|^{2} = 301823050
a_{8} = 1 − 2i  p_{8} = 14848 − 7424i q_{8} = 33445 + 3712i |q_{8}|^{2} = 1132346969

and so on . . ..

Note the values of |q_{i}| do seem to be increasing and

a_{0} + p_{8}/q_{8} ≈ 1.4142135623731 + 1.732050807569i

is fairly close to \sqrt{2} + \sqrt{3}i.

These calculations motivate two general questions:

\underline{Question 1}. Does the sequence of partial quotients obtained using H converge to z?

\underline{Question 2}. If the answer to question 1 is ‘no’, is there any function F, so that the sequence of partial quotients obtained using F converge to z?

\underline{References}

1. I. Kaplansky, Commutative Rings, University of Chicago Press, Chicago, 1974.

2. W. J. LeVeque, Elementary Theory of Numbers, Dover Publications, 1963.

Timothy P. Keller Department of Mathematics George Mason University Fairfax, VA 22030–4444 email: tkeller@nass.usda.gov

æ