What it costs to find the point that stays put

A map that offers a choice ended where every essay on Brouwer’s theorem eventually ends. The existence of the fixed point is settled: any continuous map of a disc or a square into itself leaves some point where it was. What remains is producing the point. A theorem that says a point exists and gives no way to find it is useful for proving other things exist — equilibria, fair divisions — and useless to anyone who wants the equilibrium.

Three colours force a triangle had already supplied a way. Sperner’s lemma, which proves Brouwer’s theorem, comes with a corridor: label the corners of a fine triangulation by where the map pushes them, enter through a doorway on the boundary, and walk through doorways until reaching a triangle that carries every label. That triangle sits on an approximate fixed point. The corridor always ends, and that essay noted what it does not say: how long the corridor is. This essay measures it, finds a map on which it is very long, and finds a different procedure that does not care — and then asks how much better any procedure can do.

The corridor, on a gentle map #

A map $f$ of the square into itself moves each point $x$ to $f(x)$, and the displacement $f(x) - x$ is an arrow from where the point is to where it goes. A fixed point is exactly a place where the arrow has length nought. Near the edge of the square every arrow points inwards or along the edge, because the map does not send anything outside.

Read the map at the corners of a grid and colour each corner by the direction of its arrow: red if it points into the first third of the circle, blue for the second, green for the third. A small triangle whose three corners carry all three colours has arrows pointing in three directions spread round the circle, and if the grid is fine enough the arrows inside it, which vary continuously, must pass through nought somewhere close. Finding a fixed point to the precision of the grid is finding a three-coloured triangle.

The corridor finds one. A doorway is an edge whose two ends are red and blue. Enter the square through a doorway on its boundary; inside, the triangle entered has a third corner, and either it is green — a three-coloured triangle, and the walk is over — or it is red or blue, in which case exactly one of the triangle’s other two edges is again a red-blue doorway, and the walk leaves through it. Every triangle has at most two doorways, so the walk never branches and never revisits a triangle, and since the number of red-blue doorways on the boundary is odd, at least one entrance leads to a three-coloured triangle rather than back out.

On the gentle map in the figure, which simply pulls every point a little towards the fixed point, the corridor is nearly straight: it crosses 44 triangles and reads the map at 100 of the 1,089 corners. That is the procedure Herbert Scarf turned into the first general algorithm for fixed points and economic equilibria in 1967, and that Lemke and Howson had used three years earlier for equilibria of two-player games. On a gentle map it is cheap, because the corridor goes roughly straight from the edge to the point, and so reads a number of corners proportional to the grid’s side.

A map that spirals #

The right-hand panel shows a map with exactly the same fixed point that sends the corridor on a much longer walk. Near the edges it is identical to the gentle map. Inside a circle about the fixed point, the direction of the displacement turns as the circle is crossed: twice round the full circle between the circle’s edge and the fixed point. The corridor runs along the boundary between two colour bands, and the bands now spiral, so the corridor spirals too. It crosses 148 triangles and reads 204 corners.

Nothing about this map is pathological. It is smooth, it maps the square into itself, and it has a single fixed point; the twisting is a rotation of each arrow by an angle that grows steadily with the distance from the fixed point, and stops growing at the circle. Outside the circle — 644 of the 900 arrows drawn — it agrees exactly with the gentle map. A reading taken there reveals nothing about what happens inside.

The corridor, though, has no choice about where to walk. It must follow a red-blue boundary, and the boundary goes where the map’s direction goes. Every turn of the map is a lap of the corridor.

A twist no invariant can see #

By every topological measure, the twisted map’s fixed point is the same as the gentle one’s. Walk a small circle round it and the arrow turns once, in the same direction, as the arrows round a zero of a field on a sphere that cannot be combed flat do: its index is $+1$. The twisting rotates each arrow by an angle that depends only on the distance from the fixed point, so going once round a circle of fixed radius adds the same angle at every point of it, and adds nothing to the turning. The fixed point counts once, the boundary of the square winds once, and every invariant the theorem rests on is unchanged.

That is exactly why the twisted maps are the hard ones. Topology guarantees the fixed point through an invariant that cannot see the spiral, so it cannot steer a search through the spiral either. A procedure that reads the map learns the arrow’s direction where it reads and nothing about the directions in between, except that they change continuously. The corridor uses its readings well when the colour bands are straight and badly when they wind, because it is committed to following a band. The gap between a guarantee and a procedure is familiar from existence proofs like the one about six people at a party, which name no instance; here the gap has a size, and the size can be counted in readings.

Each turn is a lap #

On a grid 128 squares to a side, each extra turn adds about 250 readings to the corridor — roughly the length of one lap of the spiral at that resolution. With no turns it reads 395 corners; with eight, 2,383. Eight turns is about as tightly as this grid can show them: the arms of the spiral are then under five grid squares apart, and a coarser reading would no longer see the turning at all. That limit is itself informative. A finer grid can show more turns, and a map can always be twisted as tightly as the grid can resolve, so the number of turns a map can hide grows with the grid’s side.

That gives the corridor a worst case. If the number of turns grows in proportion to the grid’s side, each lap is proportional to the side, and the number of laps is proportional to the side, so the corridor reads a number of corners proportional to the square of the side — a fixed share of the whole grid. On such maps following the corridor is little better than reading every corner.

The flat line in the figure is a different procedure, which reads exactly 879 corners whatever the turning.

Halving by winding number #

On a line there is a much faster way to find a fixed point than walking towards it. A continuous map of an interval into itself has a displacement that is positive or nought at the left end and negative or nought at the right, and the intermediate value theorem says it is nought somewhere between. Evaluate it at the midpoint, keep the half whose ends still have opposite signs, and repeat: each reading halves the interval, and $\log_2 n$ readings locate the point to within $1/n$.

In the plane a sign is not enough. A displacement is an arrow, not a number, and the statement that corresponds to “opposite signs at the ends” is that the arrow turns once round as the boundary of a region is walked: the winding number of the displacement around the boundary. A loop that cannot be pulled tight is the reason it is a reliable test. If the arrow winds once round the boundary of a rectangle, the arrow cannot be nought nowhere inside, since a non-vanishing arrow field on a rectangle could be shrunk to a constant and would wind nought times. For a map of the square into itself the arrows on the boundary all point inwards, and they wind exactly once.

So halving works, with winding numbers in place of signs. Read the displacement all round the square and count how many times it turns; cut the square in half, read along the cut, and count the winding round one half; keep a half that still winds once; repeat until a single grid square is left.

The cost is no longer a logarithm, because a winding number cannot be read at a point; it has to be read round a closed curve. The first boundary is four sides of $n$ readings, the first cut another $n$, the next cut $n/2$, then $n/2$ again, then $n/4$, and so on: about $7n$ in all. On the 64-grid in the figure it reads 433 corners, almost all on the first few cuts, and it does not care at all what the map does between the cuts: the turning inside the circle is read only where a cut happens to cross it, and the winding of the cut rectangle accounts for all of it at once.

The three costs together #

Reading every corner costs $n^2$ — 263,169 readings at $n = 512$. The corridor on the gentle map costs about $3.1n$: the cheapest of all, because a corridor reads only the corners it passes and goes nearly straight. On the twisted maps it grows like $n^{1.89}$, close to the $n^2$ the laps predict, and reaches 21,069 readings at $n = 512$. Bisection costs about $7.0n$, 3,563 readings at $n = 512$, on the gentle map and the twisted ones alike; its two lines lie exactly on top of each other.

So neither procedure dominates. On a map known to be gentle the corridor is twice as cheap as bisection. On a map that might be twisted, bisection is the safe choice: its cost does not depend on the map at all, only on the grid. Its guarantee is that of a procedure that ignores the map’s details, and its price is the readings along every cut, including the many that turn out not to matter.

No method does fundamentally better #

Bisection’s $7n$ is not obviously the best possible. Michael Hirsch, Christos Papadimitriou and Stephen Vavasis showed in 1989 that, in the plane, it is the best possible up to the constant: any procedure that locates a fixed point to within $1/n$ by reading the map — choosing each reading in the light of all the earlier ones, however cleverly — must in the worst case read it on the order of $n$ times. The proof builds maps like the twisted one, hiding the fixed point at the end of a long, thin path along which the map’s direction changes, in such a way that a reading reveals only where the path is not. In three or more dimensions they proved that the number of readings needed grows like a power of $n$ that rises with the dimension, and Xi Chen and Xiaotie Deng showed in 2005 that for the corresponding problem on a grid $n$ points to a side in $d$ dimensions the answer is exactly of order $n^{d-1}$ — the size of the boundary of the box, which is what bisection reads.

The contrast with the line is the whole point. In one dimension the answer is $\log_2 n$, because a sign can be read at a single point and halving needs one reading per step. In the plane the corresponding information — a winding number — lives on a curve, and reading a curve costs as many readings as it has points. The fixed point exists for exactly the topological reason that makes it expensive to find: the guarantee is a statement about how the arrows on a whole boundary wind, not about any single arrow.

This is also why Brouwer’s theorem resists being made constructive in the analytical half of its proof. A grid fine enough to locate the fixed point to within $1/n$ has to be read at about $n$ places at least, so locating it exactly would take infinitely many readings, and no procedure that reads the map finitely often can output the exact point. Where the fixed point escapes showed that the theorem’s hypotheses cannot be weakened; this is a different kind of limit, on what can be learnt from the map rather than on what is true of it.

When the map shrinks #

There is one large class of maps on which finding the fixed point is easy, and a map that shrinks everything described it. If every distance is multiplied by at most a factor $\lambda$ smaller than one, simply applying the map over and over converges to the fixed point, and each application shrinks the distance to it by $\lambda$. The number of applications needed is about $\log(1/\varepsilon)/\log(1/\lambda)$ — no grid and no search.

At $\lambda = 0.5$ it takes eight applications. The number grows like $1/(1 - \lambda)$ as the factor approaches one: 523 at $\lambda = 0.99$, 5,250 at $\lambda = 0.999$, past bisection’s cost once $1 - \lambda$ falls to about 0.002. And at $\lambda = 1$ the map in the figure is a pure rotation about its fixed point. It still has the fixed point — Brouwer’s theorem does not need any shrinking — but iterating it does nothing useful at all: a starting point circles the fixed point for ever at its original distance.

So the two theorems sit at opposite ends of the same scale. The contraction principle buys a fast, simple algorithm with a strong hypothesis; Brouwer’s theorem asks for almost nothing and gives a point that can only be found by search, at a cost bounded below by the size of a boundary. Every map in between — shrinking a little, or shrinking only on average — has its own cost somewhere between the two.

Still open: the best constants, and the cost when the map can be asked more #

The order of the cost is known in every dimension for maps that can only be read; the constants are not. Bisection by winding number in the plane reads about $7n$ corners, the lower bound is a smaller multiple of $n$, and the best constant is not known. In higher dimensions the gap between what algorithms achieve and what is proved necessary is wider for maps that are smooth rather than merely continuous, since smoothness limits how tightly a map can twist and so how well it can hide its fixed point.

For maps that shrink distances only slightly, the cost of $1/(1-\lambda)$ applications is not the best possible. Methods that use each reading to cut away a region that cannot contain the fixed point, in the manner of the ellipsoid method, have been shown to need a number of readings that grows with the logarithm of the accuracy rather than with $1/(1-\lambda)$, in a fixed dimension; how the best cost depends on the dimension and on $\lambda$ together, and where exactly the change to Brouwer’s much higher cost happens as $\lambda$ reaches one, are active questions.

The remaining question is the one the previous essay raised about games. Finding an equilibrium is finding a fixed point of a map that is given not as a black box to be read, but as a formula — a table of payoffs — that a procedure can inspect in full. The lower bounds here do not apply to that setting, because a procedure that reads the formula might find a shortcut no amount of reading the map would reveal. Whether such shortcuts exist is the question of whether a parity argument like Sperner’s can be cashed in quickly when the whole map is in hand, and it is believed, but not proved, that it cannot.