Counting the same thing twice — page 10
Analysis
An area measured by walking round it
A surveyor's instrument from 1854 measures the area of any shape on a map by having its pointer steered once round the boundary; a small wheel rolls and slides, and its reading, times the length of one arm, is the area. Nothing touches the inside. The reason is that area can be written as an integral over the boundary — Green's theorem — and the instrument is that integral built in brass. Walk a curve that crosses itself and the same integral counts some regions twice.
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.
Discrete
The fewest triangles an edge density allows
Half of all possible edges can be drawn without a single triangle. One more, and triangles appear — not one but several at once. Push the density further and the question becomes a curve: for every share of edges, the fewest triangles a large graph can hold. The answer is a string of scallops, touching a simple parabola at the densities of the balanced multipartite graphs and bulging above it between them. It was guessed in the 1980s and proved in 2008 by a method that turns counting into positive-definite matrices.
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
Six numbers that need five pentagons
In 1638 Fermat wrote that every whole number is a sum of three triangular numbers, four squares, five pentagonal numbers, six hexagonal numbers, and so on for every polygon — and that he had a proof he would not write down. The claim is true; Cauchy proved it in 1813. What the claim hides is how unequal the cases are. Triangles and squares need their full count infinitely often. For pentagons, only six numbers ever need all five — 9, 21, 31, 43, 55 and 89 — and from hexagons on, two apiece.
Probability
Drawn without putting back
Every concentration bound on this shelf assumes the draws are independent. A real sample is not: a pollster does not ring the same person twice, and every ball taken from an urn changes what is left in it. The dependence runs the helpful way. Wassily Hoeffding proved in 1963 that a sample drawn without replacement is at least as concentrated as one drawn with it, for every convex measure of spread at once — and the variance falls by an exact factor that reaches zero when the whole urn is taken.
Algebra
Almost none of the roots are real
Pick the coefficients of a polynomial of degree a thousand at random, each one an independent draw from the bell curve, and ask how many of its thousand roots are real. The answer is about five. Mark Kac found in 1943 that the average grows only like (2/π) ln n, and the reason can be read off the real line itself: the real roots crowd towards +1 and −1 and spread evenly on a logarithmic scale of distance from them.
Applied
Tours within half again of the best
Nobody can find the shortest tour through many cities quickly, but a tour at most half as long again as the best can be built in a few steps: the shortest tree, a cheapest pairing of the cities where the tree branches oddly, an Euler circuit, and shortcuts. Nicos Christofides found it in 1976, and for forty-five years nobody could guarantee better. A strip of cities shows the half is really lost, and Laurence Wolsey's reading of the same argument shows it bounds the linear programme too.
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.
Logic
How many gates a truth table needs
Every truth function can be built from gates, and the natural measure of a function is the fewest gates that build it. For three letters the whole answer can be computed: no function needs more than four. For n letters, a count shows that almost every function needs about 2ⁿ/n gates, and a construction shows that none needs more. And for any function anyone can actually write down, the best proof in fifty years says it needs 3.1n.
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.
Analysis
The exponent a staircase shares with its set
The Cantor function rises from nought to one on a set of length nought, and it is Hölder continuous with exponent log 2/log 3 — the same number as the dimension of that set. It is not a coincidence: both numbers say that an interval of width r carries mass r to the power 0.6309, and that one inequality proves the dimension and the smoothness at once. Tilt the weights of the construction and the two numbers separate, which shows exactly what the coincidence was measuring.
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.
Geometry
How many pairs can be one apart
Place n points in the plane and count the pairs exactly one unit apart. A square grid with its spacing as the unit gives two pairs per point; the same grid with the unit chosen as a length it realises in many directions — the square root of 5, of 25, of 65, of 325 — gives three, five, eight. Counting points on circles caps the total at a constant times n to the four-thirds. Between that cap and the grids the truth has not moved since 1984, and at every size anyone can draw, the two look alike.
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.
Logic
The formula that cannot share
A circuit computes the parity of n letters with a chain of n − 1 exclusive-or gates. A formula in and, or and not, which may use each result only once, needs n² letters at least — a bound Khrapchenko proved by counting the cube's edges between true and false — and exhaustive search over every formula of four letters finds parity sitting exactly on it.
Probability
A walk that follows its own footsteps
Let a walk step up with probability equal to the share of up-steps it has taken so far, and every count of up-steps after twenty steps is exactly equally likely. The walk leaves along a straight line at a speed chosen by its first few steps, and although it is expected to come back to its start infinitely often, almost every run comes back only a few times.
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.
Topology
Counting targets when the sensors make mistakes
Add up the Euler characteristics of the regions where sensor counts are high and the answer is exactly the number of targets — until one sensor misreads. Each wrong reading is a new piece or a new hole, so the error grows with the number of sensors instead of averaging away. Smooth the readings and count each piece and hole by how long it survives as the threshold is lowered, and the count comes back exactly, with half the readings wrong, at the price of having to know how small a real feature can be.
Applied
Two auctions that earn the same
In one sealed-bid auction the winner pays its own bid; in the other it pays the second-highest bid. Bidders behave completely differently — in the second they bid what the object is worth to them, in the first they shade their bids down by exactly a fraction — and the seller's revenue is spread differently. Yet the seller expects to collect precisely the same amount, (n − 1)/(n + 1) for n bidders with values spread evenly, and so does an auction in which everybody pays. The equality breaks the moment bidders dislike risk, and it says nothing about how much a reserve price can add.
Number
Three unit fractions for every four over n
Two neighbouring fractions in the tree always differ by a unit fraction, so stepping down the tree writes any fraction as a sum of them — four over n in at most four steps. Erdős and Straus asked in 1948 whether three always suffice. Three identities settle every n except those leaving remainder 1 on division by 24, a search settles every one anyone has tried, and nobody has a proof.
Topology
Pieces minus holes on a random surface
Cut a random landscape at some height and the region above it breaks into pieces with holes in them. How many pieces, and how many holes, has no formula. Their difference does: the average Euler characteristic of the region above height u is a constant times u multiplied by the bell curve at u, exactly, for every smooth Gaussian surface — because the Euler characteristic is a sum of peaks, pits and saddles, and the average number of those can be computed point by point.
Computation
The boards on which every light goes out
In Lights Out, pressing a light toggles it and its neighbours, and the goal is to turn every light off. Over the field with two elements the puzzle is a system of linear equations, and whether every pattern can be cleared depends only on whether one matrix is invertible. On a 3 × 3 board it is; on 5 × 5 a quarter of patterns can be cleared; on 39 × 39 one in four billion. Which sizes fail is decided by a common factor of two polynomials.
Algebra
The signs no completion can change
A quadratic in several variables can be completed square by square in many orders, and each order hands back different coefficients. What no order changes is how many come out positive and how many negative — and that count, read off a completion of A − tI, says how many eigenvalues lie below t without finding a single one.