Approached too fast to be algebraic

Everything in this ladder so far has asked whether a fraction hits a number exactly. That question is about equality and it is blind to accuracy: $99/70$ misses $\sqrt2$ and so does $1/1$, and the arguments treat them alike.

Liouville’s idea, from 1844, is to ask the other question. How closely can fractions approach? The answer turns out to depend on the degree of the polynomial the number satisfies — so a number approached too closely satisfies no polynomial, and that is the first proof that transcendental numbers exist.

The barrier #

Let $\alpha$ be a root of an irreducible polynomial $P$ with whole-number coefficients and degree $d \ge 2$. Then there is a constant $c > 0$ with

$$\left|\alpha - \frac{p}{q}\right| > \frac{c}{q^{d}}$$

for every fraction $p/q$.

The proof is a page of nothing clever. $P(p/q)$ is not zero, because $P$ is irreducible of degree at least two and so has no rational root — which is the divisor argument from the bottom of this ladder. And $q^d P(p/q)$ is a whole number, so its size is at least one, so

$$\left|P\!\left(\frac{p}{q}\right)\right| \ge \frac{1}{q^d}.$$

That is the lower bound. For the upper one, the mean value theorem gives $P(p/q) = P(p/q) - P(\alpha) = (p/q - \alpha)P'(\xi)$ for some $\xi$ between them, and $|P'|$ is bounded on any interval around $\alpha$. Putting the two together and calling the bound $1/c$ gives the theorem.

The two ingredients are “a non-zero whole number is at least one” and “a differentiable function does not change faster than its derivative allows”. Neither is deep and their combination is the whole result.

What the exponent means #

The theorem says the exponent $d$ is a wall. Read the other way, it says an algebraic number of degree $d$ can be approached to within roughly $q^{-d}$ and no better, and the two readings together make the exponent a measurement of the number rather than an artefact of the proof.

For $d = 2$ the wall is at $q^{-2}$, and that is exactly where the quadratic irrationals sit. Their continued fractions are eventually periodic, their convergents satisfy $|\alpha - p/q| < 1/q^2$, and Liouville’s bound says they never do much better. Both statements are tight, and the figure shows $\sqrt2$’s convergents running between the two.

The tightness of $q^{-2}$ for every irrational is a separate and older result: Dirichlet’s pigeonhole argument gives infinitely many fractions with $|\alpha - p/q| < 1/q^2$ whatever $\alpha$ is. So $q^{-2}$ is always achievable, and Liouville says a degree-two number cannot do better. Between those two the quadratic irrationals are pinned exactly.

Building a number that breaks it #

The theorem is a barrier and barriers invite construction. Liouville’s move is to write down a number whose decimal expansion is almost all zeros, with the non-zero digits placed at positions that grow factorially:

$$L = \sum_{k \ge 1} 10^{-k!} = 0.1100010000000000000000010000\dots$$

Truncating after $k$ terms gives a fraction whose denominator is $10^{k!}$, and the error is dominated by the next term, which is $10^{-(k+1)!}$. So

$$\left| L - \frac{p_k}{q_k} \right| \approx q_k^{-(k+1)},$$

where the exponent is $(k+1)!/k! = k+1$ and grows without bound.

Now take any $d$. Choose $k > d$; the $k$-th truncation approaches $L$ better than $q^{-d}$, and Liouville’s theorem says an algebraic number of degree $d$ cannot be approached that well. So $L$ is algebraic of no degree at all: it is transcendental.

The figure computes those exponents and checks each of them against each drawn barrier — a truncation that beats $q^{-5}$, one that beats $q^{-3}$, and so on — rather than quoting the calculation.

Which numbers are hard to approximate, and which are easy #

The barrier is a lower bound and every irrational also has an upper one, so each number sits somewhere in a range — and where it sits turns out to be a real property with a real spread.

The hardest number to approximate is the golden ratio. Its continued fraction is all ones, which is the slowest possible growth, and its convergents beat $1/q^2$ by a factor that never exceeds $\sqrt5$. Hurwitz’s theorem says no irrational does worse than that, so $\varphi$ is the extreme case and the constant $\sqrt5$ is best possible because of it. That is the same fact the three-gap behaviour rests on: a number badly approximable by fractions distributes its multiples evenly, which is why it turns up wherever an even spread is wanted.

The easiest numbers are the Liouville ones. They are approximable to any exponent, they are all transcendental, and there are uncountably many of them — and yet they form a set of measure zero, so a number picked at random is not one with probability one.

The typical number sits at exponent exactly two with an unbounded but slowly growing supply of good approximations, and almost every real number does. Roth’s theorem says every algebraic irrational is typical in this sense, which was a considerable surprise: the degree does not show up in the answer at all.

So the classification by approximation exponent has three populations and the two interesting ones are both tiny. That is a shape this site keeps meeting — the algebraic numbers can be listed and the reals cannot, so almost every number is transcendental and almost none of them can be named — and it is worth noticing that the exponent gives a second, finer classification with the same character.

The two ingredients, looked at again #

Both halves of Liouville’s proof are worth a second look, because each is an instance of something this site uses repeatedly and neither is about approximation at all.

A non-zero whole number is at least one. That is the same observation that finished the two rungs below: the tail of $e$’s series and Niven’s integral are both quantities forced to be whole and shown to be small. Here the forced quantity is $q^d P(p/q)$ — a whole number because clearing the denominators of a degree-$d$ polynomial at a fraction with denominator $q$ takes exactly $q^d$ — and it is non-zero because the polynomial has no rational root.

A function does not move faster than its derivative allows. The mean value theorem converts a statement about $P$’s value into a statement about the distance from $p/q$ to the root, and the conversion costs a factor of the largest slope nearby. This is the only analysis in the argument and it is the reason the constant $c$ depends on the polynomial rather than being universal.

Put together, the two say: a fraction close to the root makes $P$ small, $P$ cannot be small unless $q$ is large, so a close fraction has a large denominator. Nothing in that sentence mentions transcendence, and the transcendence is a corollary of noticing that the required largeness depends on $d$.

What is remarkable about this, and what is not #

The construction is easy and the theorem behind it is a page, and it is worth being clear about which part was the achievement.

Not the existence. Fifteen years later Cantor showed transcendental numbers exist by counting, in an argument that is shorter than Liouville’s and exhibits nothing. The algebraic numbers arrive in finite batches and the reals do not, so almost every number is transcendental — and the counting says so without naming one.

Not the number. $L$ is a curiosity. Nobody wanted it, it answers no question outside this one, and its decimal expansion is a description of itself.

The criterion. Before 1844 there was no test whatever for transcendence. Liouville’s theorem is a test — a sufficient one, and a usable one — and having any test at all made it possible to start asking about numbers people cared about. That $e$ and $\pi$ both turned out to fail this particular test is the next part of the story.

Why the criterion misses e and π #

Liouville’s test detects numbers approached absurdly well. $e$ and $\pi$ are not.

$e$’s continued fraction has quotients growing linearly — $[2; 1, 2, 1, 1, 4, 1, 1, 6, \dots]$ — and a continued fraction’s quotients are exactly what control the quality of its convergents. Small quotients mean unremarkable approximations, and $e$’s approximation exponent is $2$, at the bottom of the range.

$\pi$’s quotients are mostly small too, with a famous exception: the quotient $292$ at the fourth place, which is why $355/113$ is so unreasonably good — accurate to seven decimal places with a three-digit denominator. That is a spike, not a pattern, and $\pi$’s exponent is known to be below $8$.

So neither is a Liouville number, and both are transcendental for reasons this criterion cannot see. Hermite’s proof for $e$ in 1873 and Lindemann’s for $\pi$ in 1882 are of a different kind entirely: they construct linear forms in exponentials that would have to be small whole numbers, which is the same template as the irrationality proofs and needs much more machinery.

The exponent, sharpened #

Liouville’s exponent $d$ is not the truth, and the century of work that reduced it is one of the better stories in the subject.

Thue improved it to $d/2 + 1$ in 1909; Siegel to about $2\sqrt d$; Dyson and Gelfond to $\sqrt{2d}$. Then in 1955 Roth proved the exponent is $2$, for every algebraic irrational of every degree: for any $\varepsilon > 0$ there are only finitely many fractions with $|\alpha - p/q| < q^{-2-\varepsilon}$.

That is best possible, since Dirichlet’s argument gives infinitely many at exponent exactly $2$. So the question is completely settled and the answer does not depend on the degree at all — the degree only affects how many exceptions there are and how large they can be.

The improvement has a cost worth naming. Roth’s theorem is ineffective: it says finitely many exceptions exist and gives no way to find them or to bound them. Liouville’s bound is explicit — the constant $c$ can be computed from the polynomial’s coefficients — and it is still the one used when an actual number is needed. A weaker theorem that names its constant is often more useful than a sharp one that does not, and this is the standing example.

What a criterion buys, and what an exhibition buys #

The comparison with Cantor’s counting argument is the sharpest instance on this site of two proofs of one statement that share nothing, and it repays being laid out.

Liouville, 1844. Constructs one number and proves it transcendental. The proof is a page, it generalises to a whole family, and the criterion it establishes can be applied to any number whose approximations are known.

Cantor, 1874. Shows the algebraic numbers can be listed and the reals cannot, so some real is not algebraic. The proof is shorter, it establishes that almost all numbers are transcendental rather than that one is, and it names none of them.

Two things are worth noticing about the pair. The counting proof is enormously stronger as a statement — it upgrades “at least one” to “all but a listable few” — and enormously weaker as a tool, because the question that mattered next was whether $e$ and $\pi$ are transcendental and counting has nothing to say about any particular number.

And the historical order is the reverse of the pedagogical one. Cantor’s argument is the one taught first because it is easier; Liouville’s is the one that came first, and it came first because exhibiting was what a proof was expected to do. The probabilistic method is the same debate a century later in combinatorics, and it went the same way: the counting argument won, and the objects it promises still cannot be produced.

Reading a number’s exponent off its continued fraction #

There is a mechanical way to see how well a number can be approached, and it makes the whole classification computable rather than mysterious.

A number’s convergents satisfy

$$\left|\alpha - \frac{p_k}{q_k}\right| \approx \frac{1}{a_{k+1} q_k^2},$$

where $a_{k+1}$ is the next quotient in the continued fraction. So a large quotient means an unusually good approximation, and the growth rate of the quotients is exactly the number’s approximation exponent.

That reads off every case in this essay. The golden ratio’s quotients are all $1$, so it never does better than $1/q^2$ by more than a constant factor — the hardest number to approach. $\sqrt2$’s are all $2$, nearly as hard. $e$’s grow linearly, which improves the constant and not the exponent. $\pi$’s are mostly small with the spike at $292$ that produces $355/113$. And a Liouville number’s quotients grow faster than any power of the denominator, which is the same statement as the one this essay proves and is where the construction’s factorials show up.

So the exponent is not an exotic invariant. It is the growth rate of a sequence of whole numbers that can be computed from the decimal expansion by the Euclidean algorithm, and every classification in this essay is a statement about that sequence.

What the picture cannot show #

The figure plots finitely many approximations and the theorems are about all of them. The line drawn as a barrier is where the barrier is; nothing in the drawing shows that no point ever crosses it, and no drawing could.

It also compresses catastrophically. The fourth truncation of $L$ has denominator $10^{24}$ and error around $10^{-120}$, so the axes are logarithms of logarithm-sized quantities and the visible spacing understates the effect by an amount that has no honest visual representation. The fifth truncation is off the page by a factor no page has.

And it draws the barrier for $\sqrt2$ as though the constant were one. It is not — the theorem gives some $c$ depending on the polynomial, and for $\sqrt2$ a workable value is $1/3$. The gradient is the content and the intercept is a convenience.

Where the ladder goes next #

Above: the transcendence of $e$ and $\pi$, which need the other template rather than this one; the Gelfond–Schneider theorem, which settles $2^{\sqrt2}$ and $e^{\pi}$ and is the answer to Hilbert’s seventh problem; and the theory of approximation exponents as a classification of irrationals, where the numbers with exponent exactly two are the overwhelming majority and Liouville’s are a measure-zero curiosity.

Beside: the counting argument, which reaches the same conclusion — transcendental numbers exist — by a route with no polynomial in it at all, and which produces nothing. The contrast between the two is the sharpest instance this site has of the difference between exhibiting and proving.

One debt. Roth’s theorem is quoted three times here and its proof is not sketched; it is genuinely a research paper and the sketch would be dishonest. What could be drawn, and is not, is the ineffectivity — a picture of a bound that names a finite set and cannot locate it.

What the degree was measuring #

A polynomial of degree $d$ cannot have its root approached faster than $q^{-d}$, because $q^d P(p/q)$ is a whole number and a non-zero whole number is at least one.

That single inequality is the whole barrier, and the construction that breaks it is the recognition that the barrier depends on $d$ while a decimal expansion does not have to. Choosing where the digits go chooses how fast the truncations converge, and choosing them to converge faster than any fixed exponent chooses a number no polynomial can reach.