Matpic
mathematics, in pictures
Concept

Algorithm

A finite procedure of precisely stated steps that takes an input and is guaranteed to stop with an answer. What usually matters about one is how many steps it needs as the input grows, which decides whether it can be run on large cases at all.

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

A cheapest assignment, and the proof that it is cheapest. A 4 by 4 cost table with the cheapest assignment marked, and a row price and column price beside each. Every used cell's two prices add to its cost, and the prices total the assignment's cost.

A price for every person and task

The cheapest assignment can be found without comparing it to any other. Attach a number to each person and each task so that no pair's two numbers exceed its cost, and if the numbers add to an assignment's total, that assignment is cheapest — proved, by an argument that never mentions the alternatives.

applied · Assignment 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 A random ranking on the triangular graph, 8 a side. A bipartite graph in which arrival t is joined to places t through 8. One random ranking of the places is used to match greedily; 5 of 8 arrivals are matched.

Matching as they arrive

Applicants arrive one at a time, and each must be given a post or turned away on the spot. Any sensible rule matches at least half as many as the best assignment chosen with hindsight, and an adversary arranging the arrivals can hold every fixed rule to exactly half. Shuffle the posts once, at random, and give each arrival its best-ranked free post: the guarantee rises to 1 − 1/e, about 63%, and no rule of any kind can do better.

discrete · Halls theorem An auction for 4 objects, bid by bid, with increment 1/5. A 4 by 4 table of values beside the log of 12 bids of an auction with increment 1/5: bidder, object, the raise, and the prices after each bid; it ends with total value 26.

Prices the bidders raise

The cheapest assignment is certified by a price on every task, and those prices can be found without anyone in charge. Let each unassigned person bid for the task that suits them best at current prices, raise its price by a little more than it is worth to them over the next best, and wait. The bidding ends, and when the increment is small enough the prices it ends at are a proof of optimality.

applied · Assignment Greedy colouring of the crown graph in two orders: two colours, and four. The crown graph on eight vertices coloured greedily twice: in the order top row then bottom row it uses 2 colours, alternating between the rows it uses 4. Numbers on the vertices give the order.

The order decides the colours

The simplest way to colour a graph is to take the vertices one at a time and give each the first colour its neighbours are not already using. It never needs more than one colour beyond the largest degree — and on a graph that needs only two colours it can be made to use as many as there are vertices on a side, depending on nothing but the order it is handed.

discrete · Graph colouring The first 600 terms of the continued fraction of ∛2. Partial quotients of ∛2 computed exactly: 1, 3, 1, 5, 1, 1, 4, 1, 1, 8, 1, 14, 1, 10, 2, 1, 4, 12, 2, 3 …; the largest in the first 600 is 7451.

A cube root that looks like chance

The continued fraction of √61 repeats after eleven terms, and every square root's must. The cube root of 2 obeys no such law. Computed exactly, by a method of Lagrange's that never leaves the whole numbers, its terms run 1, 3, 1, 5, 1, 1, 4 … and throw up a 534 at the thirty-fifth place and a 7,451 at the 571st — and in every statistic anyone has measured, they look like the terms of a number picked at random.

number · Pell Four lists, merged in pairs, find a cancelling quadruple. A merge tree for four lists of 256 random 24-bit strings: two merges on the low 8 bits, then one on all 24, ending in 1 solution(s).

Four lists find a collision sooner

Two lists of random 24-bit strings need about four thousand entries each before some string appears in both — the birthday bound. Ask instead for one string from each of four lists whose exclusive-or is zero, and lists of a few hundred suffice, because merging the lists in pairs manufactures the near-misses a direct search would have to find by luck. David Wagner's algorithm turns the square root into a cube root, and more lists into smaller roots.

probability · Birthday problem

Named alongside it

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

AssignmentCertificateComplementary slacknessContinued fractionsDualityExpectationGreedy algorithmLinear programmingMatchingRandomnessAlgebraic numberBinary

All concepts