Opposite labels that have to meet

Two opposite points that agree twice stated a version of the antipodal theorem with no continuity in it: a symmetric mesh, four labels, and a rule about opposite corners. That version, Tucker’s lemma, deserves more than a statement, because its proof is a count that can be drawn, and the count explains why the continuous theorem is true rather than merely that it is.

Take a square, cut it into a grid of small cells, and split each cell along its rising diagonal into two triangles. The cuts are symmetric under turning the square through a half-turn about its centre, which sends every point to its opposite. Label each corner of the grid with one of four labels, $+1$, $-1$, $+2$ or $-2$, and impose one condition: opposite points on the boundary carry opposite labels. Inside, the labels are free.

Tucker’s lemma says that some edge of the grid then joins a label $+i$ to the label $-i$ — a complementary edge. The figure has three, clustered together on the left. Nothing about the interior labels was chosen to make that happen, and it would happen however they were chosen.

Where labels come from #

The labels in the figure were not written by hand. At each vertex a vector field $f$ takes a value in the plane, and the label records which coordinate of that value is larger in size, and with what sign: $+1$ if the first coordinate dominates and is positive, $-1$ if it dominates and is negative, and $\pm 2$ likewise for the second.

The labels divide the plane of values into four cones, each a quarter-turn wide, and opposite labels are opposite cones. Two vectors in opposite cones point at least a right angle apart. So if the values at the two ends of an edge are $u$ and $w$, and they lie in opposite cones, then $u \cdot w \le 0$ and

$$|u - w|^2 = |u|^2 + |w|^2 - 2\,u\cdot w \ \ge\ |u|^2 + |w|^2.$$

Both values are smaller than the change in $f$ along the edge. A complementary edge is a place where the field is nearly zero, and nearly means within the amount $f$ can change across one edge of the grid. The combinatorial statement about labels is a statement about approximate zeros in disguise.

The boundary condition has a meaning in these terms too. On the boundary the field used here is odd, $f(-v) = -f(v)$, so opposite points take opposite values, which lie in opposite cones and get opposite labels. Tucker’s lemma therefore says that a field odd on the boundary of a square has an approximate zero somewhere inside, at every scale of grid.

Quarter-turns round a diamond #

The proof is a count of turning, and it is drawn best by putting the four labels at the corners of a diamond: $+1$ east, $+2$ north, $-1$ west, $-2$ south. Opposite labels are opposite corners.

Walk round the boundary of the square and, at each vertex, move to the corner of the diamond its label names. Between neighbouring vertices the label either stays, moves a quarter-turn to an adjacent corner, or jumps to the opposite corner. A jump to the opposite corner is a complementary edge, so suppose there are none. Then the walk turns by quarter-turns, and after going all the way round the square it has turned some whole number of times round the diamond.

That number is odd. Halfway round the boundary the walk has reached the point opposite its start, whose label is the opposite of the starting label — so the first half of the walk has turned through a half-turn plus some whole number of full turns. The second half visits the opposites of the first half’s vertices, in order, so it repeats the first half’s turning exactly. Twice an odd number of half-turns is an odd number of full turns.

Now count the same turning a different way. Each small triangle has a boundary of three edges, and walking round it turns the diamond walk by some amount. Add these amounts over every triangle: each interior edge is walked once in each direction by the two triangles on either side and cancels, leaving exactly the turning round the outer boundary. But a triangle with no complementary edge can hold at most two labels that are not opposites, since any three of the four labels include an opposite pair. Its walk stays on one side of the diamond and turns zero times.

So if there were no complementary edge anywhere, the total would be a sum of zeros and also an odd number. That is impossible, and so some edge must be complementary. The boundary condition supplies an odd amount of turning, and only a triangle holding opposite labels can absorb it.

This is the argument that proved three colours force a triangle in Sperner’s lemma, with the parity carried by windings instead of by doors, and it is the discrete shadow of the winding count that made opposite readings agree. There the equator’s differences wound an odd number of times round zero; here the boundary’s labels wind an odd number of times round the diamond.

One dimension down, and one up #

The lemma has a version on a line, and it is a familiar fact. Cut a segment into small pieces and label every division point $+1$ or $-1$, with the two ends labelled oppositely — the boundary condition, for a segment whose boundary is two points. Then some piece has $+1$ at one end and $-1$ at the other. Walking from one end to the other, the label has to change from $+1$ to $-1$ somewhere, and it can change only across a piece. That is the discrete form of the sign change that found the line halving two shapes: a quantity that reverses sign between opposite positions must pass through zero.

The square version is that fact with the counting of sign changes replaced by the counting of turns. On a segment, the number of places where the label changes is odd, because the walk starts at one sign and ends at the other; in the square, the boundary’s winding is odd, because the walk ends at the opposite of where it was halfway. In both cases an odd count cannot be absorbed by the pieces that avoid opposite labels, and so one piece must hold them.

In three dimensions the labels are $\pm 1$, $\pm 2$ and $\pm 3$, the corners of an octahedron, and the triangles become tetrahedra. The boundary is a sphere, a walk becomes a covering of the octahedron’s surface, and the odd number is the degree of that covering — how many times the boundary’s labels wrap round the octahedron. The proof is the same count in every dimension, and in every dimension the only ingredient that makes it odd is the boundary condition.

Reading it on a globe #

The weather version of the antipodal theorem becomes a Tucker labelling as soon as it is measured at finitely many stations. Place stations on a mesh symmetric under swapping opposite points of the Earth, and at each one compute the difference between its temperature and the temperature at its opposite station, and the same for pressure. Label each station by the larger difference, with its sign. Opposite stations have exactly opposite differences, so they get opposite labels, and the lemma finds two neighbouring stations whose labels are $+1$ and $-1$, or $+2$ and $-2$.

At such a pair both differences are small — no larger than the change in the readings between neighbouring stations. So the lemma, applied to a finite network of thermometers, says that some opposite pair of stations nearly agree on both readings, to within the resolution of the network. That is all a finite measurement could ever say, and it is exactly what the lemma says: the exact agreement belongs to the continuous idealisation, and the approximate one is what a real mesh delivers.

The same reading turns the fixed point that always stays put into Sperner’s lemma, with a triangle of three colours in place of a square of four labels. The two lemmas are siblings: Sperner’s counts doors into a triangle whose corners are fixed, Tucker’s counts turns round a square whose opposite edges are tied.

The condition that does all the work #

Every step of that proof used the boundary condition exactly once, to make the boundary’s turning odd. Drop it and nothing forces anything.

This labelling has $+2$ and $-2$ in it, both kept well apart by a band of $+1$. Its boundary walk goes from $+1$ to $+2$ and back, then to $-2$ and back, and ends having turned zero times. Zero is even, the triangles have nothing to absorb, and no complementary edge is needed. The field behind it never vanishes in the square, which is the continuous statement of the same fact.

The lemma is therefore sharp in the way the antipodal theorem is sharp. What forces a zero is not the variety of the labels, nor the size of the grid, but the single symmetry on the boundary. The halving line needed a quantity that reversed sign when the line was turned over; the square needs labels that reverse when the point is turned over.

Finer grids, and the continuous theorem #

A complementary edge is an approximate zero, and the approximation is set by the size of the grid. Refining the grid improves it.

At every size there is a complementary edge, and at every size both of its endpoint values are within one edge’s change of zero. The distances do not halve exactly as the cells do — $0.255$, $0.143$, $0.093$ against cell widths of $0.33$, $0.17$ and $0.08$ — because the farthest edge in each cluster sits wherever the labels happen to switch, not at the zero itself. But the cluster is always a few cells wide, so it shrinks with the grid, and nothing prevents taking the grid as fine as wished. As the grid shrinks the edges shrink, and a sequence of shrinking edges in a closed square has a limit point. At that point the field is exactly zero, because it is continuous and its values at nearby points were arbitrarily small.

That derivation is the whole of Borsuk–Ulam in two dimensions. Given a continuous map $g$ from the sphere to the plane, the difference $f(v) = g(v) - g(-v)$ is odd; flattening one hemisphere onto the square turns it into a field on the square that is odd on the boundary, and Tucker’s lemma plus a limit gives a point where $f$ vanishes — a pair of opposite points where $g$ agrees. The continuous theorem is what the finite lemma says at every scale at once. The implication also runs backwards: Borsuk–Ulam proves Tucker’s lemma, by building a field from the labels. So the two are equivalent, one stated with a limit and one without.

Checked at the smallest size #

Because the lemma is finite, it can be checked by exhaustion wherever the grid is small enough.

The two-by-two grid has nine vertices, eight on the boundary in four opposite pairs and one in the centre. Choosing labels for one vertex of each pair fixes its partner, so there are $4^4 \times 4 = 1{,}024$ antipodal labellings, and every one of them has a complementary edge. Dropping the condition allows $4^9 = 262{,}144$ labellings, and $4{,}652$ of those escape. At the larger size, random smooth fields that ignore the boundary condition escape more than a third of the time; those that respect it never do.

The histogram is lopsided in a way worth noting. In these samples odd numbers of complementary edges are more common than their even neighbours. That is a tendency of the smooth fields sampled, not a theorem about labellings — even counts occur throughout, and the lemma promises only one edge. The version with a parity guarantee is Ky Fan’s generalisation of 1952, which counts a differently defined kind of simplex, those whose labels alternate in sign, and proves their number odd.

A proof that finds, slowly #

The winding argument proves existence without pointing. Robert Freund and Michael Todd gave a constructive proof in 1981: start at the centre of the square and follow a path of triangles, each step decided by the labels of the triangle in hand, until the path runs into a complementary edge. Every step is determined, the path cannot cycle, and it must end at a complementary edge because nothing else can end it — the same door-following argument that makes Sperner’s lemma an algorithm.

The path can be very long. For grids described implicitly — by a rule that computes a vertex’s label on demand rather than a list of all labels — James Aisenberg, Maria Luisa Bonet and Sam Buss showed that finding a complementary edge, even in two dimensions, is complete for the class PPA of search problems whose solutions exist by a parity argument. That is the class necklace splitting turned out to belong to, and for a related reason: the proof that necklace splitting is that hard goes through Tucker’s lemma, turning a labelled grid into a necklace. The twelve-by-twelve grid is searched here by checking every edge, which is trivial; the hardness is about grids too large to list.

What a labelled grid cannot show #

Higher dimensions. Every figure is a square. The lemma holds for a symmetric triangulation of a ball in any dimension, with labels $\pm 1, \ldots, \pm n$, and the proof replaces the winding round a diamond by the degree of a map to the boundary of a cross-shaped polytope — the same count one dimension up, with nothing to draw.

The limit itself. The refinement figure shows three sizes and a falling distance. The step from “an approximate zero at every scale” to “an exact zero” is a compactness argument, and compactness is the one ingredient of the continuous theorem that no finite grid contains.

That every smooth field escapes only by breaking the boundary. The random fields that escape all ignore the boundary condition, and the ones that respect it never escape. That pattern across thousands of samples illustrates the lemma; it is the winding argument, not the sample, that makes it certain.

Still open: a fast way to the edge #

Finding a complementary edge is PPA-complete, which says that a fast method for it would give fast methods for every search problem whose answer is guaranteed by a parity argument — Nash-type equilibria among them, and fair necklace splits. Whether any PPA-complete problem can be solved in time polynomial in the size of its description is unknown. It is not even known how PPA relates to the classes around it: whether it is genuinely harder than PPAD, the class of problems guaranteed by a directed path such as Brouwer fixed points, is open, and the belief that neither is easy rests on the failure of every attempt rather than on a proof.

Four labels and a symmetry #

Tucker’s lemma is the antipodal theorem stripped to what makes it work. There is no temperature, no sphere and no continuity — only four labels, a triangulated square, and the requirement that opposite boundary points carry opposite labels. The requirement makes the boundary’s labels wind an odd number of times round the diamond of labels, and a triangle can absorb turning only by holding a label and its negative.

Read with a field behind the labels, a complementary edge is an approximate zero, and a finer grid gives a better one. Every theorem the antipodal argument has produced — the halving line, the agreeing pair of points, the necklace — is this count, taken at every scale at once. The same count also settles a question about colouring that looks as far from spheres as a question can.