Concept

Exhaustive search

Settling a question by generating every candidate and testing each one. It needs no cleverness and gives a definite answer, and it is available only when the candidates can be listed and the list is short enough to finish.

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

Trisect every angle, and an equilateral triangle appears. A triangle with angles 78°, 54°, 48°, its six angle trisectors, and the triangle whose corners are where the trisectors nearest each side meet. That inner triangle is equilateral, which is Morley's theorem.

Three trisectors and a triangle nobody expected

Cut every angle of a triangle into three. The trisectors nearest each side meet in three points, and those three points are always the corners of an equilateral triangle — for every triangle there is, with no exceptions and no reason anybody finds obvious.

geometry · Morley
3 rounds on chains of 4 and 5. Two chains of dots with pebbles placed in turn, and the transcript of a play: Spoiler picks an element of one chain, Duplicator answers in the other, and the pebbles must keep the same order.

A game that decides what can be said

Two players take turns pointing at elements of two structures; if the second can survive k rounds, then no sentence with k quantifiers tells the structures apart — a statement about infinitely many formulas, settled by a finite search.

logic · Ehrenfeucht–Fraïssé games
The de Bruijn graph on 2 letters and words of 3, and the cycle through it. A graph whose vertices are short words and whose arrows are words one letter longer, with a closed walk using every arrow exactly once marked, and the cyclic sequence it spells.

Every word once, around a cycle

A cyclic string of eight bits holds all eight three-bit words, each exactly once — and the reason such a thing exists is that the constraint linking overlapping windows is itself the construction.

computation · De bruijn
Every order of arrival for three partners, and what each player adds. A table with one row per order in which the players could arrive, giving what each adds to the group already present, and the average of each column as that player's share.

The order everybody arrives in

Three people jointly earn nine, and the question is what each is owed. Ask instead what each adds on walking into a room the others are already in, average that over every order they could have arrived in, and four modest conditions leave no other answer.

applied · Shapley value
The splits no group can beat, for three partners. The triangle of ways to split a fixed total between three players, with each coalition's demand drawn as a straight cut across it, and the region surviving every cut shaded.

A split nobody can walk away from

Every way of dividing what a group earns is a point of a triangle, and every coalition's threat to leave cuts a straight line across it. What survives all the cuts is the set of stable divisions — and for one three-player game there is nothing left.

applied · The core
3 consistent judges, and a majority that is not. A table of judges against three questions, every judge's row internally consistent, with the majority answer to each question underneath forming a combination no judge holds.

The court that contradicts itself

Three judges each answer three questions, and each answers them consistently. Take the majority on each question separately and the answers no longer hang together — the body as a whole endorses a combination no member of it holds, and no rearrangement of the procedure removes the problem.

applied · Judgement aggregation
256 consecutive pairs from xₙ₊₁ = 137xₙ + 187 mod 256. Consecutive outputs of a linear congruential generator plotted as points of a square, falling on a small family of evenly spaced parallel lines.

The planes a recurrence cannot leave

One multiplication and one addition, taken modulo a fixed number, produce a sequence that passes for random one value at a time. Taken two or three at a time it does not, and the reason is a whole-number relation that pins every point onto one of a small family of parallel lines.

computation · Pseudorandomness
Which axioms hold on which frames. A table of frames against modal axioms, each cell decided by checking the axiom under every valuation.

The axiom is the shape of the graph

Add one operator meaning necessarily and the choice of which axioms to accept stops being a matter of taste. Each candidate axiom is true of exactly those worlds-and-arrows diagrams whose arrows have a stated property, and a logic is a class of graphs.

logic · Modal logic
The most triangle-free edges on 6 points. A graph on 6 points carrying 9 edges and no triangle, found by examining every graph on those points, with the two sides its edges cross between drawn apart.

The edge that forces a triangle

A graph on six points can carry nine edges with no three of them closing a triangle. It cannot carry ten. The bound is n²/4, the graphs that achieve it are all the same shape, and both facts fall out of examining every graph there is.

discrete · Extremal graphs
Two colours avoid a progression up to 8, and no further. The numbers 1 to 8 in the two colours that avoid three equally spaced numbers in one colour, with the number 9 beside them in both colours and the pattern each choice forces.

Three in a row on the number line

Colour the numbers one to eight in two colours and it can be arranged that no three equally spaced numbers agree. Add the ninth and it cannot. The structure being forced is arithmetic rather than graphical, and the proof is a different proof.

discrete · Ramsey theory
The affine plane of order 3, one parallel class at a time. The n² cells of a complete set of orthogonal Latin squares of order 3, with the rows, the columns and each square's symbol classes drawn as lines of a plane.

The plane hiding in the squares

A complete family of orthogonal squares is not a collection of squares that happen to agree nowhere. It is a geometry — a plane with n² points in which every two points lie on exactly one line — and reading it that way is how the impossible orders were found.

computation · Latin squares
How many Latin squares there are, orders 1 to 8. The number of Latin squares of each small order, the ones up to six counted by exhaustive search and the larger ones quoted, on a logarithmic scale.

Nine thousand four hundred and eight

There are four Latin squares of order four once the first row and column are fixed, fifty-six of order five, and nine thousand four hundred and eight of order six. The exact answer is known for eleven orders and for no more — and yet a half-finished square can always be finished.

computation · Latin squares
The 576 squares of order 4, sorted by whether they associate. Every Latin square of order 4, counted by whether it associates and by which group it is when it does.

Sixteen of five hundred and seventy-six

A Latin square is a multiplication table in which every equation has exactly one solution. Ask it to be associative as well and almost every square drops out — sixteen of the five hundred and seventy-six of order four survive, and they are the two groups.

computation · Latin squares
A path of 4 bounces that closes, in a triangle of 100°, 40°, 40°. A triangular billiard table with a periodic path found by an exhaustive sweep of starting positions and directions.

The triangle nobody can settle

Does every triangular billiard table have a path that closes on itself? Acute triangles do, right triangles do, triangles with rational angles do — and for the rest the question has been open since it was asked.

dynamics · Billiards
Two models the modal language cannot separate, and two it can. Four Kripke models in two pairs: the upper pair joined by a bisimulation and agreeing on every formula, the lower pair separated by a formula found by search.

Two diagrams the language cannot tell apart

A modal formula sees a diagram of worlds and arrows through a very narrow window. Exactly how narrow is settled by a game: where one player can answer every move, no formula whatever separates the two starting worlds, however different the diagrams look.

logic · Modal logic
Axioms, the conditions on the arrows they answer to, and the one that answers to none. A table of modal axioms with the property of the accessibility relation each corresponds to, every row decided by sweeping all relations on up to four worlds.

The axiom with no property of the arrows

Each axiom of modal logic can be matched by hand to a condition on the arrows between worlds. There is a recipe that does it for a whole class of axioms, and there is an axiom the recipe cannot reach — not because nobody has looked, but because no condition on the arrows defines it at all.

logic · Modal logic
Three properties that leave the middle, and one that cannot. Four measured curves of the share of random graphs having a property, plotted against the number of points: three first-order properties running to zero or one, and the parity of the edge count sitting on a half throughout.

Nearly always, or nearly never

Toss a coin for every pair of points and ask whether the graph that results has some property. For a property a first-order sentence can state, the answer in the limit is never a genuine probability — it is zero or it is one, and the game is what proves it.

logic · Ehrenfeucht–Fraïssé games
What a sentence of depth 2 can reach. Two rings of points, of 14 and 19 points, each with a run of 9 consecutive points marked as the neighbourhood a sentence of depth 2 can inspect.

The distance a sentence can see

A first-order sentence with three quantifiers cannot notice anything about a graph beyond a fixed distance from the points it names. That single limitation is why it cannot say connected, and why the failure survives every attempt to add more quantifiers.

logic · Ehrenfeucht–Fraïssé games
The half of 24 permutations that commutators reach. A block of 24 squares, one per permutation, with the 12 generated by commutators shaded, beside bars counting the homomorphisms to each cyclic group.

The only bit that survives

A shuffle can be called even or odd, and the label behaves under composition. Ask whether some cleverer label — a number out of three, or out of four — could behave the same way, and the answer is that nothing else can — one bit is exactly what a permutation gives up.

algebra · Permutation parity
A 2×3 sliding puzzle: 360 arrangements of 720 can be reached. Two arrangements of a small sliding puzzle side by side, the solved one and the one with two tiles exchanged, with the count of positions reachable by sliding found by walking every move.

The puzzle that is exactly half solvable

A sliding puzzle sold with two tiles swapped is not a hard puzzle; it is an impossible one, and the proof is a quantity that no slide can change. The same argument, run three times at once, says that one arrangement of a scrambled cube in twelve is reachable.

algebra · Permutation parity
Every point of a hull, as a mixture of three of 11 points. A scatter of points with its convex hull outlined, and several interior points each shown inside a triangle of three of the scattered points, found by trying every triple.

Three points, however many there are

A point inside the hull of a thousand points is inside the hull of three of them. Any four points split into two groups whose hulls meet. And a family of convex sets, every three of which have a common point, has one common to all — three, in each case, being one more than the dimension.

analysis · Convexity
Five rules, and the one condition each of them gives up. A table with one row per aggregation rule and one column per condition, marking which conditions each rule satisfies when run over every profile of the agenda.

Four ways out, and what each costs

An impossibility theorem lists conditions and says no rule has them all. That leaves exactly as many escapes as there are conditions, each of them a real institution — a dictator, a two-stage procedure, a supermajority, a restricted agenda — and each escape's price can be counted rather than argued about.

applied · Judgement aggregation
The largest code at each length, distance 3, against four bounds. A table with one row per word length, giving the exact size of the largest code of that length at the stated minimum distance and the values of the Singleton, Hamming, Plotkin and Gilbert-Varshamov bounds.

The best a code can be

A code is a set of words chosen far apart, and every construction answers "here is one" rather than "here is the best". The best can be computed at small lengths, and putting four classical bounds beside the exact answer shows which of them is doing the work and where none of them is.

computation · Error-correcting codes
How many codewords lie within each radius, for a [7,3] code over 11 symbols. A bar for each decoding radius, its height the largest number of codewords found inside a ball of that radius around a randomly drawn received word, with the unique-decoding radius and the Johnson radius marked.

Past half the distance

A code of minimum distance five corrects two errors, and every account stops there. Two is the largest number for which the answer is unique — and a decoder that returns a short list instead of one answer reaches considerably further, which can be measured by counting the codewords in a ball.

computation · Error-correcting codes
The sixteen lattice polygons with a single point inside. A grid of sixteen small lattice polygons, each drawn on its own patch of grid with the single interior point marked, labelled with its number of boundary points.

Sixteen polygons with one dot inside

Fix one of Pick's two counts at one and ask what is left. The answer is a finite list, the list has exactly sixteen entries, each one is its own kind of object with a dual that is another entry, and the whole classification is a search a page can carry out.

discrete · Pick theorem
The lattice-point count inside a circle, less its area, out to radius 160. A plot of the difference between the number of lattice points in a disc and the disc's area, against radius, with envelopes proportional to the square root and the two-thirds power drawn.

The dots a circle catches

Pick's theorem gives a lattice polygon's area exactly, with no error term anywhere. Ask a circle the same question and the exactness is gone: the count is the area plus something, the something has been measured for two centuries, and nobody knows how big it is.

discrete · Pick theorem
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
Every parity pattern of length up to 12, and each occurring exactly once. A bar for each pattern length, showing the number of distinct parity patterns produced by all remainders of that power of two, which equals the number of remainders at every length.

Every pattern happens exactly once

Choose any sequence of odds and evens and there is exactly one residue class whose orbit follows it, and exactly one fraction that cycles through it forever. The Collatz conjecture is then the statement that only one of those infinitely many cycles is made of whole numbers.

dynamics · Collatz
A 6-cycle and two 3-cycles: refinement cannot tell them apart. Two graphs side by side — one cycle and two smaller cycles — with the same number of points, the same number of edges and every point of the same degree.

The game the algorithm was playing

Change what Duplicator has to offer — a whole bijection instead of one element — and the game stops measuring first-order logic and starts measuring colour refinement, the algorithm every practical graph-isomorphism test begins with. Two subjects that grew apart are one game with the moves relabelled.

logic · Ehrenfeucht–Fraïssé games
A signal both can see, and neither wants to disobey. A two-by-two game with a distribution over its four cells, drawn as the weight on each. Obeying the recommendation is a best reply for both choosers, and the pair collects 21/2 between them.

A signal both can see

Two choosers who randomise privately can reach a set of outcomes that is smaller, and worse, than the set they reach when a device draws one cell and whispers each of them their half of it. Nothing is enforced and nobody is bound, and the arrangement is stable anyway.

applied · Equilibrium
A landscape nobody is looking at, and every move goes downhill on it. The 8 states of a congestion game with 3 participants and two resources, ordered by Rosenthal's potential, with every improving unilateral move drawn as an arrow. Every arrow points downward.

The landscape nobody is looking at

Letting participants move one at a time to whatever is currently better can cycle forever, and on a network of congestible roads it cannot. The reason is a single number attached to each state that falls by exactly what the mover saves.

applied · Equilibrium
What the chain costs on a 6-gon: 39 pieces. A regular 6-gon fanned into 4 triangles, each with the three cuts that turn it into a rectangle, beside the running count of the pieces the whole chain produces — 39 of them.

Finitely many, and nobody says how many

The theorem promises a dissection exists and the proof produces one. Running the proof on a hexagon produces thirty-nine pieces, ingenuity produces five, and there is no method for proving that five cannot be four.

computation · Scissors congruence
Biproportional seats against their fair shares. A table of votes for 3 districts and 4 parties beside the seats the biproportional method gives, each with the fair share from the continuous fit, and the cell whose seats fall outside its quota marked.

The table inside every quota

Give seats to districts and parties at once, and every cell of the table has a fair share it ought to round from. A table rounding every cell to its floor or its ceiling, with every total exact, always exists. The biproportional method does not always choose one: here it gives a party 2 seats where its fair share is 3.088.

applied · Apportionment
Sixteen halves in a three-by-three-by-three table of seats. A three-way table of fair shares drawn as three slices, one per group, with sixteen cells holding a half and every line total, along districts, parties and groups, equal to zero or one.

Where the rounding runs out

In two dimensions a table of seats inside every fair share always exists. Add a third family of totals — every district and party split between groups — and it need not. Sixteen halves in a three-by-three-by-three table meet every total, and no whole table does it without a seat where the fair share is nothing, because the halves close a loop of seven.

applied · Apportionment
A network of six places and the tree that holds all fifteen of its cheapest cuts. A network with capacities on its roads beside a tree on the same places, whose edge numbers give the cheapest cut between any two places as the smallest number on the path joining them.

One tree for every cut

A network of six places has fifteen pairs, and each pair has its own cheapest cut. All fifteen can be read off a tree with five numbers on it: the cheapest cut between any two places is the smallest number on the tree's path between them. Gomory and Hu proved in 1961 that such a tree always exists, and building it takes five cuts, not fifteen.

discrete · Network flow
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
The orders of the 8 units modulo 15. A strip of the units modulo 15 with each one's multiplicative order beneath it, the largest order marked at 4 against φ(15) = 8.

The exponent that is smaller than Euler's

Euler's theorem raises every unit to the count of the units and gets one. The smallest exponent that works for all of them at once is often much smaller — and a composite is invisible to Fermat's test exactly when that smaller number divides n − 1.

number · Fermats little theorem
Five certificates against any two of three decide. A table of every minimal balanced family on three players, what each demands of the game, and whether the grand coalition's value covers it — the complete test for whether a stable split exists.

Five weighings and the question is closed

Searching the triangle of splits can only ever fail to find a stable one, which is not the same as there being none. Weighing five families of coalitions against the whole settles the question outright — and the family that fails is the proof that nothing survives.

applied · The core
The splits of any two of three decide that nobody can out-argue. The triangle of all splits of a joint gain, with the splits marked at which every player's loudest complaint against every other is matched by an equally loud complaint back.

An objection one player makes to another

The core lets a coalition object to everybody at once. Narrow it to one player objecting to one other, require every such objection to be met by an equally loud one coming back, and exactly one split survives — with no dictionary order anywhere in the argument.

applied · The core
The most mass 2 deviations out, with only a mean and a variance. The distribution putting as much probability as possible outside a window 2 standard deviations wide, found by searching every triple of support points, with the quadratic certificate that bounds it drawn over.

The bound is the answer to a search

Chebyshev's inequality is not a clever estimate that happens to be sharp. It is the exact answer to a maximisation over all distributions with a stated mean and variance, and the polynomial that proves nothing beats it is the certificate a search of that kind always produces.

probability · Concentration
What one input can do, over 1024 cases. A table of functions of several inputs with the largest effect any single input has on each, the bound that effect implies, and the true tail probability — computed by enumerating every input.

No single input can move it far

Independence was never the hypothesis doing the work. A quantity built from many separately drawn inputs concentrates whenever changing one of them moves it only a little — and that covers quantities which are not sums of anything and have no formula at all.

probability · Concentration
The smallest algebra that refutes each formula. A table of formulas against the smallest finite Heyting algebra refuting each, found by searching every order on a few points, with the formulas no such algebra refutes marked.

Refutable in something small

A formula that is not a theorem of the constructive system fails in some finite algebra, and the algebra can be found by search. That single property is what makes the propositional logic decidable — and the predicate version loses the property and the decidability with it.

logic · Non classical logic
Who survives with two pebbles and who with three, over 4 rounds. A table of three pairs of graphs with, for each, whether the duplicating player survives a two-pebble game and a three-pebble game played to a fixed depth.

The boundary at three variables

Restrict a sentence to two variable names and it can still be arbitrarily long, because the names are reused. What it cannot be is deep: every satisfiable two-variable sentence has a small model, so asking whether one is satisfiable is a bounded search. Allow a third name and the question becomes undecidable.

logic · Ehrenfeucht–Fraïssé games
The one line from which the nearfield plane looks Desarguesian. A grid of the 91 lines of the nearfield plane of order nine shaded by how many of 40 Desargues configurations with that line as axis failed; only the line at infinity has none, and every other line at least 20.

A plane no field built

Every finite field builds a projective plane, and for a long time every known plane was built that way. The plane over Dickson's nearfield of order nine has ninety-one points, ninety-one lines and every incidence right — and Desargues' theorem fails in it on most configurations tried, except for one line, from which it never fails at all.

computation · Finite geometry
The conic y = x² in the plane of order 7. A 7 by 7 grid of the affine plane over GF(7) with the points of the conic y = x² filled and its point at infinity marked: 8 points, no three collinear.

The curve that no three points in line define

In a finite plane, take as many points as possible with no three on a line. In odd order the largest such sets have one more point than the order — and every one of them, searched exhaustively in the small planes and proved by Segre for all odd orders, is a conic. In even order every tangent meets at one point, which can be added, and the curves stop being forced.

computation · Finite geometry
The Petersen graph, which a five-edge count rules off the plane. The Petersen graph drawn as an outer pentagon, an inner pentagram and five spokes: ten points, fifteen edges, girth five, and more edges than the 13.33 a flat drawing with five-edge faces allows.

Five spokes squeezed into K5

The Petersen graph has no point with four neighbours, so no stretched copy of K5 can sit inside it. Contract its five spokes and K5 appears anyway. Kuratowski's theorem forbids stretched copies and Wagner's forbids squeezed ones, the two notions disagree on this graph — and they still name exactly the same planar graphs.

discrete · Planarity
Every stable matching leaves out the same people. 4 stable matchings of a market with short lists, drawn as two columns joined by edges; every one leaves the same letter and number unmatched.

The people every stable answer leaves out

Let the lists be short and let one side take several partners. Stable matchings still exist and there can be many of them — but every one leaves out exactly the same people, and a member who is left with an empty place holds exactly the same partners in every one. A three-line count proves it.

applied · Stable matching
The odd ring that forbids a stable pairing. The ranked lists of 6 people and a stable partition of them drawn on a circle: pairs as plain chords, a ring of three or more as arrows from each person to the one they hold. An odd ring is present, as it is in every stable partition of this instance.

A ring that no pairing can break

Put everybody in one pool and a stable pairing may not exist. Allow rings as well as pairs and something stable always exists — and the pairs-only answer fails exactly when that stable arrangement contains a ring of odd length. Two sides make every ring even, which is the whole reason the two-sided theorem holds.

applied · Stable matching
The most edges with no four-cycle. Points for n = 2 to 9: the largest number of edges with no four-cycle, 1, 3, 4, 6, 7, 9, 11, 13, between the counting bound above and ½n^(3/2) below, far under the complete graph's count.

The densest graph without a square

Forbid four points joined in a cycle and a graph can keep only about ½n^(3/2) of its edges — far fewer than the quarter of all pairs a triangle-free graph keeps. Counting pairs of neighbours proves the ceiling in two lines. What reaches it is not a random graph but a finite geometry: the points of a projective plane, joined when they are orthogonal.

discrete · Extremal graphs
A local rule taking a vote. A space-time diagram of the GKL rule on 149 cells from a random row with 69 ones. Black and white regions grow and meet along slanting boundaries, and after 69 steps the whole ring is 0.

No local rule can count the votes

A ring of cells, each holding 0 or 1, has to agree on whichever value is in the majority — every cell seeing only its neighbours. The best-known rule gets it right most of the time and wrong near a tie; no rule of any radius gets it right always. Yet two rules run one after the other do, on every ring, and the first of them is the traffic rule.

dynamics · Cellular automata
A triangle, its midpoints and its centroid, turned into lines. The dual arrangement of 7 points: one line per point, crossing where points were collinear. 3 crossings are of exactly two lines, the dual of the ordinary lines; the others are where three or more meet.

Three ordinary lines from a count

Kelly's proof finds one line through exactly two of the points by minimising a distance. Melchior, seven years earlier, had found three — by turning every point into a line and counting the corners, edges and regions of the picture that results. Euler's formula for the projective plane does the rest, and it says exactly which configurations have no more than three.

geometry · Ordinary lines
Infinitely many guessers, finitely many wrong. Three rows over the first 40 places: the hats worn, the chosen representative of their class, and a row of marks showing each guess right or wrong. The 5 wrong guesses all fall within the first 14 places, up to a marked place; every later guess is right.

Infinitely many guessers, finitely many wrong

An infinite line of people each wears a black or white hat, sees every hat in front and none of their own, and must guess their own colour. With a finite line, each guesser is right half the time whatever they agree in advance. With an infinite line and the axiom of choice, they can agree a strategy under which all but finitely many are right — and nobody can carry it out.

logic · Axiom of choice
The cyclic square of order 6: no transversal, and one of 5 cells. A Latin square of order 6 with a partial transversal of 5 cells shaded — one cell in each row and column but one, each with a different symbol. No full transversal exists.

One cell short of a transversal

A transversal of a Latin square picks one cell in every row and every column with every symbol different. The cyclic squares of even order have none, and that was settled by a parity argument centuries old. Whether every square of odd order has one is a conjecture from 1967 that nobody has proved; whether every square comes within one cell of having one was settled only in 2023, and only for squares large enough.

computation · Latin squares
The postman's route: 24 blocks of street, walked in 28. A street network with its odd-degree vertices marked and the streets a shortest closed route must walk twice drawn doubled, dashed in a second colour, pairing up the odd vertices.

The streets a postman walks twice

A postman must walk every street of a district and come back. If every corner has an even number of streets, no street needs walking twice. If not, some must — and the ones repeated always join the odd corners in pairs. Pricing every way of pairing them finds the shortest round; pairing the nearest corners first does not.

discrete · Eulerian paths
Six sentences from two quantifiers, and which imply which. A diagram of the six sentences that can be built from two quantifiers and a relation, arranged from strongest to weakest with arrows for implication, each labelled with how many of the 512 relations on three points satisfy it.

Six sentences from two quantifiers

One relation, two variables, 'for every' and 'there is': there are eight ways to arrange them and six different sentences come out. Which of them imply which is a small, complete diagram, found by checking all 512 relations on three points — and the diagram crosses over in the middle, which is where every confusion about the order of quantifiers lives.

logic · Quantifiers
The pairs from five, joined when disjoint, need three colours. The Petersen graph drawn with its ten vertices labelled by pairs from one to five, edges joining disjoint pairs, and a proper colouring with three colours.

The colours a circle forces

Take every pair from five things and join two pairs when they share nothing. Three colours are enough to colour the result so joined pairs differ, and two are not — but no triangle, no dense cluster and no counting argument explains why. The reason is five points on a circle and a direction that cannot be told apart from its opposite, and the same reason, one sphere at a time, settles Kneser's question for every size.

topology · Borsuk ulam
The nearest consistent verdict: a 3-way tie at distance 4. A table of the 4 consistent judgement sets on the agenda p, q, and p and q, each with its number of disagreements with each of 3 judges and the total; the smallest total is marked.

The nearest consistent verdict

When a court's majorities contradict each other, one repair is to announce the consistent verdict that disagrees with the judges least. It treats the premises and the conclusion alike, which neither of the two standard procedures does. On the classic case it returns a three-way tie; on five judges, with every question weighted equally, it never returns a single answer on a troubled profile at all — and what breaks the tie is a decision about which question matters more.

applied · Judgement aggregation
Which agendas majority can vote on safely. A table of 7 agendas with the size of their largest minimally inconsistent set and the count of inconsistent majority outcomes over all profiles of three and five judges.

Agendas that cannot contradict themselves

A court voting on two unconnected questions never contradicts itself, and neither does one voting on a chain of thresholds. A court voting on two premises and their conjunction sometimes does. What separates them is the size of the smallest sets of judgements that cannot all be true: pairs are harmless, because two majorities always share a judge, and triples are not. The same count says exactly how large a supermajority has to be to stay consistent on any agenda.

applied · Judgement aggregation
Twenty-seven choices of trisector, and the eighteen equilateral triangles. Twenty-seven small panels, one for each choice of trisecting line at each corner of a triangle, each drawing the triangle and the triangle the chosen lines cut out; the eighteen equilateral ones are marked.

Eighteen equilateral triangles

Every angle of a triangle has three trisectors, not one, once the angle and its outside are both counted. Choosing one at each corner gives twenty-seven ways to cut out a triangle, and eighteen of them give an equilateral one. The nine that fail are exactly the choices whose labels add to 2, 5 or 8 — and all eighteen equilateral triangles have their sides in the same three directions, fixed by a third of the difference between two angles.

geometry · Morley
Weighted votes: two functions with a cut, and parity without one. For three functions of three letters, the eight assignments placed on a line by a weighted count, with true assignments filled and the threshold marked where one exists.

A plane through the cube

Some truth functions are weighted votes: give each letter a weight, add the weights of the true letters, and say yes when the total passes a threshold. On the cube of assignments, such a function is a plane cutting the true corners from the false. Majority is one. Exclusive-or is not, and never can be — and of the 65,536 functions of four letters, only 1,882 are. The ones that are are exactly what a single artificial neuron can compute.

logic · Truth functions
9 corners of the 4-cube: some corner always has 2 chosen neighbours. The 4-dimensional cube with 9 of its corners chosen so that no chosen corner has more than 2 chosen neighbours, the fewest possible, with the edges between chosen corners drawn heavy.

Half the cube and √n neighbours

Choose more than half the corners of an n-dimensional cube, any way at all, and some chosen corner has at least √n chosen neighbours. That statement about a cube settled a thirty-year question about how sensitive a truth function must be to its inputs, and its proof is a matrix of plus and minus ones whose square is n times the identity. A search over every choice for the 4-cube finds the bound exactly: nine corners, and some corner always has two chosen neighbours.

logic · Truth functions
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
A smallest model of ∀x (Ax → ∃y (By ∧ ¬Cy)) ∧ ∃x (Ax ∧ Cx) ∧ ∀x (Bx → ¬Ax). Three overlapping circles with some regions shaded as empty and a single dot in each occupied region, forming a model of a sentence of monadic first-order logic.

One thing in each region is enough

Give first-order logic its full apparatus of nested quantifiers but only one-place predicates, and every question about truth is still settled by the regions of a diagram. A predicate cannot tell apart two things in the same region, so no model ever needs more than one thing per region — and with three predicates there are only 255 models to try.

logic · Class diagrams
Carroll's babies and crocodiles, on four ellipses. Four overlapping ellipses labelled with the four classes of a sorites, the regions emptied by its premises shaded, and the regions its conclusion requires to be empty outlined.

The conclusion is what survives the erasing

Lewis Carroll's puzzles give three premises about four classes — babies, logical people, the despised, crocodile-managers — and ask what follows. Draw all four, shade what the premises rule out, then erase the classes the conclusion is not about: a region survives as empty only if everything above it was. What is left is the conclusion, and erasing a class turns out to be exactly one step of resolution.

logic · Class diagrams
Six thirtieths of a turn that add to nothing. On the left a unit circle with the roots of unity in a vanishing sum marked and coloured by origin; on the right the same unit vectors placed head to tail, returning to their start.

The sums of roots of unity that add to nothing

All n of the n-th roots of unity add to zero, and so does any regular polygon among them, turned. Those are not the only vanishing sums: six thirtieths of a turn close into a loop with no polygon in them. Which counts of roots can close at all is decided by the prime factors of n — no seven fifteenths ever add to zero — and the same question counts where the diagonals of a regular polygon cross.

algebra · Roots of unity
Counting walks that never revisit a square. Dots for the ratio of successive counts of self-avoiding walks and for the n-th root of the count, against the number of steps, both approaching a dashed horizontal line at the connective constant.

A walk that may not step where it has been

Forbid a walk on the square grid from ever revisiting a site and the number of possible n-step walks grows like 2.638ⁿ instead of 4ⁿ — a number nobody can write down exactly. On the honeycomb it is exactly √(2 + √2), proved in 2010. And the walks spread out like n to the three-quarters, faster than any ordinary walk, which physicists have used since 1949 and mathematicians still cannot prove.

probability · Random walk
Pollak's circle: one rotation in every n + 1 parks on the line. Several circles of numbered spots, each showing where cars park when every preference in a list is rotated by a fixed amount, with the one rotation that leaves the last spot empty highlighted.

Cars that park, and trees that grow

Three cars arrive at a one-way street with three spaces; each has a favourite space, drives to it, and takes the first free one from there on. Of the 27 lists of favourites, exactly 16 let every car park — the same 16 as the labelled trees on four points. The reason is a circular street with one extra space, on which every list parks and exactly one rotation of it leaves the extra space empty.

discrete · Labelled trees
A random labelled tree on 60 points. A tree drawn in horizontal layers by distance from a root point, with the leaves coloured differently from the internal points.

A random tree is one part in e leaves

Choose a labelled tree on n points uniformly at random. A point is a leaf exactly when its label never appears in the tree's Prüfer code, so the share of leaves is (1 − 1/n)^(n − 2) — half the points for a tree on four, 36.8% for a large one, the reciprocal of e. The whole degree distribution follows the same way: one plus a Poisson count with mean one.

discrete · Labelled trees
How often three candidates' majorities go in a circle. The exact probability that pairwise majority among three candidates is cyclic, for every odd number of voters from 1 to 41, under two models of how ballots are drawn, with their limits of about 8.77% and 6.25%.

How often the majority goes in a circle

Three voters and three candidates give 216 profiles, and 12 of them are cycles. Count every electorate up to 41 voters exactly and the share climbs towards 8.77%, a number Guilbaud found in 1952 as the solid angle where three half-spaces at the tetrahedral angle overlap. Add candidates and a winner goes missing half the time; let voters share one axis and cycles vanish. The number is always a property of the model of how ballots are drawn.

applied · Voting rules
Latin squares of order 4, and the ones that are also Sudoku grids. Two 4×4 Latin squares with their 2×2 boxes outlined: one in which every box also holds 1 to 4, and the cyclic square, whose top-left box repeats a symbol. Of all 576 Latin squares of order 4, 288 pass the box test.

A Latin square with boxes

A finished Sudoku is a Latin square of order nine with one extra rule: each 3×3 box holds every digit once. At order four the extra rule keeps exactly half of the 576 Latin squares, the 288 survivors are two grids in disguise, and no puzzle can be pinned down by fewer than four clues. At order nine every one of those questions needed a computer, and the answers are 6.67 × 10²¹ grids, 5.47 billion essentially different ones, and seventeen clues.

computation · Latin squares
15 stable matchings, by what each side pays. A scatter plot of every stable matching of one instance by the total rank each side receives, running from side one's best matching to side two's, with the median, the least-total and the most even matchings marked.

The matching in the middle

List every stable matching of a market, give each member their stable partners sorted from best to worst, and hand each the one in the middle. Nothing says the result should even be a matching — two people might pick the same partner — and yet it always is one, it is always stable, and the other side gets its median partners too.

applied · Stable matching
Eighty-one cards and twenty with no SET among them. A three-by-three arrangement of three-by-three grids covering the eighty-one points of four-dimensional space modulo three, with twenty cells marked that contain no three on a line.

Twenty cards with no set among them

The card game SET is a four-dimensional space over the integers mod 3, and a set is a line in it. Twenty cards can avoid every line and twenty-one cannot — a fact that took a proof in 1970 — while laying cards down at random and stopping when nothing more fits reaches twenty about once in two thousand tries.

computation · Finite fields
Three places cut apart for 13. A network of eight places with road capacities, three of them lettered, coloured by which of the three sides of the cheapest three-way cut each place falls on, with the cut roads dashed.

Three places cut apart

Separating two places as cheaply as possible is solved exactly by a flow. Separating three from one another is a different problem: no flow measures it, the pairwise answers do not add up to it, and the best shortcut known in 1994 — cut each place off on its own and throw the dearest cut away — is guaranteed only to within a third of the truth.

discrete · Network flow
Numbers whose divisors add to two, three, four, five and six times themselves. A table of multiperfect numbers with the multiple their divisor sum makes of them, the number itself and its factorisation into prime powers.

Divisors that add to three times the number

The divisors of 6 add up to 12, twice 6: a perfect number. The divisors of 120 add up to 360, three times 120, and those of 30,240 to four times it. Numbers like these were a sport for Fermat and Descartes, and they are held together by one fact — the ratio σ(n)/n is a product over the primes, and each prime can add only a little.

number · Perfect numbers
Numbers up to 600 that share their abundancy. A scatter of abundancy against n with horizontal segments joining numbers that have exactly the same abundancy.

A ratio nobody else has

Divide the sum of a number's divisors by the number and you get its abundancy: 2 for every perfect number, 12/5 for both 30 and 140. Numbers that share an abundancy are called friends. Some numbers provably have no friend at all, most have friends only far away — and for 10, whose abundancy is 9/5, nobody knows whether a friend exists.

number · Perfect numbers
Three patterns that beat one another in a circle: HHHT, TTHH, HTTH. Three coin-toss patterns at the corners of a triangle with arrows showing which beats which in two-way races, and each pattern's chance of winning when all three race.

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.

probability · Expectation
Gluing two countermodels: p ∨ ¬p. Two small Kripke models, each refuting one half of a disjunction, and the model made by placing both above a new first stage, at which neither half is forced.

A proof that says which half

Classical logic proves p ∨ ¬p without any idea which half is true. The constructive system never does that: whenever it proves a disjunction, it proves one of the two halves. The reason is a picture — two countermodels placed side by side above a new first stage that forces neither — and the logics between the two lose the property exactly when their pictures are not allowed to be glued.

logic · Non classical logic
Several colours on every vertex of a Kneser graph. A grid of Kneser graphs on pairs from five to eight points against the number of colours per vertex, each cell giving the fewest colours needed and the counting lower bound.

Several colours on every vertex

Give every pair from six points three colours, so that pairs with nothing in common share no colour. Counting says nine colours might do; ten are needed. Stahl conjectured in 1976 exactly how many colours every such problem needs — a formula that meets Lovász's topological answer at one colour a vertex and the obvious answer at k — and a search over stars and triangles confirms it in every case small enough to run.

topology · Borsuk ulam
Removing one end of an ordinary line from a triangle, its midpoints and its centroid. Two panels. Left: 7 points with all 9 connecting lines, one ordinary line solid and one of its ends ringed. Right: the same points with that end removed, 7 connecting lines left.

At least as many lines as points

Sylvester's theorem says some line through two of the points misses all the rest. Remove one end of that line and the line itself disappears, taking at least one line away with one point. Run that backwards and it proves that n points not all in a line determine at least n lines — and the only sets that manage exactly n are a line of n − 1 points with one point off it.

geometry · Ordinary lines
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
The next sum of two squares after 150. A quarter of the circle of radius √150 on the integer lattice, with the column x = 12 and the first lattice point above the circle in it, (12, 3), on the circle of radius √153.

The wait for the next sum of two squares

Sums of two squares thin out to a share of nought, and yet the gaps between them stay short. Take the largest square below any number; what is left over is small, and a small number is always close to a square. Two squarings in a row say the next sum of two squares is never more than about 2√2 times the fourth root of n away — a bound proved in 1947 that nobody has improved, sitting far above every gap anyone has found.

number · Sums of two squares
Six points in space and the triangles that link, seed 48. A projection of K₆ with straight edges, the under-strands broken at crossings. 1 of the ten pairs of disjoint triangles are linked; the pair 126 and 345 is coloured.

Six points in space and a pair that must link

Put six points anywhere in space and join every pair with a straight segment. Split the six into two triangles — there are ten ways — and at least one of the ten pairs of triangles is linked like two rings of a chain. No placement avoids it. The reason is a parity: moving an edge through another changes exactly two of the ten linking numbers, so their sum stays odd whatever is done.

topology · Linking number
Envy-free up to one item, and up to any: three people, five items. A value matrix for three people, five items with two allocations beneath it: one envy-free up to one item but not up to any, and one envy-free; the counts over all 243 allocations beside it.

Envy that any single item would cure

Envy-free up to one item lets a person's envy be excused if removing the envied bundle's best item would cure it. The stronger standard asks that removing any item would — even the one that person values least. Every allocation of three people's items can be searched, and an allocation meeting the stronger standard was there every time; for two people cut and choose finds one, for three it took until 2020 to prove, and for four nobody knows.

applied · Fair division
Every reachable arrangement of the 3×3 sliding puzzle, by moves from solved. A bar chart of the 181440 reachable arrangements of the 3×3 sliding puzzle by the fewest moves that solve them, rising to a peak at 24 and falling to 2 at the maximum distance 31.

Thirty-one moves from solved

Parity settles which half of a sliding puzzle's arrangements can be reached and is silent about how far away any of them is. Searching every reachable arrangement of the three-by-three tray answers the second question exactly — two arrangements sit thirty-one moves out — and parity turns up again, this time as a law about distance.

algebra · Permutation parity
Which arrangements sliding tokens reach, on nine graphs, against Wilson's theorem. A table of 9 small graphs drawn as icons, each with the searched count of reachable token arrangements and the fraction of all arrangements it is: a six-cycle 5/120; K₂,₃ 12/24; the 2×3 tray 60/120; a house 24/24; a six-cycle with one chord 120/120; a wheel of six 120/120; θ, inner paths 2, 2, 2 2520/5040; θ₀, inner paths 1, 2, 2 120/720; θ, inner paths 1, 3, 3 20160/40320.

Which graphs let the tokens go anywhere

A sliding puzzle is a graph with a token on every vertex but one. Richard Wilson found in 1974 what every such puzzle can reach, and the answer has a surprise in it — the half the tray is stuck with is not a fact about permutations at all, but about the board being two-coloured — and one exception, a graph of seven vertices that reaches exactly 120 of 720.

algebra · Permutation parity
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 Moser spindle: 7 points, every edge one unit, and no three-colouring. the Moser spindle drawn to scale with 7 vertices and 11 unit-length edges, coloured with four colours; none of its 2187 three-colourings is proper.

How many colours the plane needs

Colour every point of the plane so that no two points exactly one unit apart share a colour. Seven colours are enough, by a tiling with hexagons, and four are necessary, by a graph of seven points. For sixty-eight years nothing better was known on either side; then in 2018 a graph of 1,581 points showed four is not enough — and the answer is still somewhere from five to seven.

discrete · Graph colouring
All 20,736 two-state Turing machines, by when they halt. A bar chart of the two-state, two-symbol Turing machines by halting step on a blank tape: 1: 6912, 2: 2304, 3: 384, 4: 128, 5: 16, 6: 40, never: 10952.

No algorithm can read what a program does

Whether a program halts cannot be decided by any algorithm. Henry Rice showed in 1953 that the halting problem is not special: no algorithm can decide any property of what a program does — whether it ever prints a 7, whether it computes the successor function, whether it is a virus — except the two properties that hold of every program or of none. Every one of the 20,736 smallest Turing machines can be checked by hand; the theorem says why that stops.

logic · Diagonalisation
12 points, a cup of 5 and a cap of 5. 12 points in general position with the longest convex-upward chain (5 points) and the longest convex-downward chain (5 points) marked.

Every crowd holds a bowl or a dome

Among enough points in the plane, some k of them always bend upward like a bowl or some l bend downward like a dome. The number that forces it is a binomial coefficient, it is exactly right, and it proves that every large enough crowd contains a convex polygon — with a bound nobody could lower to the true answer for eighty years.

discrete · Ramsey theory
Two different graphs with the same adjacency matrix eigenvalues. a star with four arms: adjacency matrix eigenvalues 2, 0³, −2; a square and a lone point: adjacency matrix eigenvalues 2, 0³, −2. The characteristic polynomials are identical.

Two graphs the eigenvalues cannot tell apart

A graph's matrix has eigenvalues, and they count a surprising amount of the drawing: its edges, its triangles, every closed walk of every length. They do not count everything. A star with four arms and a square beside a lone point have the same eigenvalues exactly, although one of them is in two pieces — and on six points ten of the 156 graphs have a twin of this kind.

algebra · Linear maps
The core of a group worth the square of its size: the outline of its six arrival orders. Splits of 9 among three players; core corners (1, 5, 3), (5, 1, 3), (1, 3, 5), (5, 3, 1), (3, 1, 5), (3, 5, 1); arrival-order splits (1, 3, 5), (1, 5, 3), (3, 1, 5), (5, 1, 3), (3, 5, 1), (5, 3, 1); average 3, 3, 3.

The corners are the orders of arrival

Line the players up, let each join in turn, and pay each what it adds on arrival: every order gives a split. When a newcomer always adds at least as much to a bigger group, those splits are exactly the corners of the core — so the core is never empty, it is the outline of the orders, and the average over all of them lies inside it. For a group worth the square of its size the outline is a hexagon whose corners are the six orderings of 1, 3 and 5.

applied · The core
The cheapest tree for a remote user between two near ones, and each user paying for its own link. A source and 3 users with link costs source–A 2, source–B 9, source–C 2, A–B 1, B–C 1, A–C 2; the cheapest tree costs 4 and Bird's rule charges 2, 1, 1.

Each user pays for its own last link

Several users must be connected to a source, and the cheapest network that does it is a tree. Dividing its cost so that no group of users would rather build its own looks like a hard search, and it has a one-line answer: each user pays for the link that joins it to the tree on its way to the source. No group is ever overcharged — while the average over orders of arrival, the rule that settles so much else, can charge a pair more than its own connection costs.

applied · The core
Every power of x that draws a hyperoval, in the planes of order 4 to 4096. q = 4: 1 exponents in 1 classes (conic); q = 8: 3 exponents in 1 classes (conic); q = 16: 3 exponents in 1 classes (conic); q = 32: 11 exponents in 3 classes (conic, translation/Glynn I/Glynn II, Segre); q = 64: 3 exponents in 1 classes (conic); q = 128: 23 exponents in 5 classes (conic, translation, Segre/Glynn II, translation, Glynn I); q = 256: 9 exponents in 2 classes (conic, translation); q = 512: 27 exponents in 5 classes (conic, translation, Segre, translation, Glynn I/Glynn II); q = 1024: 9 exponents in 2 classes (conic, translation); q = 2048: 45 exponents in 8 classes (conic, translation, Segre, translation, translation, Glynn II, translation, Glynn I); q = 4096: 9 exponents in 2 classes (conic, translation).

Every power of x that draws a hyperoval

In a plane of order 2^h, the graph of x^k plus two points at infinity is sometimes a hyperoval — as many points as a plane allows with no three in line. Searching every exponent in every plane from order 4 to 4096 finds hundreds that work, and once six symmetries of the problem are applied they fall into exactly the families already known: the conic, the translation curves, Segre's x⁶ and Glynn's two. Whether that list is complete in every order is open.

computation · Finite geometry
How many windows of each period, on two maps and as a count of necklaces. period 1: 1 (logistic), 1 (sine), 1 (necklaces), 1 (polynomials); period 2: 1 (logistic), 1 (sine), 1 (necklaces), 1 (polynomials); period 3: 1 (logistic), 1 (sine), 1 (necklaces), 1 (polynomials); period 4: 2 (logistic), 2 (sine), 2 (necklaces), 2 (polynomials); period 5: 3 (logistic), 3 (sine), 3 (necklaces), 3 (polynomials); period 6: 5 (logistic), 5 (sine), 5 (necklaces), 5 (polynomials); period 7: 9 (logistic), 9 (sine), 9 (necklaces), 9 (polynomials); period 8: 16 (logistic), 16 (sine), 16 (necklaces), 16 (polynomials); period 9: 28 (logistic), 28 (sine), 28 (necklaces), 28 (polynomials); period 10: — (logistic), — (sine), 51 (necklaces), 51 (polynomials); period 11: — (logistic), — (sine), 93 (necklaces), 93 (polynomials); period 12: — (logistic), — (sine), 170 (necklaces), 170 (polynomials); period 13: — (logistic), — (sine), 315 (necklaces), — (polynomials); period 14: — (logistic), — (sine), 585 (necklaces), — (polynomials).

Windows counted like necklaces

The logistic map has one window of period three, two of period four, three of period five, five of period six, nine of period seven — and the sine map, which shares no algebra with it, has exactly the same numbers, in exactly the same order along the parameter. The counts are 1, 1, 1, 2, 3, 5, 9, 16, 28, 51, and they are the number of ways to thread a necklace of beads in two colours.

dynamics · Period-doubling
Every majority pattern on 5 candidates, and the fewest voters that make it. 12 tournaments on 5 candidates: wins 22222 needs 3; wins 32221 needs 3; wins 32221 needs 3; wins 32221 needs 3; wins 33211 needs 3; wins 33211 needs 3; wins 42211 needs 3; wins 43111 needs 3; wins 33220 needs 3; wins 42220 needs 3; wins 33310 needs 3; wins 43210 needs 1.

How few voters any majority needs

Any pattern of head-to-head majorities whatever — cycles within cycles, a candidate who beats the winner of every other contest and loses to its loser — can be produced by voters who each rank the candidates sensibly. McGarvey's recipe needs n(n − 1) of them for n candidates. The truth is far fewer: every pattern on five candidates takes three voters at most, a counting argument shows the number must eventually grow, and it grows only like n divided by its logarithm.

applied · Voting rules
Dodgson's rule: the fewest swaps that make a Condorcet winner. Profile of 9 ballots with no Condorcet winner; Dodgson scores A 1, B 2, C 3, D 6; Borda scores A 15, B 16, C 14, D 9; Copeland A 1, B 1, C 1, D −3.

The fewest swaps to a winner

When no candidate beats every other head to head, Charles Dodgson proposed in 1876 to elect the one that is closest to doing so — the candidate that the fewest swaps of neighbouring names on the ballots would turn into a winner of every contest. The rule is easy to state and hard to compute: the count needs a search, and deciding the winner is provably among the hardest problems of its kind. A much simpler count, the votes still to be won, usually agrees, more often the larger the electorate.

applied · Voting rules
The fewest triangles a graph can have at each edge density. Razborov's minimum triangle density: 0.55: 0.0730, 0.6: 0.1415, 0.7: 0.2871, 0.75: 0.3750, 0.8: 0.4800, 0.9: 0.7200; it equals Goodman's bound at 1 − 1/t.

The fewest triangles an edge density allows

Half of all possible edges can be drawn without a single triangle. One more, and triangles appear — not one but several at once. Push the density further and the question becomes a curve: for every share of edges, the fewest triangles a large graph can hold. The answer is a string of scallops, touching a simple parabola at the densities of the balanced multipartite graphs and bulging above it between them. It was guessed in the 1980s and proved in 2008 by a method that turns counting into positive-definite matrices.

discrete · Extremal graphs
The Hoffman–Singleton graph: five pentagons, five pentagrams. Fifty vertices of degree seven and girth five, built from five pentagons and five pentagrams joined by the rule j of pentagon h to h·i + j of pentagram i.

As many points as two steps allow

In a graph where every point has d neighbours and every point is within two steps of every other, there can be at most d² + 1 points — one, its d neighbours, and d(d − 1) more reached through them. Graphs that meet the bound exactly are rare to the point of absurdity. The pentagon does it for d = 2, the Petersen graph for d = 3, a fifty-point graph found in 1960 for d = 7, and an eigenvalue argument proves there is nothing else — except possibly one graph with 3,250 points and 57 neighbours each, which nobody has found or ruled out.

discrete · Extremal graphs
The fewest pentagonal numbers adding to each number up to 120. Fewest pentagonal numbers summing to 1..120; the most ever needed up to 20000 is 5, by 9, 21, 31, 43, 55, 89.

Six numbers that need five pentagons

In 1638 Fermat wrote that every whole number is a sum of three triangular numbers, four squares, five pentagonal numbers, six hexagonal numbers, and so on for every polygon — and that he had a proof he would not write down. The claim is true; Cauchy proved it in 1813. What the claim hides is how unequal the cases are. Triangles and squares need their full count infinitely often. For pentagons, only six numbers ever need all five — 9, 21, 31, 43, 55 and 89 — and from hexagons on, two apiece.

geometry · Figurate numbers
The fifty-four sums of four weighted squares that reach every number. The 54 universal diagonal quaternary forms, as coefficient lists: 1,1,1,1; 1,1,1,2; 1,1,1,3; 1,1,1,4; 1,1,1,5; 1,1,1,6; 1,1,1,7; 1,1,2,2; 1,1,2,3; 1,1,2,4; 1,1,2,5; 1,1,2,6; 1,1,2,7; 1,1,2,8; 1,1,2,9; 1,1,2,10; 1,1,2,11; 1,1,2,12; 1,1,2,13; 1,1,2,14; 1,1,3,3; 1,1,3,4; 1,1,3,5; 1,1,3,6; 1,2,2,2; 1,2,2,3; 1,2,2,4; 1,2,2,5; 1,2,2,6; 1,2,2,7; 1,2,3,3; 1,2,3,4; 1,2,3,5; 1,2,3,6; 1,2,3,7; 1,2,3,8; 1,2,3,9; 1,2,3,10; 1,2,4,4; 1,2,4,5; 1,2,4,6; 1,2,4,7; 1,2,4,8; 1,2,4,9; 1,2,4,10; 1,2,4,11; 1,2,4,12; 1,2,4,13; 1,2,4,14; 1,2,5,6; 1,2,5,7; 1,2,5,8; 1,2,5,9; 1,2,5,10.

Fifteen numbers decide every number

Lagrange proved that x² + y² + z² + w² takes every whole value. Ramanujan asked which other sums of four weighted squares do, and in 1917 listed fifty-five. One of them is wrong: x² + 2y² + 5z² + 5w² misses 15. The mistake points at a theorem found eighty years later — to know whether such a form reaches every number, it is enough to check that it reaches 1, 2, 3, 5, 6, 7, 10, 14 and 15. Nine checks decide infinitely many cases, and the nine numbers come out of an escalation any one can run.

geometry · Figurate numbers
Three-colourability as a sentence: there exist three sets such that …. Petersen graph coloured with three colours; witness sets R = {0,2,6}, G = {1,3,5,9}, B = {4,7,8}; all 25 first-order checks pass.

There is a relation such that

A graph can be coloured with three colours exactly when there are three sets of its points such that every point lies in one and no edge joins two points of the same set. The sets are a guess; once guessed, the rest is a list of simple checks. Ronald Fagin proved in 1974 that this shape of sentence — 'there exist relations such that' followed by first-order conditions — describes exactly the problems whose solutions can be checked quickly, the class called NP. The central question of computer science is therefore also a question about what sentences can say.

logic · Quantifiers
The midpoint in the fewest moves: four with a ruler, six with the compass alone. Minimal constructions of the midpoint of AB: 4 moves with ruler and compass, 6 circles compass-only; 55 and 45611 configurations searched.

The fewest moves to draw it

Every construction with ruler and compass is a sequence of moves — draw this line, draw that circle — and it is natural to ask for the shortest. Nobody can answer that by cleverness alone, but a machine can answer it by trying everything: the midpoint of a segment takes four moves and no fewer, the square on it five, a third of it five. Take the ruler away and the compass pays for it: six circles for the midpoint, seven for the square.

computation · Compass-only
The longest code that survives every erasure pattern, by field and dimension. q 2, k 2: 3; q 2, k 3: 4; q 3, k 2: 4; q 3, k 3: 4; q 3, k 4: 5; q 4, k 2: 5; q 4, k 3: 6; q 4, k 4: 5; q 4, k 5: 6; q 5, k 2: 6; q 5, k 3: 6; q 5, k 4: 6; q 5, k 5: 6; q 5, k 6: 7; q 7, k 2: 8; q 7, k 3: 8; q 7, k 4: 8; q 7, k 5: 8; q 7, k 6: 8; q 8, k 2: 9; q 8, k 3: 10; q 8, k 4: 9; q 8, k 5: 9; q 8, k 6: 9; q 9, k 2: 10; q 9, k 3: 10; q 9, k 4: 10.

The longest code that survives every erasure

A Reed–Solomon code of k symbols can lose any n − k of its n and still be read. Over an alphabet of q symbols it can be at most q + 1 long — and it is conjectured that no code with the same perfect tolerance can ever be longer, apart from one family of exceptions in even characteristic. A search through every possible code for small alphabets confirms it cell by cell, a proof exists when q is prime, and for every other q the question is open.

computation · Error-correcting codes
Four trees on seven points, gracefully labelled. a path: 0 6 1 5 2 4 3; a star: 0 1 2 3 4 5 6; a caterpillar: 0 5 1 6 2 4 3; a spider: 0 1 4 5 3 6 2.

A labelling every tree seems to have

Number the points of a tree 0 to n − 1 and write on each edge the difference of the numbers at its ends. The labelling is graceful if the edges then carry 1 to n − 1, each exactly once. Every tree anyone has ever checked — every one of the 551 trees on twelve points, and every tree up to about thirty-five — has such a labelling, and no one knows why. A graceful tree also tiles a complete graph by rotation, which is why the question was asked.

discrete · Labelled trees
Five cycles of the Petersen graph that cover every edge twice. Petersen graph: 57 cycles; minimum cycle double cover has 5 cycles of lengths 5, 8, 6, 6, 5; 1654 search steps.

Every edge on exactly two cycles

Draw a graph on paper without crossings and its faces are cycles, each edge on exactly two of them. George Szekeres and Paul Seymour asked in the 1970s whether every graph without a bridge has such a set of cycles, drawn on paper or not. The Petersen graph needs five, the flower snark on twenty points five as well, every random graph tried has one, and nobody has proved it — though a minimal counterexample would have to be a snark.

discrete · Eulerian paths
Smallest circuits for four functions of three letters. Four small circuit diagrams, each with three inputs feeding a few two-input gates, computing parity, a selector, majority and exactly-one-true with two, three, four and four gates.

How many gates a truth table needs

Every truth function can be built from gates, and the natural measure of a function is the fewest gates that build it. For three letters the whole answer can be computed: no function needs more than four. For n letters, a count shows that almost every function needs about 2ⁿ/n gates, and a construction shows that none needs more. And for any function anyone can actually write down, the best proof in fifty years says it needs 3.1n.

logic · Truth functions
Descartes' number, perfect but for one factor. Five boxes for the prime powers of Descartes' number, each with its divisor sum factored beneath, multiplying to exactly twice the number provided 22021 is treated as a prime.

Perfect but for one factor

In 1638 Descartes wrote to Mersenne with an odd number whose divisors add up to exactly twice the number — provided one of its factors, 22021, is counted as a prime. It is not; it is 19² × 61. Nearly four centuries later that number is still the only odd one of its kind known, and a search of every odd number below ten million finds no other. It is the closest anyone has come to an odd perfect number, and what it shows is how an odd perfect number would have to be built.

number · Perfect numbers
A single table for 9 guests over 4 nights. Small circles of 9 guests, one per night, each showing the night's seating as a closed zigzag path; every pair of guests is adjacent in exactly one of them.

Every pair side by side, once

Seat an odd number of guests at round tables for as many nights as it takes, the same table sizes every night, so that every two guests sit side by side on exactly one night. For a single table a zigzag turned a notch each night does it for any number of guests. For other table plans the answer is almost always yes — and for six guests at two tables of three, nine at tables of four and five, and eleven at three, three and five, an exhaustive search proves it is no.

probability · Inclusion exclusion
What survives on each agenda, 3 judges. A table of four agendas with, for each, the size of its largest inconsistent set, the number of independent unanimous rules for 3 judges, how many are consistent on every profile, and how many of those are dictatorships, oligarchies and other rules: two unconnected questions 324 of 324; a chain of two thresholds 129 of 324; two premises and their conjunction 7 of 5,832; a ranking of three options 3 of 5,832.

What the agenda leaves standing

Ask for a rule that settles each question from the votes on that question, follows a unanimous court and never contradicts itself, and search every such rule for three judges. On a ranking of three options, three survive: one dictator per judge. On two premises and their conjunction, seven survive: every rule in which a fixed set of judges must all agree. On a chain of thresholds, a hundred and twenty-nine, majority among them. The difference is not in the rules. It is in which answers force which, and whether that forcing ever runs back.

applied · Judgement aggregation
One try: letters set in a random order, forced or guessed. Ten rows, one per letter in the order processed, marking 5 guessed and 5 forced letters, each forced one with the clause that forced it.

A letter the clauses already decide

Set the letters of a formula one at a time, in a random order, and guess each one with a coin — unless some clause has already had its other two letters set to false, in which case the clause decides. A try succeeds when every guess is right, so what matters is how many letters get guessed. On a formula with one solution, every letter has a clause that forces it in at least one order out of three, so at most two thirds of the letters are guessed on average, and about 1.587ⁿ tries suffice. It is slower than the random walk. Refined, it is the fastest method known.

logic · Class diagrams
Every three-state machine and what becomes of it. halt: 1379; no halting entry: 12492; exact repeat: 361; shifted repeat: 2254; dies backwards: 36; unexplained: 27.

The machines that need a reason never to stop

Run every three-state machine on a blank tape and the ones that halt announce themselves: the longest stops after 21 steps. The work is in the others. Each needs a reason it will never stop, and four simple kinds of reason settle all but 27 of them — machines that sweep back and forth over a growing tape and defeat every check that looks for a repeat.

logic · Diagonalisation
Three polynomials of signs around the circle. The size of the polynomial around the unit circle divided by √64 for all-plus, random and Rudin–Shapiro sign polynomials of length 64; maxima 8.00, 2.50, 1.41.

The flattest polynomials of signs

A polynomial whose coefficients are all +1 or −1 has average size √n on the unit circle. Keeping it near √n everywhere is the problem Littlewood posed: the Rudin–Shapiro polynomials never exceed √2 times it, searching every sign pattern up to length 22 finds the best are the Barker sequences, and whether the maximum can come arbitrarily close to √n is still open.

algebra · Polynomial roots
A random Latin square of order ten with an orthogonal mate. A 10 by 10 grid with a uniformly random Latin square and an orthogonal mate written into each cell; the square has 848 transversals.

A mate is rare until order ten

Euler asked whether a Latin square can have an orthogonal mate, and for every order but two and six the answer is yes for some square. For a square chosen at random the answer is different. Exactly 6 of the 56 reduced squares of order five have a mate and none of order six does; of squares drawn at random, about one in a hundred of order seven has one, one in three hundred of order eight, one in seventy of order nine — and three in five of order ten.

computation · Latin squares
Langford pairings of order 3, 4 and 7. Rows of boxes with arcs joining equal numbers: order 3: 3 1 2 1 3 2; order 4: 4 1 3 1 2 4 3 2; order 7: 7 3 6 2 5 3 2 4 7 6 5 1 4 1.

A sum that forbids half the pairings

Put two 1s, two 2s, …, two ns in a row so that between the two ks there are exactly k other numbers. For n = 3 there is one way, 312132; for n = 4 one way; for n = 5 and 6 none at all, and the reason is a single sum — adding up the positions of every entry in two ways forces n(3n − 1)/2 to be even. A search confirms the count forbids nothing that exists and finds 26 arrangements at n = 7 and 108,144 at n = 12, but the sum is all anyone knows about why.

discrete · Pigeonhole
The low bits of a congruential generator, and the bits a permutation shows. First 128 steps of a 16-bit congruential generator: low state bits with periods 2, 4, 8, 16, 32, 64, 128, 256; permuted output bits all with period 65536.

A rotation that hides the lattice

A congruential generator modulo a power of two has a lowest bit that alternates and pairs of outputs that lie on a few lines. Keep the generator exactly as it is, and show only eight bits of each state, rotated by an amount the state's own top bits choose: every output bit now runs the full cycle, the pairs fill the square as a random sequence would, and triples pass a test the state's own bits fail by a factor of six. Nothing about the state has changed, and four outputs still give it away.

computation · Pseudorandomness
One form completed three ways, and the same straddle each time. The plane coloured by the sign of 2x² + 6xy + 3y². Three pairs of lines, one for completing with x first, one for y first and one along the eigenvectors; their coefficients are 2 and −3/2; 3 and −1; 5.541 and −0.541, and every pair has one line in a positive wedge and one in a negative wedge.

The signs no completion can change

A quadratic in several variables can be completed square by square in many orders, and each order hands back different coefficients. What no order changes is how many come out positive and how many negative — and that count, read off a completion of A − tI, says how many eigenvalues lie below t without finding a single one.

algebra · Completing the square
Luxembourg's votes and Luxembourg's power, 1958 to 1995. Paired bars for Luxembourg at five enlargements of the Council: vote share falling and power share rising from nothing in 1958 to 0.95% in 1973 and 3.02% in 1981.

A vote worth nothing until it was outnumbered

From 1958 to 1973 Luxembourg held one vote of seventeen in the Council of the European Communities and could never once change an outcome. When the Council grew, Luxembourg's share of the votes fell and its share of the power rose from nothing. Power is not a quantity a member holds; it is a property of the whole assembly, and changing the assembly moves it in directions nobody would guess.

applied · Shapley value
Three kinds of member, and a triple that breaks a grouping. Two copies of one market with three members of each of three kinds and cyclic preferences: on the left a grouping blocked by the triple B, 1, p; on the right a stable grouping.

A third kind of member

Two sides always have a stable matching, and the proof is a procedure. Add a third kind of member — capitals who rank numbers, numbers who rank letters, letters who rank capitals — and every market small enough to check still has a stable grouping. Ten million markets of three have at least ten each. Nobody can prove it continues, because the structure the two-sided proof stands on is gone.

applied · Stable matching
No pair of weights modulo ten catches everything. Two 10 × 10 grids over pairs of alternating weights modulo ten, shaded by the share of single errors and of swaps each catches. No pair is full in both; weights 3 and 1, ringed, catch every single error and 88.9% of swaps.

Ten digits need a symmetry that does not commute

A check digit should catch one wrong digit and two neighbours swapped. Over eleven symbols a weighted sum does both; over the ten decimal digits no weighted sum can, no scheme of any shape built on adding modulo ten can, and the reason is the same as the reason Euler's thirty-six officers cannot be paraded. What works is the ten symmetries of a pentagon, which do not commute.

computation · Error-correcting codes
Four seeds of the middle-square method, each until it repeats. Values against step for the four-digit seeds 6239, 1234, 5735, 4100 under the middle-square rule, each ending where a value repeats: after 111, 57, 31, 4 steps.

Square it and keep the middle

John von Neumann's first generator of random numbers squared a number and kept its middle digits. Followed from every four-digit seed, it never lasts more than 111 steps before a value repeats — a third of what the birthday problem allows a truly random rule — and one seed in five ends at zero for ever. A counter added before each squaring cures the collapse.

computation · Pseudorandomness
A function on nine points, and the tree with two marks it becomes. Left: a function on 9 points as arrows, with cycles through 2, 5, 7 and trees hanging into them. Right: the tree Joyal's rule makes from it, a path from head 7 to tail 2 with the same trees hanging below.

Every function is a tree with two marks

There are n to the n functions from n points to themselves, and n to the n − 2 trees on those points. André Joyal noticed in 1981 that the missing factor of n² is a choice of two points — a head and a tail — and that a function, read the right way, simply is a tree with a head and a tail. The reading turns Cayley's formula into one line and hands over a fact about random trees from the birthday problem.

discrete · Labelled trees
The 11 trees on 7 points, and how many labellings each has. All trees on 7 points with their numbers of symmetries and of distinct labellings; the labellings add to 16807.

Almost every tree can be turned over

Cayley's n^(n−2) counts trees with labels on their points. Take the labels off and the count has no formula, because a symmetric shape absorbs labellings: the star on seven points can be labelled only seven ways, the one asymmetric shape 5,040. The bookkeeping that reconciles the two counts says something unexpected — almost every tree, labelled or not, can be turned over onto itself, where almost every graph cannot.

discrete · Labelled trees
Two ways to cut a hexagon, one total of radii. A cyclic hexagon triangulated two ways with the incircles drawn; the inradii sum to 1.1622 both times.

A total hung in a temple

Put a polygon's corners on a circle, cut it into triangles, and add up the radii of the circles inscribed in the triangles. Cut it a different way and the total is the same — for all fourteen ways of cutting a hexagon, to every digit. The fact was painted on a wooden tablet in a Japanese temple around 1800, and the reason for it is a theorem about one triangle and the distances from its circumcentre to its sides.

geometry · Inscribed angle
Six formulas on the interval of truth values. Graphs on [0, 1] of six one-variable formulas of Łukasiewicz logic, each a zigzag of whole-number slopes with values 0 or 1 at the ends.

The zigzags a formula can draw

Let truth be any number from 0 to 1, and Łukasiewicz's connectives turn every formula in one variable into a graph. Every graph that appears is a zigzag of straight pieces with whole-number slopes, ending at 0 or 1 — and McNaughton proved in 1951 that every such zigzag appears. A logic of degrees of truth turns out to be a theory of piecewise-linear functions with integer coefficients.

logic · Non classical logic
Three truth values, two of which count as holding. Truth tables of negation, conjunction and disjunction in the logic of paradox, with the values that count as holding — both and true — shaded.

A contradiction that stays where it is

In classical logic one contradiction proves everything: from p and not-p, any q at all. Add a third truth value — both true and false — and count it as holding, and the explosion stops. The classical laws all survive as laws; what goes is exactly the reasoning that carries a contradiction somewhere it was not. Run the other way, the same three tables make a logic of gaps instead of gluts.

logic · Non classical logic
Seventy, and the totals its divisors can make. A strip of the totals 0 to 74 marking those reachable as sums of distinct proper divisors of 70; 70 itself and the excess 4 are not.

Abundant, and still not a sum of its parts

Seventy's proper divisors add to seventy-four, more than seventy itself — and yet no selection of them adds to exactly seventy. The reason is that the excess, four, cannot be made from the small divisors one, two and five. Numbers like seventy are called weird; there are thirty-six below twenty thousand, every one of them even, and nobody knows whether an odd one exists.

number · Perfect numbers
Twelve's divisors make every total up to twenty-eight. Stacked bars for each total from 1 to 28, each built from distinct divisors of 12.

Divisors that make every amount

Twelve's divisors — 1, 2, 3, 4, 6, 12 — can be chosen to add to every whole number from one to twenty-eight. Numbers like that are called practical, a test on their primes decides them, and they turn out to be counted like the primes: about 1.336 x / log x of them below x. For practical numbers Goldbach's conjecture and the twin conjecture are theorems.

number · Perfect numbers
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
A closed knight's tour of the 8 × 8 board. A 8 by 8 chequered board with a closed polygon joining the centres of all 64 squares in the order a knight visits them.

The boards a knight can tour

A knight can visit every square of a chessboard once and land a move from where it began. On a 5 × 5 board it cannot, on a 4 × 100 board it cannot, and on a 3 × 8 board it cannot, though on 3 × 10 it can in sixteen ways. Allen Schwenk found in 1991 the complete list of rectangles without a closed tour, and the reasons on it are of two kinds — a colouring that counts squares, and a second colouring that a tour would have to make agree with the first.

discrete · Hamiltonian cycles
The centre of a circle found with six circles and no straightedge. A circle with two marked points 37.3° apart and the six compass circles that construct its centre.

The centre a compass finds in six circles

A circle is drawn and its centre was never marked. A straightedge alone can never find it again. A compass alone can, from two points on the circle, in six circles — and a search through every construction of five circles or fewer shows that six is the least. The reason six works is an inversion that turns the circle into a straight line; the price of discarding the straightedge is exactly one move.

computation · Compass-only
The price of the centre, arc by arc. 10°: 5, 15°: 4, 20°: 4, 25°: 6, 30°: 3, 35°: 6, 40°: 6, 45°: 5, 50°: 5, 55°: 6, 60°: 2, 65°: 6, 70°: 5, 75°: 4, 80°: 6, 85°: 6, 90°: 5, 95°: 6, 100°: 4, 105°: 4, 110°: 5, 115°: 6, 120°: 6, 125°: 6, 130°: 5, 135°: 5, 140°: 4, 145°: 6, 150°: 3, 155°: 6, 160°: 6, 165°: 4, 170°: 5, 175°: 6.

The arcs that make the centre cheap

Finding a circle's centre with the compass alone, from two points on it, costs six circles when the points are placed with no special relation — and as few as two when the arc between them is 60°. Searching every arc in steps of five degrees maps the price exactly, and it is not a smooth function of the arc: it is a list of coincidences, each one a small number of compass steps that happens to land on a chord equal to the radius.

computation · Compass-only
Euclid's argument run twenty times. The first 20 terms of the Euclid–Mullin sequence: 2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, 23003, 30693651606209, 37, 1741, 1313797957.

Euclid's proof run as a machine

Euclid proved there is no last prime by multiplying the primes on any list, adding one, and noting that the result has a prime factor not on the list. Run the proof as a machine — start from 2, and each time take the smallest prime factor of one more than the product so far — and it produces 2, 3, 7, 43, 13, 53, 5, 6221671, … a sequence that never repeats, that reaches small primes late and large ones early, and that nobody can prove reaches every prime.

number · Infinitude of primes
Every swap-proof scrambling, graded on twins and jump swaps. 34040 permutations; twin errors caught range 50–86 of 90, jump transpositions 600–848 of 900; Verhoeff's at (848, 86).

The best of thirty-four thousand scramblings

Verhoeff's check digit multiplies digits in the symmetry group of a pentagon after scrambling each one a different number of times, and 34,040 scramblings make it catch every swap of neighbours. Graded on the rarer errors, none of them catches everything, the best catch 86 of 90 doubled-digit slips and 848 of 900 swaps across a digit — and the scrambling Verhoeff published in 1969 is one of the forty that are best at both.

computation · Error-correcting codes
Every cubic x³ + bx + c up to 30, sorted by its Galois group. A 61 by 61 grid of cubics x³ + bx + c: 309 reducible, lying on lines c = −r³ − rb; 20 cyclic with square discriminant; 3392 with group S3.

Twenty-seven million cubics, sorted by their symmetry

Write down every cubic x³ + ax² + bx + c with coefficients up to 150 and sort each by its Galois group. 98.7% have all six symmetries of three roots. The rest are reducible at a rate of fifteen in every H², or cyclic at five in every H to the three-halves — and the cyclic ones turn up four times as often as chance would allow, because discriminants are not random numbers.

algebra · Galois correspondence
Even quartics never have the full group, and one step away almost all do. Even quartics x^4 + bx^2 + d to 20: reducible 199, S4 0, A4 0, D4 1338, C4 20, V4 124. With +x: reducible 157, S4 1524, A4 0, D4 0, C4 0, V4 0.

The quartics whose roots stay paired

A quartic can have five different Galois groups, and in a box of nearly fourteen million quartics they do not come in order of size. The eight-element group D₄ outnumbers the twelve-element A₄ thirty-five to one. Every even quartic has a smaller group than S₄, and moving one step off that plane restores the full group almost everywhere.

algebra · Galois correspondence
Where the equilibria of a random four-by-four game are found. 7 equilibria with supports (1, 1), (3, 2), (4, 3), (13, 12), (14, 13), (34, 23), (134, 123).

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.

applied · Equilibrium
Two edges of a small graph, and whether one makes the other less likely. tree: 8 total, 5 with e, 5 with f, 3 with both, ratio 0.9600; forest: 24 total, 10 with e, 10 with f, 4 with both, ratio 0.9600; connected: 14 total, 10 with e, 10 with f, 7 with both, ratio 0.9800.

Edges that crowd each other out

Pick a spanning tree of a graph uniformly at random, and the presence of one edge makes every other edge less likely — a theorem of Kirchhoff's electricity. Pick a forest instead, or a connected subgraph, and the same is believed and unproved. Checking every pair of edges in every labelled graph up to six vertices, 871,926 pairs for forests alone, finds no exception, and comes as close as 0.9994 to one.

probability · Concentration
Two random strings of bits and the longest thread between them. Two random binary strings of length 36; longest common subsequence 27.

The longest thread between two random strings

Write down two random strings of a thousand bits each and find the longest sequence that can be read in both, skipping freely. It is about 81% of each, and the exact share — the Chvátal–Sankoff constant — has resisted computation for fifty years. Its fluctuations are a smaller mystery with a sharper edge: the variance is known to be at most n/2, and over every length that can be computed it grows like n to the power 0.7, with nobody able to say what it does after that.

probability · Concentration
The first ten Carmichael numbers and the divisions that make them. 561 = 3·11·17; 1105 = 5·13·17; 1729 = 7·13·19; 2465 = 5·17·29; 2821 = 7·13·31; 6601 = 7·23·41; 8911 = 7·19·67; 10585 = 5·29·73; 15841 = 7·31·73; 29341 = 13·37·61.

The numbers that fool every base

561 = 3 · 11 · 17 passes Fermat's test for every base it shares no factor with, and so do 1,105, 1,729 and 102 more numbers below ten million. They were proved infinite only in 1994. Counted to 10²¹ there are about twenty million, growing like x to a power that has crept from 0.21 to 0.35 — just past the bound the proofs guarantee and nowhere near the power of one that Erdős's argument predicts.

number · Fermats little theorem
Fixing two letters of a sixteen-leaf formula leaves four. Parity of four letters as a 16-leaf formula; fixing x3 = 0, x4 = 1 leaves 4 live leaves.

What a formula keeps when letters are fixed

Fix half the letters of a formula at random and most of its leaves become irrelevant: on the sixteen-leaf formula for the parity of four letters, two fixings leave four. How fast formulas shrink under random fixings is the whole engine behind the best lower bounds anyone has proved for formula size — Subbotovskaya's 3/2 in 1961, Håstad's 2 in 1998 — and the reason that engine stops at n³.

logic · Truth functions
Seven flips between the octagon's farthest triangulations. A shortest flip path of length 7 between two of the 132 triangulations of the octagon.

How far apart two triangulations can be

Any triangulation of a polygon can be turned into any other by flipping one diagonal at a time. On an octagon seven flips always suffice; on a polygon with m vertices the worst case is 2m − 10 flips once m reaches thirteen, a value Sleator, Tarjan and Thurston proved with hyperbolic geometry in 1988. Breadth-first search over all 58,786 triangulations of the 13-gon finds the sixteen.

discrete · Catalan numbers
The flip graph of the hexagon, given a direction. Tamari lattice T4: 14 elements 3210, 3200, 3010, 3100, 3000, 0210, 0200, 1010, 0010, 2100, 2000, 0100, 1000, 0000; 21 covering relations; 68 intervals.

Pairs of trees that count planar maps

Give every flip of a triangulation a direction and the triangulations become an order, the Tamari lattice. Counting the pairs that are in order — 1, 3, 13, 68, 399, 2,530, 16,965, 118,668, 857,956 — gives 2(4n + 1)!/((n + 1)!(3n + 2)!), which is exactly Tutte's 1962 count of planar triangulations. Chapoton noticed the match in 2006; a pair of trees and a map on a sphere turn out to be the same thing.

discrete · Catalan numbers
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
A subword can be checked with one quantifier block; a factor cannot. Subword aba: monoid 7, J-trivial, degree 3; factor aba: monoid 12, aperiodic, not J-trivial; witness abab / abba.

One block of quantifiers, read off an algebra

Which properties of words can be stated with existential quantifiers alone — 'there are positions, in this order, carrying these letters' — and Boolean combinations of such statements? Imre Simon answered in 1975: exactly those whose syntactic monoid is J-trivial. Of the 57,068 languages that automata of up to four states recognise, 848 pass the test, and every one of them is decided by which words of length three or less it contains as scattered subwords.

logic · Ehrenfeucht–Fraïssé games
A walk on Gaussian primes stopped by a moat. Step ≤ 2 from 1 + i: 720 primes reached, farthest 17 + 42i at 45.310.

A walk on Gaussian primes stopped by a moat

Start at 1 + i and step from Gaussian prime to Gaussian prime, never more than 2 at a time: the walk reaches 720 primes and stops at 17 + 42i, surrounded by a moat. Allow steps of √10 and it reaches a quarter of a million primes before stopping at distance 1,024; steps of 4 carry it to 4,313. Whether some fixed step lets a walker reach infinity is a question Basil Gordon asked in 1962, and it is open.

number · Sums of two squares
Four ways to say which pixels touch. curve 8, rest 4: curve 1 pieces, rest 2 pieces; curve 8, rest 8: curve 1 pieces, rest 1 pieces; curve 4, rest 4: curve 12 pieces, rest 2 pieces; curve 4, rest 8: curve 12 pieces, rest 1 pieces.

A curve of pixels needs two kinds of touching

On a screen a closed curve is a ring of pixels, and whether it has an inside depends on which pixels count as touching. Let diagonal pixels touch, and the inside leaks out through the corners; forbid it, and a curve can fence in a region while being twelve separate dots. Of the 1,048,575 sets of pixels in a small window, every simple closed curve obeys the Jordan curve theorem exactly when the curve and the rest of the plane are given different rules.

topology · Jordan curve
Every magic square of order three is a point in a space of three. Basis J, U = (1,-1,0,-1,0,1,0,1,-1), V = (0,-1,1,1,0,-1,-1,1,0); Lo Shu = 5J − 3U + V; dimension of the order-3 magic space 3.

The magic squares are a space

A magic square is a grid whose rows, columns and diagonals share one sum. The conditions are linear, so the squares form a space: three-dimensional for order three, eight-dimensional for order four, n² − 2n in general. Inside the space of order three the eight classical squares are eight points with coordinates ±1 and ±3. Of the 880 squares of order four, 640 are singular matrices, and the search finds the reason: a symmetry of the rows and columns that carries every number to the one it adds to seventeen with.

algebra · Linear maps
Where sellers stand when nobody wants to move. 2 sellers: 1 equilibria (e.g. 12,12 of 24); 3 sellers: 0 equilibria; 4 sellers: 3 equilibria (e.g. 6,6,17,18 of 24); 5 sellers: 4 equilibria (e.g. 4,4,12,19,20 of 24); 6 sellers: 25 equilibria (e.g. 3,3,9,14,20,21 of 24).

Sellers on a street stand back to back

Put two ice-cream sellers on a beach and they end up side by side in the middle, though customers would walk half as far if they stood at the quarter marks. Three sellers never settle at all: whoever is squeezed in the middle leaps outside, for ever. Four stand in pairs, five in pairs with one alone in the centre, six in endlessly many ways. Let them set prices too, with travel costing the square of the distance, and the conclusion reverses: the two sellers move as far apart as the beach allows.

applied · Equilibrium
A party that loses every issue wins the vote. Groups A: 110, B: 101, C: 011, D: 000, E: 000; X wins 3–2; issues won by X: 0 of 3.

A party that loses every issue can win

Two parties take opposite sides on three issues, and every voter backs the party they agree with on more of them. The party that wins the election can be on the losing side of all three issues — in a fifth of random electorates it loses most of them, and in about one in a hundred it loses every one. A majority of voters can even find themselves outvoted on most of the questions decided. Only when issues are settled by three-to-one majorities on average is that ruled out.

applied · Voting rules
Ten dots that never repeat a step. Welch array p=11, g=2: 0,1,3,7,4,9,8,6,2,5; difference triangle rows: 1 2 4 -3 5 -1 -2 -4 3 / 3 6 1 2 4 -3 -6 -1 / 7 3 6 1 2 -7 -3 / 4 8 5 -1 -2 -4 / 9 7 3 -5 1 / 8 5 -1 -2 / 6 1 2 / 2 4 / 5.

Dots that never repeat a step

Place n dots on an n-by-n grid, one in each row and column, so that no two pairs of dots are joined by the same step. These Costas arrays were invented for sonar, and finite fields build them: a primitive root modulo a prime gives one family, a pair of primitive elements in any finite field another. Yet the constructions account for almost none of the arrays that exist — 92 of the 2,160 of order ten — and for orders 32 and 33 nobody has found a single one.

computation · Finite fields
Eleven vertices, no triangle, four colours. Grötzsch graph: 11 vertices, 20 edges, triangle-free; 3-colouring search 27 nodes, none; 4-colouring 10120121230; proper 4-colourings 12480 (520 up to relabelling).

No triangle, and four colours

A graph that contains four mutually joined points needs four colours. The converse looks obvious — a graph needing four colours should contain something like that — and it is false. Grötzsch's graph has eleven points, no three of them mutually joined, and needs four colours. Mycielski found a step that adds one colour to any graph without creating a triangle, so graphs with no triangle can need any number of colours, and their need is spread through the whole graph, with no part to point at.

discrete · Graph colouring
Where 3003 appears eight times. 3003 = C(3003,1) = C(78,2) = C(15,5) = C(14,6) and their mirror images; N(3003) = 8.

How often a number can appear in Pascal's triangle

Every number bigger than one appears in Pascal's triangle at least twice, next to the 1 at each end of its own row. A few appear more often: 120 appears six times, and 3003 eight — as C(3003, 1), C(78, 2), C(15, 5) and C(14, 6), each twice. Counting every entry up to a million million finds seven numbers that appear more than four times and none that appear five, seven or more than eight. Whether any number appears ten times, or whether there is any limit at all, is unknown.

discrete · Pascals triangle
An elimination order is a tree of bags. 3 × 3 grid, optimal order a, c, g, i, b, d, f, h, e; bags abd, bcf, dgh, fhi, bdef, defh, efh, eh, e; treewidth 3.

The order that keeps elimination narrow

Eliminating letters one at a time costs whatever the widest step costs, and the least width any order can achieve is the treewidth of the formula's graph. Finding it exactly is NP-hard, but a search over sets of letters instead of sequences finds it for small graphs, and a greedy rule that adds the fewest new edges finds it on 566 of 600 random graphs and misses by more than one only once. On Tseitin's 6 × 6 grid that rule forms twenty-four times fewer resolvents than sweeping row by row. What it cannot do is prove that its order is the best.

logic · Resolution
Nine bases that cannot each have one true direction. Eighteen vectors (0, 0, 0, 1) (0, 0, 1, 0) (1, 1, 0, 0) (1, −1, 0, 0) (0, 1, 0, 0) (1, 0, 1, 0) (1, 0, −1, 0) (1, −1, 1, −1) (1, −1, −1, 1) (0, 0, 1, 1) (1, 1, 1, 1) (0, 1, 0, −1) (1, 0, 0, 1) (1, 0, 0, −1) (0, 1, −1, 0) (1, 1, −1, 1) (1, 1, 1, −1) (1, −1, −1, −1); vector i joins bases 1–2, 1–5, 1–3, 1–7, 2–5, 2–8, 2–4, 3–4, 3–6, 3–7, 4–6, 4–8, 5–9, 5–6, 6–9, 7–8, 7–9, 8–9; near-solution true: 2, 6, 10, 11, basis B9 empty.

No way to hand out true and false

Birkhoff and von Neumann read the propositions of quantum mechanics as subspaces, with "and" the intersection and "or" the span. Three lines in a plane already break the distributive law. Kochen and Specker proved something stronger: the propositions cannot be called true and false at all, if every complete measurement is to have exactly one true outcome. Cabello's eighteen directions in four dimensions show why in one line of arithmetic — nine bases, each direction in two of them, and nine is odd — and a search of all 262,144 assignments confirms it.

logic · Non classical logic
A partition in two directions is a pile of cubes. Plane partition 5 4 3 1 / 4 3 2 / 3 2 1 / 1 of 29, drawn as stacked cubes; PL(29) = 3759612.

A partition piled into a corner

A partition is a row of numbers that never increases. Let it never increase down the columns too, and it becomes a pile of cubes pushed into the corner of a room. MacMahon counted the piles with one change to Euler's product — each part size k in k colours — and in a box with a product over its cells. The second direction moves the growth from e^(√n) to e^(n^(2/3)), puts ζ(3) where π was, and makes a count that grows with a box's area. One direction further, his guess fails at six.

number · Partitions
Three random loops and the knots they tie. 0₁: 12 crossings; 3₁: 18 crossings; 4₁: 16 crossings.

Which knots a random loop ties

Long random loops are almost always knotted, but knotted as what? Sorting 14,000 closed random polygons by two values of the Alexander polynomial answers it. The trefoil leads at every length, five times as common as the figure-eight at 400 sticks. Each knot's share, divided by the unknotted share, grows like a power of the length, and the trefoil tied twice grows about twice as fast as the trefoil — what a loop carrying independent small tangles would do. Up to 300 sticks the double trefoil turns up exactly as often as two independent trefoils should.

topology · Knots
Every ordering of four in thirty-three symbols. 123412314231243121342132413214321: windows 1234 2341 3412 4123 (1231) 2314 3142 1423 4231 (2312) 3124 1243 2431 4312 (3121) (1213) 2134 1342 3421 4213 (2132) 1324 3241 2413 4132 (1321) 3214 2143 1432 4321.

The shortest string holding every ordering

Thirty-three symbols hold all twenty-four orderings of 1, 2, 3, 4 as blocks of four in a row, and no shorter string does. The formula 1! + 2! + … + n! gives the shortest length for up to five symbols and was believed for all of them — until a string of 872 for six beat its 873, and a lower bound posted anonymously on a forum left everything between 867 and 872 open.

computation · De bruijn
Two hundred and three points from two. After two rounds: 203 points, 11 rational, 76 in ℚ(√3) but not rational, 116 needing a new square root (√2: 20, √5: 22, √7: 14, √11: 36, √13: 20, √35: 4); 10 lines and 16 circles in the second round.

What two points build in two rounds

Start with two points and draw every line and circle they allow; mark every crossing; do it again. The first round gives six points, the second gives 203, and the third gives over 1.7 billion. Computed exactly, the 203 points show the tower of square roots growing in real time — eleven rational points, seventy-six that need √3, and the rest needing one of six new square roots.

computation · Constructible numbers
The bipartite share falls before it rises. n=1: 1 of 1 (100.00%); n=2: 2 of 2 (100.00%); n=3: 7 of 7 (100.00%); n=4: 41 of 41 (100.00%); n=5: 376 of 388 (96.91%); n=6: 5177 of 5789 (89.43%); n=7: 103237 of 133501 (77.33%); n=8: 2922446 of 4682270 (62.42%); n=9: 116011231 of 246348115 (47.09%).

Triangle-free, and two-sided eventually

Every graph with no triangle and the most edges possible is bipartite. Erdős, Kleitman and Rothschild proved that almost every triangle-free graph is bipartite too — and yet among the 246,348,115 triangle-free graphs on nine labelled vertices, fewer than half are. The share falls before it rises, and the reason is that small graphs are sparse.

discrete · Extremal graphs
Right triangles of area five, six and seven. area 5: 3/2, 20/3, 41/6; area 6: 3, 4, 5; area 7: 24/5, 35/12, 337/60.

The areas a right triangle can have

A right triangle with sides 3, 4 and 5 has area 6; one with sides 3/2, 20/3 and 41/6 has area 5. No right triangle with rational sides has area 1, 2 or 3. Which whole numbers are areas is a thousand-year-old question, and its best answer — two counts of solutions to quadratic equations — rests on one of the great unproved conjectures.

geometry · Pythagoras
Fifteen logics from five axioms. K: rank 0, covered by D, KB, K4, K5; D: rank 1, covered by T, KDB, D4, D5; T: rank 2, covered by B, S4; KB: rank 1, covered by KDB, KB5; KDB: rank 2, covered by B; B: rank 3, covered by S5; K4: rank 1, covered by D4, K45; D4: rank 2, covered by S4, KD45; S4: rank 3, covered by S5; KB5: rank 3, covered by S5; S5: rank 4, covered by nothing; K5: rank 1, covered by D5, K45; D5: rank 2, covered by KD45; K45: rank 2, covered by KB5, KD45; KD45: rank 3, covered by S5.

Five axioms and fifteen logics

Five familiar axioms of modal logic can be added to the basic system in thirty-two combinations. Only fifteen different logics come out, because the axioms are properties of arrows between worlds and some properties force others. Checking every frame with up to four worlds finds the fifteen, the order among them, and the small pictures that tell each from its neighbours.

logic · Modal logic
Fourteen truth functions of three letters. table 00000000: 2; table 01101001: 2; table 00001111: 6; table 00111100: 6; table 00010111: 8; table 00011000: 8; table 00000001: 16; table 00010110: 16; table 00000011: 24; table 00000110: 24; table 00011011: 24; table 00011110: 24; table 00000111: 48; table 00011001: 48.

Truth tables up to renaming

There are 256 truth functions of three letters, but many differ only in which letter is called what, or whether a letter or the answer is negated. Counted up to such renamings there are fourteen. For four letters there are 222, for five 616,126 — and almost every function of many letters is changed by every renaming, so the count settles into a simple division.

logic · Truth functions
The numbers below a hundred as sums of three cubes. Smallest solution size per n < 100: 1:9 2:1 3:1 6:2 7:2 8:16 9:2 10:2 11:3 12:11 15:2 16:2 17:2 18:3 19:3 20:3 21:16 24:2 25:3 26:3 27:6 28:3 29:3 30:10d 33:16d 34:3 35:3 36:3 37:4 38:4 39:6d 42:17d 43:3 44:8 45:4 46:3 47:8 48:4 51:796 52:11d 53:3 54:3 55:3 56:4 57:4 60:5 61:5 62:3 63:4 64:6 65:4 66:4 69:5 70:21 71:4 72:4 73:4 74:15d 75:9d 78:55 79:35 80:4 81:3 82:14 83:4 84:8d 87:4271 88:5 89:7 90:4 91:4 92:4 93:7 96:22 97:5 98:5 99:4.

Thirty-three as three cubes

Which numbers are a sum of three cubes, allowing negatives? Nothing like the rule for two squares is known — only that numbers leaving 4 or 5 on division by 9 are impossible. Every other number below a hundred has a sum with cubes under 5,000, except eight; 33 needed sixteen-digit cubes and was found in 2019.

number · Sums of two squares
Five squares on one octagon. Octagon [[1.0756,0.5516],[0.6082,1.2964],[-0.466,1.2294],[-0.8758,0.3153],[-0.797,-0.3348],[-0.3706,-0.7683],[0.2718,-0.6558],[1.1693,-0.4453]]; squares with sides 1.4975, 1.4588, 1.4407, 1.3929, 1.3921.

An odd number of squares on every polygon

Does every closed curve that does not cross itself pass through the four corners of some square? Toeplitz asked in 1911, and for polygons and smooth curves the answer is yes, because the squares can be counted and the count is odd. For rectangles of a fixed shape the count is even, which is why they needed a different proof — and for an arbitrary continuous curve the square is still not proved to exist.

topology · Jordan curve
Every closed curve with three crossings. Six sphere curves with 3 crossings; plane counts 2, 3, 3, 3, 4, 5 (total 20); symmetries 12, 6, 4, 4, 2, 2.

How many ways a curve can cross itself

A closed curve that crosses itself three times can be drawn in exactly six essentially different ways on a sphere, and twenty in the plane. Four crossings give nineteen and eighty-two; six give 376 and 2,645. Every one of them is a word — the order in which the crossings are met — and a choice of direction at each crossing, and the whole census comes from asking which of those choices close up on a sphere.

topology · Homotopy
Every failed branch datum up to eight sheets. Exceptions with three branch points: 4: 31|22|22; 6: 51|222|222; 6: 42|411|222; 6: 42|222|222; 6: 33|33|3111; 6: 33|321|222; 8: 71|2222|2222; 8: 62|5111|2222; 8: 62|2222|2222; 8: 611|422|2222; 8: 53|3311|2222; 8: 53|2222|2222; 8: 521|422|2222; 8: 5111|44|2222; 8: 5111|422|422; 8: 44|44|311111; 8: 44|3221|2222; 8: 431|332|2222; 8: 422|332|2222.

The lists no covering can have

A covering of the sphere by itself with three branch points is three permutations of the sheets whose product is the identity. The Riemann–Hurwitz count says which lists of cycle shapes might work, and a search through every permutation says which do. Up to thirteen sheets, 150 lists pass the count and fail the search — and not one of them has a prime number of sheets.

topology · Covering spaces
Thirty-three directions nobody can label. Peres set: 33 rays, 16 triads, 72 orthogonal pairs, 0 colourings. Rays: (0, 0, 1) (0, 1, 0) (1, 0, 0) (0, 1, 1) (0, 1, −1) (1, 0, 1) (1, 0, −1) (1, 1, 0) (1, −1, 0) (0, 1, √2) (0, 1, −√2) (0, √2, 1) (0, √2, −1) (1, 0, √2) (1, 0, −√2) (1, √2, 0) (1, −√2, 0) (√2, 0, 1) (√2, 0, −1) (√2, 1, 0) (√2, −1, 0) (1, 1, √2) (1, 1, −√2) (1, −1, √2) (1, −1, −√2) (1, √2, 1) (1, √2, −1) (1, −√2, 1) (1, −√2, −1) (√2, 1, 1) (√2, 1, −1) (√2, −1, 1) (√2, −1, −1).

Thirty-one directions nobody can label

In four dimensions eighteen directions are enough to show that quantum measurements cannot have answers waiting in advance, and a parity count does it in a line. In three dimensions, where Kochen and Specker first proved it, no parity count works and the smallest known set has thirty-one directions. Peres's thirty-three can be checked by hand; Conway and Kochen's thirty-one fall out of a search through every direction with coordinates between −2 and 2; and whether thirty or fewer could ever do is still being settled by exhaustive computation, which has so far ruled out everything up to twenty-four.

logic · Non classical logic
The forests of a complete graph on four points. K4 forests by size: 1, 6, 15, 16; ratios 2.4000, 2.3438.

The forests a graph can hold

Count the sets of edges in a graph that contain no cycle, sorted by size, and the counts rise and fall in a single peak — more sharply peaked, John Mason conjectured in 1972, than the binomial coefficients with the same number of edges. On every graph with up to six points the strongest of his three inequalities holds, with equality exactly where cycles are too long to matter; on random graphs with nine points it holds with a margin of about one per cent. It was proved for every graph, and every matroid, in 2018.

discrete · Generating functions
The copies each grid makes of the disc. W = 6, 113 frequencies: square grid 13x13 = 169 samples; best lattice basis (11,4), (9,-8), 124 samples.

A grid that packs the copies

Sampling a pattern on a grid makes copies of its frequencies, one for every point of a lattice, and the pattern can be read back from the samples only if the copies do not collide. For a pattern whose frequencies fill a disc the square grid wastes room between its copies. Searching every lattice of samples for the fewest that work finds a nearly hexagonal one every time — 124 samples where the square grid needs 169 — and the saving is the hexagonal packing's over the square, 13.4% in the limit. In three dimensions it is 29%, and in twenty-four the cubic grid needs 16,777,216 times as many samples as the best.

analysis · Fourier series
Two valleys for sixteen charges. N = 16: 92.911655 (48 starts), 92.920354 (12 starts).

Valleys a search cannot count

Let equal charges on a sphere push each other apart from a random start, and they settle into an arrangement where nothing moves. Up to fifteen charges every start settles into the same one. Sixteen is the first number with two, a hundredth of a unit apart in energy; by fifty-two there are at least four, and for fifty-six charges only one start in ten finds the lowest. The other valleys sit a few parts in a million above it, and nothing in the arrangement a search returns says whether it is the bottom.

geometry · Regular polyhedra
What junctions save in space. tetrahedron SMT/MST 0.81305; 12-point helix 0.79472.

A chain of tetrahedra saves more

In the plane, junctions never seem to shorten a network of roads by more than the equilateral triangle's 13.4%. In space the regular tetrahedron allows 18.7%, and the obvious guess — that it is the worst case, as the triangle is in the plane — is wrong. Points spaced along a chain of tetrahedra glued face to face do better with every point added: 20.5% at twelve, 21.4% at sixty, and about 21.6% in the limit. Random points come nowhere near, and a search that only goes downhill does not find the chain.

geometry · Triangle centres
Five arrows that almost close. f(5, 122) = 1.483983e-5 at exponents 0,32,50,77,104.

How near nought a sum of roots can come

Five arrows of length one, each pointing at a 122nd root of unity, laid end to end, return to within fifteen millionths of where they started. No five of the 123rd roots come within a thousandth. Two, three and four arrows shrink their smallest miss in a tidy power of n; five scatter over four powers of ten from one n to the next, and nobody knows the law they follow.

algebra · Roots of unity
Seven points that meet every line. q=4: minimum nontrivial blocking set 7 points {16,1,3,6,4,18,17}; meet histogram {"1":14,"3":7}; size 6 ruled out after 3125 nodes.

The fewest points that meet every line

In a finite plane any line meets every other line, so a single line is a set of points that every line passes through. Ask for such a set that contains no whole line and the answer is surprisingly expensive: in the plane of order 7, which has 57 points, it takes 12, and an exhaustive search over seventy-one million branches shows that 11 will not do. Two theorems predict the number — a square-root bound met by a copy of a smaller plane, and a bound of three halves for prime orders met by three half-lines.

computation · Finite geometry
Six entries that fix a Latin square. n=5 cyclic: min defining set 6; triangle set {0,1,5,19,23,24}; forcing steps 0,0,3,2,1,0,5,4,3,2,3,4,5,4,3,2,3,4,5,0,1,2,3,0,0.

The fewest entries that fix a Latin square

Reveal six of the twenty-five entries of the cyclic Latin square of order five — three in the top left corner, three in the bottom right — and only one Latin square agrees with them; reveal any five and at least two do. John Nelder conjectured that a square of order n can never be pinned down by fewer than ⌊n²/4⌋ entries. A search over every set of cells confirms it for every square to order five, and finds that the more symmetric a square is, the fewer entries it takes.

computation · Latin squares
Two arrows in and two out at every point. 9×9 patch from a random height function, seed 3; heights range 1..6.

Two arrows in and two out

An Eulerian circuit enters every point as often as it leaves, so it hands every edge an arrow with the arrows balanced at each point. Count those balanced orientations instead of the circuits and the question turns into the ice in a freezer: on the square grid, where every point has two arrows in and two out, there are about 1.5396 of them per point — Lieb's (4/3)^(3/2), against Pauling's guess of 1.5. Fix the walls of a square of ice and the count becomes 1, 2, 7, 42, 429, 7436: the alternating-sign matrices.

discrete · Eulerian paths
Numbers made of pyramids. below 1000000: 241 need five; first 17, 27, 33, 52, 73, 82, 83, 103, 107, 137, 153, 162; last 343867 = 341376+1771+680+20+20.

Five pyramids for every number

Stack balls in triangular pyramids and the piles hold 1, 4, 10, 20, 35, … balls. Frederick Pollock guessed in 1850 that every whole number is a sum of at most five such piles. Seventeen needs five — 10 + 4 + 1 + 1 + 1 — and so do 240 other numbers, the largest 343,867; past that, every number up to ten million needs four or fewer. Eight is proved to be enough. Five is not, and the reason is the same one that makes the three-dimensional cousins of the classical theorems hard.

geometry · Figurate numbers
A box with whole diagonals on every face. 44,117,240: face diagonals 267, 244, 125; space diagonal squared 73225.

A box with every face diagonal whole

Pythagoras gives a rectangle with whole sides and a whole diagonal — 3, 4, 5. A box with whole edges and whole diagonals on all three faces is far rarer: the smallest is 44 × 117 × 240, found in 1719, and there are only 113 essentially different ones with every edge below 300,000. Ask for the long diagonal through the box to be whole as well and the answer is unknown. No such perfect box has ever been found, and nobody has proved there is none.

geometry · Pythagoras
Twenty-two states and 265,454 formulas. two letters, depth two: 4 final states and 18 below; 265454 up-sets; lower states q below p q, p below p q, – below p q, – below q, – below p, q below p q/q, – below p q/q, p below p q/p, – below p q/p, – below p q/–, – below q/p, – below q/–, – below p/–, – below p q/q/p, – below p q/q/–, – below p q/p/–, – below q/p/–, – below p q/q/p/–.

The second letter breaks the pattern

In one letter the constructive logic has infinitely many formulas, but they climb in a column two wide, four new ones for every step a state of knowledge can take. Add a second letter and the pattern is gone: sixteen formulas at the last step, 265,454 one step back, and more than two to the power 265,428 one step further. Every one of those is a genuine formula, and the reason the two-letter lattice has never been drawn is that each layer of the model is about as large as the number of formulas the layer above can tell apart.

logic · Non classical logic
The sizes three sentences allow. every point has exactly one neighbour: 2,4,6,8,10,12,14,16,18,20,22,24,26,28,30; every two points have exactly one common neighbour: 1,3,5,7,9,11,13,15,17,19,21,23,25,27,29; every two players are both beaten by a third: 1,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30

The sizes at which a sentence can come true

Write a sentence about a relation and ask for which numbers of points some relation makes it true. "Every two points have exactly one common neighbour" comes true at every odd size and no even one, and every graph that satisfies it is a windmill of triangles. "Every two players are both beaten by some third" fails for every tournament of two to six players and holds from seven on. A search can settle one size at a time; only a proof settles all of them, and the two sentences need different kinds.

logic · Quantifiers
Each prime fixes the next digits of A. A = 1.306377883863080690468614492602605712916…; digits fixed by the primes from 11 to the 254-digit one: 1, 4, 11, 30, 87, 257.

A constant that holds the primes

There is a number A = 1.3063778838… such that A cubed, A to the ninth, A to the twenty-seventh and every further power of three, rounded down, is prime: 2, 11, 1361, 2521008887 and on for ever. W. H. Mills proved in 1947 that such a number exists. It looks like a formula for primes and is the opposite of one. Its digits are read off the primes it produces, each prime fixes about as many digits as it has, and the whole argument stands on a theorem about gaps between primes — which is why the power is 3 and not 2.

number · Infinitude of primes
Where each count of cubes stops being needed. last needing 9..6: 239, 454, 8042, 1290740; counts 114, 5721, 154467, 941641, 393997, 3922, 121, 15, 2 up to 1500000.

Nine cubes for two numbers

Every whole number is a sum of at most nine positive cubes, and only two numbers, 23 and 239, need all nine. Fifteen need eight, the last of them 454; 121 need seven, the last 8,042; six are needed for the last time at 1,290,740. The count every number needs is nine, fixed by two small accidents. The count every large number needs is somewhere between four and seven, and the computation says four — a question about how the cubes spread out, not about the cubes themselves.

number · Sums of two squares
Ten points, thirteen halving lines. points 0.253,1.518 0.242,0.216 0.717,0.119 -0.427,0.222 0.554,0.409 0.299,0.346 0.806,0.006 -1.101,0.118 1.209,-0.414 0.445,0.714; halving pairs 0-9 1-2 1-3 1-5 2-4 2-6 3-5 3-7 4-5 4-9 5-6 5-9 6-8; degrees 1,3,3,3,3,5,3,1,1,3.

Lines that leave half on each side

Scatter ten points on a page and draw every line through two of them that leaves four on each side. There are at least five such halving lines and at most thirteen, and every point lies on an odd number of them. Both facts come from turning a line through half a revolution, the argument that halves two shapes with one cut. How many halving lines n points can have is the k-set problem, and its answer lies somewhere between a little more than n and n to the four-thirds.

topology · Borsuk ulam
One random path estimates the whole tree. probe columns 4,2,5,3,6,0; choices 8,5,3,1,2,1; estimate 769; exact 2057.

One random path down a search tree

Before running a search that may take a week, it is worth knowing whether it will take a week or a century. Donald Knuth's answer, from 1975, is to walk down the search tree once at random, multiply the numbers of choices met on the way, and add up the products: the result is, on average, exactly the size of the tree. On the eight-queens tree one path guesses 769 against a true 2,057 and twenty thousand paths average to within a tenth of a per cent. On a tree built to hide its bulk, the same unbiased estimate is almost always wrong by a factor of thousands.

probability · Monte Carlo
How many matches a frustrating deal has. 0:0.016233/0.018316, 1:0.068899/0.073263, 2:0.144164/0.146525, 3:0.198194/0.195367, 4:0.201325/0.195367, 5:0.161112/0.156293, 6:0.105762/0.104196, 7:0.058554/0.059540, 8:0.027898/0.029770, 9:0.011615/0.013231, 10:0.004276/0.005292, 11:0.001406/0.001925, 12:0.000416/0.000642

A card game almost nobody wins

Shuffle a deck and deal it face up, calling ace, two, three, up to king and round again, four times through. If a card ever matches the rank being called, the game is lost, and it is won about one time in sixty-two. The chance is 0.016232727…, exact, because the forbidden pairings form thirteen separate four-by-four squares and inclusion–exclusion turns their rook numbers into a sum — a sum whose terms climb past ten before they cancel to a sixtieth, and which is also the integral of a power of a Laguerre polynomial. The obvious guess, e to the minus four, is eleven per cent too high, and two hundred thousand deals can tell.

probability · Inclusion exclusion
How often a table of random signs is singular. n=2: 0.5000 (parallel 0.500); n=3: 0.6250 (parallel 0.625); n=4: 0.6602 (parallel 0.660); n=5: 0.6558 (parallel 0.628); n=6: 0.6270 (parallel 0.547); n=7: 0.5810 (parallel 0.442); n=8: 0.5216 (parallel 0.329); n=9: 0.4515 (parallel 0.234); n=10: 0.3757 (parallel 0.154); n=11: 0.2963 (parallel 0.0978); n=12: 0.2274 (parallel 0.0619); n=13: 0.1639 (parallel 0.0361); n=14: 0.1136 (parallel 0.0217); n=15: 0.07550 (parallel 0.0127); n=16: 0.04668 (parallel 0.00683); n=18: 0.01639 (parallel 0.00229); n=20: 0.004725 (parallel 0.000683)

How often a table of random signs is flat

Fill a square table with random plus and minus signs and ask whether its determinant is nought. For four rows the answer is yes two times in three. The chance then falls, and since 2020 it has been known to fall at exactly the rate of the dullest accident, two rows or columns equal or opposite. The conjecture is that this accident is, in the end, the whole story. Every size a computer can reach says otherwise, and the theory says the computer has not gone far enough.

algebra · Determinant
How often a game picked at random has a core. n=3: 0.20:1.000 0.24:1.000 0.28:1.000 0.32:1.000 0.36:1.000 0.40:1.000 0.44:1.000 0.48:1.000 0.52:1.000 0.56:1.000 0.60:1.000 0.64:1.000 0.68:1.000 0.72:0.997 0.76:0.993 0.80:0.980 0.84:0.958 0.88:0.933 0.92:0.899 0.96:0.872 1.00:0.833; n=4: 0.20:1.000 0.24:1.000 0.28:1.000 0.32:1.000 0.36:1.000 0.40:1.000 0.44:1.000 0.48:1.000 0.52:0.991 0.56:0.937 0.60:0.843 0.64:0.737 0.68:0.634 0.72:0.517 0.76:0.424 0.80:0.323 0.84:0.258 0.88:0.182 0.92:0.134 0.96:0.091 1.00:0.066; n=5: 0.20:1.000 0.24:1.000 0.28:1.000 0.32:1.000 0.36:1.000 0.40:1.000 0.44:0.994 0.48:0.904 0.52:0.725 0.56:0.438 0.60:0.245 0.64:0.116 0.68:0.059 0.72:0.022 0.76:0.009 0.80:0.002 0.84:0.002 0.88:0.001 0.92:0.001 0.96:0.000 1.00:0.000

A core is a rare thing to find at random

A game has a core when the whole can be shared so that no group would do better on its own, and Bondareva and Shapley turned that into a finite list of checks. For three players there are five checks; for four, forty-one; for five, 1,291. Draw the coalitions' values at random and the list wins: a third of three-player games fail, nineteen four-player games in twenty, and not one five-player game in two thousand passes. The cores that theorems promise come from structure, and structure is exactly what a random game lacks.

applied · The core
A square cut into rectangles of ratio φ squared. 1/r@(0.0000,0.0000) 0.1273×0.3333; r@(0.1273,0.0000) 0.8727×0.3333; 1/r@(0.0000,0.3333) 0.1273×0.3333; r@(0.1273,0.3333) 0.8727×0.3333; 1/r@(0.0000,0.6667) 0.1273×0.3333; r@(0.1273,0.6667) 0.8727×0.3333

The rectangles a square can be cut into

Cut a square into rectangles that all have the same shape — the same ratio of long side to short, in any sizes, lying either way. Two to one is easy. The golden ratio is impossible, however many pieces are used and however small. The ratio φ squared works with six. What decides it is not the ratio but its partner: the number obtained by changing the sign of the square root, which must be positive. Changing that sign is a map that keeps every sum and product and scrambles every size, and areas that must add up to one cannot all turn negative.

computation · Scissors congruence
The Golay code drawn from an icosahedron. generator rows f19001 e72002 eac004 47d008 8bb010 33e020 bca040 7d4080 de1100 2e7200 58f400 957800; weight distribution 0:1 8:759 12:2576 16:759 24:1.

A code built from an icosahedron

Write down which corners of an icosahedron are not joined by an edge, put the table beside a diagonal of ones, and add the twelve rows together in every combination. The 4,096 strings of 24 bits that come out differ from each other in at least eight places, occur in only five weights, and — with one bit deleted — fill the space of 23-bit strings so exactly that every one of the 8,388,608 lies within three flips of exactly one of them. This is the Golay code, which carried Voyager's pictures home, and its words of weight eight cover every five of the twenty-four positions exactly once.

computation · Error-correcting codes
How high an orbit climbs. 1:1 2:2 3:16 7:52 15:160 27:9232 255:13120 447:39364 639:41524 703:250504 1819:1276936 4255:6810136 4591:8153620 9663:27114424 20895:50143264 26623:106358020 31911:121012864 60975:593279152 77671:1570824736 113383:2482111348 138367:2798323360 159487:17202377752 270271:24648077896 665215:52483285312 704511:56991483520 1042431:90239155648 1212415:139646736808 1441407:151629574372 1875711:155904349696 1988859:156914378224 2643183:190459818484 2684647:352617812944 3041127:622717901620 3873535:858555169576 4637979:1318802294932 5656191:2412493616608 6416623:4799996945368 6631675:60342610919632

How high an orbit climbs

The Collatz orbit of 27 climbs to 9,232 before it falls, and below ten million the champion, 6,631,675, climbs to sixty trillion — almost exactly the square of where it started. That is not a coincidence of the two numbers but a law of the whole family: an orbit climbs to x times its start with a chance of about one in x, and the exponent is one because half of three-halves plus half of a half is exactly one. Among N starts the luckiest climbs about N-fold, and so the records grow like the square of the start.

dynamics · Collatz
Every denominator has a fraction with small quotients. 2:1340 3:1624 4:32 5:3; need 5: 6,54,150

A small quotient for every denominator

Pick a denominator, any whole number. Among the fractions with that denominator, is there always one whose continued fraction has no large entries — whose path down the Stern–Brocot tree never turns the same way more than five times running? Stanisław Zaremba guessed so in 1972, for a reason to do with sampling a square evenly. Every denominator up to a hundred thousand obeys, with only 6, 54 and 150 needing a five. The guess is proved for almost every denominator and not for all, and the reason it ought to be true is a dimension: the reals whose quotients stay at most five fill a set of dimension 0.837, enough to give each denominator thousands of good fractions on average, and the open question is whether averages are kept everywhere.

number · Stern brocot
How often each rule finds the Condorcet winner. n=3: 0.8824/0.9412/0.9559/0.6471; n=5: 0.8259/0.9751/0.9378/0.6866; n=7: 0.8281/0.9578/0.9278/0.6833; n=11: 0.8054/0.9656/0.9179/0.7079; n=21: 0.7941/0.9619/0.9097/0.7205; n=51: 0.7804/0.9624/0.9046/0.7339; limit 0.7572±0.0009/0.9629±0.0004/0.9011±0.0006/0.7563±0.0009; P(CW) limit 0.9116.

How often the rules find the majority favourite

When one candidate beats every rival head to head, a voting rule ought to elect it. Plurality does about three times in four when every ranking is equally likely, the runoff between the top two 96 times in a hundred, Borda's count 90. Every profile of up to 51 voters is counted exactly, the limit is sampled, and adding candidates pulls plurality down below one half.

applied · Voting rules
The number of stable matchings in a random market. n=10 (400): mean 3.03±0.10, median 3, 10-90% 1-5, max 20, e^-1 n ln n 8.5; n=20 (400): mean 6.34±0.18, median 6, 10-90% 3-10, max 33, e^-1 n ln n 22.0; n=40 (400): mean 15.51±0.48, median 13, 10-90% 7-26, max 87, e^-1 n ln n 54.3; n=70 (400): mean 33.10±0.92, median 29, 10-90% 16-56, max 147, e^-1 n ln n 109.4; n=100 (400): mean 54.84±1.46, median 48, 10-90% 26-90, max 230, e^-1 n ln n 169.4; n=150 (400): mean 93.47±2.51, median 79, 10-90% 49-164, max 350, e^-1 n ln n 276.5; n=200 (200): mean 144.33±5.75, median 128, 10-90% 71-229, max 589, e^-1 n ln n 389.8; n=300 (100): mean 239.96±12.32, median 203, 10-90% 128-409, max 669, e^-1 n ln n 629.5; n=500 (40): mean 409.55±24.38, median 410, 10-90% 212-663, max 799, e^-1 n ln n 1143.1; n=700 (16): mean 648.44±83.83, median 573, 10-90% 323-1286, max 1504, e^-1 n ln n 1687.0; n=1000 (10): mean 1053.30±211.84, median 807, 10-90% 458-2467, max 2467, e^-1 n ln n 2541.2

How many stable matchings a market has

A market with random preferences on both sides has not one stable matching but many — a few at ten a side, a few dozen at a hundred, about a thousand at a thousand — and all of them are reached from the proposers' best by a chain of rotations. Boris Pittel proved that the average grows like n ln n / e. The averages measured here sit at a third of that at every size a computer can reach.

applied · Stable matching
A word that survives losing any one of its bits. codeword 100110010110, a=0 mod 13; deletions at 1..12 all decoded.

A code that survives a lost bit

A flipped bit leaves the word the right length and wrong in one place; a lost bit leaves it one short, with no sign of where the gap was. Keep only the words whose 1s sit at positions adding up to a multiple of n + 1, and any single lost bit can be put back. The price is about log₂(n + 1) bits, the same as the Hamming code pays for a flip.

computation · Error-correcting codes
A tour appears the moment it can. n=16: τ2=27; tour 0-7-6-9-12-13-8-15-11-10-4-14-1-2-3-5; last point 10.

The tour arrives with the last second neighbour

Add the edges between n points one at a time in a random order. A tour through every point cannot exist while some point has fewer than two neighbours, and in a large random graph that is the only thing stopping it: the tour appears at the very edge that gives the last point its second neighbour. Watched in thousands of small graphs, the coincidence is already the rule, and the exceptions are tiny traps around the points of lowest degree.

discrete · Hamiltonian cycles
A multiplication table and its repeats. n=30: 308 distinct products of 900.

Most numbers are missing from the table

An N × N multiplication table has N² cells, and every product in it is less than or equal to N². Yet only 22.5% of the numbers that small turn up in the 10,000 × 10,000 table, and the share keeps falling. Erdős proved in 1955 that it falls to nought; Kevin Ford found in 2008 how slowly — like a tiny power of the logarithm, 0.0861 — because a product of two numbers has too many prime factors to be typical.

number · Unique factorisation
A curve that crosses a line twelve times. n=6: upper 9,8,7,6,5,4,3,2,1,0,11,10; lower 3,2,1,0,7,6,5,4,11,10,9,8; meanders 1828 of 17424.

Curves that cross a line and close

Draw a closed curve that crosses a straight line 2n times and never crosses itself. Above the line it is a set of nested arches, below it another, and every such curve is a pair of the Catalan number's arch systems that happen to close into one loop. There are 1, 2, 8, 42, 262, 1,828 of them, and every count computed so far grows by a factor creeping towards 12.26 — a number nobody can prove, with an exponent conjectured from the physics of random surfaces.

topology · Homotopy
A decisive set halved for ever. voter 37: residues 1, 1, 5, 5, 5, 37; …111: residues 1, 3, 7, 15, 31, 63.

An electorate too large for a dictator

Arrow proved that a voting rule with his four properties must have a dictator, and his proof uses the finiteness of the electorate exactly once. With infinitely many voters the dictator can vanish: the sets of voters who get their way form an ultrafilter, and every free ultrafilter is a rule with all four properties and nobody in charge. The catch is that no such rule can be written down. Its existence is a fragment of the axiom of choice.

logic · Axiom of choice
One quantifier blind to two others. The prefix ∀x∃y∀u∃v drawn in a line, where v depends on x, y and u, and in branching form, where y depends only on x and v only on u; six points paired off by a fixed-point-free involution and five points, where no such pairing exists.

Four quantifiers, one of them blind

In 'for every x there is a y, and for every u there is a v', the last choice may depend on everything before it. Leon Henkin asked in 1961 what happens if v may depend on u alone. Using nothing but the equals sign, four such quantifiers then say that a set has an even number of points, or that it is infinite — things no ordinary sentence can say — and the game behind the sentence can end with neither player able to win.

logic · Quantifiers
The far end of a sliding tray falls as holes are added. Exhaustive search of the 2×3, 2×4 and 3×3 sliding trays with one to all-but-one holes. Far ends for the 3×3 tray: 31, 24, 21, 17, 13, 10, 7, 4; averages 21.97, 16.04, 12.70, 9.99, 7.88, 5.92, 3.75, 2.00.

A second empty square

With one empty square a sliding tray can reach exactly half its arrangements, and the half it misses is guarded by a sign. Leave a second square empty and the guard disappears — every arrangement is reachable, two tiles can be exchanged in four moves, and the far end of the three-by-three tray comes in from thirty-one moves to twenty-four. Searching every tray with every number of holes shows what each extra square of room is worth.

algebra · Permutation parity
How many words can survive two lost bits. Two-deletion-correcting code sizes by length: n=4: optimum 2, greedy 2, Helberg 2; n=5: optimum 2, greedy 2, Helberg 2; n=6: optimum 4, greedy 4, Helberg 3; n=7: optimum 5, greedy 5, Helberg 4; n=8: optimum 7, greedy 6, Helberg 5; n=9: optimum 11, greedy 9, Helberg 6; n=10: optimum -, greedy 13, Helberg 8; n=11: optimum -, greedy 20, Helberg 9; n=12: optimum -, greedy 29, Helberg 11; n=13: optimum -, greedy 46, Helberg 15.

Two lost bits

One congruence repairs any single lost bit, and the set of words it defines is believed to be the best possible. Two lost bits defeat it. An exhaustive search finds the largest codes that survive two — 2, 2, 4, 5, 7 and 11 words for lengths 4 to 9 — and Helberg's congruence, with weights that grow like Fibonacci numbers, gives a code that provably works at every length but spends a fixed share of every bit on protection. The best codes need only about four times the logarithm of the length.

computation · Error-correcting codes
A disc needs three pieces to shrink. Unit disc: two half-discs keep diameter 2; three 120-degree sectors have diameter 1.7321.

How many pieces to shrink a shape

Cut a disc in two and one half still holds a full diameter; cut it in three and every piece is narrower. In 1933 Karol Borsuk asked whether every bounded shape in d dimensions can be made narrower with d + 1 pieces, and the antipodal theorem he proved in the same paper says no number smaller will do for a ball. The guess held in the plane and in space, and failed in 1993: sixty years later, a set of sign patterns turned into points showed that some shapes need exponentially many pieces — the first in 1,325 dimensions, and now known in 64.

topology · Borsuk ulam
The 7 × 7 Fourier matrix as arrows. Entries of the order 7 discrete Fourier matrix as unit arrows, with the minor on rows 1,3,4 and columns 0,2,5 highlighted; its determinant has modulus 2.645751.

A prime leaves no room for a comb

Take the table of powers of a root of unity, pick any rows and any equal number of columns, and take the determinant. At order 12 about one such determinant in six is exactly nought. At order 11, among 184,756 of them, none is, and in 1926 Chebotarev proved that none ever is at a prime. It means a signal on p places and its transform together occupy at least p + 1, while a comb on twelve places and its transform take 4 and 3.

algebra · Roots of unity
Three distances fix a word of three bits. The cube of three-bit words with landmarks 000, 001, 010; each word labelled by its Hamming distances to them; all eight lists differ.

How few distances fix a word

An unknown word of a thousand bits can be read one bit at a time with a thousand questions. Ask instead for its distance from a chosen word, and each answer is worth about half of log₂ n bits, so roughly two hundred distances fix it. A balance reading many coins at once is the same question. So is Mastermind, in which Knuth's rule finds any of the 1,296 codes in at most five guesses and a mean of 4.476, and no first guess is best on both counts.

computation · Error-correcting codes
A sorting network on 8 wires. Batcher's odd-even merge network with 8 wires, 19 comparators and depth 6; it sorts every input, checked on all 256 strings of noughts and ones.

A sort that never looks at the answers

Most sorting decides its next comparison from the last one. A sorting network decides them all in advance: a fixed sequence of swaps-if-out-of-order, wired up before any number arrives. Whether such a thing sorts everything can be settled by trying 2ⁿ strings of noughts and ones instead of n! orderings. Nineteen comparators sort eight numbers, and proving that nothing shorter sorts eleven took decades and a satisfiability solver. Over neighbours only, one single test, the reversed row, decides the whole question.

computation · Permutation parity
Every two edges meet. Star polygons with 3, 5, 7 and 9 points: odd star polygons are straight thrackles with exactly as many edges as points; every pair of edges meets once, at a shared point or by a crossing.

Every two edges must meet

A planar drawing has edges that avoid each other. Turn the rule round and insist that every two edges meet exactly once, at a shared end or a single crossing, and the drawing is what John Conway called a thrackle. In the 1960s he conjectured that a thrackle can never have more edges than points, and put up a prize. With straight edges a short argument settles it, and the argument also bounds the longest distances in a set of points. With curved edges it is still open.

discrete · Planarity
Differences round a ring. Four numbers 0,7,3,1 under repeated differences round a ring, reaching zero in 7 steps: 0 7 3 1 / 7 4 2 1 / 3 2 1 6 / 1 1 5 3 / 0 4 2 2 / 4 2 0 2 / 2 2 2 2 / 0 0 0 0.

Differences round a ring

Write four numbers at the corners of a square and put on each side the difference of its two corners. Repeat with the new square. Whatever the four whole numbers are, the process reaches nought within a few steps. Write five numbers and it almost never does. Rings whose size is a power of two always finish, and every other ring settles into a cycle whose length depends on how a polynomial factors over two elements: 7 at seven, 341 at eleven, 31 at thirty-one.

dynamics · Iteration
The twenty monotone functions of three letters. All 20 monotone Boolean functions of three letters drawn on the cube of inputs, from the constant false to the constant true.

Functions that only go up

Of the 256 logical functions of three letters, only twenty never turn off when a letter is turned on. Dedekind asked in 1897 how many such monotone functions there are for n letters. Computing the count is hard enough that the answer has advanced one letter every twenty-five years or so, and the ninth arrived in 2023, from two groups in the same month, at forty-two digits. Almost everything about the number comes from a single layer of the cube.

logic · Truth functions
Amounts arranged by remainder. Payable and unpayable amounts for coins 5 and 7, in columns modulo 5: largest unpayable 23, 12 unpayable amounts.

The largest amount two coins cannot pay

With coins of 5 and 7, the amounts 1, 2, 3, 4, 6, 8, 9, 11, 13, 16, 18 and 23 cannot be paid, and everything else can. Two lines of argument give the formula ab − a − b for the last gap, and half the rest of the board is gaps. For three coins no such formula exists, in a sense that can be proved. And the sets that coins can make have a count that climbs at the golden ratio, a conjecture settled from a table of 67, 118, 204.

number · Euclidean algorithm
Why 78,557 · 2ⁿ + 1 is never prime. For k=78557: 3 divides when n is 0 mod 2; 5 divides when n is 1 mod 4; 7 divides when n is 1 mod 3; 13 divides when n is 11 mod 12; 19 divides when n is 15 mod 18; 37 divides when n is 27 mod 36; 73 divides when n is 3 mod 9; every exponent covered with period 36.

Numbers that never make a prime

Multiply 78,557 by a power of two and add one. The result is never prime, for any power, though almost every other odd number gives a prime within a few doublings. The reason is that seven small primes take it in turn to divide the result, on a schedule repeating every 36 steps that leaves no step uncovered. Proving nothing smaller does this has taken sixty years of search, and five candidates are still running.

number · Infinitude of primes
Boxes as a permutation. A random permutation of 24 with cycle lengths 11, 7, 5, 1; longest 11.

A hundred prisoners and one shuffle

A hundred prisoners each search fifty of a hundred boxes for their own number, one at a time, with no communication once it starts. If any fails, all are executed. Choosing at random gives them a chance of 8 × 10⁻³¹. There is a rule that gives them 31%, and no rule can do better. Every prisoner's individual chance is still one half: what the rule changes is not how often each succeeds but how those successes line up.

probability · Inclusion exclusion
A full board has exactly one winner. A random 11 by 11 Hex board filled with two colours: second colour connects with a chain of 11 cells.

A board that cannot be drawn

Colour a rhombus of hexagons in two colours. One colour must join its two sides, and only one: in all 65,536 colourings of the four-by-four board, no exception. The proof is a walk along the colour boundary, the same walk that proves Sperner's lemma, and David Gale showed that the no-draw theorem of this board game is equivalent to Brouwer's fixed-point theorem. Nobody knows the winning strategy for a full-sized board, though a short argument proves one exists.

topology · Fixed points
A game of Sprouts. A game on two spots in four moves: each move joins two spots with a free life and adds a new spot on the curve; at the end the two surviving spots lie in different regions.

A game decided before it starts

Draw some crosses on paper. Players take turns joining two free arms with a curve and adding a new cross on it. However they play, a game on n crosses lasts exactly 5n − 2 moves, so the winner is known before the first move: Euler's formula has already decided it. Its close relative Sprouts differs by one rule, leaving a real game whose winner for each size is known only by huge search, and which seems to depend on the size modulo six for no known reason.

topology · Euler characteristic
Six lines all at one angle. The six diagonals of the icosahedron: every pair meets at cosine 0.447214, an angle of 63.43 degrees.

Six lines all at one angle

Take the six long diagonals of an icosahedron: every pair meets at the same angle. Squaring each line into the matrix that projects onto it removes every sign and leaves a table no vector can kill, so at most d(d + 1)/2 lines can do this in d dimensions. The bound is reached at 2, 3, 7 and 23, and at no other dimension anyone can find.

algebra · Inner product
Ten stable matchings on four a side. The market of four a side made by doubling, with all 10 of its stable matchings joined by the rotations that lead from one to the next, 18 in all.

The market with the most stable matchings

Random preferences give a sixteen-a-side market about five stable matchings. Nesting a two-a-side market inside itself gives the same size 195,472, every one of them listed. That construction is forty years old and nothing has beaten it, while the ceiling above it has fallen from 2¹⁷ⁿ to 3.55ⁿ. The truth lies somewhere between 2.28ⁿ and that.

applied · Stable matching
A secret on a curve in a finite field. The quadratic 17 + 9x + 4x² modulo 31: shares q(1) = 30, q(2) = 20, q(3) = 18, q(4) = 24, q(5) = 7, q(6) = 29, q(7) = 28, q(8) = 4; the secret is q(0) = 17.

Two shares know nothing

Hide a number as the constant term of a quadratic modulo a prime and give eight people one value each. Any three can recover it. Any two know exactly nothing: of the 2,197 quadratics modulo 13, those matching two shares split into exactly one for each possible secret. Over the whole numbers the same two shares already give away the secret's parity.

computation · Finite fields
A code made of the flats of a space. All 32 words of the Reed–Muller code RM(1, 4), each drawn on the sixteen points of the affine space of four dimensions over two elements: one word of weight 0, one of weight 16 and thirty of weight 8.

Parallel planes take a vote

Draw a four-dimensional space with two values to a coordinate as a 4 × 4 grid, and mark its hyperplanes: thirty-two patterns any two of which differ on eight of sixteen squares. A polynomial's top coefficient can be read off any plane, and parallel planes do not overlap, so an error spoils only one vote. One of them flew to Mars, and in 2016 it turned out to reach Shannon's limit.

computation · Finite geometry
Alone on the track. Speeds 1, 2, 3, 4 relative to a still runner: the best time 0.2000 leaves every other runner at least 0.2000 away, exactly 1/5.

Alone on the track

Runners set off together at different constant speeds. Is each of them, at some moment, far from all the others? A pigeonhole on time gives half the conjectured distance in two lines, and sixty years of work have not closed the other half. The speeds 1, 2, …, k are exactly at the limit, and so, surprisingly, are 1, 3, 4, 7 and 1, 4, 5, 6, 7, 11, 13.

discrete · Pigeonhole
A season's games as a flow. Whether Detroit can still finish first: the games among the others are the left column, 27 wins to place, and each rival can absorb at most 76 minus its wins; the maximum flow is 26, so 1 wins have nowhere to go, and Detroit is out.

Out before the table says so

Detroit has 49 wins and 27 games left, so it can reach 76, and the leader has 75. On paper it is alive. It is not: the four teams ahead must play 27 games among themselves, and whoever wins them, those four finish with an average above 76. Finding that takes one maximum flow, and it is checked against every possible result of every game.

discrete · Network flow
Eight points that do not want to be a cube. Closest-pair angle for 8 points: cube 70.5288 degrees, square antiprism 74.8585 degrees at height 0.5111, numerical search 74.8583.

Eight points that refuse the cube

Place eight points on a sphere so that the closest pair is as far apart as possible. A cube manages 70.53°. Rotating one face by 45° and pushing the faces together gives 74.86°. A botanist counting pores on pollen grains asked this in 1930, and proofs still stop at fourteen points: one search in five hundred finds the best thirteen, whose failure to reach 60° is why kissing spheres stop at twelve.

geometry · Regular polyhedra
Lines that cut out as many triangles as possible. Straight-line arrangements found by a seeded climb: 5 triangles from 5 lines and 11 from 7, each meeting the bound.

The triangle a triple point buys

How many triangles can eight straight lines cut out? A count of line segments says at most 16, a parity argument takes off one, and the tables say 15. Yet every one of the 1,232,944 arrangements in which only two lines ever cross stops at 14. The fifteenth triangle exists only if three lines are made to meet at exactly one point, and moving a line by a hundredth loses it.

geometry · Ordinary lines
One function, two orders. The function a₁b₁ + a₂b₂ + a₃b₃ as a reduced decision diagram: 8 nodes with partners together, 16 nodes with them apart.

The order of the questions

Decide a Boolean function by asking about its variables one at a time, and share every state that behaves alike. For a₁b₁ + a₂b₂ + … the result has 2n + 2 nodes if partners are asked together and 2ⁿ⁺¹ if they are apart. All 40,320 orders of eight variables give anything from 10 to 32 nodes, while multiplication's middle bit grows fast in the best order of all.

logic · Truth functions
What all small machines leave on the tape. All 16777216 two-symbol Turing machines with three states, run to step 22: 7571840 halt, leaving 95 distinct strings; most common 0 (2097152), 1 (2097152), 00 (722752); the longest strings are the rarest, up to 20.85 bits.

The shortest description nobody can certify

A string's complexity is the length of the shortest program that prints it. Counting shows almost every string has no short program, and diagonal arguments show nothing can compute the length, or even prove it large for any single string past a fixed point. All 16,777,216 three-state Turing machines leave only 95 strings on their tapes, and a compressor treats π exactly as it treats random bits.

logic · Diagonalisation
Sums whose primes are few. Four abc triples and their qualities: 1+8=9, radical 6, quality 1.2263; 5+27=32, radical 30, quality 1.0190; 1+63=64, radical 42, quality 1.1127; 2+6436341=6436343, radical 15042, quality 1.6299.

Sums with too few primes

Add 2 to 6,436,341 and the sum is 23⁵: three numbers with only four primes between them, and their product 15,042 is far smaller than the sum. The abc conjecture says this can happen only so far. Of 606 such triples up to 200,000, only seven reach quality 1.4, and if the conjecture holds, Fermat's last theorem and much else follows for large exponents in a line.

number · Unique factorisation
Goldbach's comet. The number of ways to write each even number as a sum of two primes up to 12000, coloured by divisibility by 3 and 5; r(12000) = 302 and r(12002) = 115.

The comet Goldbach left behind

Count the ways each even number is a sum of two primes, and the points do not form a smear. They split into bands: 12,000 has 302 ways and 12,002 has 115. One small product over odd prime factors explains every band and brings them all to a single line, and it says the count grows without bound. Nobody can prove the count is never nought.

number · Infinitude of primes
One number for each arm. Gittins indices at discount 0.9 for s successes and f failures on a uniform prior: a fresh arm has mean 0.5 and index 0.7029.

One number for each arm

Several slot machines pay at unknown rates, and each pull both earns and teaches. The problem seems to tangle every machine with every other, and in the 1940s it was thought hopeless. Then John Gittins found that each machine alone has one number, and the rule is to play the highest. An exact search over 1,187,671 states of two arms gets the same value to six places.

probability · Optimal stopping
Crossings counted with signs. Circle maps x to dx plus a bend: degree 3: 2 fixed, signed sum -2; degree −2: 3 fixed, signed sum 3; degree 2, bent: 5 fixed, signed sum -1.

A number that counts what it cannot see

Whether a map has a fixed point seems to need the map. Lefschetz's number needs only what the map does to holes, and it stays the same however the map is bent. On a torus it is one determinant: |det(I − A)| fixed points, checked exactly on all 2,401 small matrices, 1, 5, 16, 45, 121 periodic points for Arnold's cat, and a formula that also counts solutions of equations over finite fields.

topology · Fixed points
Two sign sequences laid on themselves. Length 41: random signs (seed 41) with E = 552 and merit factor 1.523; the rotated Legendre sequence of 41 with E = 176 and merit factor 4.776.

A quarter turn quiets the echoes

Lay a sequence of signs on a shifted copy of itself and add up the squares of the overlaps. Random signs leave the total near n²/2, and the squares modulo a prime, started a quarter of the way along, cut it to a twelfth. Exhaustive search finds far quieter short sequences, and no infinite family is proved to do better than 6.342.

algebra · Polynomial roots
Three widows and the Mishna's table. The Mishna's division of estates of 100, 200 and 300 among claims of 100, 200 and 300: 33⅓ each; 50, 75, 75; 50, 100, 150.

The debts the Mishna divided

A man dies owing his three wives 100, 200 and 300. The Mishna divides an estate of 100 equally, of 300 in proportion, and of 200 as 50, 75 and 75, and for nearly two thousand years nobody could say why. The table is the nucleolus of a cooperative game, and the only division in which every pair splits its share as two people split a contested garment.

applied · The core
Six goods, three people, and no envy. Three people's random values for six goods, with an envy-free allocation shaded: Ada values the bundles at 0.86, 0.85, 0.34; Ben values the bundles at 0.64, 1.83, 0.75; Cy values the bundles at 1.05, 1.24, 1.29.

Twice as many goods as people

Indivisible goods with random values cannot always be shared so that nobody envies anybody. With one good each it works only when everyone's favourite is different; with twice as many goods as people it almost always works. Deciding each case exactly shows the chance climbing steeply in between — and a simple draft getting there only when the goods divide evenly.

applied · Fair division
Every convex shape the tangram can make. The 13 convex polygons that the seven tangram pieces can form, each with one arrangement, and the number of arrangements of each: 20, 12, 12, 12, 36, 12, 8, 8, 16, 4, 56, 24, 36.

Thirteen convex tangrams

The seven tangram pieces make thousands of figures, and only thirteen of them are convex. The proof turns a puzzle with sliding pieces into a finite list: every piece is made of the same small triangle, any convex figure puts them all on one grid, and that grid allows exactly twenty convex outlines of the right area. A search tries all twenty and finds that thirteen can be made.

computation · Scissors congruence
Seven hats, sixteen losses. All 128 ways seven red-or-blue hats can fall, each drawn as seven dots, with the 16 configurations the Hamming strategy loses framed: the team wins 112 of 128, a probability of 7/8.

Wrong guesses that arrive together

Seven players in red or blue hats each see every hat but their own, and must guess their own colour or pass. Every guess is a coin toss, yet with the Hamming code the team wins seven times in eight — not by making guesses better, but by making the wrong ones arrive together. The best chance for any number of players is fixed by the fewest losses that cover the cube.

computation · Error-correcting codes
Three edges at every point, and how many ways to pair. The 3-regular bipartite graphs with six vertices a side having the fewest (17) and the most (36) perfect matchings among all 297200, each with one matching in red.

How many ways a regular graph pairs off

Give every point of a bipartite graph the same number of edges and Hall's theorem promises a perfect matching. It promises far more: at least ((d − 1)^(d−1)/d^(d−2))ⁿ of them, by Schrijver's theorem, and at most (d!)^(n/d), by Brégman's. Listing all 297,200 cubic graphs on six and six finds only four different counts, and random graphs turn out to live near the bottom.

discrete · Halls theorem
Fifteen edges that need four colours. The Petersen graph with its 15 edges in 4 colours; a search over all colourings with three finds none.

One colour more than the busiest point

Colour the edges of a graph so that edges meeting at a point differ. The busiest point forces as many colours as it has edges, and Vizing proved that one more is always enough. So every graph is in one of two classes, and deciding which is hard — yet almost every graph is in the first, and the ones in the second carry an odd piece that cannot be paired off.

discrete · Graph colouring
Five ellipses, every combination once. A rotationally symmetric Venn diagram of five congruent ellipses (centre distance 0.7, semi-axes 1.4 and 0.5, tilted 7.5°): 32 regions on a raster, 30 crossing points.

Venn diagrams that turn into themselves

A Venn diagram shows every combination of in and out exactly once. Ask for one that looks the same after a turn of 1/n, each curve rotating onto the next, and a counting argument forbids it unless n is prime. Five congruent ellipses manage it, certified by Euler's formula; four rotated copies cannot, and it took until 2004 to show that every prime can.

logic · Class diagrams
Excluded middle fails at one point, and its double negation does not. Open sets of the real line as truth values: p = (0, ∞), ¬p = (−∞, 0), p ∨ ¬p misses 0, ¬(p ∨ ¬p) is empty and ¬¬(p ∨ ¬p) is the whole line.

Every tautology survives double negation

Intuitionistic logic refuses excluded middle, Peirce's law and every other classical principle that claims more than can be shown. Glivenko proved in 1929 that it refuses nothing outright: put ¬¬ in front of any classical tautology and the result is intuitionistically valid. Every Kripke model of up to four states confirms it for eight famous laws, a census of 11,451 formulas confirms it one by one, and a model with a growing domain shows where it stops.

logic · Non classical logic
Five powers of two that are seven more than a square. How close 2ⁿ − 7 comes to a square for n from 3 to 40, as a fraction of the gap between neighbouring squares: squares at n = 3, 4, 5, 7, 15 (1, 3, 5, 11, 181 squared), and at no other n up to 10000.

Five powers of two, seven more than a square

2³ − 7 = 1², 2⁴ − 7 = 3², 2⁵ − 7 = 5², 2⁷ − 7 = 11², 2¹⁵ − 7 = 181². Ramanujan asked in 1913 whether there are any more. Testing every exponent up to 10,000 finds none, and Nagell proved in 1948 that none exist, by moving to a number system where 2 splits into two primes and factorisation is still unique. The same five solutions decide when a two-error-correcting code can be perfect.

number · Unique factorisation
One swap splits the long cycle. A shuffle of 100 boxes whose longest cycle has 61 boxes, drawn as a ring; swapping the contents of two boxes 30 steps apart splits it into cycles of 30 and 31, so every cycle has at most 50 and all prisoners succeed.

One swap saves every prisoner

A hundred prisoners following the cycles of a shuffle all survive about 31% of the time. Let a helper look into the room first and swap the contents of two boxes, and they survive every time. With fewer boxes each, more swaps are needed — exactly one per cut a long cycle needs — and the number of swaps a random room demands has an exact distribution.

probability · Inclusion exclusion
Seven numbers whose 128 subset sums all differ. The 128 subset sums of 20, 31, 37, 40, 42, 43, 44, spread from 0 to 257 with no two equal, above those of the powers of two 1 to 64.

Numbers whose subset sums all differ

The powers of two 1, 2, 4, …, 64 have 128 subset sums and no two are equal. So do 20, 31, 37, 40, 42, 43 and 44, whose largest member is smaller, and an exhaustive search shows no seven numbers do it with less. A pigeonhole on the sums says the largest member must grow like 2ⁿ/n; a variance argument improves that to 2ⁿ/√n; the best known sets sit near 0.22 × 2ⁿ. Whether the truth is a constant times 2ⁿ is Erdős's five-hundred-dollar question, and the pigeonhole cannot reach it.

discrete · Pigeonhole
Fifty-four numbers funnel into 6174. The 54 values Kaprekar's routine can produce from four digits, arranged by how many further steps they need to reach 6174: 1, 3, 12, 10, 10, 10, 8 at zero to six steps.

Fifty-four numbers funnel into 6174

Take four digits, not all the same, arrange them largest first and smallest first, and subtract. Repeat. Every one of the 9,990 starts reaches 6174, and none needs more than seven steps. The reason is that the first subtraction forgets almost everything: its result depends only on two differences of digits, so ten thousand starts collapse to fifty-four values, and a map on fifty-four points can be drawn whole. Change the number of digits or the base, and the same collapse ends in cycles instead.

dynamics · Iteration
A list of sentences each denying all the later ones. Fourteen sentences, each saying that every later sentence is false, drawn as a grid of which sentences each one mentions — every cell above the diagonal and none on or below it — beside the only consistent assignment of truth values, in which the last sentence alone is true.

A liar without a loop

Every paradox of truth seemed to need a sentence that talks about itself, directly or round a loop. Stephen Yablo found one that does not: an infinite list in which each sentence says that all the later ones are false. Cut it off anywhere and exactly one assignment of truth values works — all false but the last; keep it infinite and none does. A finite system with no loop always has exactly one, so the paradox lives in the one place a finite picture cannot draw: a list with no last sentence.

logic · Diagonalisation
Filling a unit with the largest piece that fits. A unit bar filled greedily by 1/2, 1/3, 1/7, 1/43 and 1/1807, and below it what is left of 1 after each number of terms, from 1/2 down to about 10⁻⁵² after eight: 1/1806 after four.

The largest piece that still fits

Fill a unit with unit fractions, always taking the largest one that still fits: 1/2, 1/3, 1/7, 1/43, 1/1807. The denominators are Sylvester's sequence, each one more than the product of all before it, and after k of them what is left is exactly one over the next term minus one. Curtiss proved in 1922 that no k unit fractions get closer to 1 from below; an exact search confirms it to six terms. Applied to almost any other fraction, the same greedy rule is wasteful — 8/97 ends with a denominator of 150 digits.

number · Stern brocot
Langley's adventitious angle. The isosceles triangle with apex 20° and base angles 80°, the cevian from B at 60° to the base meeting AC at D, the cevian from C at 50° meeting AB at E, and the angle BDE, computed as 30° to nine places.

Thirty degrees without a circle

In a triangle with angles 20°, 80° and 80°, draw cevians at 60° and 50° to the base and the angle between them and the segment they cut off is exactly 30°. Whole-number answers in angle problems usually come from a circle, through the inscribed-angle theorem; this one does not, since the four points are not concyclic. Testing every whole-degree quadrilateral finds 1,002,733 with a whole-degree answer: 939,929 explained by a circle, and 62,804 that are not.

geometry · Inscribed angle
The shortest solution runs along one side (3 discs). Hanoi graph with 3 discs: 27 states; route classic of 8 states.

One tour through every position of the Tower of Hanoi

Draw every position of the Tower of Hanoi as a point and every legal move as a line, and the picture is a Sierpiński triangle. The famous shortest solution runs straight down one side of it, spelling the binary Gray code as it goes. The slowest honest solution threads through every position once and spells the ternary one. And unlike the cube the binary Gray code walks, which has 1,344 closed tours at four dimensions, the triangle has exactly one at every size.

discrete · Hamiltonian cycles
A picture hung on 2 nails: a b a′ b′. word a b a′ b′ of length 4 on 2 nails; solves the puzzle: true.

A picture that falls when any nail is pulled

Hang a picture on two nails so that it stays up, but falls the moment either nail is pulled out. The string has to go round the nails in a pattern that is a commutator — once round each, then back round each in the same order — and the reason is that a loop in a plane with holes in it is a word in a group in which order matters. With more nails the commutators nest, and an exhaustive search finds the shortest strings for two, three and four nails: 4, 10 and 16 passes.

topology · Homotopy
The weight of the army, with the target on row 5. Pagoda weights x^d for target row 5; half-plane total 1.000000; first 5 rows 0.909830.

The golden ratio stops the fifth soldier

Soldiers fill a half-plane and advance by peg-solitaire jumps across a line. Two can send one of them a row forward, four two rows, eight three, twenty four rows — and no army at all, of any finite size, reaches the fifth. John Conway's proof weighs every square by a power of 1/φ, and the golden ratio's own equation x² + x = 1 is exactly what makes a forward jump cost nothing and the whole infinite army weigh exactly as much as the square it cannot reach.

geometry · Golden ratio
Thirteen votes in twenty-five, and 1 to 4 seats. clustered voters: seats over 4006 maps from 1 to 4.

Every map of twenty-five voters

Put twenty-five voters on a five-by-five grid, thirteen red and twelve blue, and divide them into five districts of five connected squares. There are exactly 4,006 ways to do it, and the same votes give red one seat, two, three or four depending on which map is drawn. Listing every map turns the accusation of gerrymandering into a measurement: how unusual a given map is among all the maps that could have been drawn — and the answer depends on where the voters live as much as on how many there are.

applied · Voting rules
13 cards, any two sharing exactly one symbol. JKLM CFIJ BEHJ GHIM CEGL BFGK DEFM CDHK BDIL ABCM AFHL AEIK ADGJ

A deck where any two cards match once

A card game deals cards of eight pictures each, and any two cards in the deck share exactly one picture. The deck is the projective plane of order seven with its lines dealt as cards — 57 of them, of which the game prints 55. The two left out can be reconstructed from the counts of the pictures alone; a deck built one card at a time, by careful search, gets stuck at about two dozen; and the bound of 57 needs one exception, a deck that never stops.

computation · Finite geometry
The question a liar answers truthfully. knight/yes/yes/yes; knight/no/no/no; knave/yes/no/yes; knave/no/yes/no

The question a liar answers truthfully

On an island where knights always tell the truth and knaves always lie, one question gets an honest answer from both: ask not whether something is so, but whether the islander would say yes if asked. The knave lies about his lie. Written as truth functions, the trick is the identity (Q ↔ K) ↔ K = Q, it is the only one of the sixteen possible questions that works, and applied a second time it strips out an unknown language too — enough to solve Boolos's puzzle of the three gods, checked here against every case.

logic · Truth functions
Positions at each distance, and what sequences could reach. 0:1/1 1:9/9 2:54/54 3:321/324 4:1847/1944 5:9992/11664 6:50136/69984 7:227536/419904 8:870072/2519424 9:1887748/15116544 10:623800/90699264 11:2644/544195584

Every position of the pocket cube

The two-by-two Rubik's cube has 3,674,160 positions once its orientation in the hand is ignored, few enough to visit every one. Breadth-first search finds that none is more than eleven face turns from solved, or fourteen quarter turns, and that only 2,644 positions sit at that distance. Counting move sequences proves only nine; the gap between nine and eleven is the cube's relations, the first of which appear at three turns. Two faces alone reach 29,160 positions, arranged by a copy of the symmetric group on five things acting on six corners.

algebra · Cayley graph
Sincere approval ballots can elect any of the five. A: 111113 -> 10,0,7,7,7; B: 323221 -> 8,25,7,12,12; C: 411311 -> 8,12,19,7,12; D: 142434 -> 10,13,12,27,13; E: 231112 -> 8,6,7,7,20

Where a sincere voter stops approving

Approval voting asks each voter to tick every candidate they find acceptable, and the most ticks wins. A voter with a ranking votes sincerely by ticking a top segment of it — but the ranking does not say where the segment ends. On the 27 ballots where five classic rules elect five different candidates, some choice of sincere stopping points elects each of the five, the Condorcet loser included. The Condorcet winner can always be elected this way; with three candidates and a large electorate, almost every candidate can; and a voter unsure which race is close can do strictly better by skipping a favourite.

applied · Voting rules
A square whose every diagonal is a transversal. n=5 k=2: rows 01234 34012 12340 40123 23401

Queens on a torus, and the squares whose every diagonal is a transversal

Roll a chessboard into a torus so that its diagonals wrap round, and ask for n queens that do not attack. Pólya proved in 1918 that it can be done exactly when n shares no factor with 6, by two short sums. A Latin square whose every wrapped diagonal holds each symbol once — a Knut Vik design, from Norwegian field trials — is the same problem solved n times at once. Search finds 10, 28, 88 and 4,524 placements at 5, 7, 11 and 13; every one is a straight line until 13, where 4,394 are not.

computation · Latin squares
The fewest ones that build a number. 10:7 100:14 1000:21 1439:26 2000:23

The fewest ones that build a number

Build a number from ones using only addition, multiplication and brackets, and ask for the fewest ones. Six needs five, as (1+1)·(1+1+1); seven needs six. A power of three needs exactly three ones per factor, and no number does better for its size; building from binary digits never needs more than three ones per doubling. Between those bounds, the cheapest expressions are found by multiplying cheap factors and adding one. Every prime up to thirty thousand costs exactly one more than the number before it — a pattern that holds until 353,942,783.

number · Unique factorisation
Four dice that beat each other in a circle. A>B 24/36; B>C 24/36; C>D 24/36; D>A 24/36; means 2.667,3.000,3.333,3.000

Four dice that beat each other in a circle

Bradley Efron's four dice are numbered so that A beats B, B beats C, C beats D and D beats A, each two times in three. Whichever die an opponent picks, there is another that beats it, and the die with the lowest average beats one with a higher average. Rolling two of each reverses half the circle. Three dice can never beat each other more strongly than the golden ratio's reciprocal, 0.618, and an exhaustive search reaches 0.6; four can reach 2/3, which Efron's dice do exactly; no number of dice can reach three in four.

probability · Expectation

Named alongside it

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

ParityCounterexampleLower boundConjecturePermutationInvariantModular arithmeticOpen problemCounting argumentFinite fieldLatticePrimes

All concepts