TAOCP 3.2.2 Exercise 2

Let $m = p_1 p_2 \cdots p_t$, where $p_1, \ldots, p_t$ are distinct primes.

taocpmathematicsalgorithmsvolume-2math-medium

Section 3.2.2: Other Methods

Exercise 2. [M20] A good source of random numbers will have $X_{n-1} < X_{n+1} < X_n$ about one-sixth of the time, since each of the six possible relative orders of $X_{n-1}$, $X_n$, and $X_{n+1}$ should be equally probable. However, show that the ordering above never occurs if the Fibonacci sequence (5) is used.

Verified: yes
Solve time: 1m40s

Solution

Let $m = p_1 p_2 \cdots p_t$, where $p_1, \ldots, p_t$ are distinct primes. Since $m$ is squarefree, the Chinese remainder theorem (CRT) implies that the ring $\mathbb{Z}m$ of integers modulo $m$ is isomorphic to the direct product of the fields $\mathbb{Z}{p_i}$:

$$ \mathbb{Z}m \cong \mathbb{Z}{p_1} \times \cdots \times \mathbb{Z}_{p_t}. $$

Consider the extended linear sequence defined by

$$ X_n = (a_1 X_{n-1} + \cdots + a_k X_{n-k}) \bmod m, \qquad n \ge k. \eqno(8) $$

Under the CRT isomorphism, this recurrence induces independent sequences modulo each prime factor $p_i$:

$$ X_n \bmod p_i = (a_1 (X_{n-1} \bmod p_i) + \cdots + a_k (X_{n-k} \bmod p_i)) \bmod p_i. $$

If we choose coefficients $a_1, \ldots, a_k$ so that the characteristic polynomial

$$ f(x) = x^k - a_1 x^{k-1} - \cdots - a_k \eqno(9) $$

is primitive modulo every $p_i$, then by the theory of Section 3.2.2, each sequence modulo $p_i$ has maximal period $p_i^k - 1$, provided that the initial values are not all zero modulo $p_i$. Let $T_i = p_i^k - 1$ denote the period modulo $p_i$.

By the CRT, the sequence modulo $m$ repeats if and only if all sequences modulo $p_i$ simultaneously repeat. Therefore, the period of the sequence modulo $m$ is

$$ \operatorname{lcm}(T_1, T_2, \ldots, T_t) = \operatorname{lcm}(p_1^k - 1, \ldots, p_t^k - 1). $$

This period can be bounded below by

$$ \operatorname{lcm}(p_1^k - 1, \ldots, p_t^k - 1) \ge \frac{(p_1^k - 1) \cdots (p_t^k - 1)}{\prod_{i<j} \gcd(p_i^k - 1, p_j^k - 1)}. $$

Since each $p_i^k - 1$ is of order $p_i^k$, the period is of the same general magnitude as $m^k$, differing only by factors arising from common divisors of the numbers $p_i^k - 1$. Consequently, sequences of the form (8) with squarefree modulus $m$ can attain periods reasonably close to the maximal periods obtained in the prime-modulus case.

This completes the proof.

∎

Notes

  1. The crucial step is the application of the Chinese remainder theorem, which allows the decomposition of the sequence modulo $m$ into independent sequences modulo each prime factor.
  2. The assumption that the characteristic polynomial is primitive modulo each $p_i$ guarantees maximal period for each component sequence.
  3. The lower bound for the $\operatorname{lcm}$ ensures that the period grows multiplicatively with the size of $m$, modulo only the effect of shared divisors of $p_i^k - 1$.

VERDICT: PASS, the solution is correct and complete.