Linear system
Named by 11 essays across 5 fields — each of them below, with the objects they name alongside it.
Colours that count more than three
Three colours prove the trefoil is knotted and say nothing at all about the figure-eight, which refuses them exactly as an unknotted loop does. The repair is to stop colouring and start counting — with five colours, or seven, and with the arithmetic done modulo the number of them.
The chain that stops
Give a chain a state it cannot leave and there is no long run to find — every walk ends. What is worth computing instead is how long it lasts and where it finishes, and both are exact answers to a linear system rather than limits of anything.
Four numbers and the rule is yours
A linear generator can be solved. Given a few of its outputs, the multiplier and the increment fall out of two congruences, and every future output is then known exactly — which is a failure of a completely different kind from the lattice defect, and is not detected by any test of how evenly the points are spread.
A polynomial behind the colourings
The figure-eight knot and the cinquefoil both have determinant five, so they admit exactly the same colourings, and every counting argument treats them as one. Put a variable where the colouring rule has a two and the determinant becomes a polynomial — and the two knots come apart.
Three patterns in a circle
Race three coin patterns at once and the gamblers' accounting still gives each one's chance of arriving first — one fairness equation per pattern. What it does not give is any way to read the three-way result off the two-way ones. HHHT, TTHH and HTTH beat one another in a circle, and HHH loses both its head-to-head races and still finishes ahead of one of the patterns that beat it.
Every point at the average of its neighbours
A planar graph can be drawn without crossings, but finding such a drawing looks like a search. Tutte found in 1963 that it is not: pin one face to a convex polygon, put every other point at the average of its neighbours, and the drawing that results has straight edges, convex faces and no crossings at all — provided no two points can cut the graph apart. It is the position a network of equal springs settles into, and it is also where a random walk expects to leave.
The boards on which every light goes out
In Lights Out, pressing a light toggles it and its neighbours, and the goal is to turn every light off. Over the field with two elements the puzzle is a system of linear equations, and whether every pattern can be cleared depends only on whether one matrix is invertible. On a 3 × 3 board it is; on 5 × 5 a quarter of patterns can be cleared; on 39 × 39 one in four billion. Which sizes fail is decided by a common factor of two polynomials.
Every light on, from every light off
In Lights Out, pressing a light toggles it and its neighbours. On a five-by-five board only one pattern in four can be reached from all off — and yet all on is always one of them. The same is true on every board and on every network of lights whatever, provided the influence runs both ways. The proof is a single observation about symmetric matrices over a field with two elements, and it fails, as a three-arrow example shows, the moment influence runs one way.
Every random game has an odd number of equilibria
Find every equilibrium of eleven thousand random games — pure and mixed, by trying every pair of strategy sets the players might mix over — and the totals are 1, 3, 5, 7, … and never an even number. The count is a sum of signs: equilibria of index +1 outnumber those of −1 by exactly one in every game. The average grows about 28% with each strategy added, and searching for the game with the most turns up the coordination game's 2ⁿ − 1, a pattern that holds only up to five strategies.
When a press skips its own light
In Lights Out every board can be turned from all off to all on, because each press toggles its own light. Change the rule so a press toggles only the neighbours and the guarantee is gone: 310 of the 3,600 boards up to sixty by sixty cannot be lit. A single comparison of powers of two predicts every one of them, and on general graphs the answer depends on whether the number of vertices is odd or even, for a reason that is one line of algebra.
Half the chance for every silent set
In the lights game where a press toggles only the neighbours, a random network can be lit about 56 times in a hundred when it has an even number of vertices and 44 when odd. The numbers are 0.560562 and 0.439438, they add to one, and they come from a chain: each new vertex raises or lowers the dimension of the silent sets by one, and each dimension halves the chance.
Named alongside it
The objects these essays reach for when they reach for this one.
ParityFinite fieldKernelInvariantMarkov chainRankExhaustive searchExpectationKnotKnot determinantModular arithmeticRandom graph