Matpic
mathematics, in pictures
Concept

Stern brocot tree

The binary tree of fractions built by repeatedly taking the mediant of two neighbours. Every positive rational appears in it exactly once and already in lowest terms, because the construction preserves primitivity rather than restoring it by cancelling.

Named by 8 essays across one field — each of them below, with the objects they name alongside it.

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 The tree of Pythagorean triples. A tree rooted at 3-4-5. Each triple has three children, obtained by three fixed integer matrices, and every primitive triple appears exactly once somewhere in it.

A tree that holds every triple

Three fixed matrices, applied to 3-4-5 over and over, produce every primitive Pythagorean triple there is — each of them once, none of them twice, and with no test for common factors anywhere in the procedure.

number · Pythagoras The tree as words in two matrices. 6 nodes of the Stern–Brocot tree, each as the word of turns reaching it, the matrix that word multiplies out to, its two columns as fractions, and the mediant of those columns.

Two matrices that generate the tree

A node of the Stern–Brocot tree is not really a fraction — it is the pair of fractions it lies between. Written as the columns of a matrix, the two turns of the tree become two multiplications, and the determinant that kept everything in lowest terms becomes a property of a product.

number · Stern brocot Every positive rational, in one sequence. The first 32 terms of Stern's diatomic sequence as bars, with the ratios of consecutive terms beneath. Every ratio is in lowest terms, no two agree, and each term counts the hyperbinary representations of its index.

Every rational in one sequence

The tree lists every positive fraction once and needs a tree to do it. One recursion on the whole numbers lists them in a single row — and each term of it counts something nobody was asking about, which is why the enumeration works.

number · Stern brocot 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 The tree writes 4/17 as four unit fractions, and a search finds three. Left-neighbour chain 4/17, 3/13, 2/9, 1/5, 0/1, gaps 1/221, 1/117, 1/45, 1/5; three-term decomposition 1/5 + 1/30 + 1/510.

Three unit fractions for every four over n

Two neighbouring fractions in the tree always differ by a unit fraction, so stepping down the tree writes any fraction as a sum of them — four over n in at most four steps. Erdős and Straus asked in 1948 whether three always suffice. Three identities settle every n except those leaving remainder 1 on division by 24, a search settles every one anyone has tried, and nobody has a proof.

number · Stern brocot

Named alongside it

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

MediantBijectionContinued fractionsFarey sequenceLowest termsUnimodularBinaryCounting two waysDeterminantMatrixModular groupConjecture

All concepts