Matpic
mathematics, in pictures
Concept

Counting two ways

Counting one collection by two different routes and reading off the identity that the two answers are forced to agree on. It is the standard route to a combinatorial identity, and the identity is forced rather than verified term by term.

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

Odd numbers as square shells. Nested L-shaped shells of 1, 3, 5 … 11 cells stack into a 6 by 6 square.

Every square is a stack of odd numbers

Add up the odd numbers in order and the running totals are 1, 4, 9, 16, 25. This is not a coincidence, and the reason fits in a single picture.

geometry · Figurate numbers The sieve of Eratosthenes below 100. A grid of the whole numbers with the composites struck out by the prime that removes them.

The primes are what is left over

Eratosthenes' sieve does not find the primes. It removes everything else, one prime at a time, and whatever survives is prime by default — which is a strange way to reach the most studied objects in arithmetic.

number · Prime distribution The Stern–Brocot tree to depth 4. Every positive rational, each appearing exactly once, generated by taking mediants.

Every fraction, exactly once

Take two fractions, add the tops and add the bottoms. That is not how fractions are added, it is not an average, and repeating it produces every positive rational exactly once, already in lowest terms.

number · Stern brocot Two factor trees of 360. The same number split two different ways, both ending in the same primes.

One way to factor, and no other

Every number breaks into primes in exactly one way. That is so familiar it is hard to see as a claim at all — until it is put beside an arithmetic where it is false, and where six has two different factorisations that cannot be reconciled.

number · Unique factorisation The divisors of 60. Every divisor as a lattice point, one axis per prime, joined when one divides the other by a single prime.

The shape of a number's divisors

Lay a number's divisors out as a lattice with one axis per prime, and two of the most useful facts in arithmetic stop being formulas and become the width and the corner of a rectangle.

number · Unique factorisation 28 is perfect, because its divisors form this rectangle. Two rows of divisors: the powers of two, and the same powers multiplied by the Mersenne prime.

Numbers that are their own parts

Six is one plus two plus three. Twenty-eight is one plus two plus four plus seven plus fourteen. Euclid explained where such numbers come from; Euler proved there are no others of that kind; and whether an odd one exists has been open for two thousand years.

number · Perfect numbers The circle of radius √25 on the integer lattice. A circle drawn on the whole-number grid, with the lattice points it passes through marked.

Two squares, and a lattice

Whether a prime is the sum of two squares is decided entirely by its remainder on division by four. A fact about circles is settled by a fact about remainders, and neither statement contains any hint of the other.

number · Sums of two squares Necklaces of 5 beads in 2 colours. Every string of beads, grouped by the rotations that carry one onto another.

Necklaces that prove a theorem

Thread five beads in two colours, thirty-two ways. Two of them are all one colour; the other thirty fall into rings of five. That count, and nothing else, is Fermat's little theorem.

number · Fermats little theorem One number, two dials: 3 and 5. A grid of remainder pairs, each cell holding the smallest number that leaves those two remainders.

Two dials at once

Watch one number on two clocks with different faces. If the faces share no factor, every pair of readings occurs exactly once — so two remainders name a number, and a hard calculation can be split into two easy ones.

number · Modular arithmetic Counting a 5 by 3 rectangle two ways. Lattice points in a rectangle cut by a diagonal of slope q over p, coloured by which side they fall.

Counting one rectangle, twice

Whether seven is a square modulo eleven, and whether eleven is a square modulo seven, are two unrelated-looking questions. Their answers are linked, and the link is a rectangle of dots counted along its rows and then along its columns.

number · Quadratic reciprocity Two squares of side 12 inside one of side 17. Two overlapping squares laid into opposite corners of a larger one, with the overlap and the two uncovered corners marked.

The square that cannot shrink

The usual proof that the square root of two is irrational is about even and odd numbers. There is a proof about squares instead, in which a supposed solution is folded into a smaller one — and the folding is a drawing.

number · Irrationality The partition 5 + 4 + 2 + 1 and its conjugate. A row of dots for each part, and the same dots read down the columns instead.

A diagram turned on its side

Write a partition as rows of dots, then read the columns instead. Every theorem in this essay is that one move, and the move proves things that no formula suggests.

number · Partitions 16 colourings in 6 classes. Every way of colouring the corners, with the ones a motion carries to each other placed on the same row; the number of rows is the number of genuinely different colourings.

Colourings nobody can tell apart

Sixteen ways to colour four corners in two colours, and only six of them are genuinely different. The count can be got by pooling the sixteen — or by never forming a single class and instead averaging how many colourings each motion leaves untouched.

algebra · Symmetry groups All 24 arrangements of 4 objects, and the 9 that move every one. Every permutation of 4 objects drawn as a grid of cells, with the diagonal — where an object stays where it began — shaded, and the arrangements that avoid it entirely marked.

Nobody gets their own hat

Hand back a pile of hats at random and ask for the chance that not one person gets their own. The answer barely moves as the crowd grows — it is a third and a bit at four people, and a third and a bit at four thousand.

probability · Inclusion exclusion A product of 3 polynomials, and what its coefficients count. The coefficients of a product of small polynomials, with the combinations of choices that reach one marked total written out beneath it.

A polynomial that counts

Hang a counting sequence on the powers of a variable and the two ways of combining choices — this and that, this or that — become multiplication and addition, so a recursion turns into an equation and the equation can be solved.

discrete · Generating functions A determinant counting the 16 spanning trees. A small graph, the minor of its Laplacian, and every one of its spanning trees drawn as thumbnails.

A determinant that counts trees

Write down a graph's Laplacian, strike out one row and its column, take the determinant. The answer is the number of spanning trees — and the minus signs in the determinant are what cancel every subset of edges that is not one.

algebra · Determinant The partition product's coefficients to q¹². A row of series coefficients computed by expanding a product, beside the same numbers obtained another way.

Every partition, hidden in a product

Multiply out one factor for each part size and the coefficient of q to the n is the number of partitions of n. Nothing is being approximated: the product is a bookkeeping device that does the counting by multiplying.

number · Partitions The product of (1 − qᵏ), and what survives at 12. The coefficients of the pentagonal product drawn as signed bars, with the partitions into distinct parts that Franklin's move leaves unpaired.

The terms that cancel almost everything

Multiply out the product of 1 − q, 1 − q², 1 − q³ and so on, and nearly every coefficient is zero. What survives is a single plus or minus one at 1, 2, 5, 7, 12, 15 — and the reason is a way of pairing partitions off so that each pair cancels.

number · Partitions Everybody's share of the 24 chains. The subsets of a set of 4, each labelled with the fraction of maximal chains it lies on; the shares of any antichain add to at most one, and to exactly one only for a whole layer.

Everybody's share of the chains

There are twenty-four ways to build a four-element set one element at a time. Every subset lies on some of them, and no two incomparable subsets share one — so an antichain is a set of disjoint shares of a single whole.

discrete · Posets At most 3 of the 7 arcs can pairwise meet. The 7 elements arranged round a circle with the 7 arcs of 3 consecutive drawn, and the largest collection of arcs that pairwise intersect picked out.

The largest family that always meets

Change the question from "no two comparable" to "every two share an element" and the answer changes shape. The best antichain is a whole layer; the best intersecting family is a star, and the proof is a circle.

discrete · Posets The two supplements, and the residue classes that decide them. A table of odd primes with the Legendre symbols of minus one and two beside the residue of p modulo four and modulo eight.

The two supplements, and where the eight comes from

The main law relates two odd primes to each other and says nothing about −1 or about 2. Those two are settled separately, by their own counts, and the answers arrive modulo four and modulo eight — which is a clue about where the whole subject is really taking place.

number · Quadratic reciprocity Multiplication by 3 modulo 11, and the sign of the shuffle. Residues in two rows joined by strings showing where multiplication sends each one, with a strip beneath comparing the sign of the shuffle to the Legendre symbol for every multiplier.

The symbol is the sign of a shuffle

Multiplying every residue modulo p by a fixed number rearranges them. That rearrangement is a permutation, permutations have a sign, and the sign is exactly the Legendre symbol — so a question about squares becomes a question about crossings.

number · Quadratic reciprocity A bad path, and the path it reflects to. Two grids, 6 by 5. On the left a monotone path that dips below the diagonal, with its first offending step marked; on the right the same path with everything after that step reflected, which ends one square right and one square below the corner.

Counting the paths that go wrong

The number of good paths across a grid has no obvious formula. The number of bad ones does, because every bad path can be reflected into a path to a different corner, and that reflection is a perfect matching between two sets nobody chose to relate.

discrete · Catalan numbers One word, four objects. The balanced word (()())() drawn as a lattice path, as nested brackets, as a triangulation of a 6-gon and as a binary tree. The four are the same object in four notations, and each is built here from the word itself.

One word, and four objects

A balanced string of brackets, a lattice path, a triangulated polygon and a binary tree are four different-looking things counted by the same numbers. They are not four things that happen to agree — each is a way of writing the others down, and the translation is mechanical.

discrete · Catalan numbers Four solids with the same counts and every volume. The Reeve tetrahedra at heights 1, 2, 3, 5, drawn in wireframe with a table of their lattice-point counts and volumes. All have four boundary points and none inside; their volumes run from 0.17 to 0.83.

The theorem that has no version in space

A lattice polygon's area is decided completely by two counts of dots. The obvious guess is that a lattice solid's volume is decided by the same two counts in three dimensions, and there is a family of tetrahedra with identical counts and every volume that says otherwise.

discrete · Pick theorem The share that provably comes down. The proportion of starting values that fall below their own start within k steps, plotted against k up to 12. The proportion rises towards one; at the largest k drawn it is 0.94.

Almost every number comes down

The Collatz conjecture is open and a great deal about it is not. Whether a number falls below its own start in the first few steps is decided entirely by its remainder on division by a power of two, and the share of numbers for which it happens can be counted exactly.

dynamics · Collatz The same modulus, four multipliers, four qualities. 4 linear generators at modulus 1021, drawn as scatters of consecutive pairs and ranked by the spacing of the lines their points fall on. The spacings differ by more than a factor of two.

The test that ranks the generators

Every linear generator's output lies on a family of parallel planes. Which generator is better is decided by how far apart those planes are, and that distance is the length of the shortest whole-number vector the modulus annihilates — a quantity that can be computed exactly rather than estimated by testing.

computation · Pseudorandomness A triangle appears when the count says it should. The measured probability of containing a triangle against the edge chance, on graphs of 200 points, beside the expected number of triangles capped at one.

Finding a threshold with two moments

Every monotone property of a random graph has a threshold, and locating one is nearly always the same two calculations — count what the property needs, and check the count does not concentrate on rare cases. The triangle is where the method is cleanest.

probability · Random graphs A run down a diagonal, and the entry it adds to. 9 rows of Pascal's triangle with 5 entries shaded and the entry they add to marked. The claim is checked by adding the shaded entries: 1 + 3 + 6 + 10 + 15 = 35.

The run that lands one place along

Add up a run of entries down one of Pascal's diagonals and the total is another entry of the triangle — one row further down and one place along. The same triangle holds four more sums of that kind, and each is a different question answered by the same additive rule.

discrete · Pascals triangle 35 routes across a 4 by 3 grid. A grid with each cell holding the number of monotone routes reaching it. The far corner holds 35, which is the binomial coefficient of 7 choose 3.

Every entry counts the routes to it

Turn Pascal's triangle forty-five degrees and it becomes a grid of street corners, with each entry counting the ways of walking there. Identities between the entries then become statements about routes, and the statements are proved by cutting the routes in one place.

discrete · Pascals triangle Every positive rational, in one sequence. The first 32 terms of Stern's diatomic sequence as bars, with the ratios of consecutive terms beneath. Every ratio is in lowest terms, no two agree, and each term counts the hyperbinary representations of its index.

Every rational in one sequence

The tree lists every positive fraction once and needs a tree to do it. One recursion on the whole numbers lists them in a single row — and each term of it counts something nobody was asking about, which is why the enumeration works.

number · Stern brocot

Named alongside it

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

BijectionModular arithmeticPrimesRecursionBinomial coefficientLatticeCounting argumentParityAlgebraic identityCyclic groupGenerating functionLattice paths

All concepts