The pattern in e's continued fraction

Several earlier essays have quoted the continued fraction of $e$ without proving it. A fraction that never closes listed it beside $\sqrt2$ and π; approached too fast to be algebraic used its growing terms to explain why $e$ is hard to approximate in one sense and easy in another; the tail too small to be a whole number noted that Euler proved the pattern with a Riccati equation and that the proof belonged here and was not here.

This is that proof, in a modern form so short it fits on a page, and it turns out to be a story about integrals as much as about fractions.

Reading the terms off without assuming them #

The figure’s terms were not typed in. A continued fraction of a number is found by repeatedly taking the whole part and inverting what is left, and that process can be run on any exact fraction. The trick is to run it on two fractions, one known to be just below $e$ and one just above: every term on which the two expansions agree is a term of $e$’s expansion too, because $e$ lies between them. The lower bound is a partial sum of $\sum 1/k!$ and the upper bound adds a strict overestimate of the remaining tail, so both are exact and both are certain.

With eighty terms of the series the bounds agree for more than thirty terms of the fraction, and those terms are exactly the pattern: $2$, then $1, 2k, 1$ for $k = 1, 2, 3, \dots$. The figure checks each term against the rule. That is evidence for the pattern at the start, and evidence is all a finite computation can give — the pattern could in principle break at term forty. What rules that out is a proof.

The comparison puts $e$ in its place among familiar numbers. A continued fraction that eventually repeats belongs to a root of a quadratic equation with whole-number coefficients — that is Lagrange’s theorem, and why the expansion of a square root has to repeat is its proof. The golden ratio and $\sqrt2$ are the simplest periodic cases. π’s terms follow no known pattern at all, and its early 292 is the reason $355/113$ is such a remarkable approximation. $e$ is between the two: a pattern as regular as a square root’s, but growing rather than repeating. So once the pattern is proved, $e$ is not a quadratic irrational — a result that needs nothing else.

The fractions the pattern produces #

The pattern is easier to feel through the fractions it makes. The convergents of $e$ — the fractions obtained by stopping the continued fraction after each term — begin

$$2, \quad 3, \quad \tfrac{8}{3}, \quad \tfrac{11}{4}, \quad \tfrac{19}{7}, \quad \tfrac{87}{32}, \quad \tfrac{106}{39}, \quad \tfrac{193}{71}, \quad \tfrac{1264}{465}, \quad \tfrac{1457}{536}, \quad \tfrac{2721}{1001}, \dots$$

alternately below and above $e = 2.718281828\ldots$, each closer than the last. The ones just before a large term are the notably good ones: $19/7 = 2.7142\ldots$ comes before the $4$ and is already right to three figures; $193/71 = 2.718309\ldots$ comes before the $6$; $2721/1001 = 2.7182817\ldots$ comes before the $8$ and is right to seven figures with a four-digit denominator.

Every one of them is a best approximation: no fraction with a smaller denominator is closer to $e$. That is the general property of convergents that the fraction that never closes established, and it means the list above is the complete record of the record-breaking fractions for $e$ — the best approximations anyone could find by searching, produced instead by a pattern of ones and even numbers.

The same pattern also explains why decimal digits of $e$ look irregular while its continued fraction does not. Decimal digits are a record of base ten, a choice made for human convenience, and in that base $e$ shows no structure at all. The continued fraction is a representation that belongs to the number itself, with no base chosen, and in it the structure of $e$ — a structure it inherits from being the exponential of $1$ — is on display.

Three integrals that are e’s own errors #

The proof is due to Henry Cohn, who published it in 2006, and it replaces Euler’s differential equation with three definite integrals. For each $n \ge 0$ let

$$A_n = \int_0^1 \frac{x^n (x - 1)^n}{n!}\, e^x \,dx, \qquad B_n = \int_0^1 \frac{x^{n+1} (x - 1)^n}{n!}\, e^x \,dx, \qquad C_n = \int_0^1 \frac{x^n (x - 1)^{n+1}}{n!}\, e^x \,dx.$$

The integrands are polynomials times $e^x$, and the polynomials vanish at both ends of the interval to high order, so every integration by parts moves a derivative onto the polynomial with no boundary terms. Doing that once gives three relations that step from $n - 1$ to $n$:

$$A_n = -B_{n-1} - C_{n-1}, \qquad B_n = -2n\,A_n + C_{n-1}, \qquad C_n = B_n - A_n.$$

The third is just the observation that the two integrands differ by $x^n(x-1)^n\,[x - (x - 1)]/n!$. The coefficient $2n$ in the second — the only place anything but $\pm 1$ appears — is where the even numbers in the pattern will come from.

Why the integrals are the errors #

Now compare with the convergents. It is convenient to write $e$’s fraction as $[1; 0, 1, 1, 2, 1, 1, 4, 1, 1, 6, \dots]$ — the same number, with a harmless zero that makes the terms come in uniform triples $1, 2n, 1$. The convergents $p_k/q_k$ of any continued fraction obey the rule that each new numerator is the current term times the previous numerator plus the one before, and the same for denominators. With terms coming in triples $1, 2n, 1$, that rule, written three steps at a time, reads

$$p_{3n} = p_{3n-1} + p_{3n-2}, \quad p_{3n+1} = 2n\,p_{3n} + p_{3n-1}, \quad p_{3n+2} = p_{3n+1} + p_{3n},$$

and the same for $q$. These are the integral relations in another form. Set

$$A_n = q_{3n}\,e - p_{3n}, \quad B_n = p_{3n+1} - q_{3n+1}\,e, \quad C_n = p_{3n+2} - q_{3n+2}\,e.$$

At $n = 0$ both sides agree: $A_0 = e - 1$, $B_0 = 1$, $C_0 = 2 - e$, and the first convergents are $1/1$, $1/0$ and $2/1$ — the middle one a formal convergent that the zero term produces, harmless because it is only ever used inside the recurrence. And the recurrences for the right-hand sides, obtained from the convergent rule, are exactly the three integral relations. So by induction each integral is exactly the error of a convergent of the continued fraction $[1; 0, 1, 1, 2, 1, 1, 4, \dots]$. The figure checks this at $n = 1$ to $4$ with the integrals computed numerically and the convergents computed exactly, and they agree to six places.

The finish is one line. The integrands are at most $1/n!$ times $e$ in size on the interval, so $A_n \to 0$: the errors of the convergents go to zero, the convergents converge to $e$, and the continued fraction whose terms are $1, 2n, 1$ is $e$’s own. The pattern is proved.

Where the integrals came from #

Cohn’s integrals were not pulled out of the air. Polynomials with high-order zeros at both ends of an interval, multiplied by $e^x$ and integrated, are the tool Charles Hermite used in 1873 to prove that $e$ is not merely irrational but transcendental — not the root of any polynomial with whole-number coefficients.

The reason the tool works is the one the integrals display here. Integrating such a product by parts, repeatedly, produces a whole-number combination of $e$ and $1$ plus nothing — the boundary terms vanish because of the zeros — so the integral is a small whole-number combination $q e - p$. The polynomial’s high-order zeros make the integral tiny while the coefficients stay whole. Hermite used polynomials vanishing at several points $0, 1, 2, \dots, m$ simultaneously, which gave small whole-number combinations of $1, e, e^2, \dots, e^m$ all at once and ruled out any polynomial relation among them. Cohn’s integrals are the simplest case, with zeros only at $0$ and $1$, and what they produce is precisely the best approximations to $e$ alone.

So the continued fraction of $e$ and the transcendence of $e$ are two outputs of one method, and the method is integration by parts against a polynomial chosen to vanish where the boundary terms would otherwise appear. The integrals are also the Padé approximants of the exponential in disguise: the fractions $p/q$ they define are the ratios of polynomials that best match $e^x$ at $x = 1$, for the same reason that Lambert’s convergents were the best rational approximations of the tangent. The curve that is its own slope is, underneath, the reason every one of these constructions closes up so neatly: differentiating $e^x$ changes nothing, so integrating by parts against it only ever moves derivatives onto the polynomial.

How close the convergents get #

A continued fraction’s terms control how well its convergents approximate. The general rule is that the convergent before a term $a$ has error about $1/(a\,q^2)$, so large terms mean unusually good approximations.

For $\sqrt2$, with every term equal to $2$, the product $q^2|\sqrt2 - p/q|$ settles at a constant and never falls. For $e$ it dips every third convergent, the one immediately before a term $2k$, and the dips deepen like $1/(2k)$. So $e$’s convergents beat $1/q^2$ by a factor that grows — slowly, logarithmically in $q$, because $k$ grows only like the logarithm of the denominators.

That is exactly the borderline behaviour. A number that could be approximated to within $1/q^{2+\varepsilon}$ infinitely often, for some fixed $\varepsilon > 0$, would have an irrationality measure above $2$; $e$’s approximations beat $1/q^2$ only by a factor like $\log q$, which is smaller than any power. The irrationality measure of $e$ is exactly $2$, the same as that of almost every real number, and it is read off directly from the growth of the pattern’s even terms. In the language of the approximation exponent, $e$ is as far from a Liouville number as a number can be while still having unbounded terms.

Why a growing pattern rules out a quadratic #

A pattern and a period are different things, and the difference is exactly the difference between $e$ and the square roots. Lagrange proved that a continued fraction repeats from some point on if and only if the number is a root of a quadratic equation with whole-number coefficients; why the expansion has to repeat shows the mechanism, a walk through finitely many states that must eventually revisit one. A repeating expansion takes only finitely many distinct values, so its terms are bounded.

The terms of $e$ are not bounded: $2, 4, 6, 8, \dots$ appear at every third place and grow without end. So the expansion never repeats, and $e$ is not the root of any quadratic — a statement stronger than irrationality, obtained in one line from the pattern. The same reasoning gives it for $\sqrt e$ and for $e^{2}$, whose patterns also grow.

The contrast with Pell’s equation is instructive. For $\sqrt{D}$ the period is what makes one solution generate all the others: the convergent at the end of each period solves $p^2 - Dq^2 = \pm1$, and the repetition is a multiplication. For $e$ nothing recurs, and no convergent is special in that way; the convergents just before the even terms are good, the others ordinary, and each good one is better than the last by a factor that grows with the term it precedes. What $e$ has instead of a period is a rule — a formula for the $n$th term — and a rule is enough to prove everything a period would have proved except the quadratic equation, which is false.

The same shape in the square root of e #

The pattern is not special to $e$ itself.

For $e^{1/m}$ with a whole number $m$, the expansion is $[1; m - 1, 1, 1, 3m - 1, 1, 1, 5m - 1, \dots]$, and for $m = 2$ that is the figure’s $1; 1, 1, 1, 5, 1, 1, 9, \dots$. The same integrals, with $e^{x/m}$ in place of $e^x$, prove it. And there are patterns for $e^{2/m}$ as well, obtained from the continued fraction of the hyperbolic tangent in Lambert’s proof, which is the source from which Euler’s and all later versions of these expansions ultimately descend.

Other powers are less tidy. The continued fraction of $e^2$ begins $7; 2, 1, 1, 3, 18, 5, 1, 1, 6, 30, \dots$ and does have a pattern — period five, with two terms growing linearly — but $e^3$ has none known. The powers with patterns are exactly the ones that the hyperbolic tangent’s fraction reaches; beyond them, $e$’s regularity seems to stop.

Euler’s route, and why the integrals are simpler #

Euler proved the pattern in 1737 by relating $e$’s continued fraction to the solution of a Riccati differential equation, $y' = 1 + y^2$ in a scaled form, whose solution can be written both as a ratio of series and as a continued fraction. The proof is a genuine piece of analysis and it establishes more than the pattern — it produces the whole family of expansions for $\tanh$ and for $e^{2/m}$.

Cohn’s integrals do less and are shorter, and the reason they work is the one integration by parts always offers: moving a derivative from one factor to the other turns one integral into a combination of others, and here the combination reproduces the recurrence of the convergents exactly. The coefficient $2n$ that appears is the derivative of $x^n(x-1)^n$ counted twice, and the even numbers of the pattern are nothing more than that. It is a small example of a general phenomenon: when a sequence of integrals satisfies a three-term recurrence, a continued fraction is hiding in it, and the integrals are the errors of its convergents.

What the pictures cannot show #

The pattern beyond the bounds. The bars and the table show terms fixed by exact bounds, thirty of them for $e$. The proof covers every term, and the figures are consistent with it and nothing more. For π the table is the whole of what is known: its terms can be computed to any length, and no pattern has ever been found or ruled out.

The integrals exactly. The areas in the fourth figure were computed by Simpson’s rule, and they agree with the exact convergent errors to six significant places. The equality is exact, and it comes from the induction; the numerical agreement is a check on the relations, which a sign error in them would fail.

Why the measure is exactly two. The error figure shows the dips deepening like $1/(2k)$ over twenty-three convergents. That they never deepen faster — that no subsequence of approximations beats $1/q^{2+\varepsilon}$ — follows from the pattern and the general theory of continued fractions, which the figure illustrates without proving.

Still open: patterns that nobody can find #

The continued fraction of $e$ has a pattern and π’s apparently does not. For the simplest algebraic numbers beyond square roots, nothing is known either way: whether the terms of the continued fraction of the cube root of two are bounded is open, and so is the analogous question for every algebraic number of degree three or more. Computations of millions of terms find the occasional large one, in the proportions a random number would show, which is what almost every number does and what no one can prove any particular algebraic number does.

For π the question is not even whether its terms are bounded — they are believed to be unbounded, like almost every number’s — but whether any structure at all can be proved about them. The generalised continued fractions of π, with numerators other than one, do have patterns, some found by Euler and Brouncker and many more found recently by computer search; the simple continued fraction, with every numerator one, remains the patternless row of the table above.

A pattern and its proof #

The continued fraction of $e$ is $2$ followed by the triples $1, 2k, 1$, and the terms can be checked from exact bounds for as far as anyone cares to compute. Proving the pattern for every term takes three integrals of polynomials times $e^x$, related by integration by parts in exactly the way the convergents are related by the continued fraction’s own recurrence — so that each integral is, identically, the error of one convergent.

The pattern proves at once that $e$ is irrational, that it is not the root of any quadratic, and that its irrationality measure is exactly two. It is also the reason $e$ sits apart from both the square roots, whose terms repeat, and π, whose terms have never been caught doing anything at all.