Every word once, around a cycle

Write the eight bits $00010111$ in a circle and read them through a window three wide, sliding one step at a time and wrapping round the end. The eight windows are $000$, $001$, $010$, $101$, $011$, $111$, $110$, $100$: all eight three-bit words, each exactly once.

Such a cycle is a de Bruijn sequence, and the first thing to notice about it is that the length is exactly right. There are $2^3 = 8$ words to accommodate and $8$ starting positions in the cycle, so nothing is wasted: every position carries a different word, and there is no room for a repeat. A sequence of that length either contains every word once or misses some and repeats others; there is no middle case.

The second thing to notice is that this is not obviously possible. Consecutive windows overlap in two letters, so the words cannot be listed in any order — each must begin where the previous one ended. Requiring all eight, once each, in a cycle, subject to that constraint, is asking a lot.

Making the constraint the construction #

The trick is to stop thinking of the words as things to be listed and start thinking of them as transitions.

Build a graph. Its vertices are the words of length $n-1$ — for $n = 3$, the four words $00$, $01$, $10$, $11$. Its edges are the words of length $n$: the edge labelled $abc$ runs from vertex $ab$ to vertex $bc$. Each edge is an overlap made explicit, and a walk along edges spells a sequence in which consecutive windows overlap correctly, because that is exactly what following an edge means.

Now the requirement every word exactly once becomes every edge exactly once, and a cyclic sequence becomes a closed walk. A closed walk using every edge exactly once is an Eulerian circuit, and the question of when one exists was settled in the first paper of graph theory.

Euler’s condition is that the graph be connected and every vertex have as many edges in as out. Both hold here for a reason that is arithmetic rather than lucky: each vertex $w$ has exactly $k$ edges out, one for each letter that can be appended, and exactly $k$ edges in, one for each letter that can be prepended. And the graph is connected, since any word can be turned into any other by shifting in the letters of the target one at a time.

So the sequence exists for every alphabet size and every word length, and the proof of existence is Euler’s theorem applied to a graph the problem builds for itself. That is the whole argument, and its shape — recast the object as a walk, then quote a walk theorem — is the most reliable trick in combinatorics on words.

Building one #

Existence proofs of this kind are usually constructive, and this one is. Hierholzer’s method builds an Eulerian circuit by walking until stuck, which in a graph with balanced degrees can only happen back at the start, and then splicing in detours from any vertex that still has unused edges.

Two other constructions are worth knowing because they produce specific sequences rather than an arbitrary one.

The greedy method, sometimes called the prefer-one rule, starts with $n$ zeros and repeatedly appends the largest letter that does not create a repeated window. It never gets stuck, which is a small theorem in itself, and it produces the lexicographically largest sequence.

The necklace concatenation method is prettier. List the aperiodic cyclic words — the necklaces — whose length divides $n$, in lexicographic order, and concatenate them. The result is a de Bruijn sequence, and it is the lexicographically smallest one. Both facts require proof, and the second construction has the advantage that any window can be computed without generating the whole sequence.

Why the greedy rule never gets stuck #

The greedy construction deserves its own paragraph, because it is the one that looks as though it should fail.

Start with $n$ zeros. At each step, look at the last $n-1$ letters, and append the largest letter that does not produce a window already seen. Stop when no letter works. The claim is that when the rule stops, every window has appeared — the greedy walk never paints itself into a corner with edges left over.

The reason is a parity-like argument on the graph. Suppose the walk stops at a vertex $v$ with unused edges somewhere in the graph. The walk has used equal numbers of in- and out-edges at every vertex it passed through and left, so the only vertex where the counts can differ is the one it is standing on and the one it started from — and those are the same vertex, since the all-zeros word is where the rule begins and the last window it can no longer extend is all zeros again. So at every vertex the used edges are balanced, and the unused edges also form a balanced subgraph. A balanced subgraph with any edge at all contains a cycle, and that cycle must touch the walk somewhere, since the graph is connected. But if the walk passes through a vertex of that cycle, the greedy rule would have taken one of the cycle’s edges when it was there, because it takes the largest available letter and it left the vertex by some edge.

Making that last step precise is where the actual proof does its work, and the standard treatment argues instead that the unused edges must all be zero-labelled and traces them back to the start. Either way, the outcome is the same: the rule is a construction with no backtracking that produces the lexicographically largest sequence, which is what makes it usable when the sequence is wanted one letter at a time rather than all at once.

The same graph, running as a rule #

The graph in these figures is not only a bookkeeping device; it is the transition diagram of a dynamical system, and reading it that way connects the subject to a different part of the site.

A state is the last $n-1$ letters, and a step drops the oldest letter and admits a new one. That is the shift: the map that takes an infinite word to the word with its first letter removed. Restricting attention to the last $n-1$ letters makes the shift a finite-state machine, and the de Bruijn graph is that machine’s diagram.

Two consequences follow, and both are worth the detour. A random walk on the graph, choosing letters uniformly, produces a random word, and the chain forgets where it came from after $n-1$ steps exactly — its memory is the window and nothing more. And a de Bruijn sequence is a closed orbit of that machine visiting every transition once, which makes it the most efficient possible test of the machine: any device whose behaviour depends on the last $n$ inputs is exercised completely by one.

The same shift, on the unit interval rather than on words, is the doubling map that a chaotic rule iterates; binary expansion is the dictionary between the two, and the de Bruijn graph is the shift’s transition diagram after the expansion has been truncated to a window.

How many there are #

Existence is one question and abundance is another.

For two letters, the number of distinct de Bruijn cycles of order $n$ is

$$2^{\,2^{n-1} - n},$$

which is $1$, $2$, $16$, $2048$ for $n = 2, 3, 4, 5$ — an enormous number of them very quickly. The table above finds the first three by brute force, testing every binary string of the right length and dividing by the number of rotations, and compares the count with the formula rather than assuming it.

Where does the formula come from? From the BEST theorem, which counts Eulerian circuits in a directed graph as the number of spanning trees oriented toward a fixed root, multiplied by a product of factorials of the out-degrees. Applied to the de Bruijn graph, the spanning tree count is computable and the product is $((k!)^{k^{n-1}})$, and the general formula is

$$\frac{(k!)^{k^{n-1}}}{k^{n}}.$$

The counting is the same kind of accounting that counts labelled trees: a determinant of a matrix built from the graph, evaluated in closed form because the graph is regular enough to make it easy.

What the sequence is used for #

The reason de Bruijn sequences are built rather than merely admired is that they solve a positioning problem with no waste.

Mark a rotating shaft with a cyclic binary pattern and read $n$ adjacent cells with $n$ sensors: because every window is different, the reading identifies the angle exactly. A pattern of $2^n$ cells resolves $2^n$ positions with $n$ sensors, which is optimal, and there is no need for the separate track per bit that a plain binary encoder requires. The same device appears in touch surfaces that locate a stylus by the pattern printed under it.

They also give a shortest test sequence. A device whose state depends on the last $n$ inputs must be tested on every one of the $k^n$ input histories; feeding it a de Bruijn sequence exercises all of them in $k^n$ steps rather than $n k^n$, a saving of a factor of $n$.

And they appear in the arithmetic of finite fields. A maximal-length shift register — a register whose next bit is a fixed linear combination of the previous ones, chosen so that the state cycles through every non-zero value — produces a sequence containing every non-zero window once, which is a de Bruijn sequence with one zero missing. That the good choices correspond to primitive elements of a finite field is why the subject sits next to coding theory.

Where the name came from #

Nicolaas de Bruijn published the count in 1946, and discovered afterwards that the sequences and their number had appeared in 1894 in a note by Camille Flye Sainte-Marie, answering a question posed in a French problem journal. The rediscovery is well documented because de Bruijn documented it himself, in a paper whose title acknowledges the priority.

The objects are older than either. Sanskrit prosodists knew the binary case for $n = 3$ by the tenth century, as a mnemonic listing all eight patterns of long and short syllables in one wheel — the word yamātārājabhānasalagām is a de Bruijn sequence for three-syllable metres, with each syllable’s length read from the vowel. That a mnemonic device and a shaft encoder are the same object, separated by a millennium, is the sort of coincidence that suggests the object is forced rather than invented.

The name that stuck is de Bruijn’s, and the graph carries it too, though the graph in its general form is closer to what Good published independently in 1946 — the two papers appeared within a few months, which is why the construction is sometimes called the Good–de Bruijn graph.

Where it fails, and what it costs #

Nothing fails, which is unusual. Sequences exist for every alphabet size and every word length, and the construction is efficient. What is worth stating instead is where the variants become hard.

Ask for a two-dimensional version — an array in which every $m \times n$ block of symbols appears exactly once — and existence is still known but the constructions are much harder, and the analogous counting is open in most cases.

Ask for a sequence in which every window appears once and the sequence has some further property, such as being invariant under complementation or having balanced runs, and the question becomes a search rather than a construction.

Ask for a linear rather than cyclic sequence containing every word once, and the length is $k^n + n - 1$; the cyclic version is the natural object and the linear one is it with the wrap-around written out.

What the pictures cannot show #

The graph is drawn for four vertices and eight edges, and the interesting cases are the ones too big to draw: at $n = 6$ over two letters the graph has thirty-two vertices and sixty-four edges, and at $n = 10$ it has five hundred and twelve vertices. The drawing conveys the mechanism and nothing about scale.

The counting table stops at word length four, because the search is over $2^{16}$ strings and the next row would be over $2^{32}$ — a search whose result is a number in the billions. The formula is checked where the search can reach, which is three rows, and believed beyond.

And the sliding-window figure shows the wrap-around by writing the sequence out twice, which is the only way a straight line of type can show a cycle. A reader has to supply the identification of the two ends, which is the same compromise every picture of a cyclic object makes.

The ladder from here #

Below: the bridges of Königsberg, whose theorem is what makes the sequence exist, and Gray codes, which are the Hamiltonian counterpart — visiting every vertex once rather than every edge, on the cube rather than on this graph. Sideways: counting labelled trees, whose determinant is the one the BEST theorem uses, and primitive elements, which build these sequences by arithmetic instead. Above: two-dimensional arrays, and the shift registers that generate the sequences in hardware.

What is worth carrying away #

The lesson is the reduction, and it is worth stating in the general form because it applies well beyond words.

A problem asked for an arrangement of overlapping things subject to a consistency condition between neighbours. Recasting each thing as an edge, and the shared overlap as a vertex, turned the consistency condition into the automatic condition that a walk is connected — and the problem became a standard one with a two-hundred-year-old answer.

The general shape: when objects must be sequenced and consecutive objects must agree on part of themselves, make the shared part a vertex and the object an edge. The sequencing problem is then Eulerian, which is easy. The alternative encoding — objects as vertices, compatibility as edges — makes it Hamiltonian, which is hard. Both encodings are available for every such problem, and the first one is the one to look for.