TAOCP 3.2.2 Exercise 18
We are asked to show that the sequence of $8$-bit blocks U_n = (X_{8n}, X_{8n+1}, \dots, X_{8n+7}) fails the serial test on pairs, where the $X_n$ are generated by method (10) with $k=35$ and
Exercise 18. [M22] Let $(X_n)$ be the sequence of bits generated by method (10), with $k = 35$ and CONTENTS$(A) = (00000000000000000000000000000100101)_2$; show that this sequence $(U_n)$ fails the serial test on pairs (Section 3.3.2(ii)) when $d = 8$.
Verified: no
Solve time: 4m27s
Solution
We are asked to show that the sequence of $8$-bit blocks
$$ U_n = (X_{8n}, X_{8n+1}, \dots, X_{8n+7}) $$
fails the serial test on pairs, where the $X_n$ are generated by method (10) with $k=35$ and
$$ \text{CONTENTS}(A) = (00000000000000000000000000000100101)_2. $$
Step 1: Determine the linear recurrence
From the given CONTENTS$(A)$, the nonzero coefficients correspond to positions $31,34,35$. Hence, by Exercise 16,
$$ X_n = X_{n-31} + X_{n-34} + X_{n-35} \pmod 2. \tag{1} $$
This is a linear recurrence modulo $2$ of degree $35$.
Step 2: Identify consecutive 8-bit blocks
Let $U_n = (X_{8n}, \dots, X_{8n+7})$. The serial test on pairs examines the distribution of consecutive pairs
$$ (U_n, U_{n+1}) \in \mathbf{F}_2^8 \times \mathbf{F}_2^8 = \mathbf{F}_2^{16}. $$
To show that the serial test fails, it suffices to prove that some $16$-bit patterns cannot occur, i.e., that the $16$ bits of $(U_n, U_{n+1})$ satisfy a nontrivial linear relation over $\mathbf F_2$.
Step 3: Express the recurrence modulo 8
We express equation (1) in terms of $U_n$. Write $n = 8m + r$ with $0 \le r \le 7$. Then
$$ X_{8m+r} = X_{8m+r-31} + X_{8m+r-34} + X_{8m+r-35} \pmod 2. $$
We reduce each index modulo $8$ to identify which block it belongs to:
- $8m + r - 31 = 8(m-4) + (r+1)$, because $-31 = -32 + 1 = -4\cdot 8 + 1$
- $8m + r - 34 = 8(m-5) + (r+6)$
- $8m + r - 35 = 8(m-5) + (r+5)$
Hence for $0 \le r \le 7$,
$$ X_{8m+r} = X_{8(m-4) + (r+1)} + X_{8(m-5) + (r+6)} + X_{8(m-5) + (r+5)} \pmod 2. $$
Here the inner indices $(r+1)$, $(r+5)$, $(r+6)$ are interpreted modulo $8$ within each block.
Step 4: Identify a linear relation among consecutive blocks
The key observation is that the recurrence connects $X_{8m+3}$ and $X_{8m}$ from blocks $U_m$ and $U_{m+1}$. In particular, consider the bits at positions $r=0,1,2,3,4,5,6,7$ in block $U_4$, which correspond to indices $X_{32}, \dots, X_{39}$.
From Step 3, for $n=4$ (so $8n = 32$) and $r=3$:
$$ X_{35} = X_{4\cdot 8 + 3} = X_{8\cdot 0 + 4} + X_{8\cdot (-1) + 9} + X_{8\cdot (-1) + 8} \pmod 2. $$
Interpreting negative indices modulo $35$ (since the sequence has period dividing $2^{35}-1$) gives a valid linear combination in terms of earlier blocks.
Explicitly, working through the arithmetic:
$$ X_{35} = X_4 + X_6 + X_5 \pmod 2, $$
where $X_4, X_5, X_6 \in U_0$.
This shows that the fourth bit of $U_4$ is a linear combination of bits from $U_0$ only.
Step 5: Implication for the serial test on pairs
Now consider the pair $(U_0, U_1)$:
- $U_0$ contains $X_0, \dots, X_7$
- $U_1$ contains $X_8, \dots, X_{15}$
From Step 4, the recurrence implies that certain linear combinations of bits in $U_0$ and $U_1$ determine bits in $U_4$. In particular, observe that
$$ X_{35} + X_4 + X_5 + X_6 = 0 \pmod 2. $$
Express $X_{35}$ in terms of $U_4$:
$$ X_{35} = (U_4)_3. $$
Thus we obtain a nontrivial linear relation involving bits from $U_0$ and $U_4$.
By translating indices modulo $2^8$, one can check that no combination of $U_0$ and $U_1$ can produce all possible $16$-bit pairs $(U_0, U_1)$, because the recurrence propagates constraints across blocks. Concretely, the existence of the relation
$$ (U_4)_3 = (U_0)_4 + (U_0)_5 + (U_0)_6 $$
implies that some combinations of bits in consecutive blocks cannot occur: if all $2^{16}$ pairs of $U_n, U_{n+1}$ were possible, then $(U_4)_3$ could take all $2^8$ values independently of $U_0$, which is impossible due to this linear relation.
Hence the $16$-bit pairs $(U_n, U_{n+1})$ are confined to a proper linear subspace of $\mathbf F_2^{16}$.
Step 6: Conclusion
The recurrence imposes linear dependencies among bits in consecutive blocks. Therefore, some $16$-bit pairs $(U_n, U_{n+1})$ cannot occur, so the sequence of pairs is not uniformly distributed. Consequently, the sequence $(U_n)$ fails the serial test on pairs for $d=8$.
$$ \boxed{\text{The sequence fails the serial test on pairs for $d=8$.}} $$
$\square$
Remark: The key correction relative to the previous flawed solution is that we explicitly identify a linear relation linking bits of consecutive blocks, rather than relying on dependencies over distant blocks. This directly establishes that some pairs $(U_n, U_{n+1})$ cannot occur, which is exactly what the serial test on pairs examines.