TAOCP 3.2.2 Exercise 11
Let f(z) = 1 - a_1 z - \cdots - a_k z^k, \qquad G(z) = \frac{1}{f(z)} = \sum_{n \ge 0} A_n z^n.
Exercise 11. [**] [M36] The purpose of this exercise is to analyze certain properties of integer sequences satisfying the recurrence relation
$$X_n = a_1 X_{n-1} + \cdots + a_k X_{n-k}, \qquad n \ge k.$$
If we can calculate the period length of this sequence modulo $m = p^r$, when $p$ is prime, the period length with respect to an arbitrary modulus $m$ is the least common multiple of the period lengths for the prime power factors of $m$.
a) If $f(z)$, $a(z)$, $b(z)$ are polynomials with integer coefficients, let us write $a(z) \equiv b(z)$ (modulo $f(z)$ and $m$) if $a(z) = b(z) + f(z)u(z) + mv(z)$ for some polynomials $u(z)$ and $v(z)$ with integer coefficients. Prove that the following statement holds when $f(0) = 1$ and $p^r > 2$: If $z^{\lambda} \equiv 1$ (modulo $f(z)$ and $p^r$) and $z^{\lambda} \not\equiv 1$ (modulo $f(z)$ and $p^{r+1}$), then $z^{p\lambda} \equiv 1$ (modulo $f(z)$ and $p^{r+1}$) and $z^{p\lambda} \not\equiv 1$ (modulo $f(z)$ and $p^{r+2}$).
b) Let $f(z) = 1 - a_1 z - \cdots - a_k z^k$, and let
$$G(z) = 1/f(z) = A_0 + A_1 z + A_2 z^2 + \cdots.$$
Let $\lambda(m)$ denote the period length of $(A_n \bmod m)$. Prove that $\lambda(m)$ is the smallest positive integer $\lambda$ such that $z^{\lambda} \equiv 1$ (modulo $f(z)$ and $m$).
c) If $p$ is prime, $p^r > 2$, and $\lambda(p^r) \ne \lambda(p^{r+1})$, then $\lambda(p^{r+1}) = p \cdot \lambda(p^r)$ for all $r \ge 0$. (Thus, to find the period length of the sequence $(A_n \bmod 2^e)$, we can compute $\lambda(4)$, $\lambda(8)$, $\lambda(16)$, $\ldots$ until we find the smallest $e \ge 3$ such that $\lambda(2^e) = \lambda(4)$; then the period length is determined mod $2^e$ for all $e$. Exercise 4.6.3–26 explains how to calculate $X_n$ for large $n$ in $O(\log n)$ operations.)
d) Given that the polynomials $f(z)$ and $g(z)$ in part (d) are relatively prime modulo $p$ (see Section 4.6.1), prove that the sequence $(X_n \bmod p^e)$ has exactly the same
period length as the special sequence $(A_n \bmod p^e)$ in (b). (No longer period could be obtained by any choice of $X_0, \ldots, X_{k-1}$, since the general sequence is a linear combination of "shifts" of the special sequence.) [Hint: By exercise 4.6.2–22 (Hensel's lemma), there exist polynomials such that $a(z)f(z) + b(z)g(z) \equiv 1 \pmod{p^e}$.]
Verified: no
Solve time: 4m15s
Let
$$ f(z) = 1 - a_1 z - \cdots - a_k z^k, \qquad G(z) = \frac{1}{f(z)} = \sum_{n \ge 0} A_n z^n. $$
Since $f(z)G(z) = 1$, comparison of coefficients gives
$$ A_n = a_1 A_{n-1} + \cdots + a_k A_{n-k} \qquad (n \ge k), $$
with $A_0 = 1$ and $A_n = 0$ for $n < 0$.
We prove the four parts in order.
(a) Lifting periods modulo prime powers
Assume $f(0) = 1$, $p^r > 2$, and
$$ z^\lambda \equiv 1 \pmod{f(z), p^r}, \qquad z^\lambda \not\equiv 1 \pmod{f(z), p^{r+1}}. $$
Then there exist polynomials $u(z), v(z) \in \mathbf{Z}[z]$ such that
$$ z^\lambda = 1 + f(z) u(z) + p^r v(z), $$
with $v(z) \not\equiv 0 \pmod p$. Reducing modulo $f(z)$ gives
$$ z^\lambda \equiv 1 + p^r v(z) \pmod{f(z)}. $$
Raising both sides to the $p$th power and using the binomial theorem:
$$ z^{p\lambda} \equiv (1 + p^r v(z))^p = \sum_{j=0}^p \binom{p}{j} p^{rj} v(z)^j \pmod{f(z)}. $$
For $1 \le j \le p-1$, $\binom{p}{j}$ is divisible by $p$, so $\binom{p}{j} p^{rj}$ is divisible by $p^{r+1}$. Also, the last term $p^{rp} v(z)^p$ is divisible by $p^{r+1}$ because $p^r > 2$. Hence
$$ z^{p\lambda} \equiv 1 \pmod{f(z), p^{r+1}}. $$
Similarly, reducing modulo $p^{r+2}$, all terms except $1 + p^{r+1} v(z)$ are divisible by $p^{r+2}$. Since $v(z) \not\equiv 0 \pmod p$,
$$ z^{p\lambda} \not\equiv 1 \pmod{f(z), p^{r+2}}. $$
This establishes part (a).
(b) Period of the special sequence
Let $\lambda(m)$ denote the period of $(A_n \bmod m)$. We prove that $\lambda(m)$ is the smallest positive integer $\lambda$ such that
$$ z^\lambda \equiv 1 \pmod{f(z), m}. $$
Forward direction. Suppose $z^\lambda \equiv 1 \pmod{f(z), m}$. Then there exist polynomials $u(z), v(z) \in \mathbf{Z}[z]$ such that
$$ z^\lambda - 1 = f(z) u(z) + m v(z). $$
Multiplying by $G(z) = 1/f(z)$ gives
$$ (z^\lambda - 1) G(z) = u(z) + m v(z) G(z). $$
Since $u(z)$ is a polynomial, its coefficients vanish for sufficiently large degree. Letting $n \ge k$ be sufficiently large, the coefficient of $z^n$ in $u(z)$ is zero, so
$$ A_{n+\lambda} - A_n \equiv 0 \pmod m. $$
Because $(A_n)$ satisfies a linear recurrence of order $k$, the difference sequence $(A_{n+\lambda} - A_n)$ also satisfies the same recurrence. Agreement of $k$ consecutive terms implies agreement of all subsequent terms, so
$$ A_{n+\lambda} \equiv A_n \pmod m \quad \text{for all } n \ge 0. $$
Hence $\lambda$ is a period.
Converse direction. Suppose $\lambda$ is a period of $(A_n \bmod m)$, i.e.,
$$ A_{n+\lambda} \equiv A_n \pmod m \quad (n \ge 0). $$
Then
$$ (z^\lambda - 1) G(z) = \sum_{n \ge 0} (A_{n+\lambda} - A_n) z^n $$
has all coefficients divisible by $m$. Hence
$$ (z^\lambda - 1) G(z) = m H(z) $$
for some integer power series $H(z)$. Multiplying by $f(z)$ gives
$$ z^\lambda - 1 = m f(z) H(z), $$
which shows
$$ z^\lambda \equiv 1 \pmod{f(z), m} $$
by taking $u(z) = 0$ and $v(z) = H(z)$. This completes the converse.
Therefore the least positive integer $\lambda$ with $z^\lambda \equiv 1 \pmod{f(z), m}$ is exactly $\lambda(m)$.
(c) Periods modulo successive prime powers
Let $\lambda_r = \lambda(p^r)$. Suppose $p^r > 2$ and $\lambda_r \ne \lambda_{r+1}$. By part (b),
$$ z^{\lambda_r} \equiv 1 \pmod{f(z), p^r}, \qquad z^{\lambda_r} \not\equiv 1 \pmod{f(z), p^{r+1}}. $$
Applying part (a),
$$ z^{p \lambda_r} \equiv 1 \pmod{f(z), p^{r+1}}. $$
Hence the minimal period $\lambda_{r+1}$ divides $p \lambda_r$. Conversely, reducing $z^{\lambda_{r+1}} \equiv 1 \pmod{f(z), p^{r+1}}$ modulo $p^r$ gives $z^{\lambda_{r+1}} \equiv 1 \pmod{f(z), p^r}$, so $\lambda_r \mid \lambda_{r+1}$. Therefore $\lambda_{r+1}$ is a multiple of $\lambda_r$ dividing $p \lambda_r$. Since $\lambda_{r+1} \ne \lambda_r$, the only possibility is
$$ \lambda_{r+1} = p \lambda_r. $$
(d) Period of a general sequence
Let
$$ g(z) = X_0 + (X_1 - a_1 X_0) z + \cdots + (X_{k-1} - a_1 X_{k-2} - \cdots - a_{k-1} X_0) z^{k-1}, $$
so that the generating function of $(X_n)$ is
$$ \sum_{n \ge 0} X_n z^n = \frac{g(z)}{f(z)}. $$
Assume $f(z)$ and $g(z)$ are relatively prime modulo $p$. By the hint and Hensel's lemma, for each $e \ge 1$ there exist polynomials $a(z), b(z) \in \mathbf{Z}[z]$ such that
$$ a(z) f(z) + b(z) g(z) \equiv 1 \pmod{p^e}. $$
Multiplying by $G(z) = 1/f(z)$ gives
$$ a(z) + b(z) \frac{g(z)}{f(z)} \equiv G(z) \pmod{p^e}. $$
Hence $G(z)$ is congruent modulo $p^e$ to a polynomial plus a polynomial multiple of the generating function of $(X_n)$. Consequently, every sufficiently far shift of $(A_n \bmod p^e)$ is a linear combination of shifts of $(X_n \bmod p^e)$.
Conversely,
$$ \frac{g(z)}{f(z)} = g(z) G(z), $$
so $(X_n \bmod p^e)$ is a linear combination of shifts of $(A_n \bmod p^e)$.
Thus the two sequences generate the same shift-invariant module over $\mathbf{Z}/p^e \mathbf{Z}$. A linear combination of shifts of a periodic sequence