Throwing things away — page 3

Topology

The symmetries a cover has of its own

A covering space can be shuffled without disturbing anything below it, and how many ways there are is decided by the subgroup it corresponds to. When there are as many symmetries as sheets the covering is called regular, and that is the same statement as the subgroup being normal.

Geometry

Six points on a conic, and the line they share

Put six points on an ellipse, join them into a hexagon, and extend each pair of opposite sides until they meet. The three meeting points always lie on one straight line. The statement uses no length, no angle and no focus — which is why it holds for every conic at once, and why a straightedge alone can draw the curve through any five points.

Geometry

Equal diagonals in a curved quadrilateral

Two ellipses and two hyperbolas sharing the same foci cut out a four-sided region with curved sides and no symmetry to speak of. Its two diagonals are nevertheless exactly equal. The reason is a stretch that carries one ellipse onto the other and moves every pair of points so that crossed distances match — a property only confocal curves have.

Logic

The sentence between a premise and its consequence

When one formula implies another, something sits between them written only in the words the two have in common: a sentence the first implies and that implies the second. A refutation of the first together with the denial of the second hands such a sentence over, and every possible one lies between a strongest and a weakest that can be computed outright.

Probability

A sum stopped early still says something

Inclusion–exclusion corrects an overcount, then the correction's overcount, and so on to the end. Stop after any number of terms and the result is not merely an approximation: after an odd number it is too high and after an even number too low, always. So two or three terms bracket an answer whose full sum is out of reach — as long as the events being counted are rare.

Topology

Every word driven to a normal form

The classification is usually met as a statement: two numbers name the surface. The proof is a procedure — a short list of cut-and-reglue moves that drive any gluing word to one of the standard forms, with a measure that never rises to say why the procedure stops.

Discrete

A walk that splices in its own detours

Euler proved that a walk crossing every bridge once needs every landmass to have an even number of bridges, and then stated, without proof, that this was enough. The missing half took 137 years, and it is not an argument but a procedure: walk until stuck, notice that stuck can only mean home, and splice in a detour from anywhere with edges left. The procedure never fails, and the reason fits in one sentence about arriving and leaving.

Analysis

Uniform, except on a small set

The functions xⁿ settle on their limit at every point and never uniformly — the trouble is all in a strip next to 1. Throw the strip away and the convergence is uniform on what is left, however thin the strip. Egorov proved that this always happens on an interval, Lusin proved the matching fact about a single function, and a bump sliding off along the whole line shows why both need a set of finite length to start from.

Dynamics

Chaos on a set nobody lands on

Stretch the interval by three and fold it, and a third of it lands outside. Almost every starting point wanders chaotically for a few steps and then leaves for good; the points that never leave form a Cantor set of no length, on which the map is as chaotic as any map can be. How fast points escape, how fast they are stretched, and how thin the surviving set is are three numbers tied by one equation: the dimension is one minus their ratio.

Algebra

Discs that fence in the eigenvalues

Draw one disc for each row of a square matrix, centred on the diagonal entry, with a radius equal to the sum of the sizes of everything else in that row. Every eigenvalue lies inside one of the discs, and a group of discs set apart from the rest holds exactly as many eigenvalues as it has discs. Nothing is solved to find them.

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.

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.

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.

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.

Probability

What a jump costs evenly spread points

Scrambled Sobol' points integrate a smooth function with an error that falls like N to the power −3/2. Put a jump in the integrand along a tilted line and the exponent halves, to −3/4, because about √N of the N boxes the points fill are cut by the jump and each of those is left to chance. A jump along an axis costs almost nothing, the cost grows with the length of the jump and the dimension, and integrating across the jump before sampling gives the whole rate back.

Geometry

A skeleton that ignores small teeth

The medial axis of a shape grows a branch to every bump on its outline, however small, so a scanned shape has a skeleton made mostly of noise. Keep only the points of the axis whose nearest boundary points are spread across a circle of radius at least λ, and the branches to bumps smaller than about 2λ disappear while the real skeleton stays. That λ-medial axis moves only a little when the outline wobbles by much less than λ — and the price is λ itself, a size below which a feature is declared not to exist, which can even cut a shape's skeleton in two.

Topology

What homology forgets about a loop

Let the letters of a loop commute and the loop group of a space becomes its first homology group: a loop now records only how often it went round each hole. What is thrown away is exactly the loops that bound a surface. On the figure eight that is nearly everything — of the loops of sixty letters that homology calls nought, about one in 6,700 is a loop that actually shrinks.

Logic

What a formula keeps when letters are fixed

Fix half the letters of a formula at random and most of its leaves become irrelevant: on the sixteen-leaf formula for the parity of four letters, two fixings leave four. How fast formulas shrink under random fixings is the whole engine behind the best lower bounds anyone has proved for formula size — Subbotovskaya's 3/2 in 1961, Håstad's 2 in 1998 — and the reason that engine stops at n³.

Topology

A cut that gets sharper as the map gets lazier

Iterating a map that shrinks distances by 0.9999 takes 141,254 steps to reach its fixed point to a millionth. Cutting takes six: read the map at one point, and the fixed point must lie on the far side of the line halfway between the point and its image. The cut gets better exactly where iteration gets worse, because a map that barely shrinks puts its fixed point almost on every such line.