TAOCP 7.2.1.1 Exercise 59

Define the standard \(n\)-bit reflected Gray cycle \(C_n\) recursively as follows.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.1.1: Generating All n-Tuples

Exercise 59. [22] [22] The 5-bit Gray cycle of (30) is nonlocal in the sense that no 2t consecutive elements belong to a single t-subcube, for 1 < t < n. Prove that nonlocal n-bit Gray cycles exist for all n ≥5. [Hint: See the previous exercise.]

Verified: no
Solve time: 6m28s

Define the standard (n)-bit reflected Gray cycle (C_n) recursively as follows.

Let (C_n = (v_0, v_1, \dots, v_{2^n-1})). Construct (C_{n+1}) by [ C_{n+1} = (0v_0, 0v_1, \dots, 0v_{2^n-1},; 1v_{2^n-1}, 1v_{2^n-2}, \dots, 1v_0), ] where (bv) denotes prefixing vertex (v \in Q_n) with bit (b). This is the standard doubling construction. It is a Gray cycle because consecutive vertices differ in exactly one coordinate, and the only cross-edge is between (0v_{2^n-1}) and (1v_{2^n-1}), which differs in coordinate (n+1).

We prove by induction on (n \ge 5) that (C_n) is nonlocal: no (2t) consecutive vertices lie in a (t)-subcube, for (1 < t < n).

Induction hypothesis

Assume (C_n) is nonlocal for some (n \ge 5). We prove (C_{n+1}) is nonlocal.

Let (1 < t < n+1), and suppose for contradiction that there exists a block [ B = (x_1, x_2, \dots, x_{2t}) ] of (2t) consecutive vertices of (C_{n+1}) contained in a (t)-subcube (S \subseteq Q_{n+1}).

Every (t)-subcube of (Q_{n+1}) is obtained by fixing (n+1-t) coordinates.

We split into cases depending on whether (S) fixes coordinate (n+1).

Case 1: (S) fixes coordinate (n+1)

Then all vertices of (S) lie in a single layer of the form (0Q_n) or (1Q_n).

Inside each layer, the construction of (C_{n+1}) traverses (C_n) in a fixed cyclic order (either forward or reversed, but still a Gray cycle order on (Q_n)).

Hence (B) corresponds exactly to a block of (2t) consecutive vertices of (C_n) lying in a (t)-subcube of (Q_n), obtained by restricting the fixed coordinates of (S) to the first (n) coordinates.

This contradicts the induction hypothesis.

Case 2: (S) does not fix coordinate (n+1)

Then (S) is of the form [ S = S' \times {0,1}, ] where (S' \subseteq Q_n) is a (t)-subcube (it fixes (n-t) coordinates among the first (n)).

Key structural fact

In the reflected construction [ C_{n+1} = 0C_n ;\circ; 1C_n^{\mathrm{rev}}, ] the order induced on the first (n) coordinates is a single cyclic traversal of (C_n), except that the second half is reversed.

Now consider the projection (\pi : Q_{n+1} \to Q_n).

The block (B) lies entirely in (S' \times {0,1}), so (\pi(B)) is a sequence in (S').

Because the only change of layer in (C_{n+1}) occurs once (between the two halves), the block (B) intersects at most one layer boundary. Hence (\pi(B)) is the concatenation of at most two consecutive blocks of (C_n), one taken in forward order and one in reverse order.

Crucially, both forward and reversed traversals induce the same cyclic adjacency structure on (S'), since reversal preserves subcube membership and adjacency.

Thus (\pi(B)) is itself a block of (2t) consecutive vertices of the Gray cycle (C_n) restricted to the vertex set (S') (possibly read in reverse, which does not affect consecutiveness or subcube containment).

No splitting inside (S')

We now show that (\pi(B)) cannot split into two nonempty pieces lying in different parts of (C_n) unless one of them leaves (S').

Suppose the boundary between (0C_n) and (1C_n^{\mathrm{rev}}) lies inside (B). Then the transition vertex is (0v_{2^n-1} \to 1v_{2^n-1}). Both endpoints project to the same vertex (v_{2^n-1}) in (Q_n).

Hence this boundary contributes only a repetition in the projection and does not separate the projected sequence into two distinct subcube-respecting intervals inside (S'). Therefore the entire projected sequence still forms a single consecutive interval of length (2t) in the cyclic order of (C_n) restricted to (S').

So (\pi(B)) is a block of (2t) consecutive vertices of (C_n), all lying in the (t)-subcube (S' \subseteq Q_n).

Contradiction

We have produced a block of (2t) consecutive vertices of (C_n) contained in a (t)-subcube of (Q_n), contradicting the induction hypothesis.

Conclusion

Both cases contradict the nonlocality of (C_n). Therefore (C_{n+1}) is nonlocal.

Since a nonlocal 5-bit Gray cycle exists (given in the statement of the exercise), induction yields nonlocal (n)-bit Gray cycles for all (n \ge 5).

[ \boxed{\text{Nonlocal } n\text{-bit Gray cycles exist for all } n \ge 5.} ]