TAOCP 7.1.4 Exercise 111

Exercise 111. [M22] [M22] Verify the summation formula (79) in Theorem U.

Verified: no
Solve time: 7m07s

Solution

Let $\Gamma_3 = (g(0), g(1), \dots, g(7))$ be the 3-bit Gray binary code in cyclic order, so consecutive terms including $g(7) \to g(0)$ differ in exactly one bit, by the defining property of Gray code in Section 7.2.1.1.

Define a bijection from the $8 \times 8$ grid to 6-bit strings by assigning each row index $r \in {0,\dots,7}$ the 3-bit word $R(r)=g(r)$ and each column index $c \in {0,\dots,7}$ the 3-bit word $C(c)=g(c)$. To the grid point $(r,c)$ assign the 6-bit number

$$ F(r,c) = (R_1(r),R_2(r),R_3(r),C_1(c),C_2(c),C_3(c)). $$

The mapping is bijective because both $R$ and $C$ are permutations of the 3-bit strings, hence each 3-bit word occurs exactly once as a row label and exactly once as a column label.

Consider horizontal adjacency. If $(r,c)$ and $(r,c')$ are adjacent east-west neighbors in the torus order, then $c'$ is the next or previous element of $\Gamma_3$ cyclically. By the Gray property, $C(c)$ and $C(c')$ differ in exactly one bit, while $R(r)$ is unchanged. Therefore $F(r,c)$ and $F(r,c')$ differ in exactly one of the last three coordinate positions.

Consider vertical adjacency. If $(r,c)$ and $(r',c)$ are adjacent north-south neighbors, then $r'$ is the next or previous element of $\Gamma_3$ cyclically. Again $R(r)$ and $R(r')$ differ in exactly one bit, while $C(c)$ is unchanged. Therefore $F(r,c)$ and $F(r',c)$ differ in exactly one of the first three coordinate positions.

For wrap-around adjacency, the pairs $(7,c)\leftrightarrow(0,c)$ and $(r,7)\leftrightarrow(r,0)$ also correspond to consecutive elements in the cyclic Gray sequence $\Gamma_3$, so the same one-bit change property holds.

Thus every move north, south, east, or west changes exactly one coordinate bit in the associated 6-bit representation, and every 6-bit string appears exactly once in the $8 \times 8$ torus.

This completes the proof. ∎