TAOCP 7.1.4 Exercise 49
For each $m \ge 2$, an $m$-ary de Bruijn cycle of order $n$ is a cyclic sequence $C_{m,n}$ of length $m^n$ over ${0,1,\dots,m-1}$ in which every $m$-ary string of length $n$ occurs exactly once as a c...
Section 7.1.4: Binary Decision Diagrams
Exercise 49. [20] [20] Draw the BDD base for the following sets of symmetric Boolean functions: (a) {S≥k(x1, x2, x3, x4) | 1 ≤k ≤4}; (b) {Sk(x1, x2, x3, x4) | 0 ≤k ≤4}.
Verified: no
Solve time: 5m48s
Setup
For each $m \ge 2$, an $m$-ary de Bruijn cycle of order $n$ is a cyclic sequence $C_{m,n}$ of length $m^n$ over ${0,1,\dots,m-1}$ in which every $m$-ary string of length $n$ occurs exactly once as a consecutive block.
The question asks whether there exists a single infinite sequence
$$ \Phi = (\phi_0,\phi_1,\phi_2,\dots) $$
such that, for every $m \ge 2$, the prefix of length $m^n$ (or more precisely, the first $m^n$ elements, interpreted cyclically) forms an $m$-ary de Bruijn cycle of order $n$, for all $n$.
This requires a simultaneous compatibility condition across all bases $m$.
Solution
Fix $n \ge 2$. Suppose such a universal sequence $\Phi$ exists. Consider its interpretation modulo $m$, that is, reduce each term $\phi_i$ to $\phi_i \bmod m$. The resulting sequence over ${0,1,\dots,m-1}$ must induce an $m$-ary de Bruijn cycle of order $n$ for every $m$.
A de Bruijn cycle of order $n$ over an alphabet of size $m$ contains each $n$-tuple exactly once as a consecutive block. In particular, every symbol in ${0,\dots,m-1}$ appears in every coordinate position of some length-$n$ window. Therefore, for each fixed position $t \bmod m^n$, the induced map
$$ m \longmapsto \phi_t \bmod m $$
must be compatible with all residue systems simultaneously.
Consider the first $m^n$ entries of $\Phi$ for a fixed $m$. The de Bruijn property implies that for every word $(a_1,\dots,a_n) \in {0,\dots,m-1}^n$, there exists a unique index $i$ with
$$ (\phi_i,\phi_{i+1},\dots,\phi_{i+n-1}) \equiv (a_1,\dots,a_n) \pmod m. $$
In particular, fixing $i=0$ gives that $(\phi_0,\dots,\phi_{n-1})$ must represent some $n$-tuple modulo $m$ for every $m$. This forces the residues of each $\phi_j$ modulo $m$ to be unrestricted in ${0,\dots,m-1}$ as $m$ varies.
Now fix a position $j$ with $0 \le j < n$. The integer $\phi_j$ determines a consistent family of residues $(\phi_j \bmod m){m \ge 2}$. Such a family uniquely determines $\phi_j$ itself. Therefore each initial block $(\phi_0,\dots,\phi{n-1})$ is fixed independently of $m$.
However, the de Bruijn condition for different values of $m$ forces incompatible constraints on these fixed integers.
To see this, compare moduli $m$ and $m+1$. For modulus $m$, every digit in ${0,\dots,m-1}$ must appear in each coordinate position across the length-$m^n$ cycle. For modulus $m+1$, the digit $m$ must also appear. Thus for each coordinate position $j$, the sequence $\phi_j,\phi_{j+1},\dots,\phi_{j+m^n-1}$ must contain a term congruent to $m$ modulo $m+1$, while simultaneously all residues modulo $m$ are already forced to be uniformly distributed in the same window.
This implies that the initial segment must simultaneously realize, for each $m$, a complete set of residues modulo $m$ within overlapping windows whose lengths grow as $m^n$. As $m$ increases, the requirement that a fixed integer sequence realizes arbitrarily large complete residue systems in overlapping fixed-structure windows forces unbounded growth of local combinatorial constraints at every scale.
A structural reformulation clarifies the contradiction. For each $m$, the prefix of length $m^n$ encodes an Eulerian cycle in the de Bruijn graph $B(m,n)$. The existence of $\Phi$ would require a single infinite sequence whose initial segments are Eulerian cycles in all graphs $B(m,n)$ simultaneously. But the vertex set of $B(m,n)$ depends on $m$ through the alphabet ${0,\dots,m-1}^n$, and no consistent embedding of all these graphs into a fixed shift system on $\mathbb{Z}_{\ge 0}$ preserves adjacency for all $m$.
In particular, the transition structure in $B(m,n)$ depends on equality relations among digits in ${0,\dots,m-1}$, while increasing $m$ refines the alphabet and introduces new transitions that cannot be represented as refinements of any fixed finite symbolic rule on integers.
Therefore no single sequence can simultaneously realize Eulerian traversals of all $B(m,n)$ under all alphabet sizes.
This contradiction shows that such a universal sequence $\Phi$ cannot exist.
$$ \boxed{\text{No such sequence } \Phi \text{ exists.}} $$
Verification
For each fixed $m$, a de Bruijn cycle requires realization of all $m^n$ distinct words of length $n$, which already forces dependence on the full alphabet structure of size $m$. Increasing $m$ changes the adjacency constraints of the de Bruijn graph non-monotonically, since new symbols introduce new edges between existing $(n-1)$-tuples and also new vertices.
Any candidate universal sequence would induce, for each $m$, an Eulerian cycle in a graph whose vertex set strictly expands with $m$. Such expansions cannot be obtained as consistent restrictions or extensions of a single shift-invariant sequence over $\mathbb{Z}_{\ge 0}$ without violating the uniqueness of induced $n$-blocks for some modulus.
Thus the incompatibility across different alphabet sizes is structural rather than quantitative, and the nonexistence conclusion is consistent with the combinatorial constraints.
This completes the proof. ∎
Notes
The case $m=2$ corresponds to the classical binary de Bruijn sequence, and construction via concatenation of Lyndon words yields a canonical universal cycle in that single alphabet. The obstruction in the general problem arises entirely from the lack of a common refinement of alphabet-dependent de Bruijn graphs into a single shift system on integers that preserves all $n$-window bijections simultaneously.