Duality
Named by 47 essays across 9 fields — each of them below, with the objects they name alongside it.
Why the list of perfect solids stops at five
There are infinitely many regular polygons and exactly five regular solids. The reason is not deep, but it is very sharp, and it can be checked on a single row of corners.
The plane, divided by whoever is nearest
Scatter some points and colour every other point of the plane by which one is closest. The result is a tiling nobody designed, and its dual triangulation has a property that no part of the construction mentions.
One connective is enough
Of the sixteen ways to combine two truth values, exactly two can build all the others by themselves. Which two is not obvious, and the reason turns out to be five properties that a connective either has or escapes.
Seven points, seven lines
A geometry with seven points, in which every two points lie on exactly one line and every two lines meet in exactly one point. There are no parallels, the whole thing is built out of the two-element field, and one of its lines has to be drawn as a circle.
Two numbers that have to meet
Every linear program has a shadow — a second program built from the same numbers read the other way, whose minimum can never fall below the first's maximum. That much is a one-line calculation; the theorem is that the two numbers are always exactly equal.
What a constraint is worth
A linear program and its dual reach the same number. What the dual's variables are is a separate question, and the answer converts a solution into a rate for every constraint — piecewise constant, zero on the constraints that are not doing any work.
The value from both sides
Two choosers move at the same instant, and each asks the cautious question — how much can be guaranteed, whatever the other does. With pure choices the two answers are usually different numbers; allow a probability and they are forced to be the same one.
Thirteen more when one word is dropped
The list of regular solids stops at five because the definition asks for two things at once. Ask for only the second — every corner alike — and thirteen more appear, each of them cut off a Platonic solid at a depth found rather than chosen.
The four that are allowed to cross themselves
Drop convexity from the definition of a regular solid and four more appear. Their faces are pentagrams, they pass through one another, and the alternating sum that gives two for every ordinary solid gives minus six for two of them.
Six in four dimensions, and three forever after
The count of regular solids goes five in three dimensions, six in four, and then three in every dimension above — for good. Four dimensions is the last place anything unusual happens, and it happens twice.
The five solids as three groups
There are five regular solids and only three groups of rotations between them, because a solid and its dual share their symmetries exactly. The largest of the three is the smallest group with no way of coming apart, which is why the general equation of the fifth degree has no formula.
Sharing a cost that is not the sum of its parts
Three users need capacities three, six and twelve of one shared thing, and serving any group costs the largest of them. Averaging what each adds over every order of arrival divides the bill — and for this family the average collapses to a rule anybody could apply by hand.
One dimension up, and the circles disappear
The Delaunay triangulation is defined by a condition about circles, which is awkward to compute and awkward to reason about. Lift every point onto a paraboloid and the circles turn into planes, the condition turns into convexity, and a two-dimensional problem is solved by looking at a three-dimensional shape from underneath.
When the sites are not the same size
Give every site a weight and the boundaries slide. The cells stay convex and the edges stay straight, which is surprising, and one thing happens that the unweighted diagram never allows — a site can end up owning nothing at all.
The shape described from outside
A convex shape can be given by its boundary or by the family of lines that touch it, and the second description turns the constant-width condition into one line of arithmetic — after which the perimeter falls out, and curves with no corners at all can simply be written down.
A price for every person and task
The cheapest assignment can be found without comparing it to any other. Attach a number to each person and each task so that no pair's two numbers exceed its cost, and if the numbers add to an assignment's total, that assignment is cheapest — proved, by an argument that never mentions the alternatives.
The function seen from its tangents
A convex function is the upper envelope of its own tangent lines, so it can be described by giving, for each slope, how far the line of that slope has to be pushed down. That description is a second function, and applying the construction twice returns the original.
A wall between two bodies
Two convex sets that do not meet can be told apart by a single straight line, and the line is a certificate — one object, checkable in a moment, proving something about every point of both. Remove convexity from either and no line exists, which is what the hypothesis was for.
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.
When several pairs share the roads
For one pair of places, the most that can travel between them equals the cheapest cut that separates them. Give three pairs a hub of three roads to share and the two numbers come apart: the pairs can send 3/2 between them, while separating every pair costs 2. Two pairs still meet their cut, but only by splitting units in half.
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.
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.
What the search has when it fails
A largest matching is easy to find and hard to certify: the claim that nothing larger exists is a claim about every arrangement not tried. The certificate turns out to be free — it is the wreckage of the search that failed.
The product that makes a division fair
Divide goods to make the total happiness as large as possible and the result can be monstrously unfair; make the least happy person as happy as possible and it can waste. Multiply the people's values together and maximise the product instead, and something unexpected happens — nobody envies anybody when goods can be split, and nobody envies by more than one item when they cannot.
Where two roots run into each other
Put every quadratic equation at a point of a plane, one coordinate per coefficient. Each possible root becomes a straight line there, every one of those lines touches the same parabola, and that parabola is the discriminant — the crease where the plane of roots is folded onto the plane of equations.
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.
When one of the two numbers is missing
The duality theorem is usually quoted as an equality: a linear program and its dual reach the same number. That is one of four cases. A program can run away to infinity, or have no feasible point at all, and then its dual is forced into a matching failure. Every small program with coefficients from minus one to one has been classified, and the table has exactly four occupied cells out of nine.
The lines the optimum lies under
Change the resources a linear program is given and its best value changes too, tracing a graph. Every solution of the dual is a straight line lying above that graph, and the graph is exactly the lowest of those lines — a bent roof of finitely many planks. Require the answer to be in whole numbers and the roof stays where it was while the graph falls away beneath it in steps, and the space between is the part of the problem no price can see.
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.
Zero in four dimensions
Corners minus edges plus faces is two for every solid. One dimension up, corners minus edges plus faces minus cells is zero for every one of the six regular four-dimensional solids, from the five-cell to the six-hundred-cell, and for every other convex solid in four dimensions. The alternating sum does not break when the dimension rises: it alternates, two in odd dimensions and zero in even ones, because it is measuring a sphere and not a solid.
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.
The cheapest way to send
Put a price on every road as well as a capacity and ask for the cheapest way to send four units. Twenty-eight ways exist and one is cheapest, and two certificates prove it without comparing it with the other twenty-seven: no cycle of roads it leaves unused costs less than nothing to push round, and there are prices at the places that every usable road fails to beat.
Prices the bidders raise
The cheapest assignment is certified by a price on every task, and those prices can be found without anyone in charge. Let each unassigned person bid for the task that suits them best at current prices, raise its price by a little more than it is worth to them over the next best, and wait. The bidding ends, and when the increment is small enough the prices it ends at are a proof of optimality.
The prices nobody can break away from
When houses are sold to buyers who value them differently, there is a whole range of prices at which nobody wants to walk away, and it has a remarkable shape — one corner best for every buyer at once, one best for every seller at once, and the buyers' corner pays each buyer exactly what the market would lose without them.
Prices at every corner
The duality theorem says a linear program's best value equals its dual's, and says nothing about how to find either. The simplex method finds both at once — it walks from corner to corner, and at each one asks the constraints that meet there for prices. A negative price names an edge that climbs; when none is negative, the prices are the proof.
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.
Prices for things wanted only together
When every buyer wants one thing, there are always prices at which everyone is content with what they get. Let one buyer want two things together and there may be none — and whether there are is decided exactly by whether the market's best fractional allocation beats its best whole one.
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.
One, plus a quarter, plus a ninth
Give n workers n jobs with every cost drawn at random, average one, and find the cheapest way to pair them. However large n is, the cheapest total averages less than π²/6, and for every n it is exactly 1 + 1/4 + 1/9 + … + 1/n². Parisi guessed the formula in 1998 from n = 1, 2 and 3; thirteen sizes of random tables, solved exactly, land on it within sampling error.
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.
A cube through a hole in a cube
Prince Rupert of the Rhine bet that a hole could be cut through a cube large enough for an equal cube to pass through it, and won. The trick is to look at the cube along a direction near its long diagonal, where its shadow is a hexagon wide enough to hold a square face with room to spare: a cube 6% larger can pass. All five Platonic solids turn out to have such a passage, found by searching over the directions from which a solid is seen — and in 2025 a solid was found that has none.
A relaxation that answers in halves
The cheapest set of points touching every edge of a graph is hard to find. Allow each point to be taken fractionally and the problem becomes a linear programme — and its best answers are never messier than halves. Every point gets 0, ½ or 1, the 0s and 1s can always be trusted, and the proof is a picture: double the graph into a bipartite one, where a matching decides everything exactly.
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.
Sixty rotations as far apart as rotations can be
The sixty rotations of the icosahedron are each at least 72 degrees from every other. A single polynomial, with coefficients that are all positive and values that are nowhere positive where it matters, proves that no sixty rotations do better and no sixty-one do as well. The same calculation proves the tetrahedron's twelve best at 120 degrees, and leaves the cube's twenty-four short of what it allows.
Two colonels and a linear programme
Two colonels divide their soldiers among three battlefields at once, and whoever sends more to a field wins it. Every division can be beaten by some other, so neither colonel has a safe plan — until they are allowed to choose at random. The best random choice is a linear programme, the opponent's best is its dual, and the theorem that the two meet is von Neumann's. With nine soldiers each, one optimal plan uses only seven divisions, and on every field it sends each number from nought to six exactly once.
Matching workers who will not wait
Workers arrive one at a time, each says which jobs would suit, and each must be given a job at once or lost. Any sensible rule matches half of what hindsight could. Choosing at random at each arrival can still fall to half. Draw one random order of the jobs before anyone arrives and stick to it, and the share cannot fall below 1 − 1/e, 63.2%. The same number is a ceiling for every rule, since on one shuffled triangle of a market they all score alike.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
ConvexityLinear programExhaustive searchCertificateEuler characteristicLinear programmingAssignmentPlatonic solidsComplementary slacknessConvex hullCounterexampleExistence proof