TAOCP 7.2.1.1 Exercise 58

Section 7.2.1.1: Generating All n-Tuples

Exercise 58. ▶ [21] [21] Let α be the delta sequence of an n-bit Gray cycle, and obtain β from α by changing q occurrences of 0 to n, where q is odd. Prove that ββ is the delta sequence of an (n + 1)-bit Gray cycle.

Verified: no
Solve time: 1m48s

Solution

Let $\alpha = (a_0, a_1, \dots, a_{2^n-1})$ be the delta sequence of an $n$-bit Gray cycle in the $n$-cube $Q_n$. Let $(v_0, v_1, \dots, v_{2^n-1})$ be the corresponding Hamiltonian cycle, so that each step from $v_k$ to $v_{k+1}$ flips coordinate $a_k$ (indices modulo $2^n$).

Each coordinate $i \in {0,1,\dots,n-1}$ appears exactly $2^{n-1}$ times in $\alpha$, since every $i$-edge of $Q_n$ is used equally often in a Hamiltonian cycle and the cycle has length $2^n$.

Form a sequence $\beta$ by replacing exactly $q$ occurrences of $0$ in $\alpha$ by $n$, where $q$ is odd. Interpret $\beta$ as a sequence of edge labels in the $(n+1)$-cube $Q_{n+1}$, where labels $0,\dots,n-1$ act on the first $n$ coordinates and label $n$ flips the new coordinate.

Fix an embedding of $Q_n$ into $Q_{n+1}$ by associating to each vertex $v_k \in Q_n$ a lifted vertex $(v_k, \varepsilon_k)$, where $\varepsilon_k \in {0,1}$ is defined by $\varepsilon_0 = 0$ and, for each step $k$,

$$ \varepsilon_{k+1} = \begin{cases} \varepsilon_k, & a_k \neq 0,\ 1 - \varepsilon_k, & a_k = 0 \text{ and was replaced by } n,\ \varepsilon_k, & a_k = 0 \text{ and was not replaced}. \end{cases} $$

Thus $\varepsilon_k$ records the parity of the number of replaced occurrences of $0$ among the first $k$ steps.

Each step labeled $i < n$ changes only the $n$-cube component, and each step labeled $n$ changes only the last coordinate. Therefore the lifted sequence defined by $\beta$ is a valid walk in $Q_{n+1}$.

Since $\alpha$ visits each vertex of $Q_n$ exactly once before returning to $v_0$, the projection of the lifted walk onto the first $n$ coordinates is a bijection from positions $k$ to vertices $v_k$. The second coordinate $\varepsilon_k$ depends only on the parity of the number of replacements up to time $k$, so distinct indices $k$ produce distinct lifted vertices $(v_k, \varepsilon_k)$. Hence the lifted sequence visits $2^n$ distinct vertices of $Q_{n+1}$.

The total number of replaced $0$ occurrences equals $q$, and $q$ is odd, so

$$ \varepsilon_{2^n} = 1. $$

Since $v_{2^n} = v_0$, the lifted walk starting at $(v_0,0)$ ends at $(v_0,1)$. Thus $\beta$ forms a Hamiltonian path in a subgraph of $Q_{n+1}$ consisting of exactly one vertex from each pair ${(v,0),(v,1)}$.

The sequence $\beta\beta$ concatenates this path with its translate under flipping the last coordinate. Starting from $(v_0,1)$, the second copy of $\beta$ traverses the complementary set of vertices, since every step labeled $n$ toggles the last coordinate and every step labeled $i<n$ preserves it. Therefore the second traversal visits exactly the remaining $2^n$ vertices of $Q_{n+1}$, and it returns from $(v_0,1)$ back to $(v_0,0)$.

The concatenated sequence $\beta\beta$ thus visits every vertex of $Q_{n+1}$ exactly once and returns to its starting point, and each step changes exactly one coordinate. Hence it is a valid Hamiltonian cycle in $Q_{n+1}$, and its delta sequence is a Gray code for $(n+1)$ bits.

This completes the proof. ∎