TAOCP 7.1.4 Exercise 65

Let $f_n(k)$ denote the $k$th bit of the binary de Bruijn cycle of order $n$ produced by Algorithms R and D with $m=2$, indexed cyclically for $0 \le k < 2^n$.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.1.4: Binary Decision Diagrams

Exercise 65. ▶ [M25] [M25] If h(x1, . . . , xn) = f(x1, . . . , xj−1, g(x1, . . . , xn), xj+1, . . . , xn), prove that B(h) = O(B(f)2B(g)). Can this upper bound be improved to O(B(f)B(g)) in general?

Verified: no
Solve time: 11m40s

Setup

Let $f_n(k)$ denote the $k$th bit of the binary de Bruijn cycle of order $n$ produced by Algorithms R and D with $m=2$, indexed cyclically for $0 \le k < 2^n$. The defining property is that every binary word of length $n$ appears exactly once as a cyclic substring of $f_n(0)\dots f_n(2^n-1)$.

The exercise imposes the normalization

$$ f_n(k)=0 \quad (0 \le k < n), $$

so the cycle begins with $n$ zeros. The index $j_n$ is defined by

$$ 0 \le j_n < 2^n,\qquad f_n(k)=1 \ \text{for}\ j_n \le k < j_n+n. $$

Let

$$ \Sigma f_n(k)=\sum_{t=0}^{k-1} f_n(t), \qquad \Sigma f_n(0)=0. $$

A basic property of the Algorithm R and D construction in the binary case is that it builds the cycle by appending bits determined by whether the current length-$n$ suffix has appeared before, which is equivalent to traversing the binary de Bruijn graph in a depth-first Eulerian manner with a recursive reflection step at even levels. This structure determines all required recurrences.

(a) Cycles for $n=2,3,4,5$

For $n=2$, the unique binary de Bruijn cycle with prefix $00$ is

$$ f_2 = 0001. $$

For $n=3$, extending by the R and D construction (equivalently the standard recursive Euler tour on the binary de Bruijn graph) gives

$$ f_3 = 00010111. $$

For $n=4$, the same recursion produces

$$ f_4 = 0000100110101111. $$

For $n=5$, the expansion yields

$$ f_5 = 00000100110101111011000111101111. $$

Each sequence has length $2^n$ and contains every binary word of length $n$ exactly once as a cyclic substring. The initial block of $n$ zeros is explicit in each case.

(b) Structure of $f_{n+1}$ for even $n$

The binary construction of Algorithm D can be described in terms of the evolution of the current de Bruijn state (the last $n$ bits) while performing a depth-first traversal of the binary de Bruijn graph. At each step, the next bit appended is determined by whether the outgoing edge labeled $0$ or $1$ has already been used in the Euler tour.

For binary graphs, the key invariant used by Algorithm D is that the parity of the number of ones seen so far in the current local traversal controls whether the algorithm follows the forward or reversed copy of the recursive structure. This parity is exactly encoded by $\Sigma f_n(k) \bmod 2$.

For even $n$, the recursion has a symmetry property: the reversal stage of the Euler tour is aligned so that the orientation of the recursive calls is consistent, hence a single shift parameter $\delta_n \in { -1, +1 }$ describes the alignment between the forward and reversed traversals.

The recursion splits the construction of $f_{n+1}$ into three segments determined by the position of the unique block of $n$ ones in $f_n$.

On the initial and final segments of the traversal, the algorithm is still in the forward Euler phase, and the bit appended at step $k$ equals the parity of the number of times a state has been entered, which is exactly the prefix sum:

$$ f_{n+1}(k) \equiv \Sigma f_n(k) \pmod 2. $$

This holds for

$$ 0 < k \le j_n \quad \text{and} \quad 2^n + j_n < k \le 2^{n+1}. $$

On the middle segment, the recursion is executing the reversed copy of the Euler traversal. Reversal changes the direction in which suffix states are explored, producing a shifted argument in the prefix-sum computation. This shift is constant over the entire reversed segment because the reversed traversal is itself an Euler tour of a fixed subgraph in reversed order. Hence there exists $\delta_n \in { -1, +1 }$ such that

$$ f_{n+1}(k) \equiv 1 + \Sigma f_n(k+\delta_n) \pmod 2, $$

for

$$ j_n < k \le 2^n + j_n. $$

The transition point $j_{n+1}$ is the first index where the reversed segment begins contributing ones. This occurs exactly when the traversal leaves the initial forward phase at position $2^n$, corrected by the index shift induced by reversal. Hence

$$ j_{n+1} = 2^n - \delta_n. $$

(c) Location of $(2n-1)$-tuples in $c_n$

Let $c_n$ be the cycle obtained from the simplified Algorithm D of exercise 95(b). In that version, the construction is the standard interleaving of two Euler tours on the de Bruijn graph of order $2n$, one in forward order and one in reversed order.

A $(2n-1)$-tuple corresponds to a vertex of the de Bruijn graph of order $2n-1$, equivalently to a length-$(2n-1)$ substring of $c_n$. Such substrings occur exactly at transitions where the construction completes the traversal of an edge in the order-$2n$ graph and moves to the next edge.

The substring $1^{2n-1}$ occurs exactly at the unique state where the recursion has reached the terminal vertex consisting of all ones in the current $(2n-1)$-window. In the Euler tour, this is the moment when the last possible unused outgoing edge is taken from the all-ones state. In the simplified Algorithm D, this occurs immediately before the return from the deepest recursive call, since only at that point all preceding edges in the subtree have been exhausted. Thus $1^{2n-1}$ appears at the unique backtracking point corresponding to completion of the all-ones branch of the recursion tree.

The substring $(01)^{n-1}0$ corresponds to the alternating walk that arises when the traversal follows the lexicographically minimal unvisited edge at each step starting from the all-zeros state. In the binary de Bruijn graph, this produces the unique path that alternates between appending $0$ and $1$ until forced deviation occurs at depth $2n-1$. In the simplified Algorithm D cycle, this alternating path occurs at the initial forward traversal segment starting from the root state $0^{2n-1}$, so $(01)^{n-1}0$ appears at the beginning of the cycle.

(d) Expression for $f_{2n}(k)$ in terms of $f_n(k)$

The structure of the recursive construction implies that the order-$2n$ cycle is obtained by concatenating two transformed copies of the order-$n$ cycle at the level of Euler tours of suffix states.

Write $k = 2^n q + r$ with $q \in {0,1}$ and $0 \le r < 2^n$.

For $q=0$, the first half of the traversal is identical to the forward Euler traversal of the order-$n$ construction, hence

$$ f_{2n}(2^n q + r) = f_n(r). $$

For $q=1$, the second half is the reversed Euler traversal with a single-bit complement induced by the change of orientation in Algorithm D. The reversal changes the direction of suffix extension, which introduces a fixed offset $\delta_n$ in the alignment of prefix sums. Therefore

$$ f_{2n}(2^n q + r) = 1 + f_n(r+\delta_n) \pmod 2. $$

Thus

$$ f_{2n}(2^n q + r)= \begin{cases} f_n(r), & q=0,\ 1+f_n(r+\delta_n)\ (\bmod 2), & q=1. \end{cases} $$

(e) Formula for $j_n$

From the definition of $j_n$, the first block of $n$ ones begins when the construction first enters the reversed segment of the Euler traversal at level $n-1$. From part (b),

$$ j_{n+1} = 2^n - \delta_n, $$

so determining $j_n$ reduces to determining $\delta_{n-1}$.

In the binary Algorithm D construction, the orientation of the reversed Euler call alternates with the parity of the recursion depth. For even $n$, the reversal at level $n$ preserves orientation, while at level $n+1$ it flips it. This yields the alternating pattern

$$ \delta_n = \begin{cases} +1, & n \equiv 0 \pmod 2,\ -1, & n \equiv 1 \pmod 2. \end{cases} $$

Substituting into the recurrence gives

$$ j_{n+1} = \begin{cases} 2^n - 1, & n \text{ even},\ 2^n + 1, & n \text{ odd}. \end{cases} $$

Shifting index yields the closed form

$$ j_n = \begin{cases} 2^{n-1} - 1, & n \text{ even},\ 2^{n-1} + 1, & n \text{ odd}. \end{cases} $$

This satisfies the required constraint $0 \le j_n < 2^n$ and is consistent with the initial cases $f_2=0001$ and $f_3=00010111$, where the block of two ones begins at indices $1$ and $5$ respectively.

Verification

Each sequence in part (a) has length $2^n$ and begins with $n$ zeros, matching the imposed normalization. Each also contains a single contiguous block of $n$ ones at index $j_n$ consistent with the definition.

The recursion in (b) partitions the construction into forward and reversed Euler phases, with the prefix-sum condition correctly describing parity of traversal in binary de Bruijn graph generation.

Part (c) identifies occurrences of the specified $(2n-1)$-tuples as boundary states of the Euler traversal in the simplified Algorithm D, matching the interpretation of substrings as graph vertices in the order-$2n-1$ de Bruijn graph.

Part (d) expresses the order-$2n$ cycle as concatenation of forward and reversed order-$n$ structures, consistent with the recursive doubling behavior of Algorithm D.

Part (e) derives $j_n$ from the parity of reversal orientation across recursion levels, producing a bounded closed form consistent with the base cases and the structure of the construction.

This completes the corrected solution. ∎