Matpic
mathematics, in pictures
Theme

The same thing twice — page 15

Two constructions that look unrelated and turn out to be the same object wearing different clothes.
A knot drawn with three sines: 5₂ as a Lissajous knot. Frequencies 2, 3, 7 with phases 0.1, 0.7, 0.3; 7 crossings from above; Alexander polynomial 2t − 3 + 2t⁻¹; determinant 7. Analysis

Three sines tie a knot

Let a point move with a different sine wave in each of the three directions of space, the three frequencies whole numbers with no common factor, and it traces a closed curve that is usually knotted. With frequencies 2, 3 and 7 the curve is the knot 5₂. The trefoil, the simplest knot of all, can never be made this way: the half-turn that shifting time by half a period performs forces a condition on the knot's polynomial that the trefoil fails.

 The coordinate change that makes the map a rotation. Graphs of the departure from the identity of the conjugacy between the circle map and the golden rotation, at three nonlinearities, each smooth and growing steeper with K. Dynamics

How smooth the disguise is

An unlocked circle map is a rigid rotation in different coordinates, and whether those coordinates are smooth is decided by arithmetic. Solving for the change of coordinates means dividing, harmonic by harmonic, by numbers that come arbitrarily close to nought — and the golden rotation number keeps them far enough away that the result is not merely smooth but analytic, while a number lying close to a fraction makes it buckle.

 How long x² + c runs before repeating, for four constants. Four survival staircases on a logarithmic scale of length: two following the birthday curve, and two for c equal to 0 and minus 2 lying far to the right. Probability

Two constants that do not walk at random

Pollard's factoring method trusts x² + c modulo a prime to repeat as soon as a random function would, after about √p steps. For c = 1 and c = 3 it does. For c = 0 and c = −2 it runs twelve to eighteen times longer on average, with almost no tail and enormous cycles, because those two maps are multiplication in disguise and their cycles are set by the order of 2 rather than by chance. Every other constant walks at random — including in the one respect in which x² + c is plainly not random, that it is two-to-one.

 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.

 The Cantor function inside a funnel of exponent log 2/log 3. The Cantor staircase with two curves of the form plus or minus the distance to one quarter raised to the power log 2 over log 3, forming a funnel the staircase stays inside. Analysis

The exponent a staircase shares with its set

The Cantor function rises from nought to one on a set of length nought, and it is Hölder continuous with exponent log 2/log 3 — the same number as the dimension of that set. It is not a coincidence: both numbers say that an interval of width r carries mass r to the power 0.6309, and that one inequality proves the dimension and the smoothness at once. Tilt the weights of the construction and the two numbers separate, which shows exactly what the coincidence was measuring.

 Three splits that between them beat every other. The triangle of splits of one pound among three players, with the three half-and-half splits marked and every other lattice point coloured by which of the three dominates it: 134, 134, 134 beaten by exactly one, 91 by more. Applied

Three splits that answer every other

When any two of three people can take a pound, no division of it is safe from a pair walking off. Von Neumann and Morgenstern's answer was not a division but a set of them: three half-and-half splits that never beat one another and between them beat everything else. It is a solution — and so is the line on which one player is held at any fixed share below a half, so the same game has infinitely many, each describing a different settled way of treating the third player.

 Descents of 10 as a sum of 9 hidden coins. Bars of 9 coin probabilities beside a bar chart of the descents distribution for n = 10, with dots giving the coin-sum distribution landing on every bar. Discrete

Coins hidden in the roots

The polynomial that counts permutations by their descents has no product formula, and nothing in the definition of a descent is a coin toss. But every root of the polynomial is real and negative, and a polynomial like that is a product of coins in disguise: each root r is a coin landing heads with chance 1/(1 − r). The descent count of a random permutation is exactly a sum of independent coins nobody can point to — which is why it is bell-shaped, and why its coefficients obey inequalities the inversion count breaks.

 One try: letters set in a random order, forced or guessed. Ten rows, one per letter in the order processed, marking 5 guessed and 5 forced letters, each forced one with the clause that forced it. Logic

A letter the clauses already decide

Set the letters of a formula one at a time, in a random order, and guess each one with a coin — unless some clause has already had its other two letters set to false, in which case the clause decides. A try succeeds when every guess is right, so what matters is how many letters get guessed. On a formula with one solution, every letter has a clause that forces it in at least one order out of three, so at most two thirds of the letters are guessed on average, and about 1.587ⁿ tries suffice. It is slower than the random walk. Refined, it is the fastest method known.

 Four equal quarters of an L-shaped plate. An L-shaped plate cut by two perpendicular halving lines at 48.8 degrees into four pieces of equal area. Topology

Four equal quarters with two lines

Any flat shape, however lopsided, can be cut into four pieces of equal area by two perpendicular straight lines. The proof turns the pair of lines like the hands of a clock: the area in one quadrant, minus a quarter, reverses its sign every quarter-turn, so somewhere it is zero. The same kind of argument cuts a solid into eight equal pieces with three planes. It stops working in five dimensions, where some masses cannot be cut into thirty-two equal pieces by five hyperplanes — and in four, nobody knows.

 How often a walk comes home, on three lattices and a tree. Four curves of the logarithm of the return probability after 2n steps, for n up to 60: three lattices flattening, and the free group falling along a straight line. Algebra

How rarely a walk on a group comes home

Walk at random on the picture of a group, one generator at a time, and ask for the chance of standing at the start after 2n steps. On the line, the plane and three-dimensional space it falls like a power of n. On the tree that pictures the free group it falls by the factor √3/2 every step, exponentially. Kesten proved in 1959 that this is no accident of two examples: the chance falls exponentially exactly when the group's balls are mostly boundary, so a probabilistic rate and a geometric ratio are the same measurement.

 How many three-state chains constant rates can produce. s 0.05: 94.9%; s 0.1: 90.2%; s 0.2: 79.6%; s 0.3: 70.3%; s 0.5: 47.7%; s 0.7: 22.9%; s 1: 4.3%. Analysis

When a table of moves came from steady rates

A process that jumps between states at constant rates, watched once a year, produces a table of yearly moves that is the exponential of its rates. Most tables that anyone could write down are not — a random three-state table is only about one time in twenty-three — and the few that are can have two different sets of rates behind them, but only once the process has forgotten where it started.

 A ball in a cube and the word of walls it hits, direction (1, √2, √3). A cube drawn in perspective with a billiard path of 30 bounces inside it, each bounce point coloured by the pair of walls it is on, and the word ZYXZYZXYZZXYZYXZYZXYZZYXZYZXYZ below. Dynamics

The word a line spells in a cube

A ball bouncing in a cube hits three kinds of wall, and the order spells a word in three letters. On a square table the word had n + 1 different blocks of length n; in the cube it has $n^2 + n + 1$ — three, seven, thirteen, twenty-one — for a direction in general position. What general position has to exclude turns out to be more than any rational relation among the three speeds.

 Morley's construction on a sphere. A spherical triangle with angles 76.1, 97.3, 48.8 degrees, its angle trisectors as great-circle arcs, and the inner triangle they form, with sides 0.23902, 0.23881, 0.23902. Geometry

The trisectors on a sphere almost agree

Draw Morley's construction on a sphere and the triangle the trisectors cut out is not equilateral — but its sides agree to within a tenth of a percent even when the angles add to 222°. Every step of the rotation proof survives on the sphere except one, and that one is the angle sum.

 Where interpolation through 11 nodes magnifies an error. Lebesgue functions of equispaced, Chebyshev and optimal nodes of degree 10; constants 29.900, 2.489, 2.052. Analysis

The best nodes have no formula

Interpolating through n points magnifies any error in the data by at most the Lebesgue constant of the points. Chebyshev's points keep it near (2/π)·log n; stretching them to the ends of the interval brings it within two hundredths of the best possible; and the best possible points, characterised in 1978 by having every bump of the error curve the same height, have never been given a formula.

 Sperner's corridor to the same fixed point, on a gentle map and a twisted one. Two 32 by 32 labelled grids; the corridor crosses 44 triangles reading 100 corners on the gentle map and 148 triangles reading 204 corners on the twisted one. Topology

What it costs to find the point that stays put

Brouwer's theorem promises a point a map leaves where it is, and Sperner's corridor walks to it. On a gentle map the walk is short; twist the map about its fixed point and the corridor follows every turn, so its cost grows like the square of the grid. Halving the square by winding number finds the same point in a number of readings proportional to the grid's side whatever the map does — and no method that only reads the map can do fundamentally better.

 Every envy-free way to split one rent among three rooms. A triangle of rent splits of 90 with the envy-free hexagon (corners 30, 30, 30; 46.7, 21.7, 21.7; 50, 25, 15; 45, 35, 10; 35, 40, 15; 28.3, 33.3, 28.3) and the maximin, equal and grid splits marked. Applied

A rent nobody envies is not one rent

Three housemates, three rooms, one rent, and Sperner's lemma promises a split nobody envies. It does not promise one split. For housemates who judge rooms by value for money, the envy-free splits fill a polygon, and in a typical house some room's rent can move across a quarter of the total without anyone envying anyone. Choosing inside it is a second decision. The rule the rent-splitting websites use makes the worst-off housemate as well off as possible, and in almost every house it rewards a housemate who understates what the rooms are worth.

 The same rule in the adversary's order and in a random order. Two copies of the 8-a-side triangular graph matched greedily with the worst ranking: 4 matched in the adversary's order, 5 in a random order (average 5.30). Discrete

Matching when the arrivals are shuffled

An adversary who chooses the order in which applicants arrive can hold any fixed matching rule to half the best. Take the order away and let it be random, and the plainest rule of all — give each arrival its first free place in a fixed list — rises to 1 − 1/e, because shuffling the arrivals turns out to be exactly the trick RANKING plays with the places, seen from the other side. Shuffle both and the guarantee rises again, to somewhere between 0.696 and 0.727, and where in that interval it lies is not known.

 The Mandelbrot set counted cell by cell. A 96-cell-wide grid over the Mandelbrot set: 2034 cells certainly inside (1.3794), 290 undecided after 60 steps (0.1967). Algebra

The area of the Mandelbrot set, from two sides

The Mandelbrot set has an area, and nobody knows it. Counting grid cells closes in on 1.5066 from both sides, but every count judges a cell by a single point, and points on the boundary never declare themselves. An exact formula exists — π times one minus a sum over the coefficients of the map onto the set's outside — and every partial sum is a guaranteed upper bound; after sixteen thousand coefficients the bound is still 1.786, and at the rate it falls it would need something like 10²⁵ more.

 The factorials, and three smooth curves through all of them. Γ(x+1), Γ(x+1)(1 + 0.5 sin² πx) and the degree-six interpolating polynomial through 0!…6!, on a log scale over 0 ≤ x ≤ 5.4; at x = 1/2: 0.88623, 1.32934, -3.58301. Analysis

Only one curve through the factorials bends the right way

Infinitely many smooth curves pass through 1, 1, 2, 6, 24, 120, and some of them even obey the factorial's own rule, f(x + 1) = (x + 1)·f(x), at every x. Ask that the logarithm of the curve bend upwards everywhere and exactly one survives — Euler's integral. A wiggle of any size breaks the condition somewhere, the smaller the wiggle the further out, and the proof that nothing else survives is a squeeze that computes √π along the way.

 What a seller collects under first-price and second-price rules. Histograms of 20000 simulated revenues with 3 uniform bidders: second-price mean 0.4988, variance 0.0497; first-price mean 0.4995, variance 0.0167. Applied

Two auctions that earn the same

In one sealed-bid auction the winner pays its own bid; in the other it pays the second-highest bid. Bidders behave completely differently — in the second they bid what the object is worth to them, in the first they shade their bids down by exactly a fraction — and the seller's revenue is spread differently. Yet the seller expects to collect precisely the same amount, (n − 1)/(n + 1) for n bidders with values spread evenly, and so does an auction in which everybody pays. The equality breaks the moment bidders dislike risk, and it says nothing about how much a reserve price can add.

 Where the Rössler flow's peaks fall, as one parameter changes. Peak values of x against c from 2.5 to 6.2 for the Rössler system with a = b = 0.2: period 1, 2 and 4 at c = 2.5, 3.5 and 4, chaos beyond about 4.2, a period-3 window near 5.3. Dynamics

A flow that doubles like a parabola

Otto Rössler's three equations have one nonlinear term and a single knob. Turn it and the orbit closes after one loop, then two, then four, then never — the logistic map's cascade, in a flow in three dimensions. Record each peak of the orbit against the one before and the reason appears: the points lie on a single rounded hump. The gaps between doublings shrink by ratios 3.49, 4.54, 4.59, climbing towards Feigenbaum's 4.669, and the chaos contains a period-3 window that repeats the whole cascade.

 Leading digits of products of random numbers, against Benford's law. 1 factor: ones 11.1%, nines 11.1%; 2 factors: ones 24.1%, nines 3.4%; 3 factors: ones 30.1%, nines 4.2%; 6 factors: ones 30.1%, nines 4.6%; the law gives 30.1% and 4.6%. Probability

Multiplying makes the digit one common

Multiply a few random numbers together and the product starts with 1 about 30 per cent of the time and with 9 under 5 per cent — Benford's law, which no factor contains. The logarithm of a product is a sum, the central limit theorem spreads that sum across many powers of ten, and once it is spread its fractional part is uniform. The approach is geometric, at a rate fixed by a single number for each kind of factor; sums never get there, and the powers of two get there with no randomness at all.

 The low bits of a congruential generator, and the bits a permutation shows. First 128 steps of a 16-bit congruential generator: low state bits with periods 2, 4, 8, 16, 32, 64, 128, 256; permuted output bits all with period 65536. Computation

A rotation that hides the lattice

A congruential generator modulo a power of two has a lowest bit that alternates and pairs of outputs that lie on a few lines. Keep the generator exactly as it is, and show only eight bits of each state, rotated by an amount the state's own top bits choose: every output bit now runs the full cycle, the pairs fill the square as a random sequence would, and triples pass a test the state's own bits fail by a factor of six. Nothing about the state has changed, and four outputs still give it away.

 One form completed three ways, and the same straddle each time. The plane coloured by the sign of 2x² + 6xy + 3y². Three pairs of lines, one for completing with x first, one for y first and one along the eigenvectors; their coefficients are 2 and −3/2; 3 and −1; 5.541 and −0.541, and every pair has one line in a positive wedge and one in a negative wedge. Algebra

The signs no completion can change

A quadratic in several variables can be completed square by square in many orders, and each order hands back different coefficients. What no order changes is how many come out positive and how many negative — and that count, read off a completion of A − tI, says how many eigenvalues lie below t without finding a single one.

All themes