A picture that falls when any nail is pulled
Worth reading first: The group a space has at a point · What homology forgets about a loop.
A picture hangs from a string tied to its two top corners, and the string is laid over nails in a wall. With one nail the string goes over it and the picture hangs; pull the nail and the picture falls. With two nails the obvious thing is to put the string over both, and then the picture survives losing either nail, hanging by the other. The puzzle asks for the opposite: hang the picture on two nails so that it falls if either nail is pulled out — not only if both are. It is not obvious that this can be done at all.
It can, and the answer is one of the central objects of topology in disguise. The group a space has at a point built the group of loops in a space, and the plane with some points removed — the wall with its nails — has a particularly simple one: a loop is recorded by the sequence in which it goes round the nails, clockwise or anticlockwise, and two sequences describe the same loop exactly when one can be cancelled down to the other. The string is a loop; the picture falls when the loop is trivial. The puzzle becomes: find a word that is not trivial, but becomes trivial when the letters for any one nail are deleted. The commutator is such a word, and this essay builds the rest from it, measures how long the string must be, and finds the shortest strings by exhaustive search.
A string is a word
The string runs from one corner of the picture, up into the wall, and back down to the other corner. Since the two corners are held together by the picture’s frame, the string and the frame form a closed loop, and what matters about the loop is how it winds among the nails. The picture can slide; the string can be pulled and loosened; it cannot pass through a nail. So the loop is to be considered up to deformation in the plane with the nails removed — up to homotopy, in the language of a loop that cannot be pulled tight.
Cutting a space to find its group computed the loop group of the plane with points removed: it is the free group on letters, one per point. A loop is written as a word by reading off the passes it makes round each nail, in order: for once round nail clockwise, for once round it anticlockwise, and similarly for , and the rest. Two words describe the same loop if and only if one becomes the other by inserting or deleting adjacent pairs like — once round a nail and straight back — and the free group is exactly what is left when such pairs cancel and nothing else does. In particular and are different loops: going round then cannot be deformed into going round then without crossing a nail.
The picture falls exactly when its loop can be pulled away from all the nails, which is when its word cancels down to nothing. The figure draws the word : once round , once round , then once back round , once back round . No letter sits next to its own inverse, so nothing cancels, and the word is not trivial. The picture hangs.
Pulling a nail deletes a letter
Removing a nail from the wall changes the space: the plane now has one fewer hole. A loop in the old space is still a loop in the new one, and its word in the new free group is obtained by deleting every letter for the removed nail, since a pass round a nail that is no longer there is no pass at all. That deletion is a homomorphism from one free group to another — it respects the joining of words — and the puzzle asks for a word that every one of these homomorphisms kills.
For the computation takes a line each, and the figure sets it out. Pull nail : the word becomes , which cancels to nothing, and the picture falls. Pull nail : it becomes , which cancels too. Two nails, a string that hangs, and a picture that falls whichever nail is pulled.
The word is the commutator of and , usually written , and the reason it works is the reason it is called that. In a group where and commute — where — the commutator is . In the free group and do not commute, so the commutator is not trivial; but as soon as either letter is set to 1, the other commutes with everything left and the commutator collapses. The obvious hanging — over both nails, the word — fails the puzzle for the opposite reason: deleting leaves , which does not cancel, and the picture stays up.
Three nails: a commutator inside a commutator
For three nails, the two-nail solution can be used as a single letter. Let and take the commutator of with the third nail: , where is read backwards with every letter inverted. Written out, it is , ten passes, and the figure draws it on three nails.
Pulling deletes the two letters and leaves , which cancels from the middle outwards. Pulling or turns into nothing, since already falls without either of them, and then is , which cancels. So the picture falls whichever of the three nails is pulled, and hangs while all three are in. Each pass of the string over a nail is also a step in the covering space that every cover is a subgroup built over the punctured plane, and the commutator is the loop that returns to its starting sheet in every two-sheeted cover and still is not trivial. The principle is general: if falls when any of a set of nails is pulled, and falls when any of another set is pulled, then falls when any nail of either set is pulled — because killing either or kills the commutator. Any construction that combines solutions by commutators inherits the property.
Pulling each of three nails
The figure checks the three deletions letter by letter. With pulled the word is ; the two inner pairs cancel, leaving , which cancels. With pulled the same happens with in place of . With pulled the word is , which cancels from the centre out: goes, then , then , then . In each case the cancellation is not a deformation anyone would find by fiddling with a string on a wall, and that is what makes the puzzle hard to solve physically and easy to solve in the group.
The full word, meanwhile, does not cancel at all: it is a reduced word, with no letter next to its own inverse, and a reduced word in a free group is never trivial. That last statement is the theorem doing the real work. It says the picture really does hang — that no clever sliding of the string can get it off three nails that are all present — and it is the content of the claim that the loop group of the punctured plane is free, which cutting a space to find its group derived from Seifert and van Kampen’s theorem.
There is a second thing a hanging must not do: it must not depend on how the nails are arranged. The free group sees only the order in which the string passes the nails, so the same word works with the nails in a row, in a triangle, or scattered over the wall; only the labels matter.
Two ways to build a string for many nails
Nesting commutators one nail at a time works for any number of nails: and so on. But it is wasteful, and the tree on the left of the figure shows why. A commutator has length twice the lengths of and together, so each new nail doubles the whole string built so far and adds two passes. The string for nails has passes: 4 for two nails, 10 for three, 22 for four, 46 for five, and over 98,000 for sixteen. Nail ’s letters, at the bottom of the tree, are doubled once for every nail added after it.
The tree on the right builds the string the other way. Split the nails into two halves, solve each half, and take the commutator of the two solutions. By the principle of the last section, the result falls when any nail of either half is pulled. Each letter now sits under only as many commutators as the tree is deep, which is the number of times the nails can be halved: two levels for four nails, three for eight. If is a power of two, the length satisfies with , so — 16 passes for four nails, 64 for eight, 256 for sixteen, against 98,302 by nesting. Erik Demaine, Martin Demaine, Yair Minsky, Joseph Mitchell, Ronald Rivest and Mihai Pătraşcu gave this construction, and many variations on the puzzle, in 2012.
How long the string must be
The two recipes give upper bounds. Is the halving recipe the best possible, or is there a cleverer word? For small numbers of nails the question can be settled by brute force. Every candidate is a reduced word in the letters and their inverses — any word can be reduced first without changing the loop — and it may also be taken cyclically reduced, with the first letter not the inverse of the last, since the picture’s frame closes the loop and a cancelling pair across the join can be slid round and removed. For each length in turn, the search builds every such word letter by letter, maintaining for each nail the word that would remain if that nail were pulled, already cancelled; it abandons a branch the moment one of those remainders is longer than the number of letters still to come, since no completion could then cancel it.
The answer for two nails is that nothing shorter than the commutator works: 4 passes, and the 8 words of that length that do work are the commutator and its rotations and mirror images. For three nails, no word of 9 passes or fewer works, and the nested commutator’s 10 is the minimum. For four nails the minimum is 16, met by the halving construction and not by nesting, and 1,536 words of that length work. So far the halving recipe is exactly optimal for every number of nails the search can reach.
The figure plots the two recipes on a logarithmic scale because they diverge so fast. The nested string is a straight line on that scale — exponential growth — and the halved one bends over like a power, as it must.
Every shortest string for three nails
The census for three nails is worth looking at whole, because it shows how rare solutions are. The search inspects about fifteen million words of length up to ten, most of them cut off early by the cancellation test. At every length up to nine the count is zero. At ten it is 240, counted as written, so a single loop is counted once for each letter it could start at and each of its relabellings.
The 240 are not all nested commutators. One of them is , which is not a commutator with a nail on the outside at all: pulling leaves , which cancels from the middle, pulling leaves , and pulling leaves , and each goes to nothing by a different route. What they share is the property every solution must have: in each of them, every nail’s letters occur with total exponent zero — as many clockwise passes as anticlockwise — since otherwise pulling the other nails would leave a nonzero power of this one. That net count is the winding number round the nail, the same whole number that two loops and one number read off as a linking number in space, and for a hanging string it is zero round every nail. A word in which every letter’s exponents sum to zero is exactly a word that what homology forgets about a loop cannot see: it lies in the commutator subgroup, and homology, which only counts net windings round each hole, records it as nothing. The picture-hanging string is a loop that homology says is trivial and the loop group says is not.
The same idea in linked rings
There is a three-dimensional cousin of the puzzle, and it predates it by a century. The Borromean rings are three closed loops in space, linked together so that they cannot be separated, but such that removing any one ring lets the other two fall apart; linked, and no two of them are drew them and computed that every pair has linking number zero. Links with this property for any number of components are called Brunnian, after Hermann Brunn, who described them in 1892.
The connection is exact rather than metaphorical. Take two rings of the Borromean rings, unlinked from each other, and think of them as two holes that the third ring must wind round. In the space outside the first two, the third ring is a loop, and its word in the loop group of that space is a commutator — the third ring is precisely a picture hung on two nails. Removing either of the first two rings deletes a letter and lets the third slip free. Brunnian links of many components are built by iterating the same commutator construction, and the halving trick that shortens the picture-hanging string shortens them too.
What the search cannot settle
The figures check every claim they make about particular words: each word is reduced, each deletion is cancelled letter by letter, and every count is exhaustive over its length. What exhaustion cannot do is reach far. For five nails the halving recipe gives 28 passes, and a search through all words up to that length in ten letters is beyond what the pruning brings within reach; the claim that 28 is the minimum for five nails is therefore not made here.
The drawings of strings are schematic as well, and the windings they show are counted in the sense of the turns a tangent makes only round the nails, never as the string’s own curling. A real string slides into the configuration of least length, and the spread-out passes in the figures — each drawn on its own track so that the order of the word can be read — are nothing like what hangs on a wall; the topology is identical and the geometry is not. And the whole analysis treats nails as points and the string as perfectly flexible and frictionless. Friction is what makes the obvious two-nail hanging work in a real house, and a picture hung by a commutator, though it falls in principle when either nail is pulled, may well stay up by catching on the frame.
Still open: the shortest string for every number of nails
The search finds that the shortest strings for two, three and four nails have 4, 10 and 16 passes, and that halving achieves the last of these. Whether halving is optimal for every number of nails — whether some word shorter than about passes solves the puzzle for large — is a question about the free group, and the exhaustive method answers it only for the smallest cases. A general lower bound would have to show that a word surviving all deletions must carry a minimum amount of nested non-commutativity, a statement about the lower central series of the free group that the counting arguments in this essay do not reach.
The variations are open in the same sense. Demaine and his coauthors asked for strings that fall when any of nails are pulled but not fewer, or when certain specified sets of nails are pulled; they showed that any such rule that is monotone — pulling more nails never rescues the picture — can be realised by some string, and gave constructions of polynomial length. The shortest string for each rule is not known in general.
The commutator holds the picture up
A string on nails is a loop in the punctured plane, which is a word in the free group, and pulling a nail deletes that nail’s letters. A picture that falls when any nail is pulled is a word that survives as a whole and dies under every deletion: the commutator for two nails, commutators of commutators for more. Nesting one nail at a time doubles the string with each nail; halving the nails keeps it at . Exhaustive search finds the shortest strings for two, three and four nails at 4, 10 and 16 passes — 8, 240 and 1,536 words — and nothing shorter. Every solution winds round each nail as often one way as the other, so homology cannot see it at all: the picture hangs by exactly what homology forgets.
Shares its objects with
Essays that name at least two of the same things, and that neither author linked.
- How a random path winds round a point — both name free group, fundamental group, homotopy
- The only bit that survives — both name commutator, exhaustive search, homomorphism
- A covering is a permutation — both name free group, fundamental group
- A sort that never looks at the answers — both name exhaustive search, recursion
- Counting the subgroups of a free group — both name free group, recursion
- One tour through every position of the Tower of Hanoi — both name exhaustive search, recursion
Named objects
A dashed tag is an object no other essay names yet.
CommutatorExhaustive searchFree groupFundamental groupHomomorphismHomotopyRecursion