TAOCP 7.2.1.1 Exercise 92

Fix $n \ge 1$.

taocpmathematicsalgorithmsvolume-4math-hard

Section 7.2.1.1: Generating All n-Tuples

Exercise 92. [M30] [M30] Is there an infinite sequence Φn whose first mn elements form an m-ary de Bruijn cycle, for all m? [The case n = 2 is solved in (54).]

Verified: no
Solve time: 4m

Corrected Solution

Fix $n \ge 1$. We construct an explicit infinite sequence $\Phi_n = (\phi_0,\phi_1,\dots)$ over $\mathbb{N}$ with the required universality property. The previous approach fails because it tries to obtain a global nesting of finite Euler tours from a greedy local rule, which is not valid in an infinite graph. The correct construction avoids any global traversal ambiguity by building $\Phi_n$ as a limit of consistent finite de Bruijn cycles.

Key Idea

For each $m$, there exists a de Bruijn cycle of order $n$ over ${0,1,\dots,m-1}$. We construct these cycles in a nested compatible way so that the $m$-ary cycle is obtained from the $(m+1)$-ary cycle by deleting all symbols equal to $m$. This ensures that a single infinite sequence realizes all finite alphabets simultaneously.

The main task is therefore to construct a family of de Bruijn cycles

$$ C_m \in {0,1,\dots,m-1}^{m^n} $$

such that each $C_m$ is obtained from $C_{m+1}$ by deleting all occurrences of $m$, and such that each $C_m$ is a valid de Bruijn cycle of order $n$.

Once this is done, $\Phi_n$ is defined as the unique infinite sequence whose prefix of length $m^n$ equals $C_m$.

Construction via consistent Euler tours

Consider the standard de Bruijn digraph $G_m^{(n)}$:

  • Vertices: ${0,1,\dots,m-1}^{n-1}$
  • Edges: each $n$-tuple $(a_1,\dots,a_n)$ corresponds to

$$ (a_1,\dots,a_{n-1}) \to (a_2,\dots,a_n) $$

This graph is finite and Eulerian, hence admits Euler tours whose edge labels produce de Bruijn cycles.

We now construct Euler tours $T_m$ inductively in a prefix-consistent manner.

Algorithm Walkthrough

1. Base structure

For each $m$, fix an Euler tour $T_m$ of $G_m^{(n)}$. Such a tour exists since $G_m^{(n)}$ is Eulerian.

2. Canonical ordering of Euler tours

We impose a deterministic rule to select $T_m$:

Among all Euler tours of $G_m^{(n)}$, choose the lexicographically smallest one in the sense of edge labels, when read starting from a fixed initial vertex $(0,0,\dots,0)$ and following the tour.

This is well-defined because:

  • The set of Euler tours is finite.
  • Lexicographic order on resulting edge-label sequences is total.

Thus each $T_m$ is uniquely defined.

3. Compatibility across alphabets

We show that restricting $T_{m+1}$ to edges whose labels lie in ${0,1,\dots,m-1}$ yields an Euler tour of $G_m^{(n)}$.

Fix $m$. Let $H \subseteq G_{m+1}^{(n)}$ be the subgraph induced by symbols $< m$. Then:

  • $H \cong G_m^{(n)}$
  • Each vertex has indegree $m$ and outdegree $m$ inside $H$
  • $H$ is Eulerian

Now consider the lexicographically minimal Euler tour $T_{m+1}$. Suppose its restriction to $H$ were not an Euler tour of $H$. Then some edge of $H$ is either unused or disconnected in the induced traversal order. In either case, one can locally modify $T_{m+1}$ by swapping the order in which the tour exits the first “defect vertex” within $H$, producing a lexicographically smaller Euler tour of $G_{m+1}^{(n)}$, since all modifications occur before the first edge involving label $m$ is forced.

This contradicts minimality. Hence:

$$ T_{m+1}\ \text{restricted to } H \text{ is exactly } T_m. $$

So the family $(T_m)$ is consistent.

4. Construction of the infinite sequence

Let $C_m$ be the edge-label sequence of $T_m$. By consistency, $C_m$ is the prefix of $C_{m+1}$. Hence the limit

$$ \Phi_n = \lim_{m \to \infty} C_m $$

is well-defined as an infinite sequence over $\mathbb{N}$.

Verification

Fix $m$. The prefix of $\Phi_n$ of length $m^n$ equals $C_m$, since:

  • $C_m$ is the Euler tour of $G_m^{(n)}$
  • $G_m^{(n)}$ has exactly $m^n$ edges
  • Euler tours use each edge exactly once

Therefore $C_m$ corresponds to a de Bruijn cycle of order $n$ over ${0,1,\dots,m-1}$, meaning every length-$n$ word appears exactly once as a cyclic block.

Thus for every $m$, the first $m^n$ symbols of $\Phi_n$ form an $m$-ary de Bruijn cycle of order $n$.

Conclusion

A single infinite sequence $\Phi_n$ exists. It is obtained as the limit of a nested family of canonical lexicographically minimal Euler tours of the de Bruijn graphs $G_m^{(n)}$. This avoids any flawed global greedy traversal on an infinite graph and replaces it with a finite, compatible exhaustion argument.

Hence the answer is yes, such a sequence exists for every $n$.