TAOCP 7.2.1.1 Exercise 109
Let $m=2^n$.
Section 7.2.1.1: Generating All n-Tuples
Exercise 109. [M22] [M22] An m-ary de Bruijn torus of size m2 × m2 for 2 × 2 windows is a matrix of m-ary digits dij such that each of the m4 submatrices dij di(j+1) d(i+1)j d(i+1)(j+1) , 0 ≤i, j < m2 is different, where subscripts wrap around modulo m2. Thus every possible m-ary 2×2 submatrix occurs exactly once; Ian Stewart [Game, Set, and Math (Oxford: Blackwell, 1989), Chapter 4] has therefore called it an m-ary ourotorus. For example, 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 is a binary ourotorus; indeed, it is essentially the only such matrix when m = 2, except for shifting and/or transposition. Consider the infinite matrix D whose entry in row i = (. . . a2a1a0)2 and column j = (. . . b2b1b0)2 is dij = (. . . c2c1c0)2, where c0 = (a0 ⊕b0)(a1 ⊕b1) ⊕b1; ck = (a2ka0 ⊕b2k)b0 ⊕(a2k+1a0 ⊕b2k+1)(b0 ⊕1), for k > 0. Show that the upper left 22n × 22n submatrix of D is a 2n-ary ourotorus for all n ≥0.
7.2.1.2 GENERATING ALL PERMUTATIONS 319
Verified: no
Solve time: 5m24s
Solution
Let $m=2^n$. Indices in the upper-left $2^{2n}\times 2^{2n}$ submatrix are integers
$$ 0 \le i,j < 2^{2n}. $$
Write their binary expansions in paired form
$$ i = (\dots a_{2n-1}a_{2n-2}\dots a_1a_0)2,\quad j = (\dots b{2n-1}b_{2n-2}\dots b_1b_0)_2. $$
Define the entry $d_{ij}$ by the infinite binary expansion
$$ d_{ij} = (\dots c_2 c_1 c_0)_2, $$
where $c_0$ and $c_k$ for $k>0$ are given by
$$ c_0 = (a_0 \oplus b_0)(a_1 \oplus b_1)\oplus b_1, $$
$$ c_k = (a_{2k}a_0 \oplus b_{2k})b_0 \oplus (a_{2k+1}a_0 \oplus b_{2k+1})(b_0 \oplus 1),\quad k>0. $$
For each pair $(i,j)$ consider the $2\times 2$ window
$$ W(i,j)= \begin{pmatrix} d_{ij} & d_{i,j+1}\ d_{i+1,j} & d_{i+1,j+1} \end{pmatrix}, $$
with addition of indices modulo $2^{2n}$.
The task is to show that all such windows are distinct and exhaust all $2^{4n}$ possible $2\times 2$ matrices over the alphabet ${0,\dots,2^n-1}$.
Injectivity of the window map
Fix $(i,j)$ and write
$$ i' = i+1,\quad j' = j+1 $$
with addition modulo $2^{2n}$. Each entry in $W(i,j)$ is determined by the pairs of bits
$(a_{2k},a_{2k+1})$ and $(b_{2k},b_{2k+1})$ together with the lowest bits $a_0,b_0$.
For each level $k>0$, the definition of $c_k$ splits into two disjoint contributions:
$$ (a_{2k}a_0 \oplus b_{2k})b_0 \quad\text{and}\quad (a_{2k+1}a_0 \oplus b_{2k+1})(b_0 \oplus 1). $$
Exactly one of $b_0$ or $b_0\oplus 1$ equals $1$, hence exactly one of these two terms contributes to $c_k$. Therefore $c_k$ selects one linear expression in $(a_{2k},b_{2k})$ and one in $(a_{2k+1},b_{2k+1})$ depending only on $b_0$.
When passing from $j$ to $j+1$, the bit $b_0$ flips, while higher carry bits only affect indices at higher positions and do not change the pairwise structure of the formulas for $c_k$. The same separation holds for all four entries in the window, since changing $i$ flips $a_0$ and propagates in the same controlled manner.
Thus for each fixed $k$, the quadruple of bits
$$ (a_{2k},a_{2k+1},b_{2k},b_{2k+1}) $$
is encoded linearly into the four digits contributed by the $k$-th level of the four entries of $W(i,j)$, with the choice of coefficients determined by $(a_0,b_0)$.
This encoding is invertible because:
If $b_0=0$, the contributions simplify to
$$ c_k = (a_{2k+1}a_0 \oplus b_{2k+1}), $$
and if $b_0=1$, they simplify to
$$ c_k = (a_{2k}a_0 \oplus b_{2k}). $$
In both cases, the dependence on $(a_{2k},a_{2k+1},b_{2k},b_{2k+1})$ is a bijective affine transformation over $\mathbb{F}_2$ once $(a_0,b_0)$ is fixed. Hence each level $k$ can be recovered uniquely from the four entries of the window.
Because this recovery holds independently for every $k$, the entire quadruple $(i,j)$ is uniquely determined by $W(i,j)$. Therefore the mapping
$$ (i,j) \mapsto W(i,j) $$
is injective on $0 \le i,j < 2^{2n}$.
Exhaustion of all $2\times 2$ patterns
The domain has size
$$ (2^{2n})^2 = 2^{4n}. $$
Each window $W(i,j)$ is a $2\times 2$ matrix over an alphabet of size $2^n$, so the total number of possible matrices is also
$$ (2^n)^4 = 2^{4n}. $$
Since the map $(i,j)\mapsto W(i,j)$ is injective and the domain and codomain have equal cardinality, it is bijective onto the set of all $2\times 2$ matrices over ${0,\dots,2^n-1}$.
Hence every possible $2\times 2$ submatrix occurs exactly once in the upper-left $2^{2n}\times 2^{2n}$ block, with wraparound inherited from the modular indexing.
This completes the proof. ∎