nLab continued fraction

Contents

Contents

Idea

A continued fraction (Kettenbrüche in German) is a finite or infinite expression of the form

x=a 0+b 1a 1+b 2a 2+b 3a 3+x = a_0 + \frac{b_1}{a_1 + \frac{b_2}{a_2 + \frac{b_3}{a_3 + \cdots}}}

with convergence under appropriate conditions. The most commonly used form is where b i=1b_i = 1 for all ii; such is called a regular continued fraction.

Every real number may be (more or less1) uniquely expressed as a finite or infinite regular continued fraction for which all the a ia_i are integers and a i>0a_i \gt 0 for i>0i \gt 0. The expression is an infinite continued fraction if and only if the real number is irrational, so that there is a bijection

×( +) +{irrationals}\mathbb{Z} \times (\mathbb{N}_+)^{\mathbb{N}_+} \to \{irrationals\}
(a 0;a 1,a 2,)x=a 0+1a 1+1a 2+1a 3+.(a_0; a_1, a_2, \ldots) \mapsto x = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \cdots}}}.

This is in fact a homeomorphism if we endow the left side with the product topology and the right side with the subspace topology, regarding the set of irrationals as a subset of the real line (with its standard topology). (The space of irrationals becomes in this way a kind of prototypical chaotic dynamical system, where the dynamics on the product space is given by a shift map.)

Coalgebraic formulation

We can describe the basic theory of continued fractions for real numbers in terms of dynamics of fractional linear transformations on the real projective line 1()\mathbb{P}^1(\mathbb{R}), with the point at infinity playing a special role. From an nPOV, it is useful to cast this in coalgebraic terms.

Let us denote by R\mathbf{R} the interval [1,][1, \infty] (considered as a subset of the projective line 1()\mathbb{P}^1(\mathbb{R})); if 1x<1 \leq x \lt \infty, we let fl(x)fl(x) be the floor of xx (the greatest integer such that fl(x)xfl(x) \leq x). We denote by +\mathbb{N}_+ the set of positive integers (so, excluding 00). Put 1={*}\mathbf{1} = \{\ast\}, and define a map

α:R1+R× +\alpha: \mathbf{R} \to \mathbf{1} + \mathbf{R} \times \mathbb{N}_+

where α(x)=((xfl(x)) 1,fl(x))\alpha(x) = ((x - fl(x))^{-1}, fl(x)) if x<x \lt \infty, and α()=*\alpha(\infty) = \ast. This defines a coalgebra of the functor F:SetSetF: Set \to Set defined by the formula

F(X)=1+X× +.F(X) = \mathbf{1} + X \times \mathbb{N}_+.

Let us define xRx \in \mathbf{R} to be rational if it is a quotient of two integers (including 00, so 1/0=1/0 = \infty is here considered “rational”). Define τ:RR\tau: \mathbf{R} \to \mathbf{R} by τ(x)=(xfl(x)) 1\tau(x) = (x - fl(x))^{-1} if x<x \lt \infty, and τ()=\tau(\infty) = \infty.

Lemma

An element xRx \in \mathbf{R} is rational if and only if there exists n0n \geq 0 such that τ n(x)=\tau^n(x) = \infty.

Proof

Only if: this is clear for x=x = \infty. Otherwise, write x=p/qx = p/q in lowest terms, so that p,q>0p, q \gt 0 and gcd(p,q)=1\gcd(p, q) = 1. We argue by strong induction on qq, where we have p=nq+rp = n q + r for which n=fl(p/q)n = fl(p/q) and 0r<q0 \leq r \lt q by the Euclidean algorithm. If r=0r = 0, then τ(x)=\tau(x) = \infty and we are done; otherwise τ(p/q)=q/r\tau(p/q) = q/r where q>r>0q \gt r \gt 0 and gcd(q,r)=1\gcd(q, r) = 1, whence τ n(q/r)=\tau^n (q/r) = \infty for some nn by inductive hypothesis, and then τ n+1(p/q)=\tau^{n+1}(p/q) = \infty.

If: argue by induction on the least nn such that τ n(x)=\tau^n(x) = \infty. If n=0n = 0, then x=τ 0(x)=x = \tau^0(x) = \infty is rational. Otherwise, we have

x=fl(x)+1/τ(x)x = fl(x) + 1/\tau(x)

and since τ n1(τ(x))=\tau^{n-1}(\tau(x)) = \infty, we have that τ(x)\tau(x) is rational by inductive hypothesis, and therefore xx is also rational.

Lemma

If (a 0,a 1,a 2,)( +) (a_0, a_1, a_2, \ldots) \in (\mathbb{N}_+)^{\mathbb{N}} is any sequence of positive integers, then there is a unique xRx \in \mathbf{R} such that a n=fl(τ n(x))a_n = fl(\tau^n(x)) for all n0n \geq 0. (This xx must be irrational by Lemma .)

Proof

In a nutshell, xx is given by the continued fraction

x=a 0+1a 1+1a 2+1a 3+x = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \cdots}}}

and so it is really only a matter of proving that this continued fraction converges, i.e., that its truncations p n/q n=[a 0,a 1,,a n]p_n/q_n = [a_0, a_1, \ldots, a_n], namely the rational numbers p n/q np_n/q_n with τ n+1(p n/q n)=\tau^{n+1}(p_n/q_n) = \infty and fl(τ k(p n/q n))=a kfl(\tau^k(p_n/q_n)) = a_k for 0kn0 \leq k \leq n, form a Cauchy sequence.

For a +a \in \mathbb{N}_+, let a:RRa \cdot -: \mathbf{R} \to \mathbf{R} denote the fractional linear transformation xa+1xx \mapsto a + \frac1{x}. We have

[a]=a,[a 0,a 1,,a n]=a 0[a 1,,a n][a] = a \cdot \infty, \qquad [a_0, a_1, \ldots, a_n] = a_0 \cdot [a_1, \ldots, a_n]

and since a:RRa \cdot -: \mathbf{R} \to \mathbf{R} is monotone decreasing, we have that a 0(a 1)a_0 \cdot (a_1 \cdot -) is monotone increasing. Thus some easy inductions establish

  • [a 0]<[a 0,a 1,a 2]<[a 0,a 1,a 2,a 3,a 4]<[a_0] \lt [a_0, a_1, a_2] \lt [a_0, a_1, a_2, a_3, a_4] \lt \ldots
  • [a 0,a 1]>[a 0,a 1,a 2,a 3]>[a 0,a 1,a 2,a 3,a 4,a 5]>[a_0, a_1] \gt [a_0, a_1, a_2, a_3] \gt [a_0, a_1, a_2, a_3, a_4, a_5] \gt \ldots
  • [a 0,,a 2n]<[a 0,,a 2n,a 2n+1][a_0, \ldots, a_{2n}] \lt [a_0, \ldots, a_{2n}, a_{2n+1}]

so that sup n[a 0,,a 2n]inf n[a 0,,a 2n+1]\sup_n [a_0, \ldots, a_{2n}] \leq \inf_n [a_0, \ldots, a_{2n+1}], and all that remains is to show lim m|p m/q mp m+1/q m+1|=0lim_{m\to \infty} {|p_m/q_m - p_{m+1}/q_{m+1}|} = 0.

In fact we have

|p mq mp m+1q m+1|=|p mq m+1p m+1q m|q mq m+1=1q mq m+1\left|\frac{p_m}{q_m} - \frac{p_{m+1}}{q_{m+1}}\right| = \frac{{|p_m q_{m+1} - p_{m+1}q_m|}}{q_m q_{m+1}} = \frac1{q_m q_{m+1}}

The second equation is proved by induction on the length jj of continued fraction representations [x 1,,x j][x_1, \ldots, x_j]. Put [a 1,,a m]=q mr m[a_1, \ldots, a_m] = \frac{q_m}{r_m} and [a 1,,a m+1]=q m+1r m+1[a_1, \ldots, a_{m+1}] = \frac{q_{m+1}}{r_{m+1}}, with all fractions in reduced form, and suppose as induction hypothesis that |q mr m+1q m+1r m|=1{|q_m r_{m+1} - q_{m+1}r_m|} = 1. The fractional linear transformation a 0a_0 \cdot -, being represented by the integral matrix

A 0=(a 0 1 1 0)A_0 = \left( \array{ a_0 & 1 \\ 1 & 0 }\right)

with determinant 1-1, takes (±1)(\pm 1)-determinant matrices to (±1)(\pm 1)-determinant matrices. In particular it takes the determinant of absolute value 11 on the left to one on the right,

(q m q m+1 r m r m+1)A 0(p m p m+1 q m q m+1),\left( \array{ q_m & q_{m+1} \\ r_m & r_{m+1} }\right) \; \; \stackrel{A_0}{\mapsto} \; \; \left( \array{ p_m & p_{m+1} \\ q_m & q_{m+1} }\right),

and this completes the induction.

Here p m=a 0q m+r m>2r mp_m = a_0 q_m + r_m \gt 2r_m and p m+1=a 0q m+1+r m+1>2r m+1p_{m+1} = a_0 q_{m+1} + r_{m+1} \gt 2r_{m+1}. Similarly, if

[a 2,,a m]=r ms m,[a 2,,a m+1]=r m+1s m+1,[a_2, \ldots, a_m] = \frac{r_m}{s_m}, \qquad [a_2, \ldots, a_{m+1}] = \frac{r_{m+1}}{s_{m+1}},

then q m>2s mq_m \gt 2s_m and q m+1>2s m+1q_{m+1} \gt 2s_{m+1}. Thus we have

  • |[a 2,,a m][a 2,,a m+1]|=1s ms m+1{|[a_2, \ldots, a_m] - [a_2, \ldots, a_{m+1}]|} = \frac1{s_m s_{m+1}}
  • [a 0,,a m][a 0,,a m+1]|=1q mq m+1<1(2s m)(2s m+1)=14s ms m+1{[a_0, \ldots, a_m] - [a_0, \ldots, a_{m+1}]|} = \frac1{q_m q_{m+1}} \lt \frac1{(2s_m)(2s_{m+1})} = \frac1{4s_m s_{m+1}}

so that by induction, |p 2m/q 2mp 2m+1/q 2m+1|14 m{|p_{2m}/q_{2m} - p_{2m+1}/q_{2m+1}|} \leq \frac1{4^m}, completing the proof that the infinite continued fraction converges.

Remark

It may be tempting to believe that this FF-coalgebra structure makes R\mathbf{R} the terminal coalgebra. That is unfortunately not correct because the coalgebra structure ξ:RF(R)\xi: \mathbf{R} \to F(\mathbf{R}) is not an isomorphism (it fails to be surjective because no element maps to (1,1,)(1, 1, \infty) under ξ\xi; this is the fact that the standard continued fraction for 22 is just 22 and not 1+1/11 + 1/1). However, below we will exhibit a different kind of coalgebra making half-open intervals a terminal coalgebra.

Topology of infinite continued fractions

Let I\mathbf{I} be the set of irrational elements xRx \in \mathbf{R}. The results above imply that I\mathbf{I} equipped with the map

II× +:xα((xfl(x)) 1,fl(x))\mathbf{I} \to \mathbf{I} \times \mathbb{N}_+: x \stackrel{\alpha}{\mapsto} ((x - fl(x))^{-1}, fl(x))

is a terminal coalgebra for the functor × +:SetSet- \times \mathbb{N}_+: Set \to Set, isomorphic to ( +) (\mathbb{N}_+)^{\mathbb{N}} under the coalgebra structure

( +) ( +) s,o( +) +1( +) × +.(\mathbb{N}_+)^{\mathbb{N}} \stackrel{(\mathbb{N}_+)^{\langle s, o\rangle}}{\to} (\mathbb{N}_+)^{\mathbb{N} + \mathbf{1}} \cong (\mathbb{N}_+)^\mathbb{N} \times \mathbb{N}_+.

Endow I\mathbf{I} with the subspace topology coming from R\mathbf{R} (as one-point compactification of [1,)[1, \infty)), and ( +) (\mathbb{N}_+)^{\mathbb{N}} with the topology of the product of countably many discrete spaces \mathbb{N}.

Lemma

The coalgebra isomorphism I( +) \mathbf{I} \to (\mathbb{N}_+)^{\mathbb{N}} is a continuous map.

Proof

It suffices to check that each composite

I( +) π n +\mathbf{I} \to (\mathbb{N}_+)^{\mathbb{N}} \stackrel{\pi_n}{\to} \mathbb{N}_+

is continuous. Following the notation τ(x)=(xfl(x)) 1\tau(x) = (x - fl(x))^{-1} above, this composite map is xfl(τ n(x))x \mapsto fl(\tau^n(x)), so it suffices to check that fl:I +fl: \mathbf{I} \to \mathbb{N}_+ is continuous, or in other words that

{xI:fl(x)=m}\{x \in \mathbf{I}: fl(x) = m\}

is open for every mm. This set is clearly open, being the intersection (m,m+1)I(m, m+1) \cap \mathbf{I} (noting that of course mIm \notin \mathbf{I}!).

Lemma

The coalgebra isomorphism ψ:( +) I\psi: (\mathbb{N}_+)^{\mathbb{N}} \to \mathbf{I} is continuous.

Proof

This merely says that for each sequence of positive integers (a 0,a 1,)(a_0, a_1, \ldots) and for a given ϵ>0\epsilon \gt 0, that there exists NN such that |ψ(a 0,a 1,)ψ(b 0,b 1,)|<ϵ{|\psi(a_0, a_1, \ldots) - \psi(b_0, b_1, \ldots)|} \lt \epsilon provided a i=b ia_i = b_i for i=0,,Ni = 0, \ldots, N. But this just follows the proof of convergence of continued fractions given in the proof of Lemma .

Corollary

The coalgebra isomorphism ψ\psi is a homeomorphism.

This makes the space of irrationals I\mathbf{I} the terminal coalgebra for the endofunctor × +:TopTop- \times \mathbb{N}_{+}: Top \to Top.

Examples and further results

Example

A continued fraction [a 0,a 1,][a_0, a_1, \ldots] is periodic, i.e., satisfies a i=a k+ia_i = a_{k+i} for some fixed kk and all ii, only if it is the root of a quadratic equation a 0(a 1(a k1x))=xa_0 \cdot (a_1 \cdot \ldots (a_{k-1} \cdot x)\ldots ) = x (where the operator on the left can be written as a fractional linear transformation). Every quadratic irrational is eventually periodic (i.e., for some kk and NN we have a i=a k+ia_i = a_{k+i} for all iNi \geq N): the proof is part of the theory of Pell's equation?.

This example shows that periodic points are dense in the discrete dynamical system α 1:I× +I\alpha^{-1}: \mathbf{I} \times \mathbb{N}_+ \to \mathbf{I}, since quadratic surds are dense among all irrationals.

Part of the story of Pell’s equation is that an integer solution to x 2Dy 2=±1x^2 - D y^2 = \pm 1, with DD is a square-free integer, is a pair (x,y)=(p,q)(x, y) = (p, q) where p/qp/q is a reduced form fraction (a rational approximant) represented by a finite truncation of the continued fraction of D\sqrt{D}.

Example

The quadratic irrational represented by [1,1,1,][1, 1, 1, \ldots] is the golden ratio Φ=12(1+5)1.618\Phi = \frac1{2}(1 + \sqrt{5}) \approx 1.618\ldots. Many properties of this constant (as manifested both mathematically and physically) are due to this fact and the fact that of all infinite continued fractions, the convergence rate of its rational approximants is slowest for this number.

Remark

Were the Pythagoreans the first to do coalgebra? John Baez remarks in Week 265 that the Pythagoreans were fascinated by pentagrams, and drops hints that they may have been aware of the continued fraction for the golden ratio and also the fact that Φ\Phi is irrational. The Pythagorean pentagram on display in Baez’s page clearly indicates an infinite stream of pentagons which can be viewed as a coalgebraic behavior stream. And indeed if Φ\Phi were a rational number p/qp/q with p,qp, q as small as possible, then we would also have Φ=q/(pq)\Phi = q/(p-q), with numerator and denominator even smaller, contradiction. This is analogous to one of the famous proofs of irrationality of 2\sqrt{2}: if 2=p/q\sqrt{2} = p/q, then also 2=(2qp)/(pq)\sqrt{2} = (2q - p)/(p-q), which generates an infinite descending stream of positive numerators and denominators, contradiction.

Example

The continued fraction for Euler's number e is given by

[2,1,2,1,1,4,1,1,6,1,1,8,].[2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, \ldots].

A proof may be found here.

Example

The regular continued fraction for Ludolph's number π\pi displays no regularity, but other types of continued fractions do. See Wikipedia.

The popularity of certain rational approximations to pi such as 227\frac{22}{7} or 355113\frac{355}{113} can be explained by the fact that these are rational approximants obtained by truncating the regular continued fraction for π\pi, coupled with the following result.

Theorem

The truncation p/q=[a 0,a 1,,a n]p/q = [a_0, a_1, \ldots, a_n] is a “best” rational approximant to the irrational number β=[a 0,a 1,]\beta = [a_0, a_1, \ldots], in the sense that it minimizes the distance to β\beta among all rational numbers r/sr/s whose denominators ss are less than or equal to qq.

The space of irrationals I\mathbf{I} may be identified with the space of irrationals in the interval (0,1)(0, 1) (by taking their reciprocals). Here the action α 1:Irr(0,1)×Irr(0,1)\alpha^{-1}: Irr(0, 1) \times \mathbb{N} \to Irr(0, 1) is generated by the shift map τ:xx 1mod1\tau: x \mapsto x^{-1} \; mod \; 1.

Theorem

The map τ\tau is topologically mixing. Moreover, if Irr(0,1)Irr(0, 1) is equipped with the probability measure

μ(I)=1log2 Idx1+x,\mu(I) = \frac1{\log 2} \int_I \frac{d x}{1+x},

then τ\tau is an ergodic transformation? with respect to μ\mu, making (Irr(0,1),τ,μ)(Irr(0, 1), \tau, \mu) an ergodic system.

A proof may be found here.

Reals as terminal coalgebra

Returning to the theme of coalgebras, an alternative form of continued fractions may be used to exhibit a half-open real interval as a terminal coalgebra. The alternative continued fractions are of the form

x=a 01a 11a 21a 3x = a_0 - \frac{1}{a_1 - \frac{1}{a_2 - \frac{1}{a_3 - \cdots}}}

where the a ia_i are suitable integers; for now we will call them antiregular continued fractions (not knowing what others call them), or acf’s for short. These acf’s correspond to fractional linear transformations belonging to PSL 2()PSL_2(\mathbb{Z}), generated by the transformations z1/zz \mapsto -1/z, zznz \mapsto z-n.

Consider the linear order 1\mathbb{R}_{\geq 1} (this time excluding \infty); let β(x)\beta(x) be the smallest integer strictly greater than xx.

Consider the endofunctor GG on the category of linearly ordered sets XX where G(X)G(X) is the set ×X\mathbb{N} \times X equipped with the ordinal product or lexicographic order. (Actually we replace \mathbb{N} with the set of integers greater than or equal to 22.) Define a map

ξ: 1 2× 1\xi: \mathbb{R}_{\geq 1} \to \mathbb{N}_{\geq 2} \times \mathbb{R}_{\geq 1}

where ξ(x)=(β(x),1xβ(x))\xi(x) = (\beta(x), -\frac1{x - \beta(x)}).

Theorem

(Pavlovic-Pratt) The map ξ\xi defines a GG-coalgebra structure ξ: 1G( 1)\xi: \mathbb{R}_{\geq 1} \to G(\mathbb{R}_{\geq 1}), making 1\mathbb{R}_{\geq 1} the terminal GG-coalgebra.

Rationals as initial algebra

Now let Q={r:r>1}{}\mathbf{Q} = \{r \in \mathbb{Q}: r \gt 1\} \cup \{\infty\}, the set of rational elements of R\mathbf{R}. On the category of linear orders, let HH be the endofunctor H(X)=G(X)+1H(X) = G(X) + 1, the ordinal sum where GG was defined above.

The initial HH-algebra is the free monoid + *\mathbb{N}_+^\ast, lexicographically ordered according to the convention given in this remark (where initial segments of words ww are greater than ww).

On the other hand, we have an HH-algebra structure on \mathbb{Q}, a function

ξ:( +×Q)+1Q\xi:\; (\mathbb{N}_+ \times \mathbf{Q}) + 1 \to \mathbf{Q}

where for *1\ast \in 1, ξ(*)=\xi(\ast) = \infty, otherwise ξ(n,r)=n+11/r\xi(n, r) = n+1-1/r. Observe that this is indeed a monotone map between the linear orders H(Q)QH(\mathbf{Q}) \to \mathbf{Q}.

Theorem

(Q,ξ)(\mathbf{Q}, \xi) is the initial HH-algebra.

The inverse map ξ 1:QH(Q)\xi^{-1}: \mathbf{Q} \to H(\mathbf{Q}) is in essence another form of the acf (see above): if ceil(s)ceil(s) denotes the least integer greater than or equal to ss, then ξ 1()=*\xi^{-1}(\infty) = \ast, and otherwise

ξ 1(r)=(ceil(r)1,1/(rceil(r)).\xi^{-1}(r) = (ceil(r) - 1, -1/(r - ceil(r)).

The HH-algebra isomorphism + *Q\mathbb{N}_+^\ast \to \mathbf{Q} takes a finite word a 0a 1a na_0 a_1 \ldots a_n to the rational number to which the acf

a 0+11a 1+11a 2+11a 3+1a_0 + 1 - \frac{1}{a_1 + 1 - \frac{1}{a_2 + 1 - \frac{1}{a_3 + 1 - \cdots}}}

evaluates.

Rational tangles

Among the many uses of continued fractions, we mention a quite remarkable one due to John H. Conway.

Definition

A rational tangle is a subspace TT of the 3-disk D 3D^3 obtained by embedding two arcs

(α 1,α 2):I+ID 3,(\alpha_1, \alpha_2): I + I \to D^3,

with endpoints on the boundary D 3\partial D^3, such that the pair of spaces (D 3,T=α 1(I)+α 2(I))(D^3, T = \alpha_1(I) + \alpha_2(I)) is homeomorphic to the pair (D 2×I,{x,y}×I)(D^2 \times I, \{x, y\} \times I), with x,yD 2x, y \in D^2 distinct points. Two rational tangles S,TS, T are isotopic if there exists an orientation-preserving homeomorphism (D 3,S)(D 3,T)(D^3, S) \to (D^3, T) that is the identity on D 3\partial D^3.

Conventionally, rational tangles (or more general 2-tangles) are exhibited by tangle diagrams placed within a disk (with appropriate over- and under-crossings), say a unit disk |z|1{|z|} \leq 1 in the complex plane, with endpoints situated at primitive 8 th8^{th} roots of unity exp((2k+1)iπ/8)\exp((2k+1)i\pi/8); these endpoints are indicated by their directions NE, NW, SW, SE. There is a trivial 2-tangle with a chord from NE to NW and another from SE to SW; this is denoted [0][0]. Two operations that can be used to generate further 2-tangles are

  • “Turn” (rotate the disk through 90 degrees counterclockwise),

  • “Twist” (insert a “horizontal” twist that interchanges NE and SE, which can be a positive twist or a negative twist depending on convention).

Theorem

(Conway) The set of isotopy classes of rational tangles is in bijection with the set of rational elements q{}q \in \mathbb{Q} \cup \{\infty\}, in such a way that if [q][q] is the isotopy class corresponding to qq, then [1/q][-1/q] is the class corresponding to a turn of [q][q], and [1+q][1+q] is the class corresponding to a positive twist of [q][q].

In particular, every rational tangle can be brought back to the trivial tangle [0][0] by a series of (positive) twists and turns, and every rational tangle is isotopic to the tangle obtained by applying a 180 degree counterclockwise turn to it. A very readable account of this result may be found in an article by Kauffman and Lambropoulou, here.

It should be remarked that the twist and turn operations correspond to group elements in PSL 2()PSL_2(\mathbb{Z}) (cf. the article Moebius transformation, in particular the remarks on the surjective homomorphism B 3PSL 2()B_3 \to PSL_2(\mathbb{Z}) where B 3B_3 is the braid group on 33 strands):

turn=(0 1 1 0),pos.twist=(1 1 0 1)turn = \left( \array{ 0 & 1 \\ -1 & 0 }\right), \qquad pos.twist = \left( \array{ 1 & 1 \\ 0 & 1 }\right)

John Baez asks a question about this in TWF228, and reports on an answer in TWF229. He returns to this topic in an illuminating comment here.

David Corfield speculates at the Café that the infinite tangles mentioned by Kauffman and Lambropoulou, as limits of rational tangles, might be viewed as belonging to a coalgebraic completion of the collection of rational tangles (along the lines of seeing the terminal coalgebra R\mathbf{R} as a coalgebraic completion of the initial algebra Q\mathbf{Q}, as in Theorem ).

The Calkin-Wilf and Stern-Brocot trees

The Calkin-Wilf tree is an infinite complete binary tree whose vertices are in 1-to-1 correspondence with the positive rational numbers. The tree may be defined inductively by the following very simple recipe (Calkin & Wilf, 2000):

  • 1/11/1 is at the top of the tree, and
  • each vertex i/ji/j has two children: its left child is i/(i+j)i/(i+j) and its right child is (i+j)/j(i+j)/j

For example, the first four levels of the Calkin-Wilf tree are:

1/11/21/31/44/33/23/55/22/12/32/55/33/13/44/1 \frac{1/1}{ \frac{1/2}{ \frac{1/3}{1/4\quad 4/3} \quad \frac{3/2}{3/5\quad 5/2}} \quad \frac{2/1}{ \frac{2/3}{2/5\quad 5/3} \quad \frac{3/1}{3/4\quad 4/1}}}

Remarkably, every positive rational number appears exactly once in the tree, and so performing a breadth-first traversal (1/1,1/2,2/1,1/3,3/2,1/1, 1/2, 2/1, 1/3, 3/2, \dots) gives an enumeration of the positive rationals with no double-counting. In fact, Calkin and Wilf proved that the nnth number in this sequence is equal to

b(n)b(n+1)\frac{b(n)}{b(n+1)}

where b(n)b(n) is the number of ways of writing the integer nn as a sum of powers of 2, each power being used at most twice.

By locating a positive rational qq in the Calkin-Wilf tree and describing the path to qq from the root as a sequence of binary choices, one generates a string of bits which may be interpreted as an “uncompressed” representation of the continued fraction of qq. In turn, compressing this path by counting the number of repeated bits (i.e., by performing a “run-length encoding”) is a way of reconstructing the continued fraction. This is perhaps easier to see if we first express the two operations returning the left and right children of a vertex xx equivalently as

L(x) =11+1x R(x) =1+x \begin{aligned} L(x) &= \frac{1}{1 + \frac{1}{x}} \\ R(x) &= 1 + x \end{aligned}

from which it follows that

L a(x) =1a+1x R a(x) =a+x \begin{aligned} L^a(x) &= \frac{1}{a + \frac{1}{x}} \\ R^a(x) &= a + x \end{aligned}

Now, suppose a positive rational qq has continued fraction [a 0,,a n][a_0,\dots,a_n], assuming without loss of generality that nn is odd (we allow for a n=1a_n = 1). Then the path from 1 to qq in the Calkin-Wilf tree begins by taking a n1a_n - 1 steps to the left, followed by a n1a_{n-1} steps to the right, a n2a_{n-2} steps to the left, and so on, ending with a 0a_0 steps to the right. In other words,

q=R a 0L a 1R a n1L a n11q = R^{a_0}L^{a_1}\dots R^{a_{n-1}} L^{a_n-1} 1

For example:

2/5 =LLR(1)=12+11+1 12/7 =RLRRL(1)=1+11+12+11+11 \begin{aligned} 2/5 & = LLR(1) = \frac{1}{2 + \frac{1}{1 + 1}} \\ 12/7 &= RLRRL(1) = 1 + \frac{1}{1 + \frac{1}{2 + \frac{1}{1 + \frac{1}{1}}}} \end{aligned}

Finally, the Calkin-Wilf tree gives a simple algebraic characterization of the positive rationals, namely as an initial object in the category of pointed modules for the free monoid on two elements {L,R}\{L,R\}. Given any such module XX and point xXx \in X, there is a unique module homomorphism +X\mathbb{Q}^+ \to X sending 11 to xx, defined as follows: given a positive rational qq, locate qq on the Calkin-Wilf tree, and then retrace the path from 11 to qq in XX, beginning at xx and applying the actions L:XXL : X \to X and R:XXR : X \to X as appropriate.

The Calkin-Wilf tree was first described in a 2000 paper by Neil Calkin and Herbert Wilf, “Recounting the rationals”, but is closely related to the much older Stern-Brocot tree, another arrangement of the positive rationals with the special property that the values are ordered from left to right. Here are the first four levels of the Stern-Brocot tree:

1/11/21/31/42/52/33/53/42/13/24/35/33/15/24/1 \frac{1/1}{ \frac{1/2}{ \frac{1/3}{1/4\quad 2/5} \quad \frac{2/3}{3/5\quad 3/4}} \quad \frac{2/1}{ \frac{3/2}{4/3\quad 5/3} \quad \frac{3/1}{5/2\quad 4/1}}}

In fact, each tree may be obtained from the other by reversing the paths from the root (e.g., 2/5=LLR(1)2/5 = LLR(1) is reached from the root of the Stern-Brocot tree by going down left twice and then right once).

Constructive aspects

The construction of a continued fraction from an arbitrary real number relies on the limited principle of omniscience to define the floor; it is not acceptable in constructive mathematics. Nevertheless, using the usual constructive meaning of rational number and irrational number (as well as convergence in the real numbers), we have that a continued fraction (involving natural numbers) represents a rational number iff it is finite and an irrational number iff it is infinite; and every rational or irrational number (if positive) is so representable. Constructively, we simply cannot say that every real number is either rational or irrational.

Now, just because a real number has an expansion as a continued fraction, that doesn't mean that it must be rational or irrational. In general, a continued fraction expansion (according to the coalgebraic formulation) is given by a stream of natural numbers, and a stream is not necessarily finite (so a list) or infinite (so a sequence). However, a stream that is not finite must be infinite; accordingly, a real number that is not rational must be irrational if it has a continued fraction; even this is not constructively valid without the continued fraction.

References

  • Wikipedia, Continued fraction

  • Claude Brezinski, Continued fractions and Padé approximants, North-Holland 1991. (vendor)

  • A. Ya. Khinchin, Continued fractions, U. Chicago Press 1964.

  • Ilan Vardi, Continued fractions from Euclid to the present day, unpublished manuscript (web)

  • Louis Kauffman and Sofia Lambropoulou, On the classification of rational tangles, arXiv (web).

Dan Piponi wrote a series of posts on his blog “A Neighborhood of Infinity”, using the programming language Haskell to illustrate some of the connections between continued fractions, rational tangles and linear operators:

The material on half-open intervals as terminal coalgebras was first given by Pavlović and Pratt,

  • Dusko Pavlovic and Vaughan Pratt, On coalgebras of real numbers, Electronic Notes in Theoretical Computer Science, Volume 19 (1999), 103–117. (web)

A type-theoretic formalization of the rationals in Coq based on the Stern-Brocot/Calkin-Wilf representation is described in:

  • Milad Niqui and Yves Bertot, QArith: Coq Formalisation of Lazy Rational Arithmetic, INRIA report RR-5004, November 2003. (web)

Their library includes two implementations of the field operations: 1. a “strict” implementation (in the programming languages sense) in which the operations are performed by first converting continued fractions to ordinary fractions, applying the usual algorithms for arithmetic, and then converting back, and 2. a “lazy” implementation operating directly on continued fractions, in which the operations only need to inspect a portion of the input stream in order to determine a portion of the output stream. This latter approach is based on ideas originally due to Gosper:


  1. For rational numbers, there are two continued fraction representations, agreeing up to say a n1a_{n-1}, but ending with a n>1a_n \gt 1 in one case and a n1,a n+1=1a_n - 1, a_{n+1} = 1 in the other (since after all a n=(a n1)+1/1a_n = (a_n - 1) + 1/1). This can be an annoyance, but there are various workarounds.

Last revised on January 22, 2017 at 03:31:21. See the history of this page for a list of all contributions to it.