Matpic
mathematics, in pictures
Theme

One point away — page 2

Constructions that work perfectly except at a single exceptional place, and what is done about it.
A series that gets better, then worse. The error of Euler's series against the number of terms kept, at x = 0.05 and 0.1 and 0.2. At 0.05 the error falls to 1.1e-8 at 20 terms and then climbs without limit. At 0.1 the error falls to 1.8e-4 at 10 terms and then climbs without limit. At 0.2 the error falls to 1.8e-2 at 5 terms and then climbs without limit. Analysis

A series that converges nowhere

Expand Euler's integral in powers of x and the coefficients are the factorials, so the series converges at no x but nought. Stopped at its smallest term it still computes the integral to within about e^(−1/x) — and every term added after that makes the answer worse.

 Announcing a mixture is worth 5/3 more than any equilibrium. The leader's payoff against the probability it announces for its first action, for a leader with a dominant action that is better off not being seen to play it, with the follower's reply switching where the follower is indifferent. The best announcement is worth 11/3; the best equilibrium of the simultaneous game is worth 2. Applied

Worth more for being seen first

Moving first sounds like a disadvantage, since the other side gets to see the move and answer it. When the move is a mixture that is announced and believed, it is never a disadvantage, it is worth exactly nothing in a game of pure conflict, and in other games it is worth more than any equilibrium — sometimes by announcing an action that would never be played in secret.

 Up to 4 choices among 60, and the thresholds that nest. For 60 candidates in random order and 1, 2, 3, 4 acceptances, the chance of ending with the best among those accepted — 37.3%, 60.0%, 74.3%, 83.5% — and where along the sequence the rule starts accepting for each number of choices in hand. Probability

The thresholds that nest

Allow a second acceptance in the secretary problem and the chance of holding the best rises from about 37 per cent to about 59. The best rule is still a threshold — but one threshold for each number of choices still in hand, the earlier ones starting sooner, and each additional choice buying less than the one before.

 Add the odds from the end: start at event 5 of 12. The odds of 12 independent events with chances 1/k — the secretary problem, the sum of the odds from the end reaching one at event 5, and the chance of stopping on the last success from each starting point, highest at 39.6%. Probability

Add the odds from the end

Watch a sequence of independent events and try to stop exactly on the last one that happens. Add up the odds of the events from the end backwards until the total reaches one, and stop at the first success from there. That rule is the best possible for any probabilities whatever, and the secretary problem is the special case in which the chances are one over the position.

 Two periodic orbits meeting at the edge of the 1/2 plateau. The circle at 4 parameter values, with the period-2 points marked — two orbits inside the plateau, drawing closer together towards its edge, and none outside it. Dynamics

How a lock comes apart

Inside a plateau the map has two periodic orbits, one attracting and one pushing away. Track them to the plateau's edge and they run into each other and vanish together — so the edge of a tongue is a collision, and the width of the plateau is how far the two can be pulled apart.

 The payoffs repetition makes available in the prisoner's dilemma. A plot of the two choosers' average payoffs, with the stage game's four cells marked, their convex hull drawn, the two minmax values shown as lines, and the region above both shaded. Applied

Patience instead of a contract

Commitment had to assume an announcement binds. Play the same game again tomorrow and the assumption is unnecessary — the future does the binding. What it costs is that nearly every outcome becomes an equilibrium, so a theory that could not choose between two now cannot choose between infinitely many.

 The band two equilibria occupy, and the point a noisy reading leaves. A line of values of the payoff parameter with three regions marked — staying out dominant, both actions equilibria, investing dominant — and a single threshold inside the middle region. Applied

The reading that is almost right

Every account of simultaneous choice so far has assumed the payoffs are known to both choosers and known to be known. Replace that with each chooser seeing a private reading off by a little, and a band of equilibria closes to a single point — so the assumption nobody states decides the answer.

 n / 2ⁿ held under a geometric series. A bar for each term of the series n / 2ⁿ with a decaying geometric curve above them, the curve lying above every bar from term 2 onwards. Analysis

The series everything else is measured against

A geometric series is not one series among many. It is the yardstick: a total exists if its terms eventually fit under one, so a single comparison settles infinitely many questions — and the test built from it says nothing at all in exactly the place where the interesting cases are.

 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.

 Where one Hénon orbit spends a million steps. A density map of 1000000 steps of one Hénon orbit counted into 420 × 140 cells: 2542 cells visited, half the time spent in 608 of them. Dynamics

Where the time goes on an attractor

A chaotic orbit's position is unpredictable within a few dozen steps. How it divides its time is not — start anywhere, follow long enough, and the fraction of time spent in each region comes out the same. That distribution lives on a set of no area, and among the infinitely many ways an orbit could spend its time, typical starts pick exactly one.

 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.

 Secants closing on the slope of the folium x³ + y³ = 3xy. The curve x³ + y³ = 3xy with secants from (1.001, 0.348) of slopes 1.274, 0.953, 0.830, 0.777, approaching the tangent slope 0.744 given by the equation's partial derivatives. Analysis

A slope for a curve that is no function

The folium x³ + y³ = 3xy loops back over itself, so no formula y = f(x) describes it, and yet at almost every point it has a perfectly good tangent. Differentiating the equation as it stands gives the slope, −(∂F/∂x) ÷ (∂F/∂y), and the only points where that fails are the ones where the curve turns vertical or crosses itself — which are exactly the points where it stops being a graph.

 The slope of x² sin(1/x): discontinuous at nought, and never jumping. The derivative of x^2 sin(1/x) on [−0.12, 0.12], with the value at nought marked and the level 0.5 crossed 77 times. Analysis

A slope can swing but never jump

A function can have a slope at every point without that slope changing continuously: x² sin(1/x) has slope nought at the origin and a slope that swings between −1 and 1 however close to the origin it is taken. What a slope cannot do is jump. Darboux proved in 1875 that a derivative takes every value between any two of its values, so a step is never a derivative — and the only way a slope can be discontinuous is by oscillating.

 The expected rank a threshold rule achieves with the values shown, against what is known. n=1: 1.0000 (c=4.000); n=2: 1.2500 (c=1.000); n=3: 1.4009 (c=1.124); n=5: 1.5868 (c=1.257); n=10: 1.8141 (c=1.416); n=20: 1.9950 (c=1.555); n=50: 2.1557 (c=1.701); n=100: 2.2284 (c=1.781); n=200: 2.2725 (c=1.838); n=400: 2.2983 (c=1.877); n=800: 2.3130 (c=1.902). Probability

The rank that remembers every value

Values arrive one at a time, each must be kept or discarded on the spot, and the aim is to keep one whose rank among all of them is low on average. Told only who is leading, the best rule gets 3.87. Shown the values, a rule gets below 2.33 — and how much lower the best possible rule goes is not known, because the rank of what is kept depends on every value seen, and the best rule may need to remember all of them.

 Every section of the Möbius band crosses the zero section. The Möbius band drawn flat, with 3 continuous sections; zeros per section: 1, 3, 1. Topology

Every section of the band must vanish

Read the Möbius band as a line standing over each point of a circle, and choose a point on each line continuously: a section. On a cylinder a section can stay away from zero all the way round. On the band it cannot — every section crosses zero an odd number of times — and that single fact is what orientability means for a bundle. There are exactly two line bundles over a circle, told apart by one sign, and two Möbius bands added together make the plain cylinder's twin.

 Dodgson's rule: the fewest swaps that make a Condorcet winner. Profile of 9 ballots with no Condorcet winner; Dodgson scores A 1, B 2, C 3, D 6; Borda scores A 15, B 16, C 14, D 9; Copeland A 1, B 1, C 1, D −3. Applied

The fewest swaps to a winner

When no candidate beats every other head to head, Charles Dodgson proposed in 1876 to elect the one that is closest to doing so — the candidate that the fewest swaps of neighbouring names on the ballots would turn into a winner of every contest. The rule is easy to state and hard to compute: the count needs a search, and deciding the winner is provably among the hardest problems of its kind. A much simpler count, the votes still to be won, usually agrees, more often the larger the electorate.

 Tails of a sum of rare events: exact, and three bounds. 10: exact 5.42e-1, Bennett 1.00e+0, Bernstein 1.00e+0, Hoeffding 1.00e+0; 15: exact 8.34e-2, Bennett 3.39e-1, Bernstein 3.42e-1, Hoeffding 9.95e-1; 20: exact 3.44e-3, Bennett 2.09e-2, Bernstein 2.35e-2, Hoeffding 9.80e-1; 25: exact 4.64e-5, Bennett 3.66e-4, Bernstein 5.50e-4, Hoeffding 9.56e-1; 30: exact 2.46e-7, Bennett 2.34e-6, Bernstein 6.10e-6, Hoeffding 9.23e-1; 35: exact 5.88e-10, Bennett 6.45e-9, Bernstein 3.92e-8, Hoeffding 8.82e-1; 40: exact 7.03e-13, Bennett 8.70e-12, Bernstein 1.67e-10, Hoeffding 8.35e-1; 45: exact 4.56e-16, Bennett 6.27e-15, Bernstein 5.21e-13, Hoeffding 7.83e-1; 50: exact 1.71e-19, Bennett 2.59e-18, Bernstein 1.27e-15, Hoeffding 7.26e-1. Probability

Charged for the variance, not the range

Hoeffding's inequality knows one thing about each term of a sum: the interval it lies in. For ten thousand coins that each land heads once in a thousand, that makes it promise almost nothing — a 92% chance of thirty heads, when the truth is two in ten million. Tell the bound each term's variance as well and it changes character: Bernstein's and Bennett's inequalities decay like the normal curve while the deviation is small and like a Poisson tail beyond, and for rare events they are millions of times sharper.

 Four stages of the four-corner Cantor dust. Four panels showing stages 1 to 4 of the four-corner Cantor set: 4, 16, 64 and 256 squares kept at the corners. Analysis

A dust that almost every line misses

Keep the four corner squares of a square, then the four corners of each of those, and so on. What is left has a length, in the sense that measures length, and yet almost every straight line misses it entirely. Stage by stage the chance that a random line hits the dust falls — to 48% by the eighth stage — and how fast it falls to nothing is one of the few questions about a simple picture that is still open.

 Two triangles and three paths: the relaxation against the shortest tour. k = 3: 12 cities; subtour relaxation 12 with 6 half-edges; shortest tour 14; ratio 1.167. Applied

A bound that may be off by a third

The shortest tour through a set of cities is hard to find, and a linear programme gives a lower bound for it in polynomial time: give every road a weight between nought and one, two at each city, at least two across every division of the map. On random cities the bound is almost always exact. On two triangles joined by three long paths it falls short by nearly a third, and whether a third is the worst it can ever do has been conjectured for decades and never proved.

 Five cycles of the Petersen graph that cover every edge twice. Petersen graph: 57 cycles; minimum cycle double cover has 5 cycles of lengths 5, 8, 6, 6, 5; 1654 search steps. Discrete

Every edge on exactly two cycles

Draw a graph on paper without crossings and its faces are cycles, each edge on exactly two of them. George Szekeres and Paul Seymour asked in the 1970s whether every graph without a bridge has such a set of cycles, drawn on paper or not. The Petersen graph needs five, the flower snark on twenty points five as well, every random graph tried has one, and nobody has proved it — though a minimal counterexample would have to be a snark.

 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.

 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.

 What a left glove is worth as the market tips. For 20 players and L from 1 to 19: the core value of a left glove (1 below 10, any value at 10, 0 above) and the Shapley value, from 0.950 to 0.003. Applied

One glove too many

Give some people left gloves and others right ones, and let any group sell the pairs it can make. If the two sides are equal, the core — the splits no group can beat by walking out — is every price at once. If one side has a single glove more, the core is one split: the scarce side takes the whole of every pair and the other side gets nothing, however large the market. The average over orders of arrival barely notices the difference, and the two rules disagree about almost everything a market is.

All themes