A walk that changes one thing at a time

Count from nothing to fifteen in binary. Somewhere in the middle, 0111 becomes 1000 and every one of the four digits changes at once. That is a nuisance for anything that reads the digits by physical means — a disc with contacts on it, a set of switches, a row of sensors — because the four will not change at exactly the same instant, and for a moment the reading is a word that was never intended.

The repair is to count in a different order.

The order in that figure visits every three-place word once and changes one place at every step, including the step from the last back to the first. The picture is why: the words are the corners of a cube, two corners are joined when their words differ in one place, and the walk is a closed tour along edges.

The cube, and what its edges mean #

The words of n places are the corners of an n-dimensional cube. That is not a metaphor: a word is a list of n coordinates each equal to 0 or 1, which is exactly what a corner of a cube is.

Two words differing in one place are joined by an edge, because an edge of a cube is what changes one coordinate and leaves the rest alone. The number of places two words differ in is the Hamming distance between them, and it is the length of the shortest route along edges from one corner to the other.

So “change one place per step” and “move along an edge” are the same instruction, and the problem becomes: find a closed walk visiting every corner exactly once. That is a Hamiltonian cycle, and asking for one is a question about a graph rather than about numbers.

The site has met this cube before, in a field that wants the opposite thing from it. Error-correcting codes choose corners far apart so that a single flip cannot reach one from another; a Gray code chooses an order in which every consecutive pair is one flip apart. Same graph, opposite objectives.

Building one by reflecting #

The code has a construction that takes one line to state. To get the order for n places: write the order for n − 1 places, then write it again reversed, put a 0 in front of every word in the first half and a 1 in front of every word in the second.

Every step inside a half changes one place, because the shorter order did. The step between the halves changes one place, because the two words either side of the join are the same word with different leading digits. And the step from the very last word back to the very first changes one place, because the last word of the reversed half is the first word of the original half with a 1 in front.

That is a recursive construction with three cases to check and it is checked: the figure walks the order it produces and asserts, step by step, that exactly one place changes, including the closing step.

The comparison in the same figure is the reason to bother. Ordinary counting to fifteen changes twenty-six places over its fifteen steps, and its worst single step changes all four.

Why any such order has to exist #

The construction proves existence by producing one, which is the best kind of proof and also the kind that explains least. A separate argument says why the cube was always going to cooperate.

Colour each corner by the parity of its word — how many 1s it contains, even or odd. Every edge of the cube joins an even corner to an odd one, because moving along an edge changes exactly one place and so flips the parity. A graph with that property is called bipartite, and any closed walk in one alternates between the two sides.

So a closed walk visiting every corner needs equally many of each parity, and the cube has exactly that: half its corners have an even number of 1s and half have an odd number. The condition is satisfied, which does not by itself produce a walk, but it does mean the obvious obstruction is absent.

The same test is what kills the question elsewhere. A cube with one corner removed has seven corners, four of one parity and three of the other, and no closed walk through all seven can exist — the alternation would have to fail somewhere. That is a complete proof of impossibility in one sentence, and it is the sort of argument parity is for: not a search, but a quantity that the desired object would have to preserve and cannot.

How many such walks there are #

The reflected construction gives one such walk. It is natural to ask how many there are, and the honest answer is a search: try every order of the corners, keep the ones in which consecutive corners are joined and the last is joined to the first.

For the three-place cube the answer is six. The search finds twelve — each walk once in each direction — and the figure halves it, because a walk and the same walk backwards use the same set of edges and are the same tour.

For four places there are 1,344, and the same search finds them in a few milliseconds. For five the answer is 906,545,760, and the search that found the first two numbers would still finish, though not on a page. For six nobody knows the exact count.

That escalation is worth pausing on. The construction gives one walk for every n, effortlessly. Counting all of them stops being possible almost immediately. Producing an object and counting the objects are unrelated difficulties, and this is one of the cleanest examples: the recursive construction has no idea how many siblings its output has.

Reading the code, and unreading it #

There is a small piece of arithmetic that makes the code usable rather than merely existent, and it is worth having because it is two lines and because it shows the reflected construction was not the only way in.

The kth word of the code is k with each place replaced by the exclusive-or of itself and the place above it. Going the other way — from a code word back to its position — each place is the exclusive-or of all the code’s places from the top down to it.

Both are immediate consequences of the reflection. Doubling the position range prefixes a 0 to the first half and a 1 to the reversed second half, and reversing a range in binary is complementing it, and complementing every place below the leading one is what an exclusive-or with the shifted value does.

The point is not the formula. It is that a construction defined by a recursion has a closed form, so the kth word can be got in a couple of operations without generating the first k − 1. Whether such a form exists is not predictable from the recursion, and here it does; the Catalan numbers are a case where a recursion also collapses into a formula, and plenty of others are cases where nothing collapses at all.

Every edge, or every corner #

The neighbouring question — a closed walk using every edge exactly once — has a completely different character, and the difference is one of the oldest results in the subject.

The bridges of Königsberg settled the edge version: such a walk exists exactly when every vertex has an even number of edges, and the test takes one pass over the graph. On the cube each corner has n edges, so an every-edge walk exists precisely when n is even.

The every-corner version has no such test. Deciding whether an arbitrary graph has a Hamiltonian cycle is one of the standard hard problems, with no known method essentially faster than trying orders, and the contrast with the edge version is the reason it is famous. Two questions about a graph, phrased almost identically, one settled by counting degrees and the other apparently requiring search.

For the cube specifically the question is settled — the reflected construction answers it for every n — but that is a fact about cubes and not a method for graphs.

What the search actually did #

The counts above deserve a word about method, because “try every order” is not what the search does and the difference is the reason it finishes.

Trying every order of sixteen corners means twenty thousand billion orders, which is not a few milliseconds. What the search does instead is grow a path one corner at a time, and at each step consider only corners joined by an edge to the current end. Most partial orders die within a few steps, and the ones that survive are already nearly walks.

That is depth-first search with the constraint applied as early as possible, and the saving is enormous: a factor of roughly a thousand million on the 4-cube. It is still exponential, and it is still the reason five is reachable and six is not.

The figure also takes care of a detail that would otherwise double every count. A walk and the same walk reversed use the same edges, so the search keeps a tour only when the corner after the start is smaller than the corner before it — a canonical form, chosen once, that admits exactly one member of each pair. Getting that wrong would have reported twelve walks on the 3-cube, and twelve is a plausible enough number that nothing else would have looked odd.

Where the same order turns up #

The order appears wherever adjacency in one place has to mean adjacency on the page. The map that puts neighbours side by side is a rectangle of truth values whose rows and columns are labelled 00, 01, 11, 10 rather than 00, 01, 10, 11 — a Gray code in two places — and the labelling is not a stylistic choice. It is what makes touching squares differ in exactly one variable, which is what makes a block of touching true squares correspond to a term with variables left out.

The same order is what puts the cube of assignments on a page without tearing it, and it is why a truth table of a formula in four variables has a two-dimensional layout at all.

Why the ordinary order is as bad as it is #

Twenty-six changes over fifteen steps sounds like a modest overhead against the code’s fifteen. The average is not the problem; the worst step is.

In ordinary counting, the step from a word of all 1s in its lower places to the next changes every one of those places at once. Over the whole range from nothing to 2ⁿ − 1 there is exactly one step that changes all n, two that change n − 1, four that change n − 2, and so on — which is where the total of 2ⁿ⁺¹ − 2 changes comes from, and why the average per step approaches two however large n gets.

An average of two and a worst case of n is precisely the profile that makes something safe on paper and unsafe in a device. Anything reading the digits at an arbitrary moment sees a word that is a mixture of the old and the new, and for a step that changes one digit the mixture is one of the two intended words. For a step that changes four, the mixture can be any of sixteen, most of which are nowhere near either.

The code removes the worst case entirely by accepting no improvement at all in the average — fifteen changes against twenty-six is a saving, but the code would be worth using if the total were higher. What is being optimised is the maximum, and that is a different objective from the one a total measures.

What the picture cannot show #

The drawings are of a cube in three dimensions and a cube in four drawn as two cubes side by side. That second drawing is a graph rather than a picture: the pairs of corners joined across the gap really are adjacent, and no arrangement on a page can make them look it. Past four places even that stops working, and the figures stop.

Only six of the 1,344 walks are drawn, and the caption says so. The count is exhaustive and the picture is a sample; conflating the two would be exactly the kind of quiet overstatement this site’s figures exist to avoid.

The 4-cube figure is a drawing of a graph and not of a shape. Nothing in it is a projection of anything: two cubes are drawn side by side with corresponding corners joined, and the joining lines cross the gap because that is where they fit. A reader who takes the picture as a perspective view of a four-dimensional object will draw wrong conclusions about which corners are near which, and the only reliable reading is the combinatorial one — two corners are adjacent when their words differ in one place, whatever the drawing does.

And the practical problem that motivated all this is not shown at all. Nothing here draws a disc with contacts, a shaft encoder or a switch, because those are physical objects and this site’s figures are generated from stated rules. What can be shown is the combinatorial fact, and the physical reading of it is a sentence rather than a picture.

Where the ladder goes next #

Three directions lead out.

The counting question is one of them, and it is open: the number of Hamiltonian cycles on the n-cube is known for n up to five and not for six, which is an unusually low ceiling for a quantity this easy to define.

The existence question in general is the other, and it is the hard one. There is no known test for a Hamiltonian cycle that avoids search, and there are good reasons to believe none exists — a belief with an enormous amount riding on it, which belongs next door with the cost of computation rather than here.

And there is the question of what other orders exist. A Gray code is any order in which consecutive words differ in one place, and the reflected one is merely the most convenient; some applications want a code that is also balanced, so that each place changes about equally often, and others want one that is monotone. Each requirement carves a subset out of the 1,344, and for larger cubes the existence of a code with a given extra property is often unknown. The cube is a very small object with a great many questions still attached to it.