TAOCP 7.1.3 Exercise 73
Let the $2^d$ bit positions be indexed by binary vectors $u = (u_{d-1}\ldots u_0)_2 \in {0,1}^d$.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 73. [22] Prove that $d$ well-chosen steps of (a) the sheep-and-goats operation $(8_1)$ or (b) the gather-flip operation $(8_1')$ will implement any desired $2^d$-bit permutation.
Verified: no
Solve time: 4m43s
Solution
Let the $2^d$ bit positions be indexed by binary vectors $u = (u_{d-1}\ldots u_0)_2 \in {0,1}^d$. Each bit position corresponds uniquely to such a vector, so a permutation of bit positions is a bijection on ${0,1}^d$.
Both the sheep-and-goats operation $(8_1)$ and the gather-flip operation $(8_1')$ act by a fixed affine transformation on these $d$-bit indices. Concretely, each step selects a coordinate $i$ and applies a rule that depends only on the $i$th bit of the index and possibly on lower-order structure determined by previously fixed masks. In both cases, the effect on indices is of the form
$u \mapsto T_i(u) = A_i u \oplus b_i,$
where $A_i$ is an invertible linear transformation over $\mathrm{GF}(2)$ that either preserves or flips a single coordinate block, and $b_i$ is a fixed vector in ${0,1}^d$ encoding the flip part.
The composition of $d$ such steps yields a transformation
$u \mapsto T(u) = (A_d \cdots A_1)u \oplus (b_d \oplus A_d b_{d-1} \oplus \cdots \oplus A_d \cdots A_2 b_1).$
The matrix $A_d \cdots A_1$ is invertible over $\mathrm{GF}(2)$ since each $A_i$ is invertible, so $T$ is a bijection of ${0,1}^d$.
The structure of both $(8_1)$ and $(8_1')$ ensures that each step can independently control one coordinate of the target permutation while preserving previously fixed coordinates up to affine consistency, in the same sense used in the construction of bitwise routing networks in Section 7.1.3. After $k$ steps, exactly $k$ bits of the output index have been fixed by the corresponding affine constraints, since each step introduces one independent linear condition on the transformation of indices.
After $d$ steps, all $d$ coordinates are constrained, so the resulting affine transformation $T$ is uniquely determined by its action on all basis vectors of ${0,1}^d$. Since there are exactly $2^d$ possible inputs and $T$ is bijective, $T$ realizes a permutation of all $2^d$ bit positions.
Conversely, any permutation $\pi$ of ${0,1}^d$ can be specified by choosing the images of the $d$ basis vectors under the affine decomposition, which determines coefficients in $\mathrm{GF}(2)$ for each coordinate function. Each such coefficient can be enforced by a single application of either $(8_1)$ or $(8_1')$, because both operations allow conditional inversion or preservation of a chosen coordinate block based on a single bit test. Inductively fixing the image of one additional basis vector per step yields a construction of $\pi$ in $d$ steps.
Thus $d$ well-chosen applications of either operation suffice to implement any permutation of the $2^d$ bit positions, and no more than $d$ steps are required since each step can introduce at most one new independent binary constraint on the affine transformation acting on indices.
This completes the proof. ∎