Theme

What a system cannot say — page 4

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.
A diagonal walk through countably many listed sets. A grid of six rows and seven columns, each cell numbered by Cantor's diagonal order, with the path of the first twenty-one cells drawn. Logic

The choice inside a countable union

A countable union of countable sets is countable: list each set, then walk the grid of all their members along its diagonals. The proof is two lines and every student meets it early. It also makes infinitely many arbitrary choices at once — one listing for each set — and without the axiom of choice the theorem can fail: there are consistent worlds in which the real numbers are a countable union of countable sets, and worlds in which countably many pairs of socks cannot be counted.

Building a spanning tree by keeping every edge that closes no loop. Four stages of a greedy pass over the fourteen edges of an eight-point graph, ending with a spanning tree of 7 edges. Logic

A spanning tree for every graph

Every connected graph has a spanning tree: a set of its edges that joins every point and closes no loop. For a finite graph the proof is a greedy pass over the edges. For an infinite graph the greedy pass has to keep going past the end of every list, and the statement turns out to be exactly as strong as the axiom of choice — Zorn's lemma supplies the tree, and the existence of spanning trees in every graph gives back the whole axiom.

Euclid's argument run twenty times. The first 20 terms of the Euclid–Mullin sequence: 2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, 23003, 30693651606209, 37, 1741, 1313797957. Number

Euclid's proof run as a machine

Euclid proved there is no last prime by multiplying the primes on any list, adding one, and noting that the result has a prime factor not on the list. Run the proof as a machine — start from 2, and each time take the smallest prime factor of one more than the product so far — and it produces 2, 3, 7, 43, 13, 53, 5, 6221671, … a sequence that never repeats, that reaches small primes late and large ones early, and that nobody can prove reaches every prime.

Four proofs about numbers, and what they compute. λn f x. n (λy. f y) (f x) computes n + 1; λn f x. n (λy. f (f y)) x computes 2n; λn f x. n (λy. n (λz. f z) y) x computes n²; λn f x. n (λy. x) (f x) computes 1 at 0, else 0. Logic

What a proof about numbers can compute

The proofs of (o → o) → o → o without detours are the whole numbers, one for each count of how often the assumption is used. A proof of the implication from that formula to itself therefore takes a number and returns one, and removing its detours computes the answer. Enumerating all 14,659 such proofs up to size 16 finds 299 different functions — sums, products, squares, cubes, tests on zero — and not one of them subtracts. The predecessor, n − 1, is not among them, and a single line about polynomials says it never will be.

Raising the input's type, and what becomes computable. N[o]: 299 functions, 0 not extended polynomials; N[o → o]: 163 functions, 42 not extended polynomials; N[(o → o) → o]: 128 functions, 46 not extended polynomials; N[o → o → o]: 72 functions, 33 not extended polynomials. Logic

One type up

A numeral is an iterator, and the formula it proves fixes what it may iterate. At the lowest type it can only repeat the successor, and every function it computes is a polynomial — no predecessor. Let the same numeral iterate a function on functions and 2ⁿ appears; let it iterate a function that takes a function and returns a value, and the predecessor appears at size 15; let it iterate a pair of values, and the predecessor, halving and parity all arrive at size 16. The trick is Kleene's, from 1932, and an exhaustive search finds it without being told.

The pieces of a random vibration. Random plane wave, 240×240 grid, wavelength 24: 23 positive and 18 negative domains. Topology

The pieces no formula counts

A random vibration of a large membrane splits the surface into regions where it bulges up and regions where it dips down. Pieces minus holes has an exact average; the number of pieces has none. Nazarov and Sodin proved it is proportional to the area, Bogomolny and Schmit predicted the constant from percolation, 0.0624, and counting the pieces of 51 random waves gives 0.0599 — below the prediction by several standard errors. The sizes of the pieces follow percolation's law; their number does not.

Two grids of random-looking bits, one of rank thirty-two. 48 by 48 bit matrices: xorshift32 low bits, rank 32; xorshift32 multiplied, rank 47. Computation

A grid of bits whose rank stops at the state

Fill a square grid with a generator's output bits and compute its rank over the field of two elements. Random bits give full rank or one short, in fixed proportions. A generator built from shifts and exclusive-ors gives full rank up to its number of state bits and then never one more — 32 for a 32-bit xorshift, 128 for the lowest bit of xorshift128+ — however large the grid. The test that catches it is decided by a line of linear algebra.

Fixing two letters of a sixteen-leaf formula leaves four. Parity of four letters as a 16-leaf formula; fixing x3 = 0, x4 = 1 leaves 4 live leaves. Logic

What a formula keeps when letters are fixed

Fix half the letters of a formula at random and most of its leaves become irrelevant: on the sixteen-leaf formula for the parity of four letters, two fixings leave four. How fast formulas shrink under random fixings is the whole engine behind the best lower bounds anyone has proved for formula size — Subbotovskaya's 3/2 in 1961, Håstad's 2 in 1998 — and the reason that engine stops at n³.

Three countable models of one theory, different only above the constants. Models A (cₙ = n), B (cₙ = −1/(n+1), supremum 0), C (cₙ = 1, 7/5, 41/29, … rising to √2, no supremum) of the theory of a dense order with increasing constants. Logic

Three models and never two

Take the theory of a dense order and add constants c₀ < c₁ < c₂ < … running upward for ever. The theory is complete — it decides every sentence — and yet it has exactly three countable models, told apart only by what lies above all the constants: nothing, a least point, or a gap with no least point. Vaught proved in 1961 that no complete theory has exactly two, and the proof builds this theory's third model out of its other two.

Nine bases that cannot each have one true direction. Eighteen vectors (0, 0, 0, 1) (0, 0, 1, 0) (1, 1, 0, 0) (1, −1, 0, 0) (0, 1, 0, 0) (1, 0, 1, 0) (1, 0, −1, 0) (1, −1, 1, −1) (1, −1, −1, 1) (0, 0, 1, 1) (1, 1, 1, 1) (0, 1, 0, −1) (1, 0, 0, 1) (1, 0, 0, −1) (0, 1, −1, 0) (1, 1, −1, 1) (1, 1, 1, −1) (1, −1, −1, −1); vector i joins bases 1–2, 1–5, 1–3, 1–7, 2–5, 2–8, 2–4, 3–4, 3–6, 3–7, 4–6, 4–8, 5–9, 5–6, 6–9, 7–8, 7–9, 8–9; near-solution true: 2, 6, 10, 11, basis B9 empty. Logic

No way to hand out true and false

Birkhoff and von Neumann read the propositions of quantum mechanics as subspaces, with "and" the intersection and "or" the span. Three lines in a plane already break the distributive law. Kochen and Specker proved something stronger: the propositions cannot be called true and false at all, if every complete measurement is to have exactly one true outcome. Cabello's eighteen directions in four dimensions show why in one line of arithmetic — nine bases, each direction in two of them, and nine is odd — and a search of all 262,144 assignments confirms it.

Predicting the unseen works until the future outgrows the past. Zipf population of 5000, mean sample 2000: seen 756, f1 561, f2 95; at t = 1, 2, 4: truth 489/873/1462, smoothed 492/843/1243. Probability

How many new kinds the next sample will show

Count how many kinds were seen once, twice, three times. Good and Toulmin's alternating sum f₁t − f₂t² + f₃t³ − … then predicts, with no bias at all, how many new kinds a further sample t times as large will reveal. It works perfectly up to t = 1 and is worthless just beyond: past that point the kinds seen most often are multiplied by t to a high power, and the spread of the estimate passes 10⁴⁰ by t = 1.5. Truncating the sum at a random point rescues it, and each fourfold increase in the first sample buys about half a unit more of future.

A random walk winding round a puncture. Lattice walk of 4000 steps around (½, ½); final winding -4.861 turns; box -12..26 × -29..22. Topology

How a random path winds round a point

A path in the plane with one point removed has a class in the punctured plane's fundamental group: how many times it has wound round the point. For a random path the class grows like the logarithm of time, and its spread has a law. Brownian motion follows Spitzer's Cauchy law, so heavy-tailed that the mean winding does not exist; a walk on a grid follows the hyperbolic secant law instead, with tails that fall exponentially. The difference is made entirely by close passes, which a grid forbids. With two points removed the class becomes a word, and some loops wind round neither point and still cannot be shrunk.

Ten thousand steps of disorder, then a highway. Langton's ant from an empty grid: highway from step 9976, moving (-2, -2) every 104 steps; position after 12000 steps (-56, -32). Dynamics

An ant that builds a highway

Two rules: on a white cell turn right, on a black cell turn left, and flip the colour as you leave. From an empty grid the ant wanders for 9,975 steps without visible order, then falls into a cycle of 104 steps that carries it diagonally for ever. That it always escapes to infinity is proved; that it always ends on a highway is not.

How many times the tangent turns. circle: 1; figure-eight: 0; limaçon with a loop: 2; two inner loops: 3; three inner loops: 4; three-lobed star: -2. Topology

The turns a tangent makes

Drive once round a closed track and count how many full turns the steering has made. A circle is one turn, a figure-eight is nought, and every loop adds one. Whitney and Graustein proved that this one number decides when one track can be bent into another without ever stopping — and it can be read off the crossings of a drawing without following the curve at all.

One number, fair in base 2 and gappy in base 6. α binary: 000010101011100011100011100011110110100001001011…; base 6: 013014043000333425113050213000000124355504543223…; zero runs after 3^k: 81:16, 243:42, 729:121. Dynamics

Fair in base two and not in base six

Almost every number has digits that look like fair coin tosses in every base, and almost no number anyone can name is known to. Stoneham's number, 1/(3·2³) + 1/(9·2⁹) + 1/(27·2²⁷) + …, is one of the few: its binary digits are provably fair. Written in base 6 the same number has a run of 121 zeros starting at the 730th digit, and a longer one at every power of three after — because in base 6 each of its terms is a terminating fraction, and the gaps between them never fill.

Ackermann's function as one polymorphic term. A : N → N → N; A(0,0)=1 in 6 steps, A(0,1)=2 in 6 steps, A(0,2)=3 in 6 steps, A(0,3)=4 in 6 steps, A(0,4)=5 in 6 steps, A(0,5)=6 in 6 steps, A(1,0)=2 in 10 steps, A(1,1)=3 in 13 steps, A(1,2)=4 in 16 steps, A(1,3)=5 in 19 steps, A(1,4)=6 in 22 steps, A(1,5)=7 in 25 steps, A(2,0)=3 in 17 steps, A(2,1)=5 in 33 steps, A(2,2)=7 in 55 steps, A(2,3)=9 in 83 steps, A(2,4)=11 in 117 steps, A(2,5)=13 in 157 steps, A(3,0)=5 in 37 steps, A(3,1)=13 in 191 steps, A(3,2)=29 in 881 steps, A(3,3)=61 in 3795 steps, A(3,4)=125 in 15765 steps. Logic

One type for every use

In the simply typed calculus a numeral must be told in advance what kind of thing it will iterate, and with input and output of one type it computes only polynomials with tests. Let a single type stand for every type — a numeral is then a term of type ∀X. (X → X) → X → X, used at whatever type each occasion needs — and the same few symbols compute subtraction, exponentials and Ackermann's function, which grows faster than anything built from primitive recursion. Every run still finishes, and the proof that it does lies just beyond the reach of second-order arithmetic.

Twenty-two states and 265,454 formulas. two letters, depth two: 4 final states and 18 below; 265454 up-sets; lower states q below p q, p below p q, – below p q, – below q, – below p, q below p q/q, – below p q/q, p below p q/p, – below p q/p, – below p q/–, – below q/p, – below q/–, – below p/–, – below p q/q/p, – below p q/q/–, – below p q/p/–, – below q/p/–, – below p q/q/p/–. Logic

The second letter breaks the pattern

In one letter the constructive logic has infinitely many formulas, but they climb in a column two wide, four new ones for every step a state of knowledge can take. Add a second letter and the pattern is gone: sixteen formulas at the last step, 265,454 one step back, and more than two to the power 265,428 one step further. Every one of those is a genuine formula, and the reason the two-letter lattice has never been drawn is that each layer of the model is about as large as the number of formulas the layer above can tell apart.

The sizes three sentences allow. every point has exactly one neighbour: 2,4,6,8,10,12,14,16,18,20,22,24,26,28,30; every two points have exactly one common neighbour: 1,3,5,7,9,11,13,15,17,19,21,23,25,27,29; every two players are both beaten by a third: 1,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30 Logic

The sizes at which a sentence can come true

Write a sentence about a relation and ask for which numbers of points some relation makes it true. "Every two points have exactly one common neighbour" comes true at every odd size and no even one, and every graph that satisfies it is a windmill of triangles. "Every two players are both beaten by some third" fails for every tournament of two to six players and holds from seven on. A search can settle one size at a time; only a proof settles all of them, and the two sentences need different kinds.

Two majorities of one class must overlap. regions (outside, S, M, SM, P, SP, MP, SMP): 3,2,0,4,2,0,4,2. Logic

Syllogisms that say most

The syllogism knew four words — all, no, some, some not — and two thousand years of logic decided which of its 256 forms were valid. Add 'most', a word everyone uses in arguments, and the 256 become 864. A diagram with marks for 'empty' and 'occupied' can no longer decide them, because 'most' compares sizes; but writing the number of things in each region turns every form into a linear programme, and the programme decides all of them at once. Thirty-one are valid, including one Augustus De Morgan found in 1847: if most M are S and most M are P, then some S are P. And 'most' cannot be passed along a chain: ninety-nine per cent of S can be M, ninety-nine per cent of M can be P, and no S be P at all.

A decisive set halved for ever. voter 37: residues 1, 1, 5, 5, 5, 37; …111: residues 1, 3, 7, 15, 31, 63. Logic

An electorate too large for a dictator

Arrow proved that a voting rule with his four properties must have a dictator, and his proof uses the finiteness of the electorate exactly once. With infinitely many voters the dictator can vanish: the sets of voters who get their way form an ultrafilter, and every free ultrafilter is a rule with all four properties and nobody in charge. The catch is that no such rule can be written down. Its existence is a fragment of the axiom of choice.

One quantifier blind to two others. The prefix ∀x∃y∀u∃v drawn in a line, where v depends on x, y and u, and in branching form, where y depends only on x and v only on u; six points paired off by a fixed-point-free involution and five points, where no such pairing exists. Logic

Four quantifiers, one of them blind

In 'for every x there is a y, and for every u there is a v', the last choice may depend on everything before it. Leon Henkin asked in 1961 what happens if v may depend on u alone. Using nothing but the equals sign, four such quantifiers then say that a set has an even number of points, or that it is infinite — things no ordinary sentence can say — and the game behind the sentence can end with neither player able to win.

Three series for Catalan's constant and how fast they arrive. Log10 errors after 1 to 60 terms: plain series -4.46, Euler transform -18.53, Ramanujan series -39.46. Analysis

The sum after Leibniz's, made geometric

Leibniz's series adds the reciprocals of the odd numbers with alternating signs and gives π/4. Square the odd numbers and the same pattern gives Catalan's constant, 0.915965…, about which almost nothing is known — not even whether it is a fraction. A formula of Ramanujan's turns its slow series into one whose terms shrink by a factor of four, which makes a thousand decimals cheap, and the decimals and continued fraction then say exactly how much digits can settle and where they stop.

How wide the narrowest refutation must be. Minimal resolution refutation widths by saturation: parity on a cycle of six: 2 (widest clause 2, 6 letters, 12 clauses); parity on K₄: 4 (widest clause 3, 6 letters, 16 clauses); parity on the prism: 4 (widest clause 3, 9 letters, 24 clauses); parity on K₃,₃: 5 (widest clause 3, 9 letters, 24 clauses); three pigeons, two holes: 2 (widest clause 2, 6 letters, 9 clauses); four pigeons, three holes: 3 (widest clause 3, 12 letters, 22 clauses). Logic

The narrowest refutation

A resolution refutation can be long, and it can be wide — use clauses with many letters. Width turns out to be the easier of the two to compute exactly: derive everything that can be derived without ever writing a clause longer than w, and see whether a contradiction appears. Doing that for small formulas shows the parity formulas of graphs needing wider clauses than they contain, by more on graphs that are harder to cut in half, and the pigeonhole formulas needing no extra width at all — although every refutation of them is exponentially long. Width is not the whole price.

What each connective of two letters can express on its own. Three-letter fragment sizes of the clones generated by single binary connectives: false 4, nor 256, not x but y 38, not x 6, x but not y 38, not y 6, xor 8, nand 256, and 7, iff 8, y 3, if x then y 38, x 3, if y then x 38, or 7, true 4. Logic

What an incomplete set of connectives can say

Nand alone can express every truth function, and Post's five properties say exactly which sets of connectives can. That answers the question at the top. Below it lies a whole landscape: and alone expresses 7 of the 256 functions of three letters, xor 8, implication 38, and the sixty-four sets that can be drawn from and, or, not, xor and the two constants fall into just 22 different classes of expressible functions. The classes fit together into Emil Post's lattice of 1941 — countably infinite, completely described, and on three letters small enough to draw.

All themes