Every necklace, in order

There are 16,777,216 de Bruijn sequences of order five and 2,048 of order four, and the Eulerian circuit that produces one needs a graph with $2^{n-1}$ vertices and $2^n$ edges built and held in memory before the first letter comes out. That is a fine existence proof and an awkward way to get a sequence.

Here is the whole of another construction. List the necklaces whose length divides $n$, in alphabetical order, and write them one after another. No graph, no search, no backtracking. It produces a de Bruijn sequence, it produces the alphabetically first one, and its letters come out in order at constant cost each.

What a necklace is, and why the lengths divide #

A necklace is a string considered up to rotation: 0011, 0110, 1100 and 1001 are one necklace, and the string chosen to represent it is the alphabetically smallest of its rotations. A necklace whose rotations are all different from it — one with no repeating pattern inside — is a Lyndon word, and Lyndon words are exactly the strings strictly smaller than every rotation of themselves.

The construction takes the Lyndon words whose length divides $n$. For $n = 4$ over two letters those are 0, 0001, 0011, 01, 0111 and 1: two of length 1, one of length 2, three of length 4. Their lengths add to $1+4+4+2+4+1 = 16$, which is $2^4$.

That is not an accident of this case. Every string of length $n$ is a power of exactly one Lyndon word — its shortest repeating block — repeated some number of times, and grouping the $k^n$ strings by that block gives

$$k^n = \sum_{d \mid n} d \cdot L_k(d),$$

with $L_k(d)$ the number of Lyndon words of length $d$. The sum of the lengths of the necklaces used is exactly the left side, so the concatenation has the right length before anything else is checked. That identity is Witt’s, it is the same counting-in-two-ways that proves Fermat’s little theorem by threading beads, and it is where the construction gets its arithmetic.

The word necklace is doing real work in that sentence and not merely decorating it. A string of beads on a loop has no first bead, so two strings that differ by a rotation are one necklace — and the whole of the construction is about rotations, because a de Bruijn sequence is itself a cyclic object whose windows wrap round the end. Both objects live one level up from strings, in the same quotient, and that is why one can be assembled out of the other.

Why the concatenation works #

The claim is that reading a window of $n$ letters at each of the sixteen positions gives sixteen different words, and the argument is a comparison of two orders.

Take any word $w$ of length $n$ and let $\ell$ be its alphabetically least rotation. That rotation factors uniquely as a decreasing concatenation of Lyndon words — the Chen–Fox–Lyndon factorisation, which says every string is a product of Lyndon words in non-increasing order and in exactly one way. When $\ell$ is the least rotation, the factors are consecutive necklaces in the list, and the place where $w$ appears in the concatenation is exactly the boundary between them.

That is the whole proof, and its content is that the alphabetical order of the necklace list is doing the bookkeeping the graph was doing. Two consecutive necklaces in the list are precisely two blocks whose junction spells a word not spelled anywhere else.

Fredricksen and Maiorana published this in 1978, and the sequence it gives is old enough to have a nickname: the granddaddy. What made it worth publishing was not that it works but that it works in order: the necklaces come out of a short recursion one at a time, so the $k^n$ letters can be produced with $O(n)$ memory rather than $O(k^n)$, and the amortised cost per letter is constant.

The least, and the greatest #

A construction that always produces the same sequence is producing a canonical one, and it is worth knowing which.

The concatenation begins with $n$ zeros, because 0 is the first necklace and the next ones start with zeros too. Nothing can begin with more zeros: $n+1$ zeros in a row would mean the all-zero window appearing twice. So the concatenation begins as small as any de Bruijn sequence can, and the factorisation argument extends that to every later position. It is the alphabetically first de Bruijn sequence of its order.

At the other end sits Martin’s rule, from 1934, which is even shorter to state: start with $n$ zeros and repeatedly append the largest letter that does not repeat a window already seen; stop when no letter can be appended.

Both claims are checked by exhaustion in the figures rather than quoted, and the exhaustion is honest about its scope: at order four there are 65,536 strings to test and at order five there are four billion, so the check runs at the two orders where it fits and the theorem covers the rest.

That the greedy rule terminates in the right place at all is the surprising part. A greedy algorithm that paints itself into a corner is the normal case — the obvious greedy rule for an Eulerian circuit gets stuck constantly, which is why Hierholzer’s algorithm exists — and here it never does. The reason is that the de Bruijn graph is connected and every vertex has equal in- and out-degree, so a maximal trail from a vertex must return to it; the greedy rule is running that argument without knowing it.

There is a third construction worth mentioning here because it is the one most people meet first and it is not canonical at all: take any spanning tree of the de Bruijn graph, orient its edges toward a root, and walk greedily while preferring non-tree edges. The BEST theorem’s count of Eulerian circuits is a count of such trees, so this route produces as many different sequences as there are spanning trees — which is the number a determinant computes — and picking one means picking a tree. Every de Bruijn sequence arises this way. What no version of it supplies is a reason to prefer one.

What it costs, and what it costs to find a place in it #

Two costs are worth separating, because they answer different questions and only one of them is small.

Producing the sequence costs constant amortised time per letter and $O(n)$ space. The recursion holds an array of $n$ letters and emits a prefix of it whenever the length divides $n$; nothing larger is ever allocated. Compared with building a graph of $2^{n-1}$ vertices, that is the difference between order 40 being routine and being impossible.

The space figure is worth making concrete. At order 20 the graph has 524,288 vertices and 1,048,576 edges, which is a few tens of megabytes of adjacency structure before a letter is emitted; the recursion holds twenty letters. At order 32 the graph is out of reach on any machine and the recursion is unchanged. The construction’s cost does not grow with the object it produces — only the number of letters does, and those are consumed one at a time.

Locating a window costs much more, and the asymmetry is the practical heart of the subject. Given a window of $n$ letters, at what position of the sequence does it sit? For the graph construction that question has no better answer than “search”. For a sequence produced by arithmetic it becomes a discrete logarithm, which is the next rung’s subject and is itself thought to be hard.

That gap is not a defect. It is the reason such sequences are used for position encoding at all: a strip that says where it is must be readable by looking at a few consecutive marks, and if reading it were as easy as writing it there would be nothing to build a decoder around.

The same trick, one alphabet up #

Nothing above used the alphabet having two letters, and the three-letter case is a good check that the argument was general rather than binary.

For $k$ letters and words of length $n$ the necklace lengths still sum to $k^n$ by Witt’s identity, and the factorisation argument still identifies each window with a junction. What changes is only the count: the number of de Bruijn sequences over $k$ letters is $(k!)^{k^{n-1}} / k^n$, which for three letters and order two is already 24, and for three letters and order three is a number with sixteen digits.

The construction picks one of those, deterministically, in alphabetical order, without knowing how many there are. That is the whole appeal of a canonical construction: counting the objects and producing one of them are different problems, and a formula for the first is no help at all with the second.

The counting formula deserves a second look for what it says about the alphabet. Over $k$ letters the number of sequences is $(k!)^{k^{n-1}}/k^n$, and the $k!$ in the base is the number of ways to order the outgoing edges at a vertex — so the count grows not because the sequences get longer but because each junction offers more choices. Doubling the alphabet does not double the answer; it raises a much larger base to a much larger power.

What a canonical choice buys #

There is a reason to care which sequence a construction produces, beyond tidiness.

Two systems that need the same de Bruijn sequence — an encoder and a decoder, two ends of a link, a manufacturer and a reader — must agree on it, and “the alphabetically first one” is an agreement that costs nothing to state and nothing to transmit. Compare the alternative: a sequence found by an Eulerian walk depends on the order the walk happened to consider the edges in, which is a fact about an implementation.

The pattern is worth naming because it recurs. When a mathematical object exists in enormous numbers, the useful theorem is usually not the existence proof but a rule for choosing one, stated so simply that two parties can arrive at the same one independently. The lexicographically least representative of an equivalence class is the standard form of that rule, and this is it applied to strings.

Where the necklaces came from #

The two constructions have very different origins, and the gap between them is a hundred and thirty years wide.

De Bruijn’s own paper of 1946 was a counting paper: it established how many such cycles there are, by the argument that became the BEST theorem, and the existence followed from the count being positive. He noted afterwards that Camille Flye Sainte-Marie had published the binary count in 1894 in a problem journal, and that it had been forgotten. Martin’s greedy rule predates de Bruijn’s paper by twelve years and was published as a note about a completely different question — the shortest string containing every word — with no graph in it.

The necklace construction is the late one and it is the one that made the objects usable. Its ingredients were all older: Lyndon’s words are from 1954, the factorisation from 1958, Witt’s identity from 1937. What Fredricksen and Maiorana supplied was the observation that putting them in alphabetical order solves a problem none of them was about.

That sequence of events is common enough to be worth expecting. A subject’s first result is often a count, its second an algorithm that materialises the object, and its third a construction that materialises it in order — and the third one usually comes from a neighbouring subject whose vocabulary happened to fit.

What the pictures cannot show #

The exhaustive checks stop at order four. All 65,536 binary strings of length sixteen are generated and the 256 de Bruijn ones kept, so the claims about least and greatest are verified there and are theorems elsewhere. At order five there are four billion strings and the figure would not build.

The recursion is not drawn. What the figures show is its output — the necklaces, in order — and the property that makes it efficient is that the output arrives one word at a time from an array of $n$ letters. A picture of an array being mutated is not a picture of anything.

And the concatenation is drawn as blocks, which the sequence does not have. The tinting marks where each necklace ends. A reader of the sequence sees sixteen letters with no boundaries in them; the boundaries are a fact about how it was made, and the whole argument is that they are exactly where the windows change.

Where the ladder goes next #

The rung above replaces the list with a machine. A shift register holding $n$ bits, with the right few of them added back in, runs through every nonzero state before repeating — and its output shows every nonzero window exactly once, which is a de Bruijn sequence one zero short. The taps that make it work are the coefficients of a primitive polynomial, so the question of which registers are maximum-length is a question about the multiplicative structure of a finite field.

Above that: the same property in two dimensions, where a page can be printed so that any small patch of it says where on the page it is, and then the question of which other families of objects — permutations, subsets, partitions — admit such a cycle at all.

What is worth carrying away #

An existence proof and a construction are different things, and the gap between them is often the whole of what is useful.

The Eulerian argument proves that a de Bruijn sequence exists and gives a way of finding one that needs the entire object in memory first. The necklace list produces the same kind of object from a recursion that never holds more than $n$ letters, and produces a specific, nameable one. The move that made that possible was replacing a search over a structure with an enumeration in an order — and the order was doing exactly the bookkeeping the structure had been doing, which is why the proof of correctness is a statement about alphabetical comparison and not about graphs at all.