Things that cannot be done — page 8
Topology
How many changes undo a knot
Cut the string at a crossing, pass it through the other strand and join it up again, and any knot can be undone by doing that often enough. The fewest changes needed is the unknotting number, and proving that fewer will not do needs a number that each change can move only a little. The signature moves by at most two per change — enough to settle thirteen of the fourteen knots up to seven crossings, and not the fourteenth.
Topology
Several colours on every vertex
Give every pair from six points three colours, so that pairs with nothing in common share no colour. Counting says nine colours might do; ten are needed. Stahl conjectured in 1976 exactly how many colours every such problem needs — a formula that meets Lovász's topological answer at one colour a vertex and the obvious answer at k — and a search over stars and triangles confirms it in every case small enough to run.
Topology
Six points in space and a pair that must link
Put six points anywhere in space and join every pair with a straight segment. Split the six into two triangles — there are ten ways — and at least one of the ten pairs of triangles is linked like two rings of a chain. No placement avoids it. The reason is a parity: moving an edge through another changes exactly two of the ten linking numbers, so their sum stays odd whatever is done.
Algebra
Which graphs let the tokens go anywhere
A sliding puzzle is a graph with a token on every vertex but one. Richard Wilson found in 1974 what every such puzzle can reach, and the answer has a surprise in it — the half the tray is stuck with is not a fact about permutations at all, but about the board being two-coloured — and one exception, a graph of seven vertices that reaches exactly 120 of 720.
Analysis
The matrix that has no logarithm
Every square matrix has an exponential, and a matrix exponential is always invertible. The converse fails, and it fails in a way that can be read straight off the eigenvalues — a real matrix with eigenvalues −1 and −2 is no exponential at all, while minus the identity is the exponential of a whole continuum of matrices that do not even commute with each other.
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.
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.
Discrete
How many colours the plane needs
Colour every point of the plane so that no two points exactly one unit apart share a colour. Seven colours are enough, by a tiling with hexagons, and four are necessary, by a graph of seven points. For sixty-eight years nothing better was known on either side; then in 2018 a graph of 1,581 points showed four is not enough — and the answer is still somewhere from five to seven.
Number
Two halves a sieve cannot tell apart
Split the whole numbers into those with an even number of prime factors and those with an odd number. To a sieve — which sees only how many numbers each small divisor divides — the two halves look almost exactly alike. Yet sifting out the small primes leaves every prime in one half and nothing at all in the other. That is Atle Selberg's parity example, and it is the reason no sieve can prove there are infinitely many twin primes.
Algebra
The biggest box built from signs
Fill a square table with plus and minus ones and ask how large its determinant can be. The columns all have the same length, so the answer is a box with fixed edges — largest when every corner is square, which is possible only when the size is a multiple of four.
Applied
The cube that takes every corner
The simplex method is fast on every program anybody meets in practice. In 1972 Victor Klee and George Minty squashed a cube so that the method, choosing the steepest edge each time, visits all of its corners — 2ⁿ − 1 moves in n variables, with the optimum one edge from the start.
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.
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.
![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.](/f/the-slope-of-x2-sin-1-x-discontinuous-at-nought-and-never-60857308.svg)
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.
Computation
The orders a plane cannot have
Every counting condition allows a projective plane of order six, and there is none. The proof that rules it out looks at one matrix identity — each point on seven lines, each two points on one — and turns it, by way of Lagrange's four squares, into the statement that six would have to be a sum of two squares. Run on the planes that do exist, the same argument hands back their orders as sums of two squares; run on six, it asks for something no arithmetic can supply.
Discrete
The crossings a graph cannot avoid
Five points all joined need one crossing, six need three, seven need nine. Euler's formula gives a lower bound that grows like the square of the number of points and is badly wrong; a sampling trick turns the same formula into a bound that grows like the fourth power and is right to within a constant. And for drawings with straight edges the count turns out to be something else entirely: the number of quadrilaterals the points make.
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.
Analysis
No integrand sits on the border
The area under 1/x out to infinity is infinite and the area under 1/x² is finite, so it is natural to look for the dividing line. There is none. Divide any divergent integrand by its own running integral and it still diverges, more slowly; divide any convergent one by the square root of its tail and it still converges, more slowly. Paul du Bois-Reymond proved in 1873 that no single integrand can separate the two families — and the slow ones are slow beyond imagining.
Applied
How few voters any majority needs
Any pattern of head-to-head majorities whatever — cycles within cycles, a candidate who beats the winner of every other contest and loses to its loser — can be produced by voters who each rank the candidates sensibly. McGarvey's recipe needs n(n − 1) of them for n candidates. The truth is far fewer: every pattern on five candidates takes three voters at most, a counting argument shows the number must eventually grow, and it grows only like n divided by its logarithm.
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.
Computation
The spiral that measures its own circle
Let a ray turn steadily while a point moves steadily out along it, and the point draws Archimedes' spiral. Distance from the centre is then proportional to angle, so dividing a length divides an angle in any ratio. The spiral's second power is stranger: the tangent at the end of the first turn cuts off, on a line through the centre, a straight length exactly equal to the circumference of the circle through that end — a curved length laid out straight, and with it the circle squared. The catch is the tangent itself.
Computation
A third reached only in the limit
No compass-and-straightedge construction trisects every angle. But a quarter, plus a quarter of a quarter, plus a quarter of that, and so on, adds up to a third — and each of those pieces is two bisections away. So an angle can be trisected by bisecting forever, every stage exact and the shortfall shrinking to a quarter each time. The construction never ends, and that is precisely what Wantzel's proof forbids: a construction is a finite thing, and a third of a general angle is only reached in the limit.
Discrete
As many points as two steps allow
In a graph where every point has d neighbours and every point is within two steps of every other, there can be at most d² + 1 points — one, its d neighbours, and d(d − 1) more reached through them. Graphs that meet the bound exactly are rare to the point of absurdity. The pentagon does it for d = 2, the Petersen graph for d = 3, a fifty-point graph found in 1960 for d = 7, and an eigenvalue argument proves there is nothing else — except possibly one graph with 3,250 points and 57 neighbours each, which nobody has found or ruled out.
Geometry
Fifteen numbers decide every number
Lagrange proved that x² + y² + z² + w² takes every whole value. Ramanujan asked which other sums of four weighted squares do, and in 1917 listed fifty-five. One of them is wrong: x² + 2y² + 5z² + 5w² misses 15. The mistake points at a theorem found eighty years later — to know whether such a form reaches every number, it is enough to check that it reaches 1, 2, 3, 5, 6, 7, 10, 14 and 15. Nine checks decide infinitely many cases, and the nine numbers come out of an escalation any one can run.