The same thing twice — page 14

Topology

Every surface is sewn from pants

A sphere with three holes — a pair of pants — is the smallest piece a surface with two or more handles can be cut into. Every such surface falls apart into them, and the Euler characteristic alone says how many pieces and how many cuts, however the cutting is done. What it does not say is the pattern, and the patterns are counted by drawing each one as a graph: two for two handles, five for three, seventeen for four.

Topology

The fewest corners a surface needs

Build a closed surface from triangles, any two meeting along a whole edge, at a single corner or not at all, and ask for the fewest corners. Two lines of counting give a floor for every surface, in terms of its Euler characteristic alone. The torus meets it with seven, the projective plane with six — and the Klein bottle, which the counting says could be built from seven, cannot, as a search of every possible arrangement shows.

Algebra

Two graphs the eigenvalues cannot tell apart

A graph's matrix has eigenvalues, and they count a surprising amount of the drawing: its edges, its triangles, every closed walk of every length. They do not count everything. A star with four arms and a square beside a lone point have the same eigenvalues exactly, although one of them is in two pieces — and on six points ten of the 156 graphs have a twin of this kind.

Algebra

A hole is a cycle that bounds nothing

A hollow triangle and a filled one have the same three edges and the same loop round them. In one the loop is the edge of something and in the other it is not, and that difference — a cycle that is not a boundary — is what a hole is. Counting holes is rank and nullity applied twice, and the Euler characteristic is what is left when the two applications cancel.

Analysis

A slope for a curve that is no function

The folium x³ + y³ = 3xy loops back over itself, so no formula y = f(x) describes it, and yet at almost every point it has a perfectly good tangent. Differentiating the equation as it stands gives the slope, −(∂F/∂x) ÷ (∂F/∂y), and the only points where that fails are the ones where the curve turns vertical or crosses itself — which are exactly the points where it stops being a graph.

Applied

The corners are the orders of arrival

Line the players up, let each join in turn, and pay each what it adds on arrival: every order gives a split. When a newcomer always adds at least as much to a bigger group, those splits are exactly the corners of the core — so the core is never empty, it is the outline of the orders, and the average over all of them lies inside it. For a group worth the square of its size the outline is a hexagon whose corners are the six orderings of 1, 3 and 5.

Applied

Each user pays for its own last link

Several users must be connected to a source, and the cheapest network that does it is a tree. Dividing its cost so that no group of users would rather build its own looks like a hard search, and it has a one-line answer: each user pays for the link that joins it to the tree on its way to the source. No group is ever overcharged — while the average over orders of arrival, the rule that settles so much else, can charge a pair more than its own connection costs.

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.

Computation

Every power of x that draws a hyperoval

In a plane of order 2^h, the graph of x^k plus two points at infinity is sometimes a hyperoval — as many points as a plane allows with no three in line. Searching every exponent in every plane from order 4 to 4096 finds hundreds that work, and once six symmetries of the problem are applied they fall into exactly the families already known: the conic, the translation curves, Segre's x⁶ and Glynn's two. Whether that list is complete in every order is open.

Discrete

Every point at the average of its neighbours

A planar graph can be drawn without crossings, but finding such a drawing looks like a search. Tutte found in 1963 that it is not: pin one face to a convex polygon, put every other point at the average of its neighbours, and the drawing that results has straight edges, convex faces and no crossings at all — provided no two points can cut the graph apart. It is the position a network of equal springs settles into, and it is also where a random walk expects to leave.

Dynamics

Every window is the whole diagram again

Zoom into one strand of the period-three window of the logistic map and the whole bifurcation diagram is there again — a single value, a fork, a cascade of doublings, chaos, bands and windows — upside down and ninety-seven times narrower. The doublings inside it shrink by Feigenbaum's 4.669, exactly as the originals do, because near the top of its hump the map's third iterate is itself a one-humped map, turned over.

Dynamics

Windows counted like necklaces

The logistic map has one window of period three, two of period four, three of period five, five of period six, nine of period seven — and the sine map, which shares no algebra with it, has exactly the same numbers, in exactly the same order along the parameter. The counts are 1, 1, 1, 2, 3, 5, 9, 16, 28, 51, and they are the number of ways to thread a necklace of beads in two colours.

Geometry

A band of a sphere is a band of its cylinder

Cut a sphere with two parallel planes and the band between them has exactly the area of the band the same planes cut from the cylinder wrapped round the sphere — whatever the band's latitude. Near the equator the sphere's band is wide and nearly upright; near a pole it is narrow and nearly flat; and the two effects cancel exactly. Archimedes proved it, wanted it on his tomb, and it gives the area of the sphere, the only honest way to pick a random point on it, and a map on which no country is the wrong size.

Logic

Closed sets obey the continuum hypothesis

Whether some set of reals is bigger than the whole numbers and smaller than the line is a question the axioms cannot answer. For closed sets it has an answer, found in 1883: strip away the isolated points, again and again, and what is left is either nothing or a perfect set, which is as large as the line — so every closed set is countable or of the line's size. The same answer holds for Borel and analytic sets, and fails to be provable exactly one step further up.

Number

The row that proves a prime

Fermat's little theorem can be fooled: 561 passes it for every base and is not prime. Thread necklaces with a fixed number of black beads instead of any colours at all, and the count becomes a statement about a whole row of Pascal's triangle — every middle entry of row n is a multiple of n exactly when n is prime — which no composite can fake. Written as polynomials it is (x + a)ⁿ = xⁿ + a, and cut down to size it is the first proof that primes can be recognised in polynomial time.

Topology

Two copies of the polygon, cross-matched

The two-sided surface that lies over a one-sided one can be built from the gluing word alone: take two copies of the polygon, one read each way round, glue a letter within the copies when it is used once each way, and across them when it is used twice the same way. The recipe works for every surface at once, doubles every count, and shows that a sphere with k cross-caps is covered by the surface with k − 1 handles — and that among all its connected double covers, exactly one is two-sided.

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.

Algebra

The sums that obey a smaller equation

The twelve non-trivial thirteenth roots of unity satisfy an equation of degree twelve. Split them into three groups of four — the right three groups — and add each group: the three sums are the roots of x³ + x² − 4x + 1, an equation of degree three with whole-number coefficients. Gauss called such sums periods, found one for every divisor of p − 1, and used them to build the seventeen-gon from four quadratic equations.

Algebra

The sums of primitive roots are always whole

Take the roots of unity of order exactly q, raise each to the power n and add them. The answer is always a whole number, it depends on n only through what n shares with q, and as n varies the sums behave like the sines and cosines of a Fourier series — so well that Ramanujan could rebuild the sum of the divisors of any number from them, and prove that their weighted total is nought, a fact that at n = 1 is the prime number theorem.

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.

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.

Dynamics

A rule that remembers one row back

Only six of the 256 elementary cellular automata can be run backwards, and all six are trivial: shifts, copies and complements. Every interesting rule forgets. But make the new row depend on the row before the current one as well — combine the rule's output with it cell by cell — and every rule, rule 30 included, becomes exactly reversible: run forwards, swap the last two rows, run the same rule again, and the starting row comes back cell for cell. Nothing is lost, and yet the patterns still look as disordered as ever.

Logic

A machine that carries one bit

Write three numbers in base two, one above another, and read the columns from the right. Whether the bottom number is the sum of the top two can be checked with one bit of memory — the carry. That two-state machine is the whole of addition, and machines can be combined, negated and made to guess a missing number. So every sentence about whole numbers built from addition can be decided by building a machine for it, and the same machines can also handle 'x is a power of two', which addition alone cannot say.

Logic

There is a relation such that

A graph can be coloured with three colours exactly when there are three sets of its points such that every point lies in one and no edge joins two points of the same set. The sets are a guess; once guessed, the rest is a list of simple checks. Ronald Fagin proved in 1974 that this shape of sentence — 'there exist relations such that' followed by first-order conditions — describes exactly the problems whose solutions can be checked quickly, the class called NP. The central question of computer science is therefore also a question about what sentences can say.