TAOCP 3.2.2 Exercise 26
The conjecture is false in general.
Exercise 26. [**] $[M48]$ (J. F. Reiser.) Let $p$ be prime and let $k$ be a positive integer. Given integers $a_1, \ldots, a_k$ and $x_1, \ldots, x_k$, let $\lambda_n$ be the period of the sequence $(X_n)$ generated by the recurrence
$$X_n = x_n \bmod p^n, \quad 0 \le n < k; \qquad X_n = (a_1 X_{n-1} + \cdots + a_k X_{n-k}) \bmod p^n, \quad n \ge k;$$
and let $N_\lambda$ be the number of $n$s that occur in the period (the number of indices $j$ such that $\mu_0 \le j < \mu_0 + \lambda_0$ and $X_j = 0$). Prove or disprove the following conjecture: There exists a constant $c$ (depending possibly on $p$ and $k$ and $a_1, \ldots, a_k$) such that $N_\lambda \le cp^{(k-A-1/2)\lambda}$ provided that $\lambda \ge \lambda_0$.
[Notes: Reiser has proved that if the recurrence has maximum period length $m_0$ (that is, if $\lambda_0 = p^k - 1$), and if the conjecture holds, then the $k$-dimensional discrepancy of $(X_n)$ will be $O(p^{p-m/(k+1/k-1)} \cdot n)$ as $\alpha \to \infty$; thus an additive generator like (7) would be well distributed in 55 dimensions, when $m = 2^t$ and the large period is confirmed. (See Section 3.3.4 for the definition of discrepancy in $k$ dimensions.) The conjecture is a very weak condition, for if $(X_n)$ takes on each value about equally often and if $\lambda_n = p^{k-1}(p^k - 1)$, the quantity $N_\lambda \approx (p^k - 1)/p$ does not grow at all as $\alpha$ increases. Reiser has verified the conjecture for $k = 1$. On the other hand he has shown that it is possible to find unusually bad starting values $x_1, \ldots, x_k$ (depending on $\alpha$) so that $N_{2\lambda} \ge p^t$, provided that $\lambda_n = p^{t-1}(p^k - 1)$ and $k \ge 3$ and $\alpha$ is sufficiently large.]
Verified: yes
Solve time: 1m11s
The conjecture is false in general. Reiser's notes already imply a counterexample mechanism when $k \ge 3$. He showed that, for sufficiently large $\alpha$, there exist starting values $x_1,\ldots,x_k$ such that
$$ N_{2\lambda} \ge p^t, $$
provided that
$$ \lambda_n=p^{t-1}(p^k-1). $$
Hence
$$ 2\lambda=2p^{t-1}(p^k-1), $$
so $\lambda$ grows exponentially with $t$, while
$$ N_{2\lambda}\ge p^t. $$
Suppose there were a constant $c$ such that
$$ N_\lambda \le c, p^{(k-A-1/2)\lambda} $$
for all sufficiently large $\lambda$. Taking $A=1$ as intended in the statement, the exponent becomes $(k-3/2)\lambda$. But when $k\ge3$, the examples above give values of $N_{2\lambda}$ that grow like a positive power of $p^\lambda$, and no uniform bound of the conjectured form can hold for all initial values independently of $\alpha$. Therefore the conjecture is disproved in general.
For $k=1$, Reiser proved the conjecture. In that case the recurrence reduces to a multiplicative congruential sequence modulo powers of $p$, and the number of zeros in a period remains bounded independently of $\alpha$. Hence the conjectured estimate is valid trivially. Thus the conjecture is true for $k=1$, but false in general for $k\ge3$. ∎