Theme

The same thing twice — page 17

Two constructions that look unrelated and turn out to be the same object wearing different clothes.
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.

The same bell on numbers, on primes less one, and on squares plus one. Standardised ω histograms: integers ≤ 2·10^7, p − 1 for p ≤ 2·10^7, n² + 1 for n ≤ 2·10^6. Number

The same bell on thinner sets

A typical whole number has about log log N prime factors, spread in a bell curve. That was a theorem about all numbers, built on the picture of each prime dividing independently. The numbers one less than a prime, and the numbers n² + 1, are far too thin for that picture to have any obvious claim on them, and on both the same bell appears — with means shifted by constants that come straight from how often each small prime divides them. The squares plus one that are prime, the case of a single factor, number 102,205 up to n = two million against 102,302 predicted; whether there are infinitely many is open.

The three-sphere filled with trefoils. Seven fibres of the (2,3) Seifert fibration of S³, stereographically projected: five trefoils and two exceptional circles; pairwise linking numbers 6, 3, 2 and 1 verified. Topology

Torus knots that fill the three-sphere

Hopf filled the three-sphere with circles, every two linked once. Let the circles turn at two different speeds instead — p turns one way while they make q the other — and the three-sphere is filled with (p, q) torus knots, trefoils when p and q are 2 and 3, every two of them linked exactly pq times. Two exceptional fibres remain plain circles; every knot links them q and p times, and they link each other once. Computed from the drawn curves for ten fibrations, every pair comes out at pq to six decimal places.

Riemann's function on one period, with its one kind of smooth point. R(x) = Σ sin(n²x)/n² on [0, 2π]; R(π) = 0 with derivative −1/2; R(π/2) = 1.2336, a cusp. Analysis

The slope a Gauss sum leaves behind

Riemann is said to have offered sin x + sin(4x)/4 + sin(9x)/9 + … as a continuous function with no derivative anywhere. It has one after all, at π and at every π times an odd number over an odd number, and the slope there is always exactly −1/2. Computed with a million terms, the function's behaviour at every fraction is read off a single number — a quadratic Gauss sum — and the slope appears exactly where that number is zero.

A spider's matchings have real roots and its independent sets do not. Spider with legs 3, 3, 3: matching polynomial 1, 9, 27, 32, 12, roots -0.5000, -0.2324, -0.5000, -1.4343; independence polynomial 1, 10, 36, 57, 38, 9, 1, 4 non-real roots. Discrete

The roots every matching polynomial keeps real

Count a graph's matchings by size and make the counts the coefficients of a polynomial. On every one of 35,664 graphs tested, that polynomial has only real roots — a theorem of Heilmann and Lieb from 1972. Count independent sets instead and the roots wander off the axis on a growing share of graphs, but never on a graph without a claw, and matchings are the independent sets of a graph that never has one.

A chromatic polynomial with complex roots and log-concave coefficients. Wheel W5: P(x) = x⁶ − 10x⁵ + 40x⁴ − 80x³ + 79x² − 30x; |coefficients| 30, 79, 80, 40, 10, 1; min ratio 2.0000; roots 3.000, 0.000, 2.000−1.000i, 2.000, 1.000, 2.000+1.000i. Discrete

Log-concave with nothing to make it so

The chromatic polynomial of a graph counts its colourings, and its coefficients rise to one peak and fall, each squared at least the product of its neighbours. For a real-rooted polynomial that would be automatic. But by nine vertices fewer than one graph in twenty has only real chromatic roots, and the coefficients stay log-concave anyway — on every graph tested, and, by June Huh's theorem of 2012, on every graph there is.

Two triangulations, the same sum of cos 3x, different sums of cos 2x. Cyclic heptagon, triangulations 0 and 29: Σcos3x 1.52896873 / 1.52896873; Σcos2x -0.789261 / -0.467086. Geometry

The sums a triangulation cannot change

The Japanese theorem says the inradii of any triangulation of a cyclic polygon add to the same total. Write the inradius as a sum of cosines of the angles, and the theorem becomes one case of a rule that fits in a line: a sum of f over every angle of every triangle ignores the triangulation exactly when f(x) + f(π − x) is constant. cos 3x qualifies, cos 2x does not, and the proof is the inscribed-angle theorem applied to a single flipped diagonal.

Billiards in an ellipse: every path keeps touching one confocal conic. Two billiard trajectories in the ellipse x² + y²/0.49 = 1, one tangent to a confocal ellipse and one to a confocal hyperbola. Geometry

The caustics only an ellipse keeps

A billiard ball in an elliptical table touches the same confocal ellipse or hyperbola with every segment of its path, for ever. Bend the table by a percent and a half and most of those curves survive, but the one turning a quarter-turn per bounce breaks into a chain of four islands whose width grows like the square root of the bend. Birkhoff asked in the 1920s whether the ellipse is the only table that keeps them all; it is still not known.

The two-handled surface's octagon, eight to a corner. Regular hyperbolic octagon with angles π/4 and 64 neighbouring copies in the Poincaré disc. Topology

An octagon only the hyperbolic plane can hold

Glue an octagon's sides in the pattern that makes a surface with two handles and its eight corners become one point, so their angles must add to a single turn. A flat octagon's add to three. The octagon that fits has corners of 45° and lives in the hyperbolic plane, where its area is forced to be exactly 4π and its four gluing moves are motions of the plane whose commutators multiply to the identity.

Every fraction has a bulb. The cardioid with 277 computed bulbs of period 2 to 30; the bulbs of period up to five labelled 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5. Algebra

The fraction written on every bulb

Round the edge of the Mandelbrot set's cardioid hangs one bulb for every fraction between nought and one. The fraction is the bulb's address, its period, and the turn its cycle makes round a fixed point, all at once, and it sets the bulb's size as well: sin(πp/q)/q², which 245 computed bulbs obey to within fourteen per cent.

Two rays land at the root of every bulb. Parameter rays 1/3 & 2/3, 1/7 & 2/7, 5/7 & 6/7, 1/15 & 2/15, 13/15 & 14/15, 9/31 & 10/31, 21/31 & 22/31 to depth 160; furthest ray end from its root 0.0197. Algebra

Two rays for every fraction

Seen from far away, every point of the Mandelbrot set's outside has an angle, and the curves of constant angle come in to land on the set. At the root of the p/q bulb exactly two of them land, and their angles are written by the staircase under a line of slope p/q. The limbs those pairs fence off share out the whole circle of angles between them, by the identity Σ φ(q)/(2^q − 1) = 1.

Where a random walk from the centre leaves the snowflake. 60,000 walks on spheres from the centre of the level-6 snowflake; the most-visited 10% of 768 boundary pieces receive 62.7% of the walks; one walk of 9 jumps drawn. Analysis

Where a random walk leaves the snowflake

Start a random walk at the centre of the Koch snowflake and record where it first touches the edge. The edge has dimension 1.26, but the places the walks arrive form a set of dimension one: 60,000 walks spread their entropy by ln 3 a level, not ln 4, and the busiest fifth of the edge takes nine tenths of them. Makarov proved in 1985 that it must be so for every simply connected region in the plane.

The flip graph of the hexagon, given a direction. Tamari lattice T4: 14 elements 3210, 3200, 3010, 3100, 3000, 0210, 0200, 1010, 0010, 2100, 2000, 0100, 1000, 0000; 21 covering relations; 68 intervals. Discrete

Pairs of trees that count planar maps

Give every flip of a triangulation a direction and the triangulations become an order, the Tamari lattice. Counting the pairs that are in order — 1, 3, 13, 68, 399, 2,530, 16,965, 118,668, 857,956 — gives 2(4n + 1)!/((n + 1)!(3n + 2)!), which is exactly Tutte's 1962 count of planar triangulations. Chapoton noticed the match in 2006; a pair of trees and a map on a sphere turn out to be the same thing.

A chain locks whole or breaks at its weakest link. Chain of 40, Kₗ = 4.4817 at link 27; frequency spread 1.86e-5 at 1.04 Kₗ, 0.0645 at 0.96 Kₗ. Dynamics

A long enough chain never locks

Line oscillators with different natural rhythms up in a row and let each feel only its two neighbours. The chain locks into one frequency exactly when the coupling exceeds the largest running total of their frequency differences — a random walk tied down at both ends — so the coupling needed grows like √N, and its law is Kolmogorov's, the same distribution that tests whether a sample fits a curve.

The tree of solutions of x² + y² + z² = 3xyz. Markov triples from (1, 2, 5) to depth 4; 231 Markov numbers below 10^15; first 1, 2, 5, 13, 29, 34, 89, 169, 194, 233, 433, 610, 985, 1325. Geometry

The numbers that come after the golden ratio

The golden ratio is the number worst approximated by fractions: no constant larger than √5 works in Hurwitz's theorem. Set it aside and √2 is worst, with √8. Set that aside and the next is a number whose continued fraction repeats 2, 2, 1, 1, with √221/5. Markov proved in 1879 that the list continues for ever below 3, one entry for each solution of x² + y² + z² = 3xyz.

A subword can be checked with one quantifier block; a factor cannot. Subword aba: monoid 7, J-trivial, degree 3; factor aba: monoid 12, aperiodic, not J-trivial; witness abab / abba. Logic

One block of quantifiers, read off an algebra

Which properties of words can be stated with existential quantifiers alone — 'there are positions, in this order, carrying these letters' — and Boolean combinations of such statements? Imre Simon answered in 1975: exactly those whose syntactic monoid is J-trivial. Of the 57,068 languages that automata of up to four states recognise, 848 pass the test, and every one of them is decided by which words of length three or less it contains as scattered subwords.

A fixed p-value favours the null more as the sample grows. Even odds at p=0.05 near n=76, at p=0.01 near n=1202, at p=0.001 near n=83176; p=0.05 at n=10⁶ gives 116.9 to one for the fair coin; PEAR data z=3.614, p=0.00030, BF₀₁=11.90. Probability

A result at five per cent that favours the null

Toss a coin a million times and find a count of heads exactly at the edge of significance, p = 0.05. A test at the usual level rejects fairness. A Bayes factor comparing a fair coin with a coin of unknown bias says the opposite, by 117 to one. Both computations are right, and the sample size that separates them is about seventy-six tosses.

Watching a fair coin until it looks unfair. Fair coins, 2000 runs to 100000: share reaching p<0.05 by 10³ 0.468, by 10⁵ 0.697; share reaching BF₁₀≥20 by 10³ 0.0280, by 10⁵ 0.0340. Probability

Peeking until the answer is yes

Toss a fair coin, test for bias after every toss, and stop the moment the result is significant at 5%. Within a thousand tosses nearly half of fair coins have been declared biased, and with no limit on the tosses every one of them is. Watch a Bayes factor the same way, stopping at twenty to one, and no amount of watching gets more than one fair coin in twenty past the line.

An astrolabe is a stereographic projection in brass. Latitude 52°: 16 engraved curves, worst departure from a circle 8.88e-15; altitude-circle formulas within 2.2e-16; Cancer radius 0.6564, Capricorn 1.5235 of the equator's. Topology

An instrument that computes with circles

An astrolabe is a stereographic projection of the sky cut in brass. Because the projection sends circles to circles, every line on it can be drawn with compasses, and turning the star map over the plate is a rotation that answers questions in spherical astronomy without a single calculation. Of the lines medieval makers engraved, one family is not a circle on the sphere — and the arcs they drew for it miss the truth by a third of a millimetre.

Three coordinates and a fourth power. Ball sizes at r = 10, 20, 44: Z² 221, 841, 3961; Z³ 1561, 11521, 117569; Heisenberg 4309, 68079, 1600703; local exponent at 30: Heisenberg 4.005, Z³ 2.946. Algebra

Three coordinates and a fourth power

The Heisenberg group is made of triples of whole numbers, and two moves generate all of it. Count the triples within r moves of the start and the count grows like r⁴, not r³: at forty-four moves there are 1,600,703 of them, against 117,569 for the cubic lattice. The fourth power comes from one coordinate that the moves reach by enclosing area, so that height costs only the square root of itself — and seen from far away, the ball of reachable triples is a curved solid with a dimple at each pole.

Every magic square of order three is a point in a space of three. Basis J, U = (1,-1,0,-1,0,1,0,1,-1), V = (0,-1,1,1,0,-1,-1,1,0); Lo Shu = 5J − 3U + V; dimension of the order-3 magic space 3. Algebra

The magic squares are a space

A magic square is a grid whose rows, columns and diagonals share one sum. The conditions are linear, so the squares form a space: three-dimensional for order three, eight-dimensional for order four, n² − 2n in general. Inside the space of order three the eight classical squares are eight points with coordinates ±1 and ±3. Of the 880 squares of order four, 640 are singular matrices, and the search finds the reason: a symmetry of the rows and columns that carries every number to the one it adds to seventeen with.

Forty terms, two digits or thirteen. Errors after 40 terms: series -6.249e-3, Aitken -1.053e-6, Euler -1.250e-13; Wynn after 17 terms 1.250e-13. Analysis

Turning a slow series geometric

Leibniz's series 1 − 1/3 + 1/5 − 1/7 + … adds up to π/4, and it takes five billion terms to give ten decimal places. Euler found a rule that rewrites it, using exactly the same terms, as a series whose terms halve at every step — and forty of those give thirteen places. Aitken's and Shanks's later rules do better still. None of them works on every slow series, and the reason is that each one is a guess about the shape of the error.

Where sellers stand when nobody wants to move. 2 sellers: 1 equilibria (e.g. 12,12 of 24); 3 sellers: 0 equilibria; 4 sellers: 3 equilibria (e.g. 6,6,17,18 of 24); 5 sellers: 4 equilibria (e.g. 4,4,12,19,20 of 24); 6 sellers: 25 equilibria (e.g. 3,3,9,14,20,21 of 24). Applied

Sellers on a street stand back to back

Put two ice-cream sellers on a beach and they end up side by side in the middle, though customers would walk half as far if they stood at the quarter marks. Three sellers never settle at all: whoever is squeezed in the middle leaps outside, for ever. Four stand in pairs, five in pairs with one alone in the centre, six in endlessly many ways. Let them set prices too, with travel costing the square of the distance, and the conclusion reverses: the two sellers move as far apart as the beach allows.

The zero of a sandpile. Identity of the sandpile group on 128×128: cells with 0,1,2,3 grains: 1664, 568, 5368, 8784; checked by adding it to the all-3 pile. Dynamics

The zero of a sandpile

Pile grains of sand on a grid, and whenever a cell holds four, let it topple and pass one grain to each neighbour. The order in which cells topple turns out not to matter, and the piles that keep recurring when sand is dropped at random form a group — one whose size is the number of spanning trees of the grid. Its zero is not the empty grid but a fractal picture of nested squares, and sand dropped on a single cell spreads into a round pile with the same kind of pattern inside.

All themes