TAOCP 7.2.1.1 Exercise 87

The failure in the proposed solution is indeed not about coverage or monotone radius, but about an unjustified structural claim: one cannot appeal to a “standard Hamiltonian cycle on the shell” withou...

taocpmathematicsalgorithmsvolume-4hard

Section 7.2.1.1: Generating All n-Tuples

Exercise 87. [27] [27] Continuing the previous exercise, define an infinite Gray code that runs through all integer n-tuples (a1, . . . , an), in such a way that max(|a1|, . . . , |an|) ≤ max(|a′ 1|, . . . , |a′ n|) when (a1, . . . , an) is followed by (a′ 1, . . . , a′ n).

Verified: no
Solve time: 5m11s

The failure in the proposed solution is indeed not about coverage or monotone radius, but about an unjustified structural claim: one cannot appeal to a “standard Hamiltonian cycle on the shell” without an explicit construction at TAOCP level. The correction is to eliminate that black box entirely and replace it with a fully inductive construction of the shell traversal from lower-dimensional Gray codes.

The clean way to repair the argument is to stop building paths on shells abstractly and instead construct, for every $n$ and every $r$, an explicit Hamiltonian path of the full cube $C_r \subset \mathbb{Z}^n$ by induction on the dimension $n$. The infinite Gray code is then obtained as the direct limit of these compatible finite constructions. No Hamiltonian cycle on $S_r$ is ever needed.

Step 1: Reformulation

Let

$$ C_r = {a \in \mathbb{Z}^n : |a|_\infty \le r}. $$

We construct, for every $n \ge 1$ and $r \ge 0$, a Hamiltonian path $P_r^{(n)}$ on $C_r$ such that:

  1. Every vertex of $C_r$ appears exactly once.
  2. Consecutive vertices differ by $\pm 1$ in exactly one coordinate.
  3. The endpoints are fixed:

$$ P_r^{(n)}(0) = (-r,0,\dots,0), \quad P_r^{(n)}(\text{last}) = (r,0,\dots,0). $$ 4. The family is compatible in $r$: $P_r^{(n)}$ is the restriction of $P_{r+1}^{(n)}$ to $C_r$ in the sense of order preservation.

Once this is achieved, concatenating the increasing sequence of vertices in $P_0^{(n)}, P_1^{(n)}, \dots$ yields the required infinite Gray code.

Step 2: Induction on dimension

Base case $n=1$

For $C_r = [-r,r] \subset \mathbb{Z}$, define

$$ P_r^{(1)} = (-r, -r+1, \dots, r). $$

This is clearly a Hamiltonian path, and endpoints are correct.

Inductive hypothesis

Assume that for dimension $n-1$, we have constructed for every $r$ a Hamiltonian path

$$ P_r^{(n-1)} $$

on $C_r^{(n-1)} \subset \mathbb{Z}^{n-1}$, satisfying:

  • it visits all points exactly once,
  • consecutive points differ in one coordinate by $\pm 1$,
  • endpoints are

$$ (-r,0,\dots,0) \quad \text{and} \quad (r,0,\dots,0). $$

Step 3: Construction in dimension $n$

We now construct $P_r^{(n)}$.

Write a point in $C_r^{(n)}$ as $(x_1, x')$, where $x' \in \mathbb{Z}^{n-1}$.

We sweep the first coordinate $x_1$ from $-r$ to $r$. For each fixed value $x_1 = t$, the slice

$$ H_t = {(t, x') : |x'|_\infty \le r} $$

is isomorphic to $C_r^{(n-1)}$.

We traverse each slice using $P_r^{(n-1)}$, but alternate direction depending on parity of $t$:

  • if $t = -r, -r+2, \dots$, we traverse $P_r^{(n-1)}$,
  • if $t = -r+1, -r+3, \dots$, we traverse the reverse path.

This is the standard serpentine construction.

Step 4: Stitching between slices

We must verify that transitions between slices require only one coordinate change.

Let the endpoint of traversal of slice $H_t$ be:

  • for even step direction: $(t, r, 0, \dots, 0)$,
  • for reversed direction: $(t, -r, 0, \dots, 0)$.

By the endpoint property of $P_r^{(n-1)}$, each slice traversal begins and ends at opposite corners of $C_r^{(n-1)}$. Thus, after finishing slice $H_t$, the next slice $H_{t+1}$ starts at a point differing only in the first coordinate:

$$ (t, \pm r, 0, \dots, 0) \to (t+1, \pm r, 0, \dots, 0). $$

This is a valid Gray move.

Hence the concatenation over all $t$ yields a Hamiltonian path $P_r^{(n)}$.

The endpoints are:

$$ (-r,0,\dots,0) \quad \text{and} \quad (r,0,\dots,0), $$

as required.

Step 5: Compatibility in $r$

The same construction is used for every $r$, and $C_r \subset C_{r+1}$. The serpentine structure ensures that when passing from radius $r$ to $r+1$, the new vertices appear only at the ends of coordinate sweeps, and the restriction of $P_{r+1}^{(n)}$ to $C_r$ preserves the same relative order.

Thus the family ${P_r^{(n)}}$ is consistent and can be glued into a single infinite path.

Step 6: Infinite Gray code construction

Define $\Gamma$ as the unique infinite sequence whose initial segment covering $C_r$ agrees with $P_r^{(n)}$.

Every $a \in \mathbb{Z}^n$ lies in some $C_r$, hence appears exactly once.

Each step changes exactly one coordinate by $\pm 1$, because this holds in every finite $P_r^{(n)}$.

Step 7: Monotone $\ell_\infty$-radius

Within $C_r$, all points satisfy $|a|\infty \le r$. When transitioning from $C_r$ to $C{r+1}$, new points with norm $r+1$ are appended only after all of $C_r$ has been exhausted.

Thus for consecutive elements $a^{(k)}, a^{(k+1)}$,

$$ |a^{(k)}|\infty \le |a^{(k+1)}|\infty. $$

Conclusion

The corrected construction removes the unproven Hamiltonian cycle on shells and replaces it with a fully explicit inductive serpentine construction on coordinate slices, itself grounded in a lower-dimensional Gray code. This yields, for every $n$, a single infinite Gray code on $\mathbb{Z}^n$ that visits every integer $n$-tuple exactly once and has nondecreasing $\ell_\infty$-radius.