Matpic
mathematics, in pictures
Concept

Continued fractions

A number written as a whole part plus one over a whole part plus one over another, nested as far as it goes. The expansion terminates exactly when the number is rational, and it is periodic exactly when the number is a quadratic irrational.

Named by 19 essays across 3 fields — each of them below, with the objects they name alongside it.

Euclid's algorithm on a 34 by 13 rectangle. The rectangle is tiled by peeling off the largest square that fits, again and again, until nothing is left.

The oldest algorithm, drawn as a tiling

Euclid's method for finding a greatest common divisor is usually presented as a loop. It is also a way of tiling a rectangle with squares, and the tiling explains why it works.

geometry · Euclidean algorithm The whirling squares. Squares with Fibonacci sides 1, 1, 2, 3, 5, 8, 13, each attached to the long side of what came before. They fill a 13 by 21 rectangle exactly.

The rectangle that eats itself

Cut a square off a golden rectangle and what is left is a golden rectangle. That single property is the whole of the golden ratio, and it explains both what the number really does and most of what is wrongly claimed for it.

geometry · Golden ratio φ as a continued fraction. The nested fraction, one quotient per step, descending to the right.

A fraction that never closes

Euclid's algorithm throws away everything except the number of squares it peeled at each step. Those counts are a second name for the number it started from — one that terminates exactly when the ratio is a ratio.

number · Euclidean algorithm The Stern–Brocot tree to depth 4. Every positive rational, each appearing exactly once, generated by taking mediants.

Every fraction, exactly once

Take two fractions, add the tops and add the bottoms. That is not how fractions are added, it is not an average, and repeating it produces every positive rational exactly once, already in lowest terms.

number · Stern brocot 8 multiples of φ in 7 boxes. The fractional parts of the first multiples of a number, dropped into equal boxes along the unit interval.

How close a fraction can get

Drop eight points into seven boxes and two of them share. That one line, applied to the multiples of an irrational number, proves that every irrational has infinitely many astonishingly good rational approximations — and no construction is needed anywhere.

number · Pigeonhole Two squares of side 12 inside one of side 17. Two overlapping squares laid into opposite corners of a larger one, with the overlap and the two uncovered corners marked.

The square that cannot shrink

The usual proof that the square root of two is irrational is about even and odd numbers. There is a proof about squares instead, in which a supposed solution is folded into a smaller one — and the folding is a drawing.

number · Irrationality Rotating by φ − 1 of a turn, 21 times. Points on a circle produced by repeatedly turning through the same angle.

Three gaps and no more

Turn a circle by the same irrational angle over and over. The points never repeat and never settle, and yet at every single stage the gaps they leave take at most three different lengths — never four, at any number of steps, for any angle.

dynamics · Golden ratio Whole-number points on x² − 2y² = 1. The branch of the hyperbola x² − 2y² = 1 in the first quadrant, with the whole-number points on it marked and labelled, and the lattice drawn faintly behind.

One solution that makes all the others

The equation x² − 2y² = 1 has infinitely many whole-number solutions, and every one of them is a power of the smallest. The multiplication that produces them is what multiplying two numbers of the form a + b√2 comes to when the √2 terms are collected — so an equation about a hyperbola turns out to carry a group.

number · Pell How closely a fraction can come, and the barrier that says no closer. Two panels at very different scales: the approximations to √2, which stay above the barrier a degree-two number obeys, and the truncations of a constructed number, which fall below every barrier drawn.

Approached too fast to be algebraic

An algebraic number of degree d cannot be approached by fractions faster than the denominator's dth power. So a number that is approached faster than that is the root of no polynomial at all — and one can be built by choosing where its decimal digits go.

number · Irrationality The only fractions that could be a cycle's shape. A table of the convergents of the base-two logarithm of three, with the approximation error, the exact value of two to the n less three to the k, and that value as a fraction of three to the k.

How short a cycle could be

The drift argument cannot see cycles at all, which is why it is not a proof. What can see them is arithmetic — a cycle's shape has to be a fraction that approximates the logarithm of three to base two extraordinarily well, and there are very few such fractions.

dynamics · Collatz 13 record approximations in 26 turns. The distance from π to each fraction the descent passes, against its denominator, on logarithmic axes. 13 of them beat every fraction with a smaller denominator.

The fractions that beat every smaller one

Walking down the tree towards a number produces a sequence of fractions closing in on it. Most of them are steps along the way; a few are the best approximations there are — closer than every fraction with a smaller denominator — and which few is decided by where the turns change direction.

number · Stern brocot The Farey tessellation, and a line down to √2 − 1. Semicircles over the unit interval joining every pair of Farey neighbours with denominators up to 13, and a vertical line at √2 − 1. The 6 arcs it crosses are the intervals of the Stern–Brocot descent to √2 − 1, and their turns spell LRRLL.

The arcs a line crosses on its way to a number

Draw a semicircle over every pair of neighbouring fractions and the half-plane above the number line is cut into curved triangles that never overlap. A straight line dropped towards any number crosses those arcs one after another, and the arcs it crosses, and the side it leaves each triangle by, are exactly the steps of the Stern–Brocot descent towards that number.

number · Stern brocot Minkowski's question-mark function. The graph of Minkowski's function ?(x) on the unit interval: continuous and increasing, sending each Stern–Brocot fraction to the binary fraction in the same position. It sends √2 − 1 to 2/5 and φ − 1 to 2/3.

The function that sends fractions to binary

The Stern–Brocot tree and the tree of binary fractions have exactly the same shape, so there is a function that sends each fraction to the binary fraction in the same position. It is continuous and increasing, it turns every quadratic irrational into an ordinary fraction, and it does all of its rising on a set of numbers so thin that at almost every point its slope is nought.

number · Stern brocot Bhāskara's cyclic method on x² − 61y² = 1, step by step. A table of the cyclic method's rows: the helper m chosen at each step and the near miss a² − Db² = k it produces, ending at k = 1 with the fundamental solution.

A method that is allowed to miss

Bhāskara's cyclic method solves x² − Dy² = 1 by aiming at the wrong target. It keeps a pair a, b with a² − Db² = k for some small k, combines it with a helper chosen so that k can be divided out, and repeats until k is 1. For D = 61 it reaches the ten-digit fundamental solution in 13 steps, where walking the convergents of √61 takes 22 — and for every D up to 100 it is faster.

number · Pell The states the continued fraction of √61 can be in. A grid of whole-number pairs with the band of reduced states shaded, the pairs that qualify marked, and the cycle of states visited by the expansion of the square root numbered in order.

Why the expansion has to repeat

The continued fraction of √61 runs 7; 1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14 and then starts again. It must: each step's state is a pair of whole numbers trapped in a small band, and only 14 pairs fit. The expansion of √61 visits 11 of them in a cycle, the other 3 form a cycle of their own, and the period reads the same backwards before its last term, which is twice the first.

number · Pell The tangent built from a continued fraction. The curve tan x on (−1.55, 1.55) with 4 of Lambert's convergents: a straight line, then rational curves that bend ever closer to the tangent and follow it towards its poles.

The fraction Lambert built for the tangent

The first proof that π is not a fraction, from 1761, does not look at π at all. It writes the tangent as an endless continued fraction, shows that the fraction's value at any rational point other than zero cannot be rational — because its tails are trapped between nothing and one — and then notes that tan(π/4) = 1.

number · Irrationality The continued fraction of e. Bars for the first 30 continued-fraction terms of e: mostly ones, with every third bar rising in a straight staircase, 2, 1, 2, 1, 1, 4, 1, 1, 6, ….

The pattern in e's continued fraction

Written as a continued fraction, e is 2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8 — two ones, then the next even number, for ever. Euler found the pattern and proved it with a differential equation. A proof from 2006 needs only three integrals, each of which turns out to be exactly the error of one of e's own convergents.

number · Irrationality How many digits Pell's first solution has, for D up to 1000. A scatter of the digit count of the smallest solution of Pell's equation against D, with the record-setting values ringed and labelled.

Sixty needs two digits and sixty-one needs ten

The smallest solution of x² − 60y² = 1 is x = 31. For x² − 61y² = 1 it is x = 1,766,319,049. The jump is not an accident of 61: the solution is exactly the product of one period's complete quotients, so its size is set by how long the continued fraction takes to come home — and for the cattle problem Archimedes is said to have posed, that product has 103,273 digits.

number · Pell Euclid's game on 34 and 21. A 34 by 21 rectangle tiled by the squares of Euclid's algorithm, each run of equal squares shaded by the player who faces it, with the deciding run outlined.

The player who meets the first long run

Turn Euclid's algorithm into a game: two players take turns cutting squares off the rectangle, any number from the current run, and whoever cuts the last one wins. The whole game is decided before it starts — by whether the ratio of the sides is more or less than the golden ratio, which is the same thing as how many runs of length one come first.

geometry · Euclidean algorithm

Named alongside it

The objects these essays reach for when they reach for this one.

Rational approximationDiophantine approximationGolden ratioPell equationFibonacciIrrationalityStern brocot treeConvergentFarey sequenceFundamental solutionIncommensurabilityMediant

All concepts