Matpic
mathematics, in pictures
Theme

The same thing twice — page 13

Two constructions that look unrelated and turn out to be the same object wearing different clothes.
The core of a market with two houses and two buyers. The core of an assignment game drawn in the plane of buyer A's payoff against buyer B's, a polygon with vertices (0, 1), (0, 0), (1, 0), (4, 3), (2, 3); the buyers' best corner is (4, 3). Applied

The prices nobody can break away from

When houses are sold to buyers who value them differently, there is a whole range of prices at which nobody wants to walk away, and it has a remarkable shape — one corner best for every buyer at once, one best for every seller at once, and the buyers' corner pays each buyer exactly what the market would lose without them.

 A 33 × 32 rectangle cut into 9 unequal squares. A squared rectangle of 9 squares with sides 18, 15, 14, 10, 9, 8, 7, 4, 1, each labelled with its size. Computation

A rectangle made only of squares

A rectangle can be cut into finitely many squares — of any sizes, as many as wanted — exactly when its two sides are in whole-number proportion. Max Dehn proved it in 1903, and the proof that stuck, found by four Cambridge undergraduates in 1940, reads the squares as currents in an electrical circuit.

 A triangulation of the square with 7 three-coloured triangles. A triangulation of the unit square into 34 triangles, vertices coloured by Monsky's rule, with the 7 triangles carrying all three colours shaded. Computation

No odd number of equal triangles

A square can be cut into two triangles of equal area, or four, or any even number. It cannot be cut into three, or five, or any odd number — whatever shapes the triangles take. Paul Monsky's proof of 1970 has no geometry in its engine at all: it colours the points of the plane by how divisible their coordinates are by two.

 The Collatz map on the 2-adic integers, before and after changing to parity coordinates. Two scatter plots of 2048 points: the Collatz map on 2-adic integers in binary-digit coordinates, a scattered cloud, and the same map in parity-vector coordinates, where every point lies on the two lines of the doubling map. Dynamics

Where the Collatz map is a coin

Extend the Collatz map from the whole numbers to the 2-adic integers — binary strings that run on for ever to the left — and it stops being mysterious. It becomes, after a change of coordinates, the simplest chaotic system there is: shifting a string of coin tosses one place. Everything about it is then known, and none of it says anything about the whole numbers, which is the most instructive failure in the whole story.

 The Voronoi diagram of points on a shape's boundary, and the axis it traces. 50 boundary samples of a shape with their Voronoi cells clipped to the shape; the cells' interior corners line up along the medial axis. Geometry

The skeleton inside a shape

Take the Voronoi diagram not of a handful of points but of a shape's whole outline: the points inside the shape that have two nearest points on its edge. What comes out is a skeleton — a thin branching tree that describes the shape and, with one number attached to each point, rebuilds it exactly. It is also where fires lit all round the edge would meet, and it is violently unstable: a tooth too small to notice grows a branch several times its own size.

 The 9 mirrors of the octahedral group, cutting the sphere into 48 triangles. A sphere crossed by the 9 great circles of the octahedral group's mirror planes, dividing it into 48 triangles with one shaded. Geometry

Three mirrors make every solid

Every symmetry of a regular solid, reflections included, is produced by just three mirrors meeting at its centre, reflected in one another over and over — a kaleidoscope. Put a single point between the three mirrors and its reflections are the corners of a solid: the regular solid itself if the point sits in a corner, and every one of its truncated and expanded relatives if it sits anywhere else.

 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.

 Error against the number of points for three randomised methods. Log-log plot of root-mean-square integration error against N from 16 to 4096 for plain Monte Carlo (slope -0.52), digitally shifted Sobol' points (-1.00) and Owen-scrambled Sobol' points (-1.43). Probability

An error bar for points that are not random

Evenly spread points integrate far better than random ones and give no error bar; random points give an error bar and integrate badly. Randomise the even points themselves — shift a lattice by a random vector, or scramble the digits of a Sobol' sequence — and both are kept: an unbiased estimate, a confidence interval from a handful of repeats, and an error that falls faster than any deterministic set's.

 Counting overlapping targets from sensor counts alone, by integrating against χ. A 36 by 32 grid of sensor counts from 7 overlapping discs; the sum of the Euler characteristics of the level sets is 7. Topology

Counting targets by their holes

The Euler characteristic adds up like an area: glue two shapes together and it is the sum of theirs minus that of their overlap. So it can be used to measure, and measuring with it does something no area can. A field of sensors that each report only how many targets they detect — not which, not where — can have its readings added up, weighted by the Euler characteristics of the regions where the count is high, and the answer is exactly the number of targets.

 A map that folds the plane over itself, with every point still counted once. The map (u, v³ + uv): its domain shaded by the sign of the Jacobian determinant and its image with the grid carried across. At 5 marked target points the preimages number 3, 3, 1, 1, 1 and their signed counts are all 1; the determinant integrates to 4.447, equal to the integral of the signed count. Algebra

The count a fold cannot change

A curved map can fold the plane over itself, so that one point has three preimages and its neighbour has one. Count each preimage with the sign of the determinant there and the jump disappears — the signed count is the same everywhere, and it is a whole number.

 The best degree-3 polynomial to eˣ: its error touches its largest size 5 times. The error curve of the best uniform polynomial approximation of degree 3 to eˣ on the interval from −1 to 1. It reaches its maximum size 5.528 × 10⁻³ at 5 points, alternately above and below, at x = -1.000, -0.682, 0.050, 0.732, 1.000. Analysis

The error that keeps coming back to its worst

Judge a polynomial by its largest error on an interval and there is exactly one best one of each degree. It is recognised without comparing it to anything else — its error rises to the same largest size, alternately above and below, one more time than there are coefficients.

 A disc of radius 0.2 and an ellipse of size 1.22 around the same interval. For 1/(1 + 25x²): the interval from −1 to 1 on the real axis, poles at 0 + 0.2i and 0 − 0.2i, the Taylor disc at 0 of radius 0.20, and the Bernstein ellipse with foci ±1 through the poles, with ρ = 1.2198. Analysis

An ellipse, not a disc

A Taylor series converges on a disc, and the disc's radius is the distance to the nearest singularity. Ask instead how well polynomials can follow a function on an interval, and the answer is an ellipse with the interval's ends as its foci — the largest one the function is smooth inside.

 3 moves along the edges to the corner that maximises 2x₁ + 3x₂. The simplex method on a two-variable program with 5 constraints, started at the origin. It visits (0, 0), (0, 8), (1, 8), (5/2, 15/2), with objective values 0, 24, 26, 55/2, and stops where the prices on both binding constraints are non-negative. Applied

Prices at every corner

The duality theorem says a linear program's best value equals its dual's, and says nothing about how to find either. The simplex method finds both at once — it walks from corner to corner, and at each one asks the constraints that meet there for prices. A negative price names an edge that climbs; when none is negative, the prices are the proof.

 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.

 400 random points and their longest rising chain, 34 long. 400 uniform random points in a unit square with the longest chain increasing in both coordinates marked: 34 points, against 2√n = 40.0. Discrete

The longest climb of a shuffle

Erdős and Szekeres guarantee that any n distinct numbers hold a climb or a fall of √n, and there are orders that allow nothing more. Shuffle a deck at random instead and the longest climb is almost exactly 2√n — with fluctuations of size n to the power one-sixth, distributed exactly as the largest eigenvalue of a large random matrix.

 Three lines through a point, reflected in the bisectors, meet again. A triangle with a point P and its cevians, their reflections in the angle bisectors, and the point P* where the reflections meet — P's isogonal conjugate, at (373.8, 290.0). Geometry

Every point has a partner across the bisectors

Draw the three lines from the corners of a triangle through any point, reflect each in the bisector of its own angle, and the three reflections meet again. The pairing this makes swaps the centroid with the symmedian point and the orthocentre with the circumcentre, bends every straight line into a conic through the corners, and sends the circumcircle to infinity.

 Five triangles between the same two circles, every one closing. An outer circle of radius 1 and an inner of radius 0.38 at Euler's distance 0.4899; five triangles inscribed in the first and circumscribed about the second, started from different points. Geometry

A triangle that fits once fits everywhere

Put one circle inside another and try to fit a triangle between them, its corners on the outer circle and its sides touching the inner. Usually no triangle fits. But if one does, then one fits starting from every point of the outer circle — and whether it does is decided by a single equation in the two radii and the distance between the centres.

 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.

 The first 16 vertices of Rado's graph, joined by binary digits. Adjacency table and circular drawing of the Rado graph on vertices 0 to 15, where i < j are adjacent when bit i of j is 1; 32 edges. Logic

The graph that coin tosses always make

Take infinitely many vertices and toss a coin for every pair to decide whether they are joined. The result is random in every detail — and, with probability one, it is always the same graph. The same graph can be written down without any coins, by joining two numbers when one binary digit of the larger is a one.

 The 46 Farey fractions of order 12, and how far each strays from even spacing. Farey fractions of order 12 against 46 evenly spaced points, with the deviation of each drawn as a bar; largest deviation 0.0616. Number

How evenly the fractions spread

List every fraction between nought and one with denominator at most n, in order. They spread across the interval almost evenly, and how fast the unevenness shrinks as n grows is — exactly, provably — the Riemann hypothesis. The link runs through a second fact: set the fractions round a circle and add them as arrows, and what is left is a whole number.

 The 4 reduced forms of discriminant −84, each in its place. The reduced binary quadratic forms of discriminant −84 (x² + 21y²; 2x² + 2xy + 11y²; 3x² + 7y²; 5x² + 4xy + 5y²) plotted at their roots in the upper half-plane, all inside the modular fundamental region. Number

Counting the classes that break factorisation

The class number measures how badly unique factorisation fails in a field, and defined through ideals it looks impossible to compute. Gauss computed it by hand, for every field he wanted, by counting quadratic forms — and every form can be squeezed, by changes of variable that keep its values, into exactly one small standard shape.

 The narrowest door in two 6-cliques joined by one edge, and the gap it pins down. two 6-cliques joined by one edge, with the vertex set of smallest conductance coloured and the 1 edges leaving it thickened. Beside it a logarithmic ruler marks half the conductance squared, the spectral gap and twice the conductance, in that order from the bottom. Probability

The narrowest door sets the pace

How fast a chain forgets is an eigenvalue, and nobody can compute the eigenvalues of a chain worth studying. Cheeger's inequality trades the eigenvalue for a picture — the narrowest door in the state space — and pins the one between the square of the other and twice it. Both ends of that range are reached, on graphs small enough to search completely.

 How far a deck of 52 is from random after each riffle shuffle. A bar chart over one to 12 riffle shuffles of the exact total variation distance from a uniformly random deck. The bars stay near one for the first few shuffles and drop sharply around 8. Probability

The forgetting that happens all at once

A single small chain forgets its start gradually, a little more with every step. A family of large ones can do something different — stay almost perfectly informed about where it began, and then lose all of it inside a window far shorter than the wait. That cliff is the cutoff phenomenon, and it is why "seven shuffles" is an answer rather than a convention.

All themes