Matpic
mathematics, in pictures
Theme

Decided by exhaustion — page 4

Questions with finitely many cases, settled by going through all of them — and what changes when a claim about every argument becomes a count.
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. Dynamics

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.

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

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.

 Four outputs are enough to find the rule. A row of 12 outputs of a linear generator, with the first 4 marked as given and the rest as predicted. The multiplier and increment recovered from the given ones reproduce every later output exactly. Computation

Four numbers and the rule is yours

A linear generator can be solved. Given a few of its outputs, the multiplier and the increment fall out of two congruences, and every future output is then known exactly — which is a failure of a completely different kind from the lattice defect, and is not detected by any test of how evenly the points are spread.

 Every pattern, exactly as often. A table over 4 window lengths of a shift register's output stream: how many bit patterns are possible, how many actually occur, and the difference between the most and least frequent, which is one in every row. Computation

Nineteen thousand bits of state

The generator most simulations actually use is not clever. It is a linear recurrence over the two-element field with an enormous state, and its virtues are a proved period, a proved equidistribution and speed — none of which is unpredictability, which it does not have and does not claim.

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

The corners are whole assignments

A table of shares can be written as a lottery over whole assignments, which one worked example shows. 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.

 16 rules, and none that survives. A table of every systematic anonymous aggregation rule for 3 judges: one row per rule, showing the verdict it gives at each count of yes-votes, whether it decides every proposition, and whether it is consistent. No row has both. Applied

No rule escapes the doctrinal paradox

A court whose members each hold a consistent position can reach an inconsistent verdict by majority. One such case is easy to build, which invites the hope that a better rule would avoid it — and every rule that responds to the votes at all fails somewhere.

 A chain of 18 worlds, and the 3 the formulas can tell apart. A row of 18 circles for the worlds of the model, shaded by which of the 3 classes each falls into, above the quotient model's 3 worlds with the arrows the collapse gives them. Logic

How many worlds a formula can need

A modal formula can be true in a model with infinitely many worlds. It can also be true in a small one — and the small one is built from the large one by throwing away every distinction the formula was never able to make.

 Three properties that leave the middle, and one that cannot. Four measured curves of the share of random graphs having a property, plotted against the number of points: three first-order properties running to zero or one, and the parity of the edge count sitting on a half throughout. Logic

Nearly always, or nearly never

Toss a coin for every pair of points and ask whether the graph that results has some property. For a property a first-order sentence can state, the answer in the limit is never a genuine probability — it is zero or it is one, and the game is what proves it.

 What a sentence of depth 2 can reach. Two rings of points, of 14 and 19 points, each with a run of 9 consecutive points marked as the neighbourhood a sentence of depth 2 can inspect. Logic

The distance a sentence can see

A first-order sentence with three quantifiers cannot notice anything about a graph beyond a fixed distance from the points it names. That single limitation is why it cannot say connected, and why the failure survives every attempt to add more quantifiers.

 The primes below 100,000, by remainder mod 4. A bar for each remainder on division by 4, showing how many primes below 100000 leave it. The 2 classes sharing no factor with 4 hold near-equal counts; the rest are empty or hold one prime. Number

Infinitely many of one kind

Euclid's argument produces a prime nobody had listed, and says nothing about what it looks like. Ask for infinitely many primes ending in 3, or leaving a remainder of 1 on division by 4, and the same construction has to be aimed — and for most targets nobody knows how to aim it.

 Five families of primes, counted below 100,000. Five counting curves on logarithmic axes: every prime, the primes one more than a multiple of four, the twin pairs, the primes one more than a square, and the Mersenne primes. Two of the five families are known to be infinite and three are open questions. Number

Which infinitudes are proved

The primes never stop, and neither — apparently — do the twin pairs, the primes one more than a square, or the Mersenne primes. Three of those four statements are theorems and one is not, and counting the members of each family tells nobody which.

 The half of 24 permutations that commutators reach. A block of 24 squares, one per permutation, with the 12 generated by commutators shaded, beside bars counting the homomorphisms to each cyclic group. Algebra

The only bit that survives

A shuffle can be called even or odd, and the label behaves under composition. Ask whether some cleverer label — a number out of three, or out of four — could behave the same way, and the answer is that nothing else can — one bit is exactly what a permutation gives up.

 A 2×3 sliding puzzle: 360 arrangements of 720 can be reached. Two arrangements of a small sliding puzzle side by side, the solved one and the one with two tiles exchanged, with the count of positions reachable by sliding found by walking every move. Algebra

The puzzle that is exactly half solvable

A sliding puzzle sold with two tiles swapped is not a hard puzzle; it is an impossible one, and the proof is a quantity that no slide can change. The same argument, run three times at once, says that one arrangement of a scrambled cube in twelve is reachable.

 The character table of the permutations of 4 places, computed from traces. A table with one row per irreducible representation and one column per conjugacy class, giving the trace of the matrix each representation assigns, with the dimension column marked. Algebra

When the label may be a matrix

A permutation carries exactly one bit into any commutative target, and commutativity is the restriction doing all the work. Drop it — let the label be a matrix — and what survives is a short finite table, computed here from traces and checked for orthogonality over every pair of rows.

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

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.

 Five rules, and the one condition each of them gives up. A table with one row per aggregation rule and one column per condition, marking which conditions each rule satisfies when run over every profile of the agenda. Applied

Four ways out, and what each costs

An impossibility theorem lists conditions and says no rule has them all. That leaves exactly as many escapes as there are conditions, each of them a real institution — a dictator, a two-stage procedure, a supermajority, a restricted agenda — and each escape's price can be counted rather than argued about.

 The largest code at each length, distance 3, against four bounds. A table with one row per word length, giving the exact size of the largest code of that length at the stated minimum distance and the values of the Singleton, Hamming, Plotkin and Gilbert-Varshamov bounds. Computation

The best a code can be

A code is a set of words chosen far apart, and every construction answers "here is one" rather than "here is the best". The best can be computed at small lengths, and putting four classical bounds beside the exact answer shows which of them is doing the work and where none of them is.

 How many codewords lie within each radius, for a [7,3] code over 11 symbols. A bar for each decoding radius, its height the largest number of codewords found inside a ball of that radius around a randomly drawn received word, with the unique-decoding radius and the Johnson radius marked. Computation

Past half the distance

A code of minimum distance five corrects two errors, and every account stops there. Two is the largest number for which the answer is unique — and a decoder that returns a short list instead of one answer reaches considerably further, which can be measured by counting the codewords in a ball.

 The sixteen lattice polygons with a single point inside. A grid of sixteen small lattice polygons, each drawn on its own patch of grid with the single interior point marked, labelled with its number of boundary points. Discrete

Sixteen polygons with one dot inside

Fix one of Pick's two counts at one and ask what is left. The answer is a finite list, the list has exactly sixteen entries, each one is its own kind of object with a dual that is another entry, and the whole classification is a search a page can carry out.

 The only fractions that could be a cycle's shape. A table of the convergents of the base-two logarithm of three, with the approximation error, the exact value of two to the n less three to the k, and that value as a fraction of three to the k. Dynamics

How short a cycle could be

The drift argument cannot see cycles at all, which is why it is not a proof. What can see them is arithmetic — a cycle's shape has to be a fraction that approximates the logarithm of three to base two extraordinarily well, and there are very few such fractions.

 Every parity pattern of length up to 12, and each occurring exactly once. A bar for each pattern length, showing the number of distinct parity patterns produced by all remainders of that power of two, which equals the number of remainders at every length. Dynamics

Every pattern happens exactly once

Choose any sequence of odds and evens and there is exactly one residue class whose orbit follows it, and exactly one fraction that cycles through it forever. The Collatz conjecture is then the statement that only one of those infinitely many cycles is made of whole numbers.

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

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.

 A 6-cycle and two 3-cycles: refinement cannot tell them apart. Two graphs side by side — one cycle and two smaller cycles — with the same number of points, the same number of edges and every point of the same degree. Logic

The game the algorithm was playing

Change what Duplicator has to offer — a whole bijection instead of one element — and the game stops measuring first-order logic and starts measuring colour refinement, the algorithm every practical graph-isomorphism test begins with. Two subjects that grew apart are one game with the moves relabelled.

 Two sums of reciprocals: 2.89 and climbing against 1.71 and level. Two curves against the logarithm of the bound: the sum of reciprocals of all primes, rising steadily, and the sum over the twin primes, flattening towards a limit. Number

The sieve that cannot finish

Sifting out the composites is the oldest method in the subject and it has a ceiling nobody has raised. The reciprocals of the twin primes add to a finite number, so no argument that measures thickness can reach them — and the inclusion–exclusion every sieve truncates goes wildly wrong before it goes right.

All themes