Things that cannot be done — page 9
Number
When minus one can be reached
x² − Dy² = 1 always has a solution. Put −1 on the right and it sometimes does and sometimes does not. A remainder rules out most D at a glance, every prime of the form 4k + 1 is guaranteed one, and between the two lies a set of D decided by arithmetic several layers deep — of which, a million numbers in, 78% are solvable, on the way to a limit of 58% that was proved only in 2022.
Topology
Six sticks tie a trefoil, and five cannot
Build a knot from straight sticks joined end to end and ask for the fewest. A trefoil takes six, and the six corners can be whole-number points in a box ten units wide. Five sticks can cross one another five times in a picture, as often as a cinquefoil needs, and still tie nothing — the five crossings always twist three one way and two the other. The fewest sticks is a measure of how knotted a knot is that no diagram shows directly.
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.
Computation
The longest code that survives every erasure
A Reed–Solomon code of k symbols can lose any n − k of its n and still be read. Over an alphabet of q symbols it can be at most q + 1 long — and it is conjectured that no code with the same perfect tolerance can ever be longer, apart from one family of exceptions in even characteristic. A search through every possible code for small alphabets confirms it cell by cell, a proof exists when q is prime, and for every other q the question is open.
Geometry
What the signs allow
Descartes' rule reads the signs of a polynomial's coefficients and bounds its positive roots by how often they change — a bound set by the number of terms, not the degree, and proved by nothing more than Rolle's theorem. Each count the rule allows can be had. But not every pair of counts, positive and negative, that the rule allows together can be had together: the first combination that never occurs is at degree four, and the list of impossible ones is still being worked out.
Geometry
Five where four were promised
In one unknown, a polynomial with three terms has at most two positive roots, whatever its degree. The natural guess for two equations in two unknowns, each with three terms, was two times two: four. It is wrong. Bertrand Haas found two such equations in 2002 whose curves cross five times in the positive quadrant, all five crowded within a tenth of one corner, and five turned out to be the most there can ever be.
Number
Perfect but for one factor
In 1638 Descartes wrote to Mersenne with an odd number whose divisors add up to exactly twice the number — provided one of its factors, 22021, is counted as a prime. It is not; it is 19² × 61. Nearly four centuries later that number is still the only odd one of its kind known, and a search of every odd number below ten million finds no other. It is the closest anyone has come to an odd perfect number, and what it shows is how an odd perfect number would have to be built.
Probability
Every pair side by side, once
Seat an odd number of guests at round tables for as many nights as it takes, the same table sizes every night, so that every two guests sit side by side on exactly one night. For a single table a zigzag turned a notch each night does it for any number of guests. For other table plans the answer is almost always yes — and for six guests at two tables of three, nine at tables of four and five, and eleven at three, three and five, an exhaustive search proves it is no.
Topology
Seven points and a knot they cannot avoid
Put seven points anywhere in space and join every pair with a straight segment. There are 360 closed paths that visit all seven points once each, and at least one of them is knotted — however the points are placed. The reason is a parity, as it was for six points and a linked pair: a number read off each path's knot adds up, over all 360, to something odd. Six points are not enough; seven always are.
Algebra
Five-eighths of the pairs, and no more
Pick two symmetries of a square at random and do them in both orders: forty times in sixty-four the result is the same. No group that fails to commute does better. The reason is a count of pairs that turns into a count of conjugacy classes, and a two-line argument about the centre that caps the answer at five-eighths — reached by the square and the quaternions, approached from above by nothing, and approached from below by groups that commute a little more than half the time.
Applied
What the agenda leaves standing
Ask for a rule that settles each question from the votes on that question, follows a unanimous court and never contradicts itself, and search every such rule for three judges. On a ranking of three options, three survive: one dictator per judge. On two premises and their conjunction, seven survive: every rule in which a fixed set of judges must all agree. On a chain of thresholds, a hundred and twenty-nine, majority among them. The difference is not in the rules. It is in which answers force which, and whether that forcing ever runs back.
Computation
Every ordering once, around a cycle
No cycle can show every ordering of three symbols as a window of three: a window holding each symbol once forces the next symbol to repeat the one just dropped, so the sequence has period three and shows three orderings of six. Two repairs work. Write each ordering by its first two entries and the transitions form a balanced graph, so Euler's theorem hands over the cycle at once. Or add a fourth symbol and ask only that each window keep a different relative order — which works too, but no graph explains why.
Topology
Seven graphs that must link
Six points joined in every way cannot be placed in space without two disjoint triangles hooking together. Trade any triangle for a three-pointed star, or a star back for a triangle, and the property survives; doing it in every possible way from K₆ reaches exactly seven graphs, the Petersen graph among them, and stops. Every placement of every one of them links, by the same parity count. Remove any edge from any of them, and placements that link nothing appear at once. The seven are the whole answer: a graph must link exactly when it contains one of them.
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.
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.
Applied
Prices for things wanted only together
When every buyer wants one thing, there are always prices at which everyone is content with what they get. Let one buyer want two things together and there may be none — and whether there are is decided exactly by whether the market's best fractional allocation beats its best whole one.
Discrete
The symmetric graphs no tour can close
Take the words of five places with two ones and join two when they share no one. The ten words look exactly alike to the graph, and no closed tour runs through them — because every way of leaving out one edge at each word leaves two pentagons. Only four connected graphs this symmetric are known to fail like that, and nobody knows whether a fifth exists.
Geometry
Three sides and four are proved
Among all shapes of a given area, the disc has the smallest lowest eigenvalue. Among triangles it is the equilateral one, among quadrilaterals the square — both proved by sliding chords to an axis. For five sides the regular pentagon wins every computation, every nudge raises its value by the square of the nudge, and there is still no proof.
Topology
Seven points split three ways
Any seven points in the plane can be divided into three groups whose convex hulls share a point, and six points in general position never can. The theorem is Helge Tverberg's; its topological version, in which straight lines may bend, is true when the number of groups is a power of a prime and false otherwise — and the proof that decides which is the same antipodal argument that halves a sandwich.
Logic
The machines that need a reason never to stop
Run every three-state machine on a blank tape and the ones that halt announce themselves: the longest stops after 21 steps. The work is in the others. Each needs a reason it will never stop, and four simple kinds of reason settle all but 27 of them — machines that sweep back and forth over a growing tape and defeat every check that looks for a repeat.
Number
The race that makes ζ(3) irrational
Roger Apéry's 1978 proof that the sum of the reciprocal cubes is not a fraction comes down to a race between two numbers. A whole-number multiplier grows by a factor of ten every 0.79 steps; the gap it multiplies shrinks by a factor of ten every 0.65. The gap wins, by a margin of about seventeen per cent, and that margin is the whole proof.
Algebra
The flattest polynomials of signs
A polynomial whose coefficients are all +1 or −1 has average size √n on the unit circle. Keeping it near √n everywhere is the problem Littlewood posed: the Rudin–Shapiro polynomials never exceed √2 times it, searching every sign pattern up to length 22 finds the best are the Barker sequences, and whether the maximum can come arbitrarily close to √n is still open.
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.
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.