Theme

What a system cannot say — page 3

Rules asked a question about themselves, and an answer that is provably not available from inside — which is a different kind of limit from not knowing yet.

Hippias's quadratrix, traced by two uniform motions. A unit square with a quarter circle, several positions of a turning radius and a falling horizontal line, their crossings, and the curve through them ending on the base at 2/π.

Computation

A curve that divides any angle

Let a radius turn at a steady rate while a horizontal line falls at a steady rate, both finishing together, and mark where they cross. The curve they trace turns heights into angles, so dividing a height — which a ruler and compass can always do — divides the angle in the same ratio. The same curve meets its base at 2/π of the side, a length from which a square with the area of a circle follows. It reaches what no marked ruler or conic can, and the ancient objection to it is exact.

A rectangle of the parity table, nearly balanced. A 32 by 32 grid of +1 and −1 entries — the parity of the inner product of row and column — with a 15 by 14 rectangle of chosen rows and columns highlighted; its entries sum to 8.

Computation

Two weak sources make one fair bit

No fixed rule can turn every weakly random source into fair bits: for any rule, some source with almost full unpredictability makes it constant. Two independent sources are different. Multiply their bits in pairs, add, and keep the parity — and if the two together carry more unpredictability than the length of one, the result is nearly fair, whatever else the sources do. The reason is that the table of those parities is balanced on every large rectangle.

$PRIMEGAME: fourteen fractions whose powers of two are the primes. The size in binary digits of the numbers produced by Conway's PRIMEGAME from 2 over 40000 steps, with the pure powers of two marked; their exponents are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.$ Dynamics

Fourteen fractions that list the primes

Change the Collatz rule so that the multiplier depends on the remainder modulo some other number than two, and the resulting maps can compute anything a computer can. John Conway proved it in 1972, which means no method can decide, for every such map, whether its orbits come down — and fourteen fractions, applied in order, turn out to be enough to print every prime.

A program whose output is its own text. The 32-character program (f=>f(f))(f=>"(f=>f(f))("+f+")") beside its output, which is identical.

Logic

The program that prints itself

The diagonal argument has always been used to destroy — to show that a list misses something, that a sentence cannot be proved. Run the same move the other way and it builds. Kleene's recursion theorem says every program can be given its own text to work with, and the proof is a program that prints itself, thirty-two characters long, which can be run and checked.

Logic

No algorithm can read what a program does

Whether a program halts cannot be decided by any algorithm. Henry Rice showed in 1953 that the halting problem is not special: no algorithm can decide any property of what a program does — whether it ever prints a 7, whether it computes the successor function, whether it is a virus — except the two properties that hold of every program or of none. Every one of the 20,736 smallest Turing machines can be checked by hand; the theorem says why that stops.

A straightedge construction on a circle, and the same construction moved by a map that keeps the circle. Two copies of one straightedge construction on a circle — six points, five chords and their crossings — the second the image of the first under a projective map fixing the circle. Chords and crossings correspond exactly, but the centre (orange) is carried to (0.551, 0.000).

Computation

The centre a straightedge cannot find

Give a straightedge one circle and its centre, and it can do everything a compass can. Take the centre away and it cannot even find it again — because to a straightedge a circle has no centre. The maps that keep a circle and its straight lines are the motions of the hyperbolic plane, and in that plane the centre is a point like any other.

The spiral of Theodorus, √2 to √17, built from square corners and a unit length. 16 right triangles with legs √k and 1 arranged in a spiral around a common corner; their long sides have lengths √2 to √17, and together they turn through 351.2 degrees.

Computation

The lengths dividers cannot reach

A pair of dividers carries a length from one place to another and draws nothing. With a straightedge it finds midpoints, parallels and right angles, and it draws the regular 17-gon. It cannot draw a segment of length √(1 + √2) — and the reason is not on the page at all, but in the other root of the equation that number solves.

A quadrilateral the Hénon map carries strictly inside itself. Hénon's trapping quadrilateral with corners (-1.33, 0.42), (1.32, 0.133), (1.245, -0.14), (-1.06, -0.5), the image of its boundary under the Hénon map lying strictly inside it, and an orbit on the attractor.

Dynamics

A region the orbit cannot leave

That the Hénon map and the Lorenz flow have attractors takes two lines of arithmetic each — a region mapped strictly inside itself, a quantity that falls outside an ellipsoid. That the attractors are strange took a computer and twenty years for Lorenz, and for Hénon's classical parameters it has never been done. The difference between the two questions is the difference between a region and what lives in it.

$The rationals and the dyadic fractions, matched 12 times without a crossing. Two number lines from 0 to 1, rationals above and dyadic fractions below, with 12 back-and-forth matchings: 1/2↔1/2, 1/3↔1/4, 2/3↔3/4, 1/4↔1/8, 3/4↔7/8, 2/5↔3/8, 1/5↔1/16, 3/5↔5/8, 4/5↔15/16, 2/7↔3/16, 1/6↔1/32, 3/8↔5/16.$ Logic

Two lists that are one order

The rationals and the fractions with a power of two below are different sets of numbers, and as orders they are exactly the same — any two countable orders that are dense and have no ends can be matched, point for point, keeping every comparison. The proof is a zigzag, and it settles every question the language of order can ask.

A loop that is a hole, and the same loop filled in. a hollow triangle: 3 points, 3 edges, 0 triangles; holes in each dimension 1, 1, 0; a filled triangle: 3 points, 3 edges, 1 triangles; holes in each dimension 1, 0, 0.

Algebra

A hole is a cycle that bounds nothing

A hollow triangle and a filled one have the same three edges and the same loop round them. In one the loop is the edge of something and in the other it is not, and that difference — a cycle that is not a boundary — is what a hole is. Counting holes is rank and nullity applied twice, and the Euler characteristic is what is left when the two applications cancel.

The plane of order 3 as a table, and the table times its transpose. The 13 × 13 incidence table of the projective plane of order 3 and its product with its transpose, which has 4 on the diagonal and 1 in every other cell.

Computation

The orders a plane cannot have

Every counting condition allows a projective plane of order six, and there is none. The proof that rules it out looks at one matrix identity — each point on seven lines, each two points on one — and turns it, by way of Lagrange's four squares, into the statement that six would have to be a sum of two squares. Run on the planes that do exist, the same argument hands back their orders as sums of two squares; run on six, it asks for something no arithmetic can supply.

$Three sizes of infinity, and the collections that have each. ℵ₀: the fractions, the algebraic numbers, every finite text, every definition of a number; 2^ℵ₀: the real numbers, the continuous functions, the open sets, the closed sets, the Borel sets; 2^(2^ℵ₀): all functions, all sets of reals, the non-Borel sets, the measurable sets.$ Logic

What counting can prove exists

There are only as many continuous functions as points of a line, only as many Borel sets, only countably many definitions — and more sets of reals than any of those. So counting proves that discontinuous functions, non-Borel sets and undefinable numbers exist without exhibiting one. It cannot prove that a set with no length exists, because the sets that have a length are exactly as numerous as all sets, and that difference turns out to be the difference between what the axioms force and what they merely allow.

A countable closed set stripped of its isolated points, 3 times. Cantor–Bendixson derivatives of the set of sums of up to 2 reciprocals: sizes 750, 40, 1, 0 in the truncation, ending empty.

Logic

Closed sets obey the continuum hypothesis

Whether some set of reals is bigger than the whole numbers and smaller than the line is a question the axioms cannot answer. For closed sets it has an answer, found in 1883: strip away the isolated points, again and again, and what is left is either nothing or a perfect set, which is as large as the line — so every closed set is countable or of the line's size. The same answer holds for Borel and analytic sets, and fails to be provable exactly one step further up.

How often 2 is a primitive root, measured against the prediction. base 2: 37.429% of primes up to 2000000, predicted 37.396%.

Number

How often two generates every remainder

For some primes p, the powers of 2 run through every non-zero remainder before repeating; for others they get stuck in a smaller cycle. Among the primes up to two million the first kind make up 37.43% — and Artin predicted 37.40% in 1927 by treating each way of getting stuck as an independent accident. For the base 5 the same prediction is wrong, because two of the accidents are secretly the same one, and nobody can yet prove that 2 works for infinitely many primes at all.

Addition as a machine with two states. Two-state carry automaton over columns (x, y, z): from carry 0 staying on 000 011 101, to carry 1 on 110; from carry 1 staying on 010 100 111, back on 001.

Logic

A machine that carries one bit

Write three numbers in base two, one above another, and read the columns from the right. Whether the bottom number is the sum of the top two can be checked with one bit of memory — the carry. That two-state machine is the whole of addition, and machines can be combined, negated and made to guess a missing number. So every sentence about whole numbers built from addition can be decided by building a machine for it, and the same machines can also handle 'x is a power of two', which addition alone cannot say.

Three-colourability as a sentence: there exist three sets such that …. Petersen graph coloured with three colours; witness sets R = {0,2,6}, G = {1,3,5,9}, B = {4,7,8}; all 25 first-order checks pass.

Logic

There is a relation such that

A graph can be coloured with three colours exactly when there are three sets of its points such that every point lies in one and no edge joins two points of the same set. The sets are a guess; once guessed, the rest is a list of simple checks. Ronald Fagin proved in 1974 that this shape of sentence — 'there exist relations such that' followed by first-order conditions — describes exactly the problems whose solutions can be checked quickly, the class called NP. The central question of computer science is therefore also a question about what sentences can say.

Smallest circuits for four functions of three letters. Four small circuit diagrams, each with three inputs feeding a few two-input gates, computing parity, a selector, majority and exactly-one-true with two, three, four and four gates.

Logic

How many gates a truth table needs

Every truth function can be built from gates, and the natural measure of a function is the fewest gates that build it. For three letters the whole answer can be computed: no function needs more than four. For n letters, a count shows that almost every function needs about 2ⁿ/n gates, and a construction shows that none needs more. And for any function anyone can actually write down, the best proof in fifty years says it needs 3.1n.

A fair coin judged by someone who thinks it is biased. Posterior probabilities of three wrong coin biases over two thousand tosses of a fair coin, for five runs; the bias 0.6 wins every run.

Probability

Certain of a coin that is not there

Bayes' theorem is exact, and it is only as good as the list of hypotheses it is given. Hand it a list that leaves out the truth and it does not hesitate: it becomes certain of the entry that is least wrong, in a precise sense — the one closest in Kullback–Leibler divergence — and if two entries are equally wrong it never settles at all. Hand it a model that assumes independence where there is none, and its intervals shrink as fast as they would for honest data while covering the truth less and less often.

Logic

The zigzags a formula can draw

Let truth be any number from 0 to 1, and Łukasiewicz's connectives turn every formula in one variable into a graph. Every graph that appears is a zigzag of straight pieces with whole-number slopes, ending at 0 or 1 — and McNaughton proved in 1951 that every such zigzag appears. A logic of degrees of truth turns out to be a theory of piecewise-linear functions with integer coefficients.

Logic

A contradiction that stays where it is

In classical logic one contradiction proves everything: from p and not-p, any q at all. Add a third truth value — both true and false — and count it as holding, and the explosion stops. The classical laws all survive as laws; what goes is exactly the reasoning that carries a contradiction somewhere it was not. Run the other way, the same three tables make a logic of gaps instead of gluts.

Cardano's formula for x³ − 3x + 1, drawn: three real roots from conjugate cube roots. The complex plane with u³ = −0.50 + 0.866i and its conjugate, their three cube roots each, and the vertical pairings whose sums are the real roots −1.879, 0.347, 1.532.

Algebra

Three real roots and no real radicals

The cubic x³ − 3x + 1 has three real roots, and Cardano's formula reaches every one of them by way of the cube roots of a complex number. That detour cannot be removed: Hölder proved in 1891 that no expression built from real radicals gives a root of an irreducible cubic whose roots are all real. The proof is three lines of the Galois correspondence, and its general form says that real radicals reach all-real roots only when square roots alone would.

Heights that shrink to nothing, slopes that grow without bound. Two stacked panels: sin(n²x)/n for n = 2, 3, 5 shrinking towards zero, and their derivatives n·cos(n²x) growing in amplitude.

Analysis

Close in height and nowhere close in slope

Uniform convergence carries continuity to the limit and carries integrals to the limit. It carries slopes nowhere. The functions sin(n²x)/n flatten to nothing while their slopes grow without bound; smooth curves converge uniformly to a corner; a Fourier series converges and its differentiated series diverges. What does carry a slope is uniform convergence of the slopes themselves — and the reason is that integration averages wiggles away while differentiation multiplies them.

Closing a path into a tour: the crossing pair the counting forces. A path through 10 points in a row, arcs from its two ends to their neighbours, and the crossing pair at step 3 whose two arcs replace that step to make a closed tour.

Discrete

Half the neighbours forces a tour

Deciding whether a graph has a closed tour through every point is one of the hardest problems computers are asked to solve. Gabriel Dirac found a condition that settles it in one glance: if every point is joined to at least half the others, a tour exists. The proof is a counting argument on a single path, it runs as an algorithm, and two small graphs show that the half cannot be lowered — while random graphs show how much stronger than necessary it is.

The centre of a circle found with six circles and no straightedge. A circle with two marked points 37.3° apart and the six compass circles that construct its centre.

Computation

The centre a compass finds in six circles

A circle is drawn and its centre was never marked. A straightedge alone can never find it again. A compass alone can, from two points on the circle, in six circles — and a search through every construction of five circles or fewer shows that six is the least. The reason six works is an inversion that turns the circle into a straight line; the price of discarding the straightedge is exactly one move.

All themes