Matpic
mathematics, in pictures
Theme

Counting the same thing twice — page 8

One collection, counted by two different methods, and an identity that falls out because both answers have to agree. The proof is the pair of counts.
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. Discrete

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.

 A line in every direction in the plane over GF(7), in 31 points. A square grid of the points of a small finite plane with the points of a Kakeya set filled, beside a list of the lines it contains, one for each direction. Computation

No set with a line in every direction is small

In the plane over the integers modulo 7 there are 49 points and lines in 8 directions. A set holding a whole line in every direction needs 31 of the points — more than half — and in any dimension such a set fills a fixed share of the space. In the real plane the same sets can have area zero. Over a finite field one polynomial of low degree shows they cannot be small.

 Credit for one prediction, three ways of leaving an input out. Groups of bars, one group for each way of filling in the inputs that are not known, each bar one input's share of the difference between the prediction and the starting value. Applied

What a missing input is worth

A model prices a house at 180 from its size, its garden and its bedrooms, and the question is how much of the price each input is responsible for. Make the inputs the players and the average over orders answers it — once somebody decides what the model says when an input is not known. Three reasonable decisions give bedrooms nothing, nothing, and sixteen, for a model that never reads them.

 Shares on two triangles and a go-between. A network of players with each node labelled by its share of what the whole network earns, and its number of links beneath it. Applied

Cutting a link costs both of its ends the same

Three players, any two of whom can earn 1 together — but only if they are linked. Link all three and each is due a third. Remove one link and the player holding both of the others is due two thirds. Averaging over orders on the game the network allows is the one rule under which breaking any link costs the two players it joined exactly the same, and it pays go-betweens more than their links.

 Loops on a torus that never cross themselves. Squares with opposite edges glued, each carrying one straight loop of a different slope, each labelled with its two crossing counts. Topology

The loops on a torus that never cross themselves

Every loop on a torus is classified by two whole numbers: how often it goes round one way and how often the other. Some classes can be drawn without the loop ever crossing itself and some cannot, and the rule is the oldest in arithmetic — the two numbers must have no common factor. The same two numbers say how often any two loops must meet.

 A twist along the horizontal loop, done once. Squares with opposite edges glued and a shaded horizontal band, showing one loop before and after the torus is twisted along the band. Topology

A twist that carries one loop to another

Cut a torus along a loop, turn one side of the cut once round, and glue it back. Nothing is torn, so every loop that did not cross itself still does not — but a loop of class (0, 1) is now a loop of class (1, 1). Two such twists reach every loop that never crosses itself, by Euclid's algorithm, and the symmetries they generate are exactly the whole-number matrices of determinant one.

 The largest value on each plane, over every direction of space. A longitude–latitude map of directions u in three dimensions, each shaded by the largest value of xᵀAx on the plane perpendicular to u. The smallest such value is the middle eigenvalue 1.829, reached at ±v₁; the largest is 3.622, reached along a great circle. Algebra

The highest point on the sphere is an eigenvalue

For a symmetric matrix, walk a unit arrow over every direction and record the value of xᵀAx. The highest value reached is the largest eigenvalue, the lowest is the smallest, and every eigenvalue in between is a saddle height, a minimum of maxima. From that one description comes a theorem no formula for the roots could give: delete a row and its column, and every eigenvalue of what is left sits between two of the original's.

 A plucked string, released. A string plucked into a tent shape at 0.5, drawn at times 0, 0.1, 0.25, 0.5, 0.75, 1: the corner splits into two corners that run apart, reflect off the ends upside down and meet again. Analysis

A plucked string keeps its corners

Heat smooths a sharp profile at once, because each harmonic decays at a rate set by the square of its frequency. Change one time derivative into two and nothing decays at all: each harmonic swings for ever, the corner of a pluck splits in two and runs along the string, and after one period the shape comes back exactly. The same sines, the same coefficients — and a flow that loses nothing.

 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%. Applied

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.

 A majority of independent voters, more often right than any of them. The probability that a simple majority of n independent voters is right, for n from 1 to 201, when each voter is right with probability 0.45, 0.51, 0.55, 0.6, 0.7. Applied

A majority wiser than its members

Condorcet's other theorem turns voting round: the voters no longer have preferences but judgements about a single fact, each a little more likely right than wrong. Then a simple majority of many of them is almost certainly right — 6,763 voters who are each right 51% of the time make a majority right 95% of the time. The theorem survives voters worse than a coin, if the average is better. It does not survive voters who share their mistakes, and when their skills differ the right rule weighs votes rather than counting them.

 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. Computation

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.

 Two ways of counting that agree at every number. For n up to 40, the counts of partitions with gaps of at least two against partitions into parts congruent to 1 or 4 mod 5, on a logarithmic scale, equal at every n, with the second identity's counts beside them. Number

Two counts that agree for no visible reason

Write 10 as a sum of whole numbers that differ from each other by at least two, and there are six ways. Write 10 as a sum of numbers that each leave 1 or 4 on division by 5, and there are six ways. The same happens for 20 (thirty-one each), for 40 (three hundred and seventy-four each), for every number anyone has checked and every number there is. The two lists look nothing alike, and no one has found a simple way to turn one into the other.

 The trefoil and its mirror image. The trefoil beside its reflection, with writhe 3 and −3. The Jones polynomials are t + t³ − t⁴ and −t⁻⁴ + t⁻³ + t⁻¹; the Alexander polynomial of both is t − 1 + t⁻¹. Topology

A polynomial that tells left from right

The trefoil and its mirror image have the same colourings, the same determinant and the same Alexander polynomial, and the first proof that they differ was a hard argument about groups. Smooth every crossing both ways, count the circles in each of the resulting pictures, and add up the counts with the right weights: the total changes when the knot is reflected.

 The two extreme states of the figure-eight knot. The figure-eight knot, then the state with every crossing smoothed the A way (3 circles) and the state with every crossing smoothed the B way (3 circles). The bracket spans 16 powers of A against 16 for four times the crossings. Topology

The crossings an alternating knot cannot lose

Peter Guthrie Tait drew knots for years and believed, without proof, that a diagram whose crossings alternate over and under, and which has no twist that can be undone, is already drawn with the fewest crossings the knot allows. The proof took a century, and when it came it needed only the two most extreme ways of smoothing the diagram and Euler's count of the regions of a map.

 One lattice, 3 generating sets, 3 shapes of ball. Lattice points reached within a fixed number of steps in the integers squared, for one step along either axis, axis steps and one diagonal, a king's moves, each drawn inside the polygon spanned by its steps and scaled by the radius. Algebra

The polygon a lattice becomes from far away

Walk the grid of whole-number points with a fixed set of moves and the places reachable in r moves fill a shape. With axis steps it is a diamond, add a diagonal and it is a hexagon, move like a knight and it is a ragged thing full of holes — which, seen from far enough away, is an octagon exactly. The generators decide the polygon, and the polygon decides the count.

 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. Applied

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.

 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. Computation

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.

 The polynomial bound falls exponentially behind the space. A log-scale plot against the dimension of the number of points of the space, the polynomial method's bound on a cap, and the known largest caps: the bound's line is less steep than the space's and pulls away from it. Computation

The polynomial that bounds the caps

For forty years the best bound on a set of SET cards with no set among them shrank only like one over the dimension. In 2016 a two-page argument made it shrink exponentially, and the whole proof is a count of monomials: a table that is diagonal on a cap, one polynomial that describes it, and the fact that three parts of a degree cannot all be large.

 The cheapest way to send 4 units, for 25. A directed network from s to t with a capacity and a price on each road, showing the whole-number flow of 4 units with the least total cost, the arrows thickened by the amount they carry. Discrete

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.

 Three tilings by cells of one area, and the wall each needs. Panels of triangles, squares and hexagons, all with cells of the same area, labelled with the wall length each cell needs once shared walls are split between neighbours: the hexagons need the least. Geometry

The least wall for equal rooms

Divide the plane into rooms of equal area using as little wall as possible, and every wall does double duty. Bees settled on hexagons long ago, and the proof that nothing does better — not even rooms with curved walls — came in 1999. The straight-walled half of it is two facts: the rooms of any division average six sides, and more sides never cost more wall.

 One symmetrisation: every chord slid to the middle. A lopsided shape with a dent beside its Steiner symmetrisation about a horizontal line, with a few vertical chords marked in both: the chords keep their lengths and are centred on the line. Geometry

Every chord slid to the middle

Take a shape, pick a line, and slide every chord that crosses the line at right angles until the line cuts it in half. The area cannot change, the boundary can only get shorter, and the result is symmetric. Do it again about another line, and another, and the shape is squeezed towards a disc — unless the lines are badly chosen, in which case it stops short.

 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. Number

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.

 Signature against unknotting, for every knot to seven crossings. A table of the fourteen prime knots with up to seven crossings, listing determinant, signature, the lower bound on crossing changes it gives, the number of changes found by search, and whether the two agree. Topology

How many changes undo a knot

Cut the string at a crossing, pass it through the other strand and join it up again, and any knot can be undone by doing that often enough. The fewest changes needed is the unknotting number, and proving that fewer will not do needs a number that each change can move only a little. The signature moves by at most two per change — enough to settle thirteen of the fourteen knots up to seven crossings, and not the fourteenth.

 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. Number

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.

All themes