Matpic
mathematics, in pictures
Concept

Complexity

How the cost of a computation grows with the size of its input, ignoring constant factors. It is what separates a method that is usable at a million items from one that is usable at a thousand, and the separations are usually about which structure the method exploits.

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

16 ways to sort it. A small order with its 16 linear extensions counted, and for each incomparable pair the fraction of extensions putting one before the other.

How many ways to sort it

An order says some things come before others and leaves the rest open. Counting the orderings consistent with it measures how much is still unknown — and the counting is as hard as any counting problem gets.

discrete · Posets The shortest tree was already in the triangulation. The Delaunay triangulation of 20 sites in faint lines with the minimum spanning tree drawn over it in heavy ones. Every tree edge is a triangulation edge, and the circles on the longest few tree edges as diameters contain no other site.

The tree inside the triangulation

The shortest network joining a set of points is built from edges chosen by length, and the triangulation is built from edges chosen by an emptiness condition about circles. The two constructions share no step, and every edge of the first is an edge of the second.

geometry · Voronoi A scatter with no lines in it. 900 consecutive pairs from a generator that squares modulo a product of two primes. The points show no family of parallel lines, and an exhaustive search for a short relation between consecutive outputs finds none.

Randomness that has to be earned

A generator that resists prediction cannot be built out of a rule anybody can fit. It has to be built out of a computation believed hard to undo, and the belief is the load-bearing part — which makes cryptographic randomness a conditional statement rather than a construction.

computation · Pseudorandomness The corner that is a half on every edge. A 3-vertex graph beside a table of the 5 corners of its matching relaxation. 4 are whole and one assigns a half to every edge.

Where the corners stop being whole

The easy theory of assignment rests on one property — the relaxation of the assignment problem has whole-numbered corners. Add a single edge that closes an odd cycle and the property fails, a corner appears with a half in every coordinate, and the problem changes character completely.

applied · Assignment One minimum, or several. Two curves side by side with their local minima marked: a convex one with a single minimum, and a fourth-power well with 2.

Where the guarantee stops

Convexity converts every downhill method into a correct one, and its absence removes the guarantee entirely rather than degrading it. What is left is a collection of partial answers, and knowing which of them apply to a given problem is most of what non-convex optimisation is.

analysis · Convexity A failed search on four clauses, read as a resolution refutation. A binary search tree branching on variables, each branch ending at a clause the partial assignment makes false, with every branch point labelled by the resolvent of the clauses below it, the top label being the empty clause.

A failed search is a proof

Search for an assignment by branching on variables and backing up whenever a clause turns false. If every branch fails, the tree the search leaves behind is itself a resolution refutation: write at each branch point the resolvent of the clauses below it, and the top of the tree is the empty clause. So every limit on short refutations is a limit on every such search — and the pigeonhole clauses, whose refutations are long, defeat them all.

logic · Resolution A necklace of 4 orange, 4 blue, 2 green beads, shared fairly with 3 cuts. A row of coloured beads cut at marked places into pieces, each piece labelled with the thief who receives it, so that both thieves get half of every colour.

As many cuts as colours

Two thieves steal a necklace and want half of every colour of bead each. However the beads are strung, they never need more cuts than there are colours — three cuts for three colours, four for four — and sometimes they need every one. The guarantee is the Borsuk–Ulam theorem again, with a point on a sphere read as a way of cutting the necklace, and every necklace of several small kinds has been checked against it.

topology · Borsuk ulam Even and Paz's halving, for 4 people. The recursive halving procedure run on a cake valued differently by 4 people: each round's marks and cuts, and the final pieces, each worth at least a 1/4 share to its owner. 8 marks are made.

How many cuts a fair share costs

Every person can be guaranteed a share of a cake worth at least one n-th by their own measure, and the oldest rule that does it asks about n²/2 questions. Splitting the people into halves and the cake at a median mark asks about n log n — and a theorem says nothing can ask fewer. Fairness has a price, and it can be counted.

applied · Fair division The midpoint of AB: simplicity 11. A construction drawn step by step — the midpoint of AB, using ruler and compass — with each circle and line numbered in order and Lemoine's count of its operations beneath.

The price of a construction

Three theorems have shown that a compass alone, a straightedge with one circle, and a compass stuck at one opening all reach exactly the points a full set of instruments reaches. None of them said what the journey costs. Émile Lemoine priced every movement of the hand in 1888, and by his count a compass that collapses when lifted — Euclid's — pays twenty-one operations, by Euclid's own method, for what a compass that holds its opening does in four.

computation · Compass-only A labelled square and the edges that join opposite labels. A square grid of 121 vertices, each coloured by one of four labels, with opposite boundary vertices carrying opposite labels, and 3 edges drawn thick where a label meets its negative.

Opposite labels that have to meet

Cut a square into triangles, label every corner +1, −1, +2 or −2, and insist only that opposite points of the edge get opposite labels. Somewhere inside, an edge must join a label to its negative. The proof counts quarter-turns round a diamond — an odd number on the boundary, zero in any triangle that avoids opposites — and making the triangles smaller turns the count back into the theorem about opposite points on the Earth.

topology · Borsuk ulam A straight line across a grid, and the word of walls it crosses. A line of slope 0.6180 crossing a unit grid, with each crossing marked V or H, beside the same path folded into a square as a billiard trajectory; the word begins VHVHVVHVHVVHVVHVHVVH.

The word a straight line spells

A ball rolling across a square table, forever, hits walls in some order: V for a side wall, H for the end wall. Unfold the table and the ball becomes a straight line across a grid, and the order of walls becomes a word — VHVHVVHVHVVHV… for the golden slope. That word has exactly n + 1 different blocks of every length n, the fewest any word that never repeats can have; every stretch of it holds its fair share of H's to within one; and its blocks occur with at most three different frequencies.

dynamics · Billiards Tseitin's clauses on the cube. the cube with a variable on each edge and a charge of 0 or 1 at each vertex, exactly one vertex charged 1. The parity demands give 32 clauses that cannot all be true.

A contradiction that is only a sum

Put a variable on every edge of a graph and ask each vertex for an odd or an even number of true edges, with the demands adding up to odd. Add all the demands and every edge is counted twice, so the left side is zero and the right side is one: the contradiction is a single sum. Resolution cannot add. It has to reach the same conclusion clause by clause, and on a graph where every group of vertices has many edges leaving it, that takes exponentially long.

logic · Resolution Unifying f(x, g(x)) with f(h(y), g(z)). Three term trees: f(x, g(x)), f(h(y), g(z)), and their common instance f(h(y), g(h(y))) under the most general unifier x ↦ h(y), z ↦ h(y).

Two terms made equal, and no more

Resolution with variables needs two literals to clash, and they clash only after something has been substituted for their variables. There are infinitely many substitutions that would do. One of them is the most general — every other is it followed by something more — and an algorithm of four rewriting rules finds it or proves there is none. That single computation turns the search for instances from guessing into arithmetic.

logic · Resolution The necklaces of 7 beads with 3 black. C(7, 3) = 35 arrangements in 5 rotation classes of sizes 7, 7, 7, 7, 7.

The row that proves a prime

Fermat's little theorem can be fooled: 561 passes it for every base and is not prime. Thread necklaces with a fixed number of black beads instead of any colours at all, and the count becomes a statement about a whole row of Pascal's triangle — every middle entry of row n is a multiple of n exactly when n is prime — which no composite can fake. Written as polynomials it is (x + a)ⁿ = xⁿ + a, and cut down to size it is the first proof that primes can be recognised in polynomial time.

number · Fermats little theorem Closing a path into a tour: the crossing pair the counting forces. A path through 10 points in a row, arcs from its two ends to their neighbours, and the crossing pair at step 3 whose two arcs replace that step to make a closed tour.

Half the neighbours forces a tour

Deciding whether a graph has a closed tour through every point is one of the hardest problems computers are asked to solve. Gabriel Dirac found a condition that settles it in one glance: if every point is joined to at least half the others, a tour exists. The proof is a counting argument on a single path, it runs as an algorithm, and two small graphs show that the half cannot be lowered — while random graphs show how much stronger than necessary it is.

discrete · Hamiltonian cycles Eliminating a letter by resolving it away. Tseitin triangle: 6 clauses; eliminating x: 4 resolvents, 2 tautologies, 4 clauses left; clause counts 6 → 4 → 2 → 1 ending with the empty clause.

Resolving one letter away at a time

Davis and Putnam's procedure of 1960 decides a set of clauses by removing its letters one at a time, replacing every clause that mentions a letter by all the ways of resolving it away. On a cycle the clauses never multiply; on a grid they swell by a factor of three and a half for each extra row, and on the 4 × 4 grid each extra unit of the order's width doubles the peak exactly. The cost is not the size of the formula but how wide it is.

logic · Resolution

Named alongside it

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

Exhaustive searchRefutationResolutionSatisfiabilityProof systemAntipodal pairExistence proofFair divisionGraphLower boundModular arithmeticParity

All concepts