Every place changes back

A Gray code on $n$ places is an order of all $2^n$ binary words in which neighbouring words differ in one place, the last included — a closed walk along the edges of the $n$-dimensional cube that visits every corner once. On four places there are 1,344 such walks. The reflected construction produces one of them, and in it the last place changes eight times, the next four, and the first two only twice each. Most of the work falls on one place.

That lopsidedness raises a question with a surprisingly clean answer: over all the walks there are, what patterns of work are possible?

The search tries every walk and records, for each, how many of its sixteen steps change each of the four places. Only four patterns occur. The most common, shared by 960 walks, is six, four, four and two. The rarest is the reflected code’s eight, four, two, two, with 48 walks. And 192 walks share the work perfectly: every place changes exactly four times.

Why every count is even #

Every number in the table is even, and the reason takes one sentence. A walk that returns to where it started has returned every place to its starting value, so each place has changed an even number of times. A place that is 0 at the start and changes once is 1; to be 0 again at the end it must change again; and so on.

That is a parity argument, and like every parity argument it forbids more than it seems to. The counts are even and they add up to the number of steps, $2^n$, since each step changes exactly one place. For three places the eight steps must be split into three even counts. The only ways are $4, 2, 2$ and its rearrangements, and $6, 2, 0$ — but a count of zero would mean one place never changes, and then the walk would visit only the four words sharing that place’s value.

So every walk on the three-place cube has one place doing half the work, and the search confirms that all six walks share the same pattern. The unevenness of the reflected code on three places was not a defect of the construction. No Gray code on three places is balanced, and the proof is that eight is not three times an even number.

When perfect sharing is possible #

The same arithmetic decides every $n$. Perfect sharing means each place changes $2^n / n$ times, and that has to be an even whole number. For $n = 4$ it is 4. For $n = 5$ it is 6.4, not a whole number at all. For $n = 6$ it is 10.67, and for $n = 8$ it is 32.

The quotient $2^n/n$ is a whole number exactly when $n$ divides a power of two — when $n$ is itself a power of two — and then it is also even, apart from the trivial case of two places. So a perfectly balanced Gray code is possible only when the number of places is 2, 4, 8, 16, and so on, and whenever it is not, the best possible is counts differing by two.

The strip makes the reflected code’s pattern visible as a rhythm. The last place changes on every other step; the one above it on every fourth; the next on every eighth; and the first only twice, once in the middle and once at the close. The sequence of places changed is the ruler sequence — 4, 3, 4, 2, 4, 3, 4, 1, … in this numbering — which records, at each step, how many times the step number can be halved. The reflection doubles the walk by repeating it with one extra change in the middle, and the repetition doubles the work of every place except the new one.

The balanced walk has no rhythm to speak of. The changes of each place are scattered through the sixteen steps, sometimes three in close succession and sometimes none for six steps, and no simple rule generates them. It was found by a search that refused, at every step, to change a place that had already used its four.

Five places, six apiece and one eight #

On five places the steps number 32, and five even counts adding to 32 can be at best $8, 6, 6, 6, 6$.

The search found such a walk with no difficulty. The same limit on each place that found the balanced walk on four places — no more than eight changes for the first place and six for each of the others — steers the walk through the 5-cube, and it closes. Against the reflected code on five places, whose counts are $16, 8, 4, 2, 2$, the most-used place now changes half as often.

That such walks exist for every number of places was proved in 1996 by Girish Bhat and Carla Savage, completing a construction of John Robinson and Martin Cohen from 1981. Their theorem says that for every $n$ there is a Gray code whose counts differ from one another by at most two, and that when $n$ is a power of two they can all be equal. The proof is not a search. It takes a code on fewer places and inserts new changes into it in a controlled way, keeping every step a single change and every count even, and rebalancing as it goes.

The idea behind the insertion can be seen in the reflected construction itself. Doubling a walk on $n - 1$ places — once with a new place at 0, once reversed with it at 1 — gives the new place only two changes and doubles everything else. The balanced constructions instead cut the shorter walk into many pieces and weave the new place in between them, so that it changes many times, each time moving to a copy of a piece traversed in the other direction. Each weave costs changes of the old places that must be absorbed without breaking the one-change rule, and the difficulty of the proof is entirely in choosing pieces whose ends line up. The counts come out within two of one another because the number of pieces can be tuned, two at a time, to whatever the arithmetic asks for.

Four kinds, and what makes them kinds #

The census of the 4-cube found only four patterns among 1,344 walks, and the count of four is itself worth explaining. The four-part lists of even numbers, none of them zero, that add up to sixteen are $10, 2, 2, 2$; $8, 4, 2, 2$; $6, 6, 2, 2$; $6, 4, 4, 2$; and $4, 4, 4, 4$. Five candidates, and the search found four of them. The pattern $10, 2, 2, 2$ never occurs.

The reason is a second constraint, stronger than parity, and it comes from cutting the walk in two. Suppose one place changes only twice. Those two steps split the walk into two stretches, one with that place at 0 and one with it at 1, and each stretch must visit all eight corners of its half of the cube — a 3-cube — using seven steps that change only the other three places. On a 3-cube a path through all eight corners must change each of its three places at least once, or it would be confined to a face of four.

Now take the pattern $10, 2, 2, 2$ and let the cut be made at one of the places changing twice. The other two twice-changing places must each change at least once in each stretch, so each changes exactly once per stretch. Within a stretch, then, two of its three places change once apiece, and those two changes cut the stretch into three pieces during which only the remaining place changes. A piece in which only one place changes can visit at most two corners, so the three pieces visit at most six — and the stretch had to visit eight. The pattern is impossible, and the argument uses nothing but the requirement that each half of the cube be covered.

Parity said the counts are even; covering the halves says, in addition, that no place can be starved while the others are nearly starved too. Between them the two conditions leave exactly the four patterns the search found.

What the count says about the reflected code #

The reflected code’s pattern is the rarest of the four. Only 48 of the 1,344 walks share it, and they are all versions of the reflected code itself, obtained by renaming the places and choosing where to start — a check beside the census applies all 384 symmetries of the 4-cube to the reflected code and finds exactly these 48 walks. The count is the orbit–stabiliser arithmetic at work: 384 symmetries, of which 8 carry the reflected walk onto itself, give $384 / 8 = 48$ distinct copies. Every other pattern contains walks that are not symmetric images of one another, which is part of why they are more numerous. The construction everyone learns first is one of the least typical Gray codes there is.

That is a common situation in combinatorics. A recursive construction produces a single, highly structured member of a large family, and the structure that makes it easy to describe is precisely what makes it unrepresentative. The Karnaugh map uses the reflected code because it is easy to write down and has a closed form — the $k$-th word is $k$ exclusive-or $k$ shifted right by one — and neither property is shared by the balanced walks, which have to be searched for or built by a much longer argument.

Parity arguments, and what they are good for #

The evenness of the counts belongs to a family of arguments that forbid without constructing. The bridges of Königsberg cannot be crossed once each because a walk through a town pairs each arrival with a departure, so every land mass except the ends needs an even number of bridges. The cube’s words cannot be toured with one corner removed because every edge joins an even word to an odd one, and seven corners cannot alternate. And here, a closed walk cannot change a place an odd number of times, because the place would end where it did not start.

Each of these is a quantity that the desired object would have to preserve — the parity of a count, the balance of two colours — checked against the object’s requirements before any search begins. They are the cheapest impossibility proofs there are, and the most useful habit they teach is to ask, of any construction problem, what the thing being built would have to keep even. The answer to the balance question on three places was available before a single walk had been drawn.

The same cube also carries the opposite kind of argument. The distance between two words is the number of places in which they differ, and the codes that correct errors are sets of corners far apart; the Gray codes are orders in which every step covers the smallest distance there is. The parity of a word — the number of its ones, modulo two — is what splits the cube into two colours, and it is the same parity that the simplest error-detecting code checks.

What the census cannot show #

The census is exhaustive on four places and nowhere else. On five places there are 906,545,760 walks, which a search could still tally, and on six the number of walks is not known, so the distribution of patterns for larger cubes is known only through theorems about which patterns exist. The figures show one balanced walk on five places; the theorem that one exists for every number of places is Bhat and Savage’s and is not drawn.

The strips show which place changes at each step and nothing about which words are visited. Two walks can have the same pattern of counts and visit the corners in completely different orders. The count pattern is a summary, the one relevant to wear on a physical device, and it discards almost everything else about the walk.

The census also says nothing about how the patterns are distributed among walks that start at different corners or run in different directions; it fixes the start and counts each walk once, which is the natural choice for a count and not the only one. A walk and its reverse have the same pattern, and a walk moved by a symmetry of the cube has the same pattern with its places renamed, so the four patterns would still be four under any convention — but the numbers 960, 192, 144 and 48 depend on it.

And the balanced walks were found by a search that restricted each place’s count as it went. That the search succeeded quickly on four and five places is evidence that balanced walks are plentiful there — 192 of 1,344 on four — and not a method that scales: the walks on large cubes are found by construction, not by search.

The question it leaves: what else a walk can be asked to do #

Balance is one requirement beyond the single change per step, and it is met for every number of places. Others are harder.

A long-run Gray code asks that every place, once changed, be left alone for as long as possible before changing again — useful when a physical switch needs time to settle. The best possible gap on $n$ places is at most $n$, and Luis Goddyn and Pavol Gvozdjak showed in 2003 that gaps of $n - O(\log n)$ are achievable; the exact best is known only for small $n$. A monotone Gray code asks that the walk move through the cube’s levels — the words with no ones, then one, then two — in order, as nearly as possible; Carla Savage and Peter Winkler constructed such codes in 1995.

The most constrained version asks for a walk that stays within just two levels, the words with $k$ and $k + 1$ ones among $2k + 1$ places. That question was open for thirty years and is the subject of the walk through the middle levels.

The requirements interact in ways the arithmetic of this page cannot settle. A walk confined to two levels changes each place a number of times that parity still forces to be even, but it can no longer change any place freely — from a word with $k$ ones it may only add a one, and from a word with $k + 1$ it may only remove one — and whether a walk exists at all under that restriction is a much harder question than how evenly one can share its work.

Returning home #

One observation settles most of this. A closed walk returns every place to its starting value, so every place changes an even number of times, and the counts are even numbers adding to $2^n$.

From that alone: no Gray code on three places is balanced; perfect balance needs the number of places to be a power of two; and on five places the best possible is a single place changing eight times while the others change six. The census on four places adds what parity cannot see — that one pattern allowed by parity never occurs — and a second counting argument, about the two halves a rarely-changing place cuts the walk into, explains why. The reflected code sits at the lopsided extreme of all this, one of the least typical walks there are, and it is the one everybody meets first because it is the one with a formula.

That pairing — a construction that is easy to describe and atypical, beside a family that is typical and hard to describe — is the recurring shape of this subject. The reflected code is to Gray codes what a formula is to a corner of a cube: a compact name for one object among very many, chosen because it can be written down, and a poor guide to what the rest of the family looks like. The census is the corrective, and on four places it is small enough to be complete.