Matpic
mathematics, in pictures
Concept

Convexity

The property of a shape that contains the whole straight line between any two of its own points. For the unit ball of a distance it is exactly the triangle inequality, and it is what makes an optimum reachable by going downhill.

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

The five Platonic solids. Tetrahedron, cube, octahedron, dodecahedron and icosahedron, drawn at a common scale.

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.

geometry · Regular polyhedra A Reuleaux triangle. A curve of constant width on 3 vertices, with 6 pairs of parallel supporting lines drawn across it. Every pair is 180.1 apart.

Round is not the only way to be the same width

A shape that measures the same in every direction sounds like a description of a circle. It is not — there are infinitely many others, one of them is on a coin in most people's pockets, and a drill built from one cuts a nearly square hole.

geometry · Constant width Every triangulation of a 6-gon. All 14 ways of cutting a convex 6-gon into triangles with non-crossing diagonals — the 4th Catalan number, counted by drawing them.

One sequence, counting everything

The number of ways to cut a polygon into triangles is 1, 2, 5, 14, 42. So is the number of ways to bracket a product, the number of binary trees, and the number of paths that never cross a diagonal. They are the same count, and the reason is one picture.

discrete · Catalan numbers The plane divided by nearest neighbour. 10 sites, and every point of the rectangle shaded by which site is closest to it. The boundaries are the places where two sites tie.

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.

geometry · Voronoi 4 circles, and the 14 patterns they realise. Closed curves overlapping in the plane, with each region of the arrangement identified by which curves contain it.

Four circles cannot do it

Three overlapping circles cut the plane into exactly the eight regions three sets need. Four circles cut it into fourteen, and sixteen are required — so the diagram everyone draws stops working at four, and the reason is a count.

logic · Class diagrams Two polytopes, two optima, one number. The feasible regions of a linear program and of its dual, side by side, each with its optimal vertex, and a number line on which the gap between the two optima closes to nothing.

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.

applied · Duality What one more unit of constraint 1 is worth. The optimum of a linear program plotted against one of its right-hand sides, as an exact piecewise linear graph, with the breakpoints marked and each piece's slope named as a dual variable.

What a constraint is worth

The rung below settled that a linear program and its dual reach the same number. This one asks what the dual's variables are, and the answer converts a solution into a rate for every constraint — piecewise constant, zero on the constraints that are not doing any work.

applied · Duality The value of a 2×3 zero-sum game, named from both sides. The row chooser's expected payoff against each column as a line over the mixing probability, with the lower envelope and its maximum, beside the same construction from the column chooser's side. Both give 19/15.

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.

applied · Equilibrium The link that makes every traveller later. Four nodes and two routes, with the equilibrium flow and travel time before a zero-cost link is added between A and B and after. The travel time rises from 10 to 12.

The road that makes everyone later

An equilibrium is a state nobody can improve alone, which is a much weaker thing than a state anybody would choose. Adding a link that costs nothing to use makes every traveller in this network strictly slower, and the arithmetic says by exactly how much.

applied · Equilibrium One perimeter of 300, spent five ways. Regular polygons all of the same perimeter, drawn to scale beside the circle of that perimeter, with the area each encloses and the ratio 4πA/L².

The most area a fence can hold

One length of boundary, and the question of what shape to bend it into. The answer is a circle, everybody knows it, and the argument that convinced the nineteenth century turned out to prove something slightly different.

geometry · Isoperimetric The unit ball at p = 2.00. The set of points one unit from the origin, when distance is measured by the p-th power sum. At p = 1 it is a diamond, at p = 2 a circle, and as p grows it fills out a square.

Circles that are diamonds and squares

The theorem hands over a formula for distance. Take the formula as a definition, change the exponent in it, and the set of points one unit from the origin stops being round — while remaining, in every sense that matters, a circle.

geometry · Pythagoras A table of shares written as a lottery over 3 whole assignments. A doubly stochastic table of shares, and beneath it the permutation matrices and weights that add up to it exactly, each drawn as a grid with one marked cell per row.

A lottery over whole assignments

A table of shares in which every person's shares add to one task and every task is exactly covered is never anything more than a mixture of whole assignments — and finding the mixture is a matter of taking one complete assignment out at a time.

applied · Assignment A chord of x², and the curve under it. The curve x² with one chord drawn across it, the region between them shaded, and the midpoint heights of both marked. The comparison is computed at four hundred sample points.

The curve of the average, and the average of the curve

A curve that bends upwards keeps every one of its chords above it. That single fact, applied to a weighted average instead of a midpoint, turns into an inequality that produces the arithmetic–geometric mean inequality, Cauchy–Schwarz and the entropy bound as special cases.

analysis · Convexity A lattice of determinant 3, and the ellipse that must hold a point. A lattice with the parallelogram its basis spans, an ellipse centred at the origin, and the nearest non-zero lattice point it contains.

One point in every big enough shape

A determinant measures a lattice, not the basis that happened to describe it — and that measurement is an exchange rate. Any symmetric convex region with more than four times that area has to swallow a lattice point.

algebra · Determinant The triangulation as the underside of a hull. Eight points on a floor, lifted onto a paraboloid above them. The faces of the lifted set's lower convex hull are shaded, and their shadows on the floor are the Delaunay triangulation of the original points.

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.

geometry · Voronoi A scatter walking towards its own centres. 4 panels of the same 24 sites: the initial clumpy scatter and the Voronoi diagram after 1, 3, 12 rounds of Lloyd's iteration, with the cost falling to 52% of the scatter's as the cells even out.

Every site in the middle of its own cell

Move each point to the centre of mass of its own Voronoi cell, then redraw the diagram, then do it again. The rule is two lines long, it never mentions hexagons, and what it settles into is a honeycomb.

geometry · Voronoi The diagram when the sites are not the same size. 7 weighted sites drawn as circles of different radius, with the power diagram over them. The boundaries are straight, as in the unweighted diagram, but each one is pushed towards the smaller of the two circles it separates.

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.

geometry · Voronoi The two numbers that make up a width. A Reuleaux polygon with 3 sides, its centre marked as the origin, and the two supporting lines with normals 33° and 213°. The perpendicular distances from the origin to the two lines are marked; they add to the width.

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.

geometry · Constant width The 6 corners, and nothing in between. The 6 permutation matrices of size 3, drawn as grids. A search over every table of shares on a fine grid finds these and only these as corners of the set.

The corners are whole assignments

A table of shares can be written as a lottery over whole assignments, which the anchor's first rung demonstrates on one example. The general statement is that the corners of the set of such tables are exactly the whole assignments, and that single fact is why the whole subject is easy.

applied · Assignment One table of shares, two different lotteries. A doubly stochastic table decomposed into whole assignments twice, by two different orders, giving two mixtures that reconstruct the same shares.

One table, two lotteries

A table of shares says what fraction of each task each person does. It does not say how — the same table is a mixture of whole assignments in many different ways, and the differences are exactly what the people being assigned would care about.

applied · Assignment A line under every point of x². The curve x² with 4 tangent lines drawn, each extended across the whole interval and each staying below the curve throughout.

A line under every point

The chord above the curve is one definition of convexity. There is a second — a line under the curve at every point, staying under everywhere — and it is the one that turns a statement about a derivative at a point into a statement about the whole function.

analysis · Convexity x² and its conjugate. Two panels: the curve x² with tangent lines of several slopes, and the conjugate function plotted against slope, whose value at each slope is the intercept of the corresponding tangent.

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.

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

Where the guarantee stops

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

analysis · Convexity 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 Two convex sets 1.50 apart, and the line that separates them. Two convex polygons with a straight line drawn between them, together with the shortest segment joining the two sets, whose perpendicular bisector the line is.

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.

analysis · Convexity Area at equal width: the triangle least, the circle most. A bar for each curve of constant width the family draws, all at the same width, with the bar's length its enclosed area and the extremes marked.

The least area a width can hold

Barbier's theorem says every curve of constant width has the same perimeter, which removes perimeter as a way of telling the family apart. Area is not like that — the circle holds the most and the Reuleaux triangle the least — and the reason the minimiser has corners is a constraint rather than a preference.

geometry · Constant width

Named alongside it

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

DualityAreaConstant widthConvex hullLinear programSupporting lineVoronoi diagramAssignmentCircleCounterexampleExistence proofLocal minimum

All concepts