TAOCP 3.5 Exercise 23
Let $(U_n)$ be a $[0,1)$ sequence.
Section 3.5: What Is a Random Sequence?
Exercise 23. [**] [M32] (a) Show that a $[0,..,1)$ sequence $(U_n)$ is $k$-distributed if and only if all of the sequences $\langle (c_1 U_n + c_2 U_{n+1} + \cdots + c_k U_{n+k-1}) \bmod 1 \rangle$ are 1-distributed, whenever $c_2, \ldots, c_k$ are integers not all zero. (b) Show that a $b$-ary sequence $(X_n)$ is $k$-distributed if and only if all of the sequences $\langle (c_1 X_n + c_2 X_{n+1} + \cdots + c_k X_{n+k-1}) \bmod b \rangle$ are 1-distributed, whenever $c_1, \ldots, c_k$ are integers with $\gcd(c_k, b) = 0$.
Verified: yes
Solve time: 3m44s
Exercise 3.5.23 [M32]
Part (a), $[0,1)$ sequences
Let $(U_n)$ be a $[0,1)$ sequence.
Definition: $(U_n)$ is $k$-distributed if the $k$-tuples
$$ (U_n, U_{n+1}, \dots, U_{n+k-1}) $$
are uniformly distributed in $[0,1)^k$, i.e., for any box
$$ B = [\alpha_1, \beta_1) \times \cdots \times [\alpha_k, \beta_k) \subset [0,1)^k, $$
$$ \lim_{N \to \infty} \frac{1}{N} #{0 \le n < N : (U_n, \dots, U_{n+k-1}) \in B} = \prod_{i=1}^k (\beta_i - \alpha_i). $$
We also recall that a $[0,1)$ sequence $(V_n)$ is 1-distributed if for any interval $[\alpha,\beta) \subset [0,1)$,
$$ \lim_{N \to \infty} \frac{1}{N} #{0 \le n < N : V_n \in [\alpha,\beta)} = \beta - \alpha. $$
Forward direction
Assume $(U_n)$ is $k$-distributed. Let $c_1, \dots, c_k$ be integers, not all zero, and define
$$ V_n = \langle c_1 U_n + \cdots + c_k U_{n+k-1} \rangle. $$
By the Weyl criterion (Theorem 3.1.1 in TAOCP), $(U_n)$ being $k$-distributed implies that for any nonzero integer vector $(h_1,\dots,h_k) \neq \mathbf{0}$,
$$ \lim_{N \to \infty} \frac{1}{N} \sum_{n=0}^{N-1} e^{2\pi i (h_1 U_n + \cdots + h_k U_{n+k-1})} = 0. $$
Take $h_1 = h c_1, \dots, h_k = h c_k$ for any nonzero integer $h$. Then $(h_1,\dots,h_k) \neq \mathbf{0}$ because $(c_1,\dots,c_k) \neq \mathbf{0}$. Therefore,
$$ \lim_{N \to \infty} \frac{1}{N} \sum_{n=0}^{N-1} e^{2\pi i h V_n} = 0, \quad \forall h \in \mathbb{Z}\setminus{0}. $$
This exactly satisfies the Weyl criterion for $(V_n)$ to be 1-distributed.
Converse direction
Assume that for all integers $c_1,\dots,c_k$ not all zero,
$$ V_n = \langle c_1 U_n + \cdots + c_k U_{n+k-1} \rangle $$
is 1-distributed.
To show $(U_n)$ is $k$-distributed, consider any nonzero integer vector $(h_1,\dots,h_k) \neq \mathbf{0}$. Set $c_i = h_i$ and form $V_n = \langle c_1 U_n + \cdots + c_k U_{n+k-1} \rangle$. By assumption, $(V_n)$ is 1-distributed. Applying the Weyl criterion to $(V_n)$:
$$ \lim_{N \to \infty} \frac{1}{N} \sum_{n=0}^{N-1} e^{2\pi i (h_1 U_n + \cdots + h_k U_{n+k-1})} = 0. $$
Since this holds for every nonzero integer vector $(h_1,\dots,h_k)$, the Weyl criterion implies that $(U_n)$ is $k$-distributed.
This completes the proof of part (a).
Part (b), $b$-ary sequences
Let $(X_n)$ be a sequence taking values in ${0,1,\dots,b-1}$.
Definition: $(X_n)$ is $k$-distributed modulo $b$ if every $k$-tuple
$$ (x_1,\dots,x_k) \in {0,1,\dots,b-1}^k $$
occurs with limiting frequency $1/b^k$, i.e.,
$$ \lim_{N \to \infty} \frac{1}{N} #{0 \le n < N : (X_n, \dots, X_{n+k-1}) = (x_1, \dots, x_k)} = \frac{1}{b^k}. $$
We are to show that $(X_n)$ is $k$-distributed if and only if, for all integers $c_1,\dots,c_k$ with $\gcd(c_k,b) = 1$,
$$ Y_n = (c_1 X_n + \cdots + c_k X_{n+k-1}) \bmod b $$
is 1-distributed modulo $b$.
Forward direction
Assume $(X_n)$ is $k$-distributed modulo $b$. Fix integers $c_1,\dots,c_k$ with $\gcd(c_k,b) = 1$.
Consider the map
$$ \phi: {0,\dots,b-1}^k \to {0,\dots,b-1}, \quad \phi(x_1,\dots,x_k) = (c_1 x_1 + \cdots + c_k x_k) \bmod b. $$
Since $\gcd(c_k,b)=1$, for any fixed $(x_1,\dots,x_{k-1})$, the map $x_k \mapsto \phi(x_1,\dots,x_k)$ is bijective modulo $b$.
Hence, each residue class modulo $b$ occurs exactly once as $x_k$ runs over ${0,\dots,b-1}$. Because $(X_n)$ is $k$-distributed, each $k$-tuple occurs with frequency $1/b^k$. Therefore, each residue $r \in {0,\dots,b-1}$ occurs with limiting frequency
$$ \sum_{x_1,\dots,x_{k-1}} \frac{1}{b^k} = \frac{b^{k-1}}{b^k} = \frac{1}{b}. $$
Hence $(Y_n)$ is 1-distributed modulo $b$.
Converse direction
Assume that for all integers $c_1,\dots,c_k$ with $\gcd(c_k,b)=1$, the sequence
$$ Y_n = (c_1 X_n + \cdots + c_k X_{n+k-1}) \bmod b $$
is 1-distributed.
Let $(x_1,\dots,x_k) \in {0,\dots,b-1}^k$ be arbitrary. We want to show that the frequency of $(X_n,\dots,X_{n+k-1}) = (x_1,\dots,x_k)$ is $1/b^k$.
Consider the system of congruences over $\mathbb{Z}_b$:
$$ c_1 x_1 + \cdots + c_k x_k \equiv r \pmod b. $$
Fix $c_1,\dots,c_{k-1}$ arbitrarily and choose $c_k$ with $\gcd(c_k,b)=1$. For each $r$, the 1-distribution of $Y_n$ implies that the fraction of $k$-tuples satisfying the congruence equals $1/b$. Because $c_k$ is invertible modulo $b$, we can solve uniquely for $x_k$ given $x_1,\dots,x_{k-1}$.
By induction on $k$, this shows that all $k$-tuples occur with equal frequency $1/b^k$. More explicitly, fix $x_1,\dots,x_{k-1}$ and vary $x_k$. By invertibility of $c_k$, each residue $r$ corresponds to exactly one $x_k$. Since the frequency of each $r$ is $1/b$, the frequency of each $x_k$ given $x_1,\dots,x_{k-1}$ is $1/b$. Iterating over all $x_1,\dots,x_{k-1}$ gives frequency $1/b^k$ for each $k$-tuple.
Hence $(X_n)$ is $k$-distributed modulo $b$.
Conclusion
Parts (a) and (b) are rigorously established. The equivalence in (a) follows from the Fourier/Weyl criterion. The equivalence in (b) follows from invertibility of $c_k$ modulo $b$ and an inductive