Matpic
mathematics, in pictures
Theme

Decided by exhaustion — page 3

Questions with finitely many cases, settled by going through all of them — and what changes when a claim about every argument becomes a count.
A sphere over a projective plane, cell by cell. An icosahedron with opposite faces drawn in matching colours, beside the count of cells it has and the count the quotient by the antipodal map has — every number halved, including the Euler characteristic. Topology

Two sheets over a one-sided surface

Above every one-sided surface sits a two-sided one, exactly twice as large, and the map between them forgets which of the two senses of turning a point was carrying. Building it turns a question about sides into a question about covers.

 Every candidate for a rational square root, tried. A column for each of 2, 3, 4, 5, 6, 7, 8, 9, listing the whole numbers that divide it with their squares, and the verdict the search returns. Number

Which roots refuse to be fractions

The square root of two is not a fraction, and neither is the square root of three, five, six or seven. The rule behind the list turns an infinite question into a search over the divisors of a single number — and the search finishes.

 The tent map and the logistic map, joined by a change of coordinate. Two cobweb diagrams side by side — the tent map at slope two and the logistic map at four — with the orbit of one carried to the orbit of the other by a curve drawn between them. Dynamics

The same map in different coordinates

The tent map and the logistic map at four look nothing alike and are the same map, carried onto each other by a change of variable. Everything either one does the other does, and the change of variable is a sine squared.

 Drop one condition, and something else satisfies the rest. A column for each of the four conditions, holding a sharing rule that breaks that one and keeps the other three, with the split each rule gives on a stated four-player game. Applied

None of the four conditions is spare

Four conditions pick out one sharing rule. The half that is usually shown is that they are enough; the other half is that each is needed — drop any one and a different rule satisfies the rest, so the list cannot be shortened.

 Every order of arrival for three users of one shared capacity, and what each player adds. A table with one row per order in which the players could arrive, giving what each adds to the group already present, and the average of each column as that player's share. Applied

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.

 The 3 mutually orthogonal squares of order 4. Every Latin square built from the field of order 4 as a·i + j, one for each non-zero multiplier, with every pair checked orthogonal. Computation

A field's worth of squares

Two orthogonal squares of order five are easy to stumble on. Four of them, every pair orthogonal, is not a stumble — it is one line of arithmetic over a field, and the field supplies as many as the order allows.

 The affine plane of order 3, one parallel class at a time. The n² cells of a complete set of orthogonal Latin squares of order 3, with the rows, the columns and each square's symbol classes drawn as lines of a plane. Computation

The plane hiding in the squares

A complete family of orthogonal squares is not a collection of squares that happen to agree nowhere. It is a geometry — a plane with n² points in which every two points lie on exactly one line — and reading it that way is how the impossible orders were found.

 How many Latin squares there are, orders 1 to 8. The number of Latin squares of each small order, the ones up to six counted by exhaustive search and the larger ones quoted, on a logarithmic scale. Computation

Nine thousand four hundred and eight

There are four Latin squares of order four once the first row and column are fixed, fifty-six of order five, and nine thousand four hundred and eight of order six. The exact answer is known for eleven orders and for no more — and yet a half-finished square can always be finished.

 The 576 squares of order 4, sorted by whether they associate. Every Latin square of order 4, counted by whether it associates and by which group it is when it does. Computation

Sixteen of five hundred and seventy-six

A Latin square is a multiplication table in which every equation has exactly one solution. Ask it to be associative as well and almost every square drops out — sixteen of the five hundred and seventy-six of order four survive, and they are the two groups.

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

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.

 A path of 4 bounces that closes, in a triangle of 100°, 40°, 40°. A triangular billiard table with a periodic path found by an exhaustive sweep of starting positions and directions. Dynamics

The triangle nobody can settle

Does every triangular billiard table have a path that closes on itself? Acute triangles do, right triangles do, triangles with rational angles do — and for the rest the question has been open since it was asked.

 A four-by-four array holding every two-by-two block. A binary array, cyclic in both directions, drawn with its wrapped row and column, in which each of the sixteen two-by-two blocks appears exactly once. Computation

A page that knows where it is

A four-by-four array of bits, cyclic in both directions, in which every two-by-two block appears exactly once. Print it repeatedly across a sheet and any four marks on that sheet are an address.

 A cycle showing every pair from 5 things exactly once. The complete graph on 5 points with an Eulerian circuit drawn, and the cyclic sequence of symbols it spells; every window of two consecutive symbols is a different pair. Computation

A cycle for every pair

A cyclic sequence in which every window of two consecutive symbols is a different pair of things. For five things it exists and for four it does not, and in both cases there are exactly as many pairs as there are places to put them.

 Two out of three, and never all three. A table of the five apportionment methods against three properties, each cell decided by a search over generated instances; no method has all three. Applied

Two out of three, and never all three

Stay inside every region's quota, never take a seat away when the house grows, never take one from a region that grew faster. Each pair is achievable. All three together are not, and the proof is that no rule anywhere manages it.

 What each rule is answering. A table of five apportionments against three measures of inequality between two regions, with a tick where no transfer of a seat reduces the measure; each measure certifies exactly one of the five. Applied

Choosing what unfair means

Ask whether moving one seat between two regions would make them more equal, and the answer depends on what "equal" is measured in. Three measures, three different answers, and each of the classical methods is the one no transfer can improve for exactly one of them.

 Eight circles touching three. Three given circles and the eight circles tangent to all of them, each labelled by which of the three it contains and which it lies outside. Geometry

Eight circles touching three

Draw three circles. How many circles touch all three? The answer is eight, the count is a fact about signs rather than about geometry, and the classical way to find them is to move the problem somewhere it becomes easy.

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

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.

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

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.

 Where a congruence decides which primes a form represents, and where it does not. Rows of primes marked by whether each is represented by x squared plus n y squared, with the residue classes that decide it where such classes exist. Number

Which primes a form takes

A prime is the sum of two squares exactly when it is 1 modulo 4. Change the form slightly, to x² + 27y², and no congruence on p decides it at all — which is where the elementary subject ends and its successor begins.

 Two indicators, and the upper sum that will not come down. A partition of the unit interval drawn against the middle-thirds set and against a set of positive length, above a chart of each one's upper sum as the partition is refined. Analysis

Which functions can be added up

Riemann's integral works when the upper and lower sums close on each other. The exact condition for that, found once measure existed to state it in, is that the points where the function jumps have measure zero — which some nowhere dense sets fail.

 Two models the modal language cannot separate, and two it can. Four Kripke models in two pairs: the upper pair joined by a bisimulation and agreeing on every formula, the lower pair separated by a formula found by search. Logic

Two diagrams the language cannot tell apart

A modal formula sees a diagram of worlds and arrows through a very narrow window. Exactly how narrow is settled by a game: where one player can answer every move, no formula whatever separates the two starting worlds, however different the diagrams look.

 A model whose worlds are sets of sentences. Worlds labelled by which of a fixed finite set of formulas they accept, with an arrow wherever every boxed formula accepted by one has its inside accepted by the other. Logic

Worlds built out of sentences

A Kripke model needs worlds, and nothing so far has said where worlds come from. They can be made of the syntax: a world is a set of formulas it commits to, one world sees another when the boxed commitments line up, and in the model that results every formula is true exactly where it was assumed.

 Axioms, the conditions on the arrows they answer to, and the one that answers to none. A table of modal axioms with the property of the accessibility relation each corresponds to, every row decided by sweeping all relations on up to four worlds. Logic

The axiom with no property of the arrows

The first rung matched each axiom to a condition on the arrows by hand. There is a recipe that does it for a whole class of axioms, and there is an axiom the recipe cannot reach — not because nobody has looked, but because no condition on the arrows defines it at all.

 The frames on which provability makes sense, and the two that are refused. Six small frames marked by whether Löb's axiom is valid on them: transitive frames with no cycles accept it, and any frame in which a world can reach itself does not. Logic

Necessity that means provable

Read the box as "the theory proves" and one modal logic stops being a proposal about what necessity might mean. It becomes a complete description of what a formal system can prove about its own proofs — and its frames run forward, compose, and stop.

All themes