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 the anchor's first rung demonstrates on one example. 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. The anchor's first rung exhibits one such case, 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.

All themes