Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

September 6, 2020

Three Phases of Continued Fraction Theory

Posted by John Baez

I don’t know much about continued fractions yet, so it’s too early to be describing historical phases of work on the subject, but I can’t resist doing it. I’ll talk about three:

  • The Greeks
  • Euler
  • Gauss

I won’t talk about general theories of continued fractions, like their connection to Pell’s equation, Calkin–Wilf trees and rational tangles, or the line of work from Gauss to Khinchin and beyond on the statistical properties of the continued fractions of ‘typical’ numbers, or the work of Pavlovic and Pratt on a characterization of [0,)[0,\infty) as the terminal coalgebra of some endofunctor on the category of totally ordered sets, which uses continued fractions. Indeed, I will not even mention these things, fascinating though they are. Instead, I’ll only talk about continued fractions that can be evaluated to give famous numbers or functions.

The Greeks

The Greeks were fascinated by anthyphairesis, a technique that includes Euclid’s algorithm for finding the greatest common divisor of two natural numbers — an algorithm that predates Euclid — and which combined with a bit of geometry easily leads to results such as this:

5+12=1+11+11+11+11+11+11+11+11+11+11+11+ \frac{\sqrt{5} + 1}{2} = 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \ddots}}}}}}}}}}}

and this:

2=1+12+12+12+12+12+12+12+12+12+12+12+ \sqrt{2} = 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \ddots}}}}}}}}}}}

By thinking about these things, one can see that any number whose ‘regular’ continued fraction expansion with 1’s in all the numerators goes on forever must be irrational. It’s not clear whether the Greeks ever used this to prove the irrationality of these numbers.

Much later, in 1770, Lagrange showed that a number is the solution of a quadratic equation with rational coefficients if and only if its continued fraction expansion with all 1’s in the numerators is eventually periodic. This still has an ancient Greek feel to me. Here’s a nice example:

3=1+11+12+11+12+11+12+11+12+11+12+11+ \sqrt{3} = 1 + \frac{1}{1 + \frac{1}{2 + \frac{1}{1 + \frac{1}{2 + \frac{1}{1 + \frac{1}{2 + \frac{1}{1 + \frac{1}{2 + \frac{1}{1 + \frac{1}{2 + \frac{1}{1 + \ddots}}}}}}}}}}}

The square root of 3 is also called Theodorus’ constant because it was proved irrational by Theodosius of Cyene, a Libyan Greek mathematician, sometime in the 5th century BC.

Euler

Leonhard Euler wrote his first work on continued fractions, De fractionibus continuis dissertatio in 1737. Here’s an English translation:

I’ve read a bit of scholarship about this paper, and it seems he got into continued fractions by trying to solve some differential equations called Riccati equations. These are the next thing after first-order linear ordinary differential equations — they look like this:

dydx=f(x)y 2+g(x)y+h(x) \frac{d y}{d x} = f(x) y^2 + g(x) y + h(x)

If you do a change of variables here, applying a fractional linear transformation to yy, you get another Riccati equation! For this reason, it turns out, you can solve Riccati equations using continued fractions.

But the visible goal of Euler’s paper is rather different: it leads up to the first proof that the number ee is irrational, by showing

e=2+11+12+11+11+14+11+11+16+11+11+18+ e = 2 + \frac{1}{1 + \frac{1}{2 + \frac{1}{1 + \frac{1}{1 + \frac{1}{4 + \frac{1}{1 + \frac{1}{1 + \frac{1}{6 + \frac{1}{1 + \frac{1}{1 + \frac{1}{8 + \ddots}}}}}}}}}}}

This fraction has a rocky start, but then it follows a regular pattern. Since it’s not periodic, ee cannot be the solution of a quadratic equation with rational coefficients. Thus, neither ee nor e 2e^2 is rational!

In 1739 Euler wrote De fractionibus continuis observationes in 1739, which has a nice English translation:

Among other features, this paper derives the formula

ln2=11+1 21+3 21+5 21+7 21+9 21+11 21+13 21+15 21+17 21+19 21+ \ln 2 = \frac{1}{1 + \frac{1^2}{1 + \frac{3^2}{1 + \frac{5^2}{1 + \frac{7^2}{1 + \frac{9^2}{1 + \frac{11^2}{1 + \frac{13^2}{1 + \frac{15^2}{1 + \frac{17^2}{1 + \frac{19^2}{1 + \ddots}}}}}}}}}}}

and one I explained in a previous post

π4=11+1 22+3 22+5 22+7 22+8 22+9 22+10 22+ \frac{\pi}{4} = \frac{1}{1 + \frac{1^2}{2 + \frac{3^2}{2 + \frac{5^2}{2 + \frac{7^2}{2 + \frac{8^2}{2 +\frac{9^2}{2 +\frac{10^2}{2 +\ddots}}}}}}}}

He gave these formulas to illustrate a general method for turning infinite series into continued fractions, which he further propounded in his Introductio in analysin infinitorum in 1748. It’s called Euler’s continued fraction formula, and here it is:

a 0+a 0a 1+a 0a 1a 2++a 0a 1a 2a n= a_0 + a_0a_1 + a_0a_1a_2 + \cdots + a_0a_1a_2\cdots a_n = a 01a 11+a 1a 21+a 2a n11+a n1a n1+a n \frac{a_0}{1 - \frac{a_1}{1 + a_1 - \frac{a_2}{1 + a_2 - \frac{\ddots}{\ddots \frac{a_{n-1}}{1 + a_{n-1} - \frac{a_n}{1 + a_n}}}}}}\,

Applying this to the familiar series

ln2=1112+1314+1516+1718+19110+ \ln 2 = \frac{1}{1} - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + \frac{1}{5} - \frac{1}{6} + \frac{1}{7} - \frac{1}{8} + \frac{1}{9} - \frac{1}{10} + \cdots

and

π4=1113+1517+19111+113115+ \frac{\pi}{4} = \frac{1}{1} - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \frac{1}{9} - \frac{1}{11} + \frac{1}{13} - \frac{1}{15} + \cdots

we get the continued fractions shown above! It’s also really easy to use this method to get a different continued fraction for ee:

e=111213141516171819110111 e = \frac{1}{1 - \frac{1}{2 - \frac{1}{3 - \frac{1}{4 - \frac{1}{5 - \frac{1}{6 - \frac{1}{7 - \frac{1}{8 - \frac{1}{9 - \frac{1}{10 - \frac{1}{11 - \ddots}}}}}}}}}}}

But in all these cases we actually get much more: we get continued fraction expansions for the functions lnz\ln z, arctanz\arctan z and e ze^z — and making the right choice of zz we get our formulas for ln2\ln 2, 4/π4/\pi and ee, respectively. Indeed Euler’s formula gives nice continued fractions for all functions with simple Taylor series, as explained here.

Euler does much, much more! For example, besides showing

ln2= 0 1dx1+x 2=11+1 21+2 21+3 21+4 21+5 21+6 21+7 21+8 21+9 21+10 21+ \ln 2 = \int_0^1 \frac{d x}{1 + x^2} = \frac{1}{1 + \frac{1^2}{1 + \frac{2^2}{1 + \frac{3^2}{1 + \frac{4^2}{1 + \frac{5^2}{1 + \frac{6^2}{1 + \frac{7^2}{1 + \frac{8^2}{1 + \frac{9^2}{1 + \frac{10^2}{1 + \ddots}}}}}}}}}}}

he shows that similarly

0 1dx1+x n=11+1 2n+(n+1) 2n+(2n+1) 2n+(3n+1) 2n+(4n+1) 2n+(5n+1) 2n+(6n+1) 2n+(7n+1) 2n+(8n+1) 2n+9(n+1) 2n+ \int_0^1 \frac{d x}{1 + x^n} = \frac{1}{1 + \frac{1^2}{n + \frac{(n+1)^2}{n + \frac{(2n+1)^2}{n + \frac{(3n+1)^2}{n + \frac{(4n+1)^2}{n + \frac{(5n+1)^2}{n + \frac{(6n+1)^2}{n + \frac{(7n+1)^2}{n + \frac{(8n+1)^2}{n + \frac{9(n+1)^2}{n + \ddots}}}}}}}}}}}

And so on.

Gauss

In 1813 Gauss introduced ordinary hypergeometric functions in his paper Disquisitiones generales circa seriem infinitam 1+αβ1γx+α(α+1)β(β+1)12γ(γ+1)xx+etc.1 + \tfrac {\alpha \beta} {1 \cdot \gamma} x + \tfrac {\alpha (\alpha+1) \beta (\beta+1)} {1 \cdot 2 \cdot \gamma (\gamma+1)}x x + \text{etc.}. These are functions of one complex variable zz that also depends on 3 parameters called a,b,ca,b,c, so they’re written

2F 1(a,b;c;z) {}_2F_1(a,b;c;z)

I find these functions pretty intimidating, but apparently they have a nice explanation. Suppose you’re studying flat connections on a holomorphic 2\mathbb{C}^2 bundle over the Riemann sphere with 3 points removed. And suppose you’re looking for flat sections of such a bundle. Then you want ordinary hypergeometric functions! That’s what they are! For a tiny bit more detail, go here.

Anyway, these functions have Taylor series that aren’t too bad:

2F 1(a,b;c;z)=1+abc1!z+a(a+1)b(b+1)c(c+1)2!z 2+a(a+1)(a+2)b(b+1)(b+2)c(c+1)(c+2)3!z 3+. {}_2F_1(a,b;c;z) = 1 + \frac{a b}{c\,1!}z + \frac{a(a+1)b(b+1)}{c(c+1)\,2!}z^2 + \frac{a(a+1)(a+2)b(b+1)(b+2)}{c(c+1)(c+2)\,3!}z^3 + \cdots.

And Gauss worked out their continued fraction expansion:

2F 1(a+1,b;c+1;z)c 2F 1(a,b;c;z)=1c+(ac)bz(c+1)+(bc1)(a+1)z(c+2)+(ac1)(b+1)z(c+3)+(bc2)(a+2)z(c+4)+ \frac{{}_2F_1(a+1,b;c+1;z)}{c{}_2F_1(a,b;c;z)} = \frac{1}{c + \frac{(a-c)b z}{(c+1) + \frac{(b-c-1)(a+1) z}{(c+2) + \frac{(a-c-1)(b+1) z}{(c+3) + \frac{(b-c-2)(a+2) z}{(c+4) + {}\ddots}}}}}

This looks almost like something you could do using Euler’s continued fraction expansion together with a bit of extra algebraic fiddling — I should try it sometime.

Ordinary hypergeometric functions have a bunch of more familiar ‘elementary’ functions as special cases, so we can get some nice examples of continued fractions out of Gauss’ work. But some of these arise already from Euler’s continued fraction expansion without needing to think about hypergeometric functions. Here’s one that seems to require the hypergeometric function technology — I’m not completely sure:

tanhz=z1+z 23+z 25+z 27+z 29+z 211+z 213+ \tanh z = \frac{z}{1 + \frac{z^2}{3 + \frac{z^2}{5 + \frac{z^2}{7 +\frac{z^2}{9 +\frac{z^2}{11 +\frac{z^2}{13 + {}\ddots}}}}}}}

But I guess the main application of Gauss’ work is not to elementary functions!

Interestingly it seems Euler beat Gauss to some of these ideas, like the formula above.

Conclusion

My conclusion is that I should read Euler’s Observations on continued fractions before moving ahead. It’s packed with delights. These are also helpful:

Posted at September 6, 2020 12:26 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3251

6 Comments & 0 Trackbacks

Michael Weiss

About whether the Greeks used anthyphairesis to prove irrationality, B. L. Van der Walden speculated about this in his classic work Science Awakening (pp.141–145). His conjectures are based on Plato’s dialog Theaetetus, our main source of information about the pre-Euclidean theory of irrationals. Specifically this passage:

Here our Theodorus drew (or wrote) something about sides of squares and showed that those of three or five feet are not commensurable in length with those of one foot, and in this manner he took up one after another up to the one of 17 feet; here something stopped him (or: here he stopped).

van der Waerden’s theory is that Theodorus was using the criterion for incommensurability which later appeared in Euclid as Prop 2, Bk X: in modern terms, the non-termination of the continued fraction. This works all the way up to and including 17\sqrt{17} without too much rending of togas, but for 19\sqrt{19} it’s a pain. As van der Waerden puts it, “it requires a sequence of 6 proportions…each of which has to be proved by means of the calculation of areas. This makes it quite understandable why Theodorus closed his explanation with 17\sqrt{17}.”

Not an iron-clad argument, but the best we have, afaik.

Posted by: Michael Weiss on September 7, 2020 6:47 PM | Permalink | Reply to this

Re: Michael Weiss

Hi! Actually there’s another theory, which by some remarkable coincidence just heard about yesterday from the set theorist Andrés E. Caicedo in a remarkable series of tweets. I won’t give away what he said, but it’s not about continued fractions.

One funny thing about this other theory is that assumes 17\sqrt{17} is the first case Theodorus couldn’t do, not the last case he could do. Apparently the Greek in Plato’s Theaetetus is not crystal clear on that issue — I don’t know.

So, this theory is about why 17\sqrt{17} is hard to prove irrational, not why 19\sqrt{19} is hard.

Posted by: John Baez on September 7, 2020 11:15 PM | Permalink | Reply to this

Re: Michael Weiss

“In this manner he took up one after another, up to the one of 17 feet, whereupon he said, this is left as an exercise to the interested student.”

Posted by: Blake Stacey on September 8, 2020 3:54 AM | Permalink | Reply to this

Re: Three Phases of Continued Fraction Theory

The Advanced Encryption Standard’s security rests on the difficulty of solving certain generalized continued fractions in a finite field.

We therefore introduce a somewhat sloppy notation which clarifies the structure. We write K for any expanded key byte, with the understanding that the exact position of that key byte in the key schedule is known to us. All constants are written as C even though they might not be all the same value. We replace the remaining subscripts and powers by a *\ast. Again, each *\ast stands for a value that we can compute and that is independent of the plaintext and key…

a i,j (6)=K+ e 5 d 5𝒟CK *+ e 4 d 4𝒟CK *+ e 3 d 3𝒟CK *+ e 2 d 2𝒟CK *+ e 1 d 1𝒟CK *+p * *\displaystyle a_{i,j}^{(6)} = K + \sum_{\substack{e_5 \in \mathcal{E}\\d_5 \in \mathcal{D}}} \frac{C}{K^\ast + \sum_{\substack{e_4 \in \mathcal{E}\\d_4 \in \mathcal{D}}} \frac{C}{K^\ast + \sum_{\substack{e_3 \in \mathcal{E}\\d_3 \in \mathcal{D}}} \frac{C}{K^\ast + \sum_{\substack{e_2 \in \mathcal{E}\\d_2 \in \mathcal{D}}} \frac{C}{K^\ast + \sum_{\substack{e_1 \in \mathcal{E}\\d_1 \in \mathcal{D}}} \frac{C}{K^\ast + p^\ast_\ast}}}}}

Keep in mind that every K is some expanded key byte, each C is a known constant, and each ∗ is a known exponent or subscript, but that these values depend on the summation variables that enclose the symbol.

Another paper manipulated the definition somewhat differently and got this:

The round function of the BES, and hence essentially the AES, is given by bM Bb (1)+(k B) i.\mathbf{b}\mapsto M_B\cdot\mathbf{b}^{(-1)} + (\mathbf{k}_B)_i.

Thus a round of the AES is simply componentwise inversion and an affine trans- formation with respect to the same field F=GF(2 8)F = GF(2^8)\ldots

I think it’s fair to say that if people are ever able to solve these, we’d enter another age of continued fractions.

Posted by: Mike Stay on September 8, 2020 9:35 PM | Permalink | Reply to this

Re: Three Phases of Continued Fraction Theory

Sorry, I meant “solving certain equations between generalized continued fractions.”

Posted by: Mike Stay on September 8, 2020 9:40 PM | Permalink | Reply to this

Re: Three Phases of Continued Fraction Theory

This isn’t the only time someone has mentioned the start of ee’s regular continued fraction as … surprising, given the rest. But the pattern really does start right away, for just the small price of a momentary nonregularity:

e=1+10+11+11+12+11+ e = 1+\frac{1}{0+\frac{1}{1+\frac{1}{1+\frac{1}{2+\frac{1}{1+\dots}}}}}

Posted by: Jesse C. McKeown on September 11, 2020 5:06 PM | Permalink | Reply to this

Post a New Comment