Topology

A picture that falls when any nail is pulled

Hang a picture on two nails so that it stays up, but falls the moment either nail is pulled out. The string has to go round the nails in a pattern that is a commutator — once round each, then back round each in the same order — and the reason is that a loop in a plane with holes in it is a word in a group in which order matters. With more nails the commutators nest, and an exhaustive search finds the shortest strings for two, three and four nails: 4, 10 and 16 passes.

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

A picture hung on 2 nails: a b a′ b′. word a b a′ b′ of length 4 on 2 nails; solves the puzzle: true.
Fig. 1 A string from the picture’s corners laid round 2 nails in the order a b a′ b′: once round nail a clockwise, once round b clockwise, once round a anticlockwise, once round b anticlockwise. Each pass is drawn in its nail’s colour and spread out so that it can be followed.

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 nn points removed: it is the free group on nn letters, one per point. A loop is written as a word by reading off the passes it makes round each nail, in order: aa for once round nail aa clockwise, a′a' for once round it anticlockwise, and similarly for bb, cc and the rest. Two words describe the same loop if and only if one becomes the other by inserting or deleting adjacent pairs like a a′a\,a' — 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 a ba\,b and b ab\,a are different loops: going round aa then bb cannot be deformed into going round bb then aa 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 a b a′ b′a\,b\,a'\,b': once round aa, once round bb, then once back round aa, once back round bb. 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

Pulling each of 2 nails. word a b a′ b′; reduced 4; each deletion reduces to 0.
Fig. 2 The word for two nails, and the same word with each nail pulled in turn. Pulling a nail deletes every pass round it, struck through, and what is left cancels to nothing, so the string slides off.

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 a b a′ b′a\,b\,a'\,b' the computation takes a line each, and the figure sets it out. Pull nail aa: the word becomes b b′b\,b', which cancels to nothing, and the picture falls. Pull nail bb: it becomes a a′a\,a', which cancels too. Two nails, a string that hangs, and a picture that falls whichever nail is pulled.

The word a b a′ b′a\,b\,a'\,b' is the commutator of aa and bb, usually written [a,b][a, b], and the reason it works is the reason it is called that. In a group where aa and bb commute — where ab=baab = ba — the commutator is a b a−1b−1=a a−1 b b−1=1a\,b\,a^{-1}b^{-1} = a\,a^{-1}\,b\,b^{-1} = 1. In the free group aa and bb 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 a ba\,b — fails the puzzle for the opposite reason: deleting aa leaves bb, which does not cancel, and the picture stays up.

Three nails: a commutator inside a commutator

A picture hung on 3 nails: a b a′ b′ c b a b′ a′ c′. word a b a′ b′ c b a b′ a′ c′ of length 10 on 3 nails; solves the puzzle: true.
Fig. 3 A string round 3 nails, a b a′ b′ c b a b′ a′ c′: the two-nail string, then once round c, then the two-nail string backwards, then once back round c. It takes 10 passes.

For three nails, the two-nail solution can be used as a single letter. Let u=[a,b]=a b a′ b′u = [a, b] = a\,b\,a'\,b' and take the commutator of uu with the third nail: [u,c]=u c u′ c′[u, c] = u\,c\,u'\,c', where u′=b a b′ a′u' = b\,a\,b'\,a' is uu read backwards with every letter inverted. Written out, it is a b a′ b′ c b a b′ a′ c′a\,b\,a'\,b'\,c\,b\,a\,b'\,a'\,c', ten passes, and the figure draws it on three nails.

Pulling cc deletes the two cc letters and leaves u u′u\,u', which cancels from the middle outwards. Pulling aa or bb turns uu into nothing, since uu already falls without either of them, and then [u,c][u, c] is c c′c\,c', 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 uu falls when any of a set of nails is pulled, and vv falls when any of another set is pulled, then [u,v][u, v] falls when any nail of either set is pulled — because killing either uu or vv kills the commutator. Any construction that combines solutions by commutators inherits the property.

Pulling each of three nails

Pulling each of 3 nails. word a b a′ b′ c b a b′ a′ c′; reduced 10; each deletion reduces to 0.
Fig. 4 The 10-pass word for three nails with each nail pulled in turn: the remaining passes cancel pair by pair to nothing every time, while the full word does not cancel at all.

The figure checks the three deletions letter by letter. With aa pulled the word is b b′ c b b′ c′b\,b'\,c\,b\,b'\,c'; the two inner pairs cancel, leaving c c′c\,c', which cancels. With bb pulled the same happens with aa in place of bb. With cc pulled the word is a b a′ b′ b a b′ a′a\,b\,a'\,b'\,b\,a\,b'\,a', which cancels from the centre out: b′ bb'\,b goes, then a′ aa'\,a, then b b′b\,b', then a a′a\,a'. 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

Two ways to build the string for 4 nails. nested 22 passes, halved 16 passes
Fig. 5 Two ways to build a string for 4 nails from commutators. Nesting one nail at a time takes 22 passes; taking the commutator of a two-nail solution for a and b with one for c and d takes 16.

Nesting commutators one nail at a time works for any number of nails: [[[a,b],c],d][[[a, b], c], d] and so on. But it is wasteful, and the tree on the left of the figure shows why. A commutator [u,v][u, v] has length twice the lengths of uu and vv together, so each new nail doubles the whole string built so far and adds two passes. The string for nn nails has 3⋅2n−1−23 \cdot 2^{n-1} - 2 passes: 4 for two nails, 10 for three, 22 for four, 46 for five, and over 98,000 for sixteen. Nail aa’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 nn is a power of two, the length L(n)L(n) satisfies L(n)=4L(n/2)L(n) = 4L(n/2) with L(1)=1L(1) = 1, so L(n)=n2L(n) = n^2 — 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

How long the string must be. 1:1/1 2:4/4 3:10/10 4:22/16 5:46/28 6:94/40 7:190/52 8:382/64 9:766/88 10:1534/112 11:3070/136 12:6142/160 13:12286/184 14:24574/208 15:49150/232 16:98302/256; shortest 4, 10, 16; four-nail count 1536
Fig. 6 The length of the string for 1 to 16 nails, nesting one nail at a time against halving, on a logarithmic scale. Circled, the shortest strings that exist for two, three and four nails, found by exhaustive search.

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

Every way to hang a picture on three nails with ten passes or fewer. counts by length 0,0,0,0,0,0,0,0,0,240; first a b a′ b′ c b a b′ a′ c′
Fig. 7 Every reduced word in a, b, c and their inverses, of each length up to 10, tested exhaustively: none of length 9 or less hangs on three nails and falls when any one is pulled, and 240 of length 10 do.

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 a b a′ c a b′ a′ b c′ b′a\,b\,a'\,c\,a\,b'\,a'\,b\,c'\,b', which is not a commutator with a nail on the outside at all: pulling cc leaves a b a′ a b′ a′ b b′a\,b\,a'\,a\,b'\,a'\,b\,b', which cancels from the middle, pulling aa leaves b c b′ b c′ b′b\,c\,b'\,b\,c'\,b', and pulling bb leaves a a′ c a a′ c′a\,a'\,c\,a\,a'\,c', 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 n2n^2 passes solves the puzzle for large nn — 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 nn 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 kk of nn 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 a b a′ b′a\,b\,a'\,b' 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 n2n^2. 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.

Named objects

A dashed tag is an object no other essay names yet.

CommutatorExhaustive searchFree groupFundamental groupHomomorphismHomotopyRecursion