Matpic
mathematics, in pictures
Concept

Hypercube

The shape whose corners are all the ways of choosing true or false for each of several variables, with edges between corners differing in one. Its edges join words differing in one place, so a path along them is a sequence of single changes and its diameter is the word length.

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

(p ∨ q) ∧ ¬r, drawn on the cube of 8 assignments. The assignments as corners of a cube, joined when they differ in one variable, with the satisfying corners filled.

A formula is a corner of a cube

A formula about three letters is a set of eight rows. Written as a table that is a list; drawn on a cube it is a shape — and the shape is what almost every later question in this field turns out to be about.

logic · Truth functions ((p ∧ q) ∨ (r ∧ s)) ∨ (¬p ∧ ¬r), covered by 3 rectangles. A grid of the assignments arranged so that neighbouring squares differ in one variable.

The map that puts neighbours side by side

Reorder the rows of a truth table so that neighbouring squares differ in one letter, and finding a short formula stops being algebra and becomes the problem of covering a shape with rectangles.

logic · Truth functions A code on the 3-cube, and the balls around its words. The corners of a hypercube with the chosen codewords marked and the words within one error of each shaded.

Distance is a picture

A message is a corner of a cube and an error is a step along an edge. Everything a code can do is decided by how far apart the corners it uses are — and that is a fact about a drawing.

computation · Error-correcting codes A closed walk on the 3-cube changing one place at a time. The corners of a 3-dimensional cube with a path through every one of them exactly once, each step moving along an edge, and the last corner one step from the first.

A walk that changes one thing at a time

Counting from nothing to fifteen in binary changes four digits at once somewhere in the middle. There is another order through the same sixteen words in which every step changes exactly one — and it is a closed walk on a four-dimensional cube.

discrete · Hamiltonian cycles The diagonal of a box, by using the theorem twice. A box 12 by 4 by 3 with the diagonal of its floor drawn, and the diagonal of the box standing on it; the two right triangles share a side and give the sum of three squares.

Two right angles and the diagonal of a box

The theorem applied once gives the diagonal of a floor. Applied again, standing on the first result, it gives the diagonal of the room — and the pattern does not stop at three, which is where a fact about triangles quietly becomes the definition of distance.

geometry · Pythagoras 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 The 1,344 tours of the 4-cube, by how often each place changes. A bar for each pattern of change counts among all closed walks through the 4-cube, with the number of tours having it; the reflected code's pattern and the perfectly even one are marked.

Every place changes back

A closed walk through every corner of a cube changes one place at each step, and each place, having changed, must change back before the walk returns home. So every place changes an even number of times — which is why no walk on three places can share the work evenly, why perfect sharing is possible only when the number of places is a power of two, and what sorts the 1,344 walks on the 4-cube into exactly four kinds.

discrete · Hamiltonian cycles A cycle through the middle two levels of the 5-cube: 20 words. The words of length 5 with 2 or 3 ones placed round a ring in the order of a Hamiltonian cycle, alternating between the two levels, each step changing a single place.

The walk through the middle levels

On seven places, the words with three ones and the words with four number thirty-five each. Is there a closed walk through all seventy, changing one place at a time and never leaving those two levels? On five places the answer is 24 walks, on seven and nine a search finds one in moments — and whether one exists for every odd length was open for thirty years, until Torsten Mütze proved in 2016 that it always does.

discrete · Hamiltonian cycles 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 The six regular 4-polytopes, and an alternating sum of 0. A table of the six regular polytopes in four dimensions with their numbers of vertices, edges, faces and cells and the alternating sum, which is zero for each.

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.

topology · Euler characteristic Eight corners of a squashed cube, visited in order by the simplex method. Klee and Minty's program in 3 variables drawn as its own deformed cube and as a plain one. The simplex method with the largest-price rule visits all 8 corners, with objective values 0, 4, 6, 10, 15, 19, 21, 25; the optimum is one edge from the start.

The cube that takes every corner

The simplex method is fast on every program anybody meets in practice. In 1972 Victor Klee and George Minty squashed a cube so that the method, choosing the steepest edge each time, visits all of its corners — 2ⁿ − 1 moves in n variables, with the optimum one edge from the start.

applied · Duality How far a deck of 52 is from random after each riffle shuffle. A bar chart over one to 12 riffle shuffles of the exact total variation distance from a uniformly random deck. The bars stay near one for the first few shuffles and drop sharply around 8.

The forgetting that happens all at once

A single small chain forgets its start gradually, a little more with every step. A family of large ones can do something different — stay almost perfectly informed about where it began, and then lose all of it inside a window far shorter than the wait. That cliff is the cutoff phenomenon, and it is why "seven shuffles" is an answer rather than a convention.

probability · Markov chains

Named alongside it

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

ParityGray codeHamming distanceCounting argumentExhaustive searchBinaryBoolean functionDimensionExclusive-orKarnaugh mapMajority ruleNormal form

All concepts