Matpic
mathematics, in pictures
Theme

Small cases lie — page 5

Patterns that hold for every example anyone would check by hand, and then stop. The cases within reach are not a sample of the cases.
5 couples seated so that no one sits beside a partner. A round table with 10 seats alternating women and men, labelled by couple, arranged so that no man sits next to his partner, with the number of such arrangements. Probability

A round table with no couple together

Seat n couples round a table, men and women alternating, so that nobody sits beside their partner. Once the women are placed the men face a board of forbidden cells that bends round a corner — and that corner is the whole difficulty. The forbidden cells form a cycle, a count of non-adjacent points on a cycle finishes the problem, and the chance of a good seating creeps towards e^(−2) far more slowly than the hat problem reaches 1/e.

 A cycle through the middle two levels of the 5-cube: 20 words. The words of length 5 with 2 or 3 ones placed round a ring in the order of a Hamiltonian cycle, alternating between the two levels, each step changing a single place. Discrete

The walk through the middle levels

On seven places, the words with three ones and the words with four number thirty-five each. Is there a closed walk through all seventy, changing one place at a time and never leaving those two levels? On five places the answer is 24 walks, on seven and nine a search finds one in moments — and whether one exists for every odd length was open for thirty years, until Torsten Mütze proved in 2016 that it always does.

 The Fermat quotient of 2 at every prime up to 4000, and where it is 0. A scatter of the Fermat quotient of 2 modulo p, divided by p, against p for the primes up to 4000; the points spread evenly between zero and one and reach zero at the Wieferich primes. Number

Two primes where Fermat holds twice

Fermat's theorem says p divides 2^(p−1) − 1. Usually p² does not. It does at 1093 and at 3511 and at no other prime anyone has found, in searches reaching past 10^19. The leftover, (2^(p−1) − 1)/p taken mod p, behaves like a random number, so a prime has about a one-in-p chance of the extra divisibility — and a random count with that chance grows so slowly that two by now is unremarkable, while nobody can prove there are any more, or that there are infinitely many primes where it fails.

 Birthdays within k days: a half at 23, 14, 9, 7 people. Curves of the probability that two of m people have birthdays within k days, for k = 0, 1, 3, 6, with the group size at which each passes one half marked. Probability

Fourteen people within a day

Twenty-three people probably include two with the same birthday. Fourteen probably include two whose birthdays are at most a day apart, and seven, two within a week. The near miss has an exact formula, found by a trick that takes k days away after every birthday and turns the question back into the plain one on a shorter year, and the pattern behind every threshold is a single square root: a window of k days either side makes each pair 2k + 1 times as likely to collide.

 The six regular 4-polytopes, and an alternating sum of 0. A table of the six regular polytopes in four dimensions with their numbers of vertices, edges, faces and cells and the alternating sum, which is zero for each. Topology

Zero in four dimensions

Corners minus edges plus faces is two for every solid. One dimension up, corners minus edges plus faces minus cells is zero for every one of the six regular four-dimensional solids, from the five-cell to the six-hundred-cell, and for every other convex solid in four dimensions. The alternating sum does not break when the dimension rises: it alternates, two in odd dimensions and zero in even ones, because it is measuring a sphere and not a solid.

 How many digits Pell's first solution has, for D up to 1000. A scatter of the digit count of the smallest solution of Pell's equation against D, with the record-setting values ringed and labelled. Number

Sixty needs two digits and sixty-one needs ten

The smallest solution of x² − 60y² = 1 is x = 31. For x² − 61y² = 1 it is x = 1,766,319,049. The jump is not an accident of 61: the solution is exactly the product of one period's complete quotients, so its size is set by how long the continued fraction takes to come home — and for the cattle problem Archimedes is said to have posed, that product has 103,273 digits.

 Counting the real roots of x⁵ − 5x³ + x² + 3x − 1 with Euclid's algorithm. Above, the graph of a polynomial over an interval with its real roots marked; below, a step function counting sign changes in the polynomial's Sturm chain, which drops by one at each root; beside them the chain of polynomials listed. Geometry

The remainders that count the roots

Run Euclid's algorithm on a polynomial and its derivative, flipping the sign of each remainder, and write down the signs of the whole chain at any point. The number of sign changes drops by exactly one each time the point passes a real root — so the roots in any interval can be counted, exactly, without finding a single one.

 The Cantor function has length 2. The graph of a singular or partly singular increasing function on the unit interval with an inscribed polygon, beside a table of inscribed lengths by stage and the value the derivative formula gives. Analysis

The length the derivative never sees

The Cantor function climbs from 0 to 1 with a slope of zero almost everywhere, so the formula ∫√(1 + f′²) dx says its graph has length 1 — the length of a flat line. The inscribed polygons say 2. Mix it half and half with the diagonal and the length becomes exactly the golden ratio, while the formula still reports only the part the slope can see.

 How many steps Newton's method needs on (z − 1)²(z + 1). A square of the complex plane shaded in bands by the number of iterations a root-finding method needs from each starting point, darker meaning slower, with the roots marked. Dynamics

A double root halves the error instead of squaring it

Near an ordinary root, Newton's method squares its error at every step and a handful of steps reach full precision. Near a double root it only halves the error — twenty steps where five would do, and a ceiling of about eight correct digits that no number of steps can break through. Doubling the step repairs the double root and ruins the simple one.

 Counting walks that never revisit a square. Dots for the ratio of successive counts of self-avoiding walks and for the n-th root of the count, against the number of steps, both approaching a dashed horizontal line at the connective constant. Probability

A walk that may not step where it has been

Forbid a walk on the square grid from ever revisiting a site and the number of possible n-step walks grows like 2.638ⁿ instead of 4ⁿ — a number nobody can write down exactly. On the honeycomb it is exactly √(2 + √2), proved in 2010. And the walks spread out like n to the three-quarters, faster than any ordinary walk, which physicists have used since 1949 and mathematicians still cannot prove.

 A + B modulo 13: 4 and 3 residues make 9. A clock face of residues with two sets marked on an inner ring and their sumset marked on an outer ring. Computation

A sum of two sets modulo a prime cannot be small

Add every element of one set of residues to every element of another. Over the whole numbers the sums always number at least |A| + |B| − 1. Modulo a prime the sums can wrap round and collide, and still they never number fewer — the theorem Cauchy proved in 1813 and Davenport again in 1935. Modulo 12 they can. A polynomial of low degree explains the difference in a paragraph.

 Credit for one prediction, three ways of leaving an input out. Groups of bars, one group for each way of filling in the inputs that are not known, each bar one input's share of the difference between the prediction and the starting value. Applied

What a missing input is worth

A model prices a house at 180 from its size, its garden and its bedrooms, and the question is how much of the price each input is responsible for. Make the inputs the players and the average over orders answers it — once somebody decides what the model says when an input is not known. Three reasonable decisions give bedrooms nothing, nothing, and sixteen, for a model that never reads them.

 How much of a sphere lies near its equator. Curves of the share of the sphere within ε of the equator against ε, for spheres in 3, 10, 100, 1000 dimensions: a straight line in three dimensions, a near step in a thousand. Probability

A sphere that is nearly all equator

On an ordinary globe, the band within a tenth of the radius of the equator holds a tenth of the surface. On a sphere in a thousand dimensions the same band holds 99.85% of it, and the band of a fifth holds all but about two parts in ten billion. Almost every point of a high-dimensional sphere is near every equator at once — and so any function that cannot change quickly is, over almost all of the sphere, almost constant.

 Sign patterns, and the far fewer points they land on. A logarithmic plot of the number of sign patterns, two to the n, against the number of distinct values the golden geometric sum takes, which is a Fibonacci number less one and falls further behind at every step. Analysis

Two sign patterns that land together

At λ = 1/φ the sign patterns + − − and − + + land in exactly the same place, because λ² + λ = 1. That one coincidence, repeated wherever it fits, puts 2ⁿ patterns onto a Fibonacci number of points, leaves the random sum's transform ringing at the same height forever, and makes a distribution that fills a whole interval live on a set of no length.

 Who does well in a random market, as it grows. A log-log plot of the average rank of partner for the proposing side and the receiving side of random balanced markets against the market's size, with dashed curves for ln n and n over ln n. Applied

One extra person on one side

In a random market of a thousand a side, whoever proposes gets about their seventh choice and whoever receives gets about their hundred-and-fortieth. Add one person to one side and the advantage of proposing all but disappears: the shorter side does well and the longer side badly, whichever side proposes, and most people are left with exactly one stable partner.

 The standard map as its kick grows. Three square phase portraits of the standard map at increasing strengths, dotted with orbits: curves spanning the square at the smallest, fewer at the critical value, and a scattered sea with islands at the largest. Dynamics

The last circle to break

Kick a spinning rotor once a turn and most of its motions stay on curves that wind round forever, walls no orbit can cross. As the kick grows the walls break one by one, and the last to go is the one whose winding is the golden ratio — at a kick of 0.9716, found by watching a sequence of periodic orbits approximate it and asking whether they are stable.

 How much the first player can guarantee, as the coin's bias moves. A plot of the first player's best guaranteed winning chance in Penney's game against the probability of heads, a third on a fair coin and rising past one half only when the coin is heavily biased. Probability

A coin that lets the first player win

On a fair coin the second player in Penney's game always has a better pattern than the first, and the first can hold them to no worse than two to one. Bend the coin and every overlap is paid for in the letters it uses: the replies change, the first player's share swings between a third and a half, and past a heads chance of 1/∛2 the first player simply names HHH and wins.

 Three patterns that beat one another in a circle: HHHT, TTHH, HTTH. Three coin-toss patterns at the corners of a triangle with arrows showing which beats which in two-way races, and each pattern's chance of winning when all three race. Probability

Three patterns in a circle

Race three coin patterns at once and the gamblers' accounting still gives each one's chance of arriving first — one fairness equation per pattern. What it does not give is any way to read the three-way result off the two-way ones. HHHT, TTHH and HTTH beat one another in a circle, and HHH loses both its head-to-head races and still finishes ahead of one of the patterns that beat it.

 9 trees on a cubic, 10 rows of three. The curve y = 1/(1 + x²) with 8 marked points on it and a 9th at infinity. Every line through three of them is drawn: 10 in all. Geometry

Rows of three, planted on a cubic

Nine trees can be planted in ten rows of three, and the arrangement that does it is not a grid or a star but nine points on a cubic curve. On the curve three points are in line exactly when their angles add up to a right angle, so choosing the points as a cyclic group turns collinearity into addition — and the count of rows it produces is the number Green and Tao proved is the most any planting can reach.

 The next sum of two squares after 150. A quarter of the circle of radius √150 on the integer lattice, with the column x = 12 and the first lattice point above the circle in it, (12, 3), on the circle of radius √153. Number

The wait for the next sum of two squares

Sums of two squares thin out to a share of nought, and yet the gaps between them stay short. Take the largest square below any number; what is left over is small, and a small number is always close to a square. Two squarings in a row say the next sum of two squares is never more than about 2√2 times the fourth root of n away — a bound proved in 1947 that nobody has improved, sitting far above every gap anyone has found.

 Writing 0.3 in base φ. The graph of x ↦ βx mod 1 for the golden ratio φ, the diagonal, and the cobweb staircase of the orbit of 0.3, beside the 8 digits it writes. Dynamics

Counting in a base that is not a whole number

Multiply by β and keep the fractional part, over and over, and the whole parts you throw away are the digits of the starting number in base β — even when β is the golden ratio. Which digit strings can ever appear is decided by one string alone: the way the number 1 is written in that base. In base φ it is .11, so 11 is the only thing forbidden; in base 1.8 it never ends, and no finite list of rules describes what is allowed.

 Switching envelopes when the largest amount is 64. A bar chart of the probability-weighted gain from switching at each amount that might be seen, 1 to 64: small positive bars and one large negative bar, adding to zero. Probability

The envelope that always looks better

Two envelopes, one holding twice as much as the other. Open one, see an amount, and reason that the other holds double or half with equal chance — so switching gains a quarter on average. By symmetry the same argument says switch back. The step that fails is not the arithmetic; it is the claim that double and half are equally likely whatever amount is seen, which no honest prior allows — and there is one prior under which the other envelope really does look better at every amount.

 An infinite graph that passes every finite test. Two columns of vertices continuing downward without end. The top left vertex joins every vertex on the right; each other left vertex joins only the one beside it. Discrete

Enough partners in every finite group

Hall's theorem says a matching exists unless some group has too few partners between them. On an infinite graph that is false: one vertex that can be paired with anybody, and every other with exactly one, passes the test on every finite group and has no matching at all. The failure needs a vertex with infinitely many choices. Forbid that, and the theorem comes back, by an argument about trees rather than about matchings.

 Envy-free up to one item, and up to any: three people, five items. A value matrix for three people, five items with two allocations beneath it: one envy-free up to one item but not up to any, and one envy-free; the counts over all 243 allocations beside it. Applied

Envy that any single item would cure

Envy-free up to one item lets a person's envy be excused if removing the envied bundle's best item would cure it. The stronger standard asks that removing any item would — even the one that person values least. Every allocation of three people's items can be searched, and an allocation meeting the stronger standard was there every time; for two people cut and choose finds one, for three it took until 2020 to prove, and for four nobody knows.

All themes